$30
Homework 1
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 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.