Homework #1

Type solutions to the homework problems listed below using preferably LYX/LATEX word processors, see the class webpage for more information about their installation and tutorials.

    1. (10 points) Write the C++ classes called ArithmeticProgression and GeometricProgression that are derived from the abstract class Progression, with two pure virtual functions, getNext() and sum(), see the course textbook p. 87–90 for more details. Each subclass should implement these functions in order to generate elements of the sequences and their sums. Test your program for the different values of d, r and the number of elements n in each progression.

What is the classification of those functions: getNext() and sum() in terms of the Big-O notation? Recall the definitions of the arithmetic and geometric progressions.

Definition: An arithmetic progression with the initial term a and the common real difference d is a sequence of the form
a, a + d, a + 2d, . . . , a + nd, . . .

Definition: A geometric progression with the initial term a and the common real ratio r is a sequence of the form

a, ar, ar2, . . . , arn, . . .




    2. (10 points) Use the STL class vector<double> to write a C++ function that takes two vectors, a and b, of the same size and returns a vector c such that c[i] = a[i]·b[i]. How many scalar multiplications are used to create elements of the vector c of size n? What is the classification of this algorithm in terms of the Big-O notation?


    3. (10 points) Use the STL class vector<int> to write a C++ function that returns true if there are two elements of the vector for which their product is odd, and returns false otherwise. Provide a formula on the number of scalar multiplications in terms of n, the length of the vector, to solve the problem in the best and the worst cases. Describe the situations of getting the best and worst cases. What is the classification of the algorithm in the best and worst cases in terms of the Big-O notation?

    4. (20 points) Write a templated C++ function called BinarySearch which searches for a target x of any numeric type T, and test it using a sorted vector of type T. Provide the formulae on the number of comparisons in terms of n, the length of the vector, when searching for a target in the best and the worst cases. Describe the situations of getting the best and worst cases. What is the classification of the algorithm in the best and worst cases in terms of the Big-O notation?
    5. (10 points) (R-4.7 p. 185) The number of operations executed by algorithms A and B is 8n log n and 2n2, respectively. Determine n0 such that A is better than B for n ≥ n0.
















    6. (10 points) (R-4.21 p. 186) Bill has an algorithm, find2D, to find an element x in an n × n array A. The algorithm find2D iterates over the rows of A, and calls the algorithm arrayFind, see Code Fragment 4.5, p. 184, on each row, until x is found or it has searched all rows of A. What is the worst-case running time of find2D in terms of n? What is the worst-case running time of find2D in terms of N, where N is the total size of A? Would it be correct to say that find2D is a linear-time algorithm? Why or why not?



    7. (10 points) (R-4.39 p. 188) Al and Bob are arguing about their algorithms. Al claims his O(n log n)-time method is always faster than Bob’s O(n2)-time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if n < 100, the O(n2)-time algorithm runs faster, and only when n ≥ 100 is the O(n log n)-time algorithm better. Explain how this is possible.






(20 points) Find the running time functions for the algorithms below and write their classification using Big-O asymptotic notation. The running time function should provide a formula on the number of operations performed on the variable s. Note that array indices start from 0.

Algorithm Ex1(A):
Input: An array A storing n ≥ 1 integers.

Output: The sum of the elements in A.
s ← A[0]

for i ← 1 to n − 1 do

    • ← s + A[i] end for return s




Algorithm Ex2(A):
Input: An array A storing n ≥ 1 integers.

Output: The sum of the elements at even positions in A.
s ← A[0]

for i ← 2 to n − 1 by increments of 2 do

    • ← s + A[i] end for return s




Algorithm Ex3(A):
Input: An array A storing n ≥ 1 integers.

Output: The sum of the partial sums in A.
s ← 0

for i ← 0    to n − 1 do

s ← s + A[0]
for j ← 1 to i do

    • ← s + A[j] end for

end for

return s




Algorithm Ex4(A):
Input: An array A storing n ≥ 1 integers.

Output: The sum of the partial sums in A.
t ← 0

s ← 0

for i ← 1 to n − 1 do

    • ← s + A[i] t ← t + s
end for

return t







7