Homework 3 ECE 345 Algorithms and Data Structures

ECE 345– Homework 3
Homework 3
ECE 345 Algorithms and Data Structures

• All page numbers are from 2009 edition of Cormen, Leiserson, Rivest and Stein.
• For each algorithm you asked to design you should give a detailed description of the idea,
proof of algorithm correctness, termination, analysis of time and space complexity. If not,
your answer will be incomplete and you will miss credit. You are allowed to refer to pages in
the textbook.
• Do not write C code! When asked to describe an algorithm give analytical pseudocode.
• Read the handout with the instructions on how to submit your Homework online.
Failure to adhere to those instructions may disqualify you and you may receive a
mark of zero on your HW.
• Write clearly, if we cannot understand what you write you may not get credit for the question.
Be as formal as possible in your answers. Don’t forget to include your name(s) and student
number(s) on the front page!
• No Junk Clause: For any question, if you don’t know the answer, you may write “I DON’T
KNOW” in order to receive 20% of the marks.
1. [Search Trees, 15 points]
Suppose we have a list of n fixed length strings that are sorted lexicographically. This list is
stored in a balanced binary search tree for easy access. Let k be the number of strings with
prefix x. Devise an algorithm to output all strings with prefix x in O(k + lg(n)) time. Hint:
First, find the first node in the tree with prefix x.
Example: A sorted list with strings of length three may look like: ABC, ABD, BCC, BDC,
CAB, CAD, DAB. If x“CA”, then your algorithm should print out CAB, CAD.
2. [Search Trees, 15 points]
A full binary tree is a binary tree where all non-leaf nodes have two children, and all leaf nodes
are at the same height. Answer the following questions about full binary trees.
(a) Give a recurrence for the number of nodes in a binary tree of height n. (note that a tree
of height 1 represents a single node).
(b) Use your solution from the previous question to argue that there are more leaf nodes than
non-leaf nodes in a full binary tree.
UofToronto–ECE 345–Fall, 2020 2 Homework 3
3. [Hashing, 10 points]
Demonstrate the insertion of keys 1, 22, 54, 13, 12, 3, and 27 (in that order) into a doublyhashed table where collisions are resolved with open addressing. Let the table have 11 slots,
let the primary hash function be hp(k) = k mod 11, and let the secondary hash function be
hs(k) = (3k mod 4 + 1).
4. [Greedy Algorithms, 15 points]
You have n younger siblings who are each playing in a soccer tournament. Every sibling wants
you to watch them play at least once, but you have other things to do, so you want to go to the
tournament as few times as possible while still seeing all of your siblings play. Their schedule
looks like S = [(s1, f1),(s2, f2), ...,(sn, fn)] where si and fi are times where sibling i will start
and finish their game respectively and si ≤ fi
. The instant you go to the tournament you see
all players who are playing, and leave immediately (i.e. ignore time spent at the tournament,
you go for only an instant in time). So if you go to the tournament at time t you will see
sibling i play if si ≤ t ≤ fi
(a) Devise a greedy algorithm to compute an optimal solution to the problem.
(b) After making your greedy choice, show that the problem is reduced to a smaller subproblem.
(c) Prove the greedy choice property by showing that there is an optimal solution that agrees
with the first greedy choice your algorithm makes.
(d) Prove the problem’s optimal substructure by showing that the optimal solution to the
subproblem (described in (b)) combined with the greedy choice leads to an optimal solution.
5. [Dynamic Programming, 20 points]
You want to go for a long, multiday hike and you need to decide how many stops to make
and where you will rest overnight. More precisely, you are hiking between points x1 and xn
and through locations x2, x3, . . . , xn−1. There are campsites where you must rest at x1 and
xn, but the problem is to decide whether to camp at xi
, i = 2, 3, . . . , n − 1. If you camp at
site xi there is an associated cost bi (you have to rent the site, set up the tent, pay for food,
etc.), and if you hike between xi and xj—without stopping inbetween—there is an associated
cost cost ci,j (from the wear and tear on your body). The total cost is the sum of the camping
costs and the corresponding hiking costs. The goal is to decide the optimal location of rests
so that the total cost for the trip is minimized. Suggest a general algorithm that you could
use to plan your trip (without any assumptions about the costs). The algorithm must return
the locations of rest, not just the total cost of the trip. As usual describe it clearly (pseudcode
is not mandatory), argue that it is correct and analyze its running time. Try to make it as
efficient as you can.