$30
Homework 0
COSC 3320
Algorithms and Data Structures
Academic Honesty Policy
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