Homework 0

COSC 3320

Algorithms and Data Structures

All submitted work should be your own. Copying or using other people’s work (including from the

Web) will result in −MAX points, where MAX is the maximum possible number of points for that

assignment. Repeat offenses will result in a failing grade for the course and will be reported to the

Chair. If you have any questions, please reach out to the professor and the TAs. The best way to

ask is on Piazza.

By submitting this assignment, you affirm that you have followed the Academic Honesty Policy.

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 2, 3, and Appendix A. 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

2.3, 2.9, 2.12, A.3 (appendix A)

Justify your answers. Show appropriate work.

This page intentionally left blank.

1 Class Questions

1.1 January 19

Question 1

Show that, in the Celebrity Problem, there can be at most one celebrity.

Solution. TYPE SOLUTION HERE.

Question 2

Give a simple lowerbound for the number of quesitons asked for the Celebrity Problem.

Solution. TYPE SOLUTION HERE.

Question 3

Improve the algorithm given in class for the Celebrity Problem so that it requires 3n − 4 questions.

Solution. TYPE SOLUTION HERE.

Question 4

Prove that, in the 2

n × 2

n Tiling Problem, no solution exists using L-shaped 3-tiles if there is not

a “hole” in the board.

Solution. TYPE SOLUTION HERE.

1.2 January 21

Question 1

Using mathematical induction, show the correctness of the Decrease-and-Conquer algorithm for

the Celebrity Problem given in class.

Solution. TYPE SOLUTION HERE.

Question 2

Explain why an O(

√

n) algorithm for determining if an integer n is prime is inefficient.

Solution. TYPE SOLUTION HERE.

2 Textbook Exercises

Exercise 2.3

The algorithm BinaryISqrt is iterative. Modify it to make it a recursive algorithm.

1

Algorithm BinaryISqrt – Binary Search Square Root

1: def BinaryISqrt(n):

Input . A natural number n

Output . b

√

nc

2: low ← 1 . Low value of guess

3: high ← n . High value of guess

4: while True:

5: mid ← b(low + high)/2c . current estimate

6: if mid2 ≤ n and (mid + 1)2 > n:

7: return mid

8: else if mid2 < n: . mid < b

√

nc

9: low ← mid

10: else: . mid > b

√

nc

11: high ← mid

Solution. TYPE SOLUTION HERE.

Exercise 2.9

There are n adults in town A and they all need to go to town B. There is only a motorbike

available which is owned by two boys. The motorbike can carry only one adult or up to two boys

at a time (note that at one least person is needed to ride a bike). Using the motorbike, all the

adults need to reach town B from town A. Show how this can be accomplished while, at the end,

leaving the motorbike with the two boys in town A.

Show the correctness of your algorithm by using mathematical induction and analyze the number

of trips needed. (Hint: Use decrease and conquer to reduce the problem size.)

Solution. TYPE SOLUTION HERE.

Exercise 2.12

Rank the following functions by order of growth; that is, find an arrangement g1, g2, g3, . . . of the

functions satisfying g1 = O(g2), g2 = O(g3), . . . .

n

1.5 + n,

3n

log3 n

, n log2 n, 1.01n

, log5 n,

1

n2

, 4

lg n

, n!,(lg n)

lg n

Note: lg or log means logarithm to the base 2 and log5 n is the usual way of writing (log n)

5

.

Justify your ordering with arguments.

Solution. TYPE SOLUTION HERE

Exercise A.3

Prove the following statement by mathematical induction:

Xn

i=0

a

i =

a

n+1 − 1

a − 1

where a 6= 1 is some fixed real number.

By the way, this is the sum of a geometric series, a useful formula that one comes across often in

algorithmic analysis.

Solution. TYPE SOLUTION HERE

2