Cristian: Add search in a sequence

2011-01-13T12:59:04Z

Add search in a sequence

New page

= Problems with Sequences =

This is a small list of exercises involving sequences of numbers, for beginners. They do not require storage, thus they have solutions without using arrays.

== Problems with sequences (no arrays needed) ==

=== Even Elements ===
How many even elements are in a sequence of <code>n</code> integer numbers?
=== Signed Elements ===
How many negative, zero, and positive elements does a sequence of <code>n</code> numbers contain?
=== Sum and Product ===
Compute the sum and the product of numbers <code>1</code> to <code>n</code>, <code>n</code> given. Is there a complexity difference between the best algorithms you can find for the two?
=== Find Element ===
Given a number <code>a</code> and a sequence of <code>n</code> elements, on what position does <code>a</code> appear in the sequence?
=== Indices and Elements ===
How many numbers in a sequence of <code>n</code> elements are equal to the position in which they appear in the sequence?
=== Increasing Sequence ===
Are the numbers in a sequence in increasing order?
=== Maximum and minimum ===
Compute the maximum and the minimum value in a sequence of <code>n</code> numbers.
=== Fibonacci numbers ===
Compute the <code>nth</code> number in the Fibonacci sequence. The Fibonacci sequence has <code>f1 = 0</code>, <code>f2 = 1</code> and <code>fn = fn-1 + fn-2</code>. Example: <code>0 1 1 2 3 5 8 13 21 ...</code>
=== Monotonic Sequence ===
Is a sequence of numbers monotonic? We define a '''monotonic sequence''' as a sequence whose numbers are either in increasing order, or in decreasing order.
=== Identical Numbers ===
What is the maximum number of consecutive identical numbers in a sequence of <code>n</code> elements?
=== Adding fractions ===
Given a sequence of numbers <code>a1 a2 ... an</code> compute the summation <math>\sum_{k=1}^n \frac{1}{a_k} = \frac{1}{a_1} + \frac{1}{a_2} + ... + \frac{1}{a_n}</math>

=== Word Counting ===
How many groups of consecutive non-zero numbers are in a sequence? Consider such groups as words, zero being a divider such as space.
=== Rotating Sequence h ===
Let's define a '''rotating increasing sequence''' as a sequence of numbers that is either in increasing order, or can be transformed into one by successive rotations (the last element becomes first). Problem: is a sequence of <code>n</code> numbers a rotating increasing sequence?
=== Rotating Monotonic Sequence h ===
Same as before we define a '''rotating monotonic sequence''' as a sequence that is either monotonic, or can be made into one by rotations. Problem: is a sequence of <code>n</code> numbers a rotating monotonic sequence?
=== Bitonic Sequence h ===
Is a sequence of numbers bitonic? We define a '''bitonic sequence''' as a sequence whose numbers are begin in increasing order, and then start decreasing and remain decreasing until the end of the sequence. Increasing and decreasing sequences are also bitonic sequences (that is, it's allowed to skip one of the two sections).
=== Rotating Bitonic Sequence h ===
Same as before we define a '''rotating bitonic sequence''' as a sequence that is either bitonic, or can be made into one by rotations. Problem: is a sequence of <code>n</code> numbers a rotating bitonic sequence?
=== Brackets h ===
Given a sequence of <code>0</code> and <code>1</code>, where <code>0</code> means open bracket and <code>1</code> means close bracket, find out if the sequence represents a correct sequence of brackets, and if so, compute the maximum number of nested brackets. Example: <code>0 1 0 0 1 0 1 1</code> is correct and has a maximum nesting factor of 2, while <code>0 0 1 1 1 0</code> is incorrect.

''Legend:''
* '''h''' means '''h'''ard. The problem is difficult.

Problems Involving Sequences - Revision history

Cristian: Add search in a sequence