$30
Homework 2
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 5 and 6. 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
5.18, 5.23, 6.11, 6.20
Justify your answers. Show appropriate work.
This page intentionally left blank.
1 Class Questions
1.1 February 09
Question 1
Show that the depth of the tree presented in class is O
log3/2 n
.
Solution. TYPE SOLUTION HERE.
Question 2
Prove the correctness of the Select algorithm by mathematical induction.
Solution. TYPE SOLUTION HERE.
1.2 February 23
Question 1
Show that the algorithm mult given in class takes O
n
2
operations. You can assume that we are
multiplying two n-bit numbers (i.e., binary numbers each of length n bits). Adding or multiplying
two bits is counted as one operation.
Solution. TYPE SOLUTION HERE.
2 Textbook Exercises
Exercise 5.18
Consider the max-sum problem: Given an array A of size n containing positive and negative
integers, determine indices i and j, 1 ≤ i ≤ j ≤ n, such that A[i] + A[i + 1] + ... + A[j] is a
maximum.
(a) Consider the array A = [5, 10, −15, 20, −4, 6, 4, 8, −10, 20]. Find the indices i and j that give
the maximum sum and state the maximum sum.
(b) Give a divide and conquer algorithm that runs in O(n log n) time. Assume, that adding or
comparing two numbers takes constant time.
(Hint: Split the array into two (almost) equal parts and recursively solve the problem on the
two parts. The non-trivial part is combining the solutions — note that it is possible that
the indices i and j that give the optimal sum might be on opposite parts.)
Solution. TYPE SOLUTION HERE.
Exercise 5.23
You are given an unsorted array of n ≥ 1 integers. Give an efficient divide and conquer algorithm
to output an element in the array that occurs more than 3 times, if such an element exists. Show
the correctness of your algorithm and analyze its run time.
Solution. TYPE SOLUTION HERE.