Algorithm design problem set

LE/EECS3101: Design and Analysis of Algorithms

Assignment 1

Due: Friday June 11, 2021 - 11:59 PM EDT

Problem 1

An alternating sequence is a sequence of integers such that its elements satisfy one of the following two properties:

• A[1] < A[2] > A[3] < ...A[n− 2] > A[n− 1] < A[n]

• A[1] > A[2] < A[3] > ...A[n− 2] < A[n− 1] > A[n]

The algorithm below is a simple iterative algorithm that returns true iff a sequence is alternat- ing.

1 fun i s A l t e r n a t i n g (A [ 1 . . n ] ) 2 i f n < 2 3 return true 4 i f A [ 1 ] == A [ 2 ] 5 return false 6 7 p r e v = A [ 1 ] < A [ 2 ] 8 for i = 3 to n : 9 i f (A [ i −1] == A [ i ] )

10 return false 11 12 c u r r e n t = A [ i −1] < A [ i ] 13 i f ( p r e v == c u r r e n t ) 14 return false 15 p r e v = c u r r e n t 16 17 postcond A[1..n] is an alternating sequence 18 return true

Questions

1. (8 points) Prove the full correctness of isAlternating. Remember to clearly state your loop invariants and any necessary preconditions.

Problem 2

Suppose you are given two arrays A[1..n] and B[1..n] of integers. You are required to find a pair of elements (A[i], B[j]) such that their absolute difference is the smallest over all such pairs.

Questions

1. (3 points) Describe a brute force algorithm that solves the problem and informally justify its running time.

2. (8 points) Assume A and B are sorted in non-decreasing order. Design a Θ(n) algorithm for the problem. Provide a clear and concise pseudocode. Hint: the idea is quite similar to that of the Merge algorithm from Merge Sort.

3. (8 points) Prove the correctness of your algorithm.

1

Problem 3

The algorithm below checks whether S1 is a substring of S2.

1 fun i s S u b s t r i n g ( S1 [ 1 . . n ] , S2 [ 1 . . m] ) 2 i f n > m 3 return false 4 5 for i = 1 to m: 6 i s S u b = true 7 for j = 1 to n : 8 i f S1 [ j ] != S2 [ i+j − 1 ] : 9 i s S u b = false

10 break 11 12 i f ( i s S u b ) 13 return true 14 return false

Questions

1. (2 points) What is the best case and worst case in terms of running time?

2. (5 points) Compute the exact running time of isSubstring.

3. (1 points) Give a suggestion on how the running time could be reduced.

Problem 4

Not-A-Dr. Oreo is teaching a course on the design and analysis of algorithms. To determine the best day of the week for his students to write the quiz, he ran a poll asking each of his n student to pick a day d ∈ N (in his world a week has an infinite number of days). Oreo collected all the answers of his students in an array A[1..n] where A[i] is the day chosen by student i. He needs your help in determining the winning day. The winning day is the day picked by more than n/2 students. You may assume that there will always be a winning day.

Questions

1. (3 points) Describe a brute force algorithm that solves the problem in Θ(n2).

2. (8 points) Give a more efficient algorithm that solves the problem using a divide and conquer strategy. Remember to provide a clear and concise pseudocode.

3. (4 points) Use a recurrence relation to prove an upper bound for your algorithm.

4. (2 points) Bonus: Assuming Oreo’s weeks have 7 days (i.e., 1 ≤ d ≤ 7), give a linear time algorithm for the problem.

2