Reductions and Partitioned Reductions
0.
f[0..100) is an array of int, determine the largest value in the middle 40 elements of f.
1.
Construct a program to compute the product of the natural numbers from 12 to 98.
2.
Construct a program to count the number of single digit values in the array f[0..N) of int.
3.
Construct a program to count the vowels in an array f[0..2000) of char.
Search Algorithms
- Linear Search Theorem
- Bounded Linear Search Theorem
Given f[0..200) of integer, determine whether all the values in f are odd. 2. Given f[100..200) of integer, determine whether the final 10 elements are an exact copy of the first 10 elements. 3. Given f[0..N) of integer, determine whether it is sorted in ascending order. 4. Given f[0..100) of integer, find the location of the largest element in f. 5. Given f[0..1000) of character, determine whether the word “cat” appears in f.
The Binary Chop
- 找一个点在x和x+1之间
- 找一个数被37整除在i和i+1之间
- integer square root
- local minimum is 3 elements where f.(i-1) ≥ f.i ⋀ f.i ≤ f.(i+1) ⋀ 1 ≤ i ≤ N-1
Given f[0..1000] of int, We are told that f.0 and f.N have opposite parity. Construct an efficient program to find an index i within f where f.i and f.(i+1) have opposite parity. 2. Given f[0..N] of int which doesn’t contain any zeros, we are told that f.0 and f.N are of opposite sign. Construct a program to find a location i within f where f.i and f.(i-1) are of opposite sign. Note that we say 2 numbers are the same sign if they are both positive to both negative and opposite sign if one is positive and the other is negative.
Recursively defined functions
- Fibonacci / Fibonacci-like
- Fusc function / Fucs-like
- Recursive function + odd/even
Segment sums and products
- Construct an algorithm to compute the minimum segment sum
- Construct an algorithm to compute the maximum segment product of the segments in f
- Maximum Segment Sum of Odd Valued Segments
Single element property Segment problems
找单一属性的最长片段
- Longest All Zero Segment
- Longest All Even Segment
”Almost” property segments
与上面类似，“几乎”单一属性的最长片段
- The Longest Almost non-Zero Segment
Pair element property segment problems
组合属性的最长片段
- The Longest Ascending Segment
- The Longest Smooth Segment: 数组中的每一对相邻元素，它们的绝对差不超过 1
- The Longest Opposite Parity Segment: 相邻元素奇偶相反
”Almost” pair element property segments
与上面类似，“几乎”组合属性的最长片段