Homework 1

COSC 3320

Algorithms and Data Structures

Your submission must be typed. We prefer you use LATEX to type your solutions — LATEX is the

standard way to type works in mathematical sciences, like computer science, and is highly recommended;

for more information on using LATEX, please see this post on Piazza — but any method of typing your

solutions (e.g., MS Word, Google Docs, Markdown) is acceptable. Your submission must be in pdf

format. The assignment can be submitted up to two days late for a penalty of 10% per day. A

submission more than two days late will receive a zero.

Reading

Chapters 4 and 5. In particular, several worked exercises with solutions are provided at the end of

each chapter. Attempting to solve the worked exercises before seeing their solutions is a good

learning technique.

The exercises below are from the book. The book is updated periodically, so be sure to use the latest

version.

Exercises

4.1(a), 4.3(6), 4.4, 5.1, 5.9

Justify your answers. Show appropriate work.

This page intentionally left blank.

1 Class Questions

1.1 January 26

Question 1

Show that any degree d polynomial p(n) = a0n

d + a1n

d−1 + · · · + an−1n + an, with a0 > 0, is

O

n

d

.

Solution. TYPE SOLUTION HERE.

Question 2

Show that, for any a > 1, n

b = O(a

n).

Solution. TYPE SOLUTION HERE.

Question 3

Show that a

logb n = n

logb a

.

Solution. TYPE SOLUTION HERE.

1.2 January 28

Question 1

Prove by mathematical induction that the gcd algorithm given in class is correct. You may assume

gcd(a, b) = gcd(b, a mod b).

Solution. TYPE SOLUTION HERE.

1.3 February 4

Question 1

Solve T(n) = 3T(n/2) + n

2

.

Solution. TYPE SOLUTION HERE.

Question 2

Show the correctness of MergeSort using Induction. You may assume the Merge subroutine is

correct.

Solution. TYPE SOLUTION HERE.

Question 3

Argue that QuickSort cannot take more than n

2

= n(n − 1)/2 comparisons.

Solution. TYPE SOLUTION HERE.

2 Textbook Exercises

Exercise 4.1

Prove the asymptotic bound for the following recurrences by using induction. Assume that base

cases of all the recurrences are constants i.e., T(n) = Θ(1), for n < c where c is some constant.

(a) T(n) ≤ 2T(n/2) + n

2

. Then, T(n) = O

n

2

log n

.

Solution. TYPE SOLUTION HERE.

Exercise 4.3(6)

Solve the following recurrences. Give the answer in terms of Big-Theta notation. Solve up to

constant factors, i.e., your answer must give the correct function for T(n), up to constant factors.

You can assume constant base cases, i.e., T(1) = T(0) = c, where c is a positive constant. You

can ignore floors and ceilings. You can use the DC Recurrence Theorem if it applies.

6. T(n) = 4T(n/2) + n

3

Solution. TYPE SOLUTION HERE.

Exercise 4.4

You are given an array consisting of n numbers. A popular element is an element that occurs

(strictly) more than n/2 times in the array. Give an algorithm that finds the popular element

in the array if it exists, otherwise it should output “NO”. Your algorithm should take no more

than 2n comparisons. (As usual, we only count the comparisons between array elements.) Give

pseudocode, argue its correctness, and show that your algorithm indeed takes no more than 2n

comparisons. (Hint: Use a decrease and conquer strategy, similar to the celebrity problem.)

Solution. TYPE SOLUTION HERE

Exercise 5.1

Determine the total number of comparisons that each of the following algorithms takes on

S = [8, 2, 6, 7, 5, 1, 4, 3].

• SimpleSort

• MergeSort

• QuickSort

Show the steps of the algorithm when calculating the number of comparisons.

Solution. TYPE SOLUTION HERE

Exercise 5.9

Given three SORTED (in ascending order) arrays A[1..n], B[1..n], and C[1..n], each containing n

numbers, give an O(log n)-time algorithm (again, counting the number of comparisons) to find

the n

th smallest number of all 3n elements in arrays A, B, and C.

Solution. TYPE SOLUTION HERE