University of Toronto
Department of Electrical and Computer Engineering
Midterm Examination
ECE 345 Algorithms and Data Structures Fall 2016
November 4, 7-9pm
Print your name and ID number neatly in the space provided below; print your name at the upper right corner of every page.
The exam is ten (10) pages including the cover page; if not, report it to the instructor or TA.
UTORid: Student number:
• This is an open book exam. You are permitted to use the textbook for the course, your personal lecture notes, and any handouts we have provided, but nothing else is permissible. No calculators, tablets, smartphones, or other electronic devices are allowed on your desk. Non-native English speakers may use a dictionary. You are allowed to reference textbook pages/sections/algorithms if you wish.
• Do all three problems in this booklet. Try not to spend too much time on one problem. Read the problems carefully! Use terminology from the textbook. You must define any different terms before you use them. You are allowed to reference pages from our textbook CLRS (such as algorithms, notation, etc).
• Write clearly and only in the space provided. Ask the proctor if you need more paper. Nothing on the back of the sheets will be graded.
• You have 110 minutes for this exam. Raise your hand if you have a question.
• Do not give C code! Write pseudocode and analyze time/memory requirements of your algorithms when
asked to receive full credit. All logarithms are base 2 unless otherwise noted.
Question Points Score Grader 1 50
3 25 Total 100
ECE 345 Midterm — Fall 2016 2 Name:
1. [Asymptotics, Amortized Analysis, Recurrences, Sorting, Induction] Short Answers, 5+15+10+10+10
Answer only in the space provided.
(a) Does it hold that f(n) = Θ(f(n/2)), for all functions f? If so, briefly explain why, without a formal proof. If not, find a function f(n) that disproves the statement, and show why. Make sure to circle your answer below.
(b) A FIFO (queue) is implemented using two stacks, S1 and S2. Each stack has the two basic opera- tions, PUSH and POP, each of which runs in O(1) time. The FIFO functions ENQUEUE and DEQUEUE are implemented as follows:
• ENQUEUE(x): PUSH element x onto the S1.
• DEQUEUE(): If S2 is empty, continuously POP from S1 and PUSH onto S2 until S1 is empty (this will
invert the order of the elements). POP from S2 and return the result.
Prove, using the accounting method of amortized analysis, that each ENQUEUE or DEQUEUE operation runs in amortized constant O(1) time. Write clearly the actual and amortized cost of each operation in the table below.
Hint: consider the maximum number of times a single element can be pushed and popped.
operation actual cost amortized cost
DEQUEUE size(S1) ∗ 2 + 1
ECE 345 Midterm — Fall 2016 3 Name:
(c) Use the Master Theorem to solve the following recurrences. Show your work.
(i) T(n)=k2·T(nk)+n2 forsomeintegerk>1
(ii) T(n)=4·T(n2)+n
(d) Give the best asymptotic Big-Oh characterization of the best case and worst case time complexity of the following algorithm. The algorithm accepts two arrays A and B of size n as inputs. Explain your reasoning for each case in no more than two lines of English.
for i=0to(n−1)
if B[i] < n
for j = 0 to (n − 1)
for k = 0 to (n − 1) x = x + A[k]
for j = 0 to i
x = x + A[j] return x
ECE 345 Midterm — Fall 2016 4 Name:
(e) Consider the following series: • P0 = 0
• Pn = 2Pn−1 + Pn−2 for n ≥ 2
Prove by induction that Pn > 2n−1.5 for all n ≥ 2. Clearly show the basis steps for n = 2 and n = 3, the induction hypothesis, and finally, the inductive step.
ECE 345 Midterm — Fall 2016 5 Name: 2. Algorithm Design, 5+5+10+5 points.
You are given an unsorted array A of n ≥ 2 elements, in the range [1…n]. An element of A is a local minimum if it is less than or equal to its neighbours. In other words:
• A[1] is a local minimum if A[1] ≤ A[2]
• A[n] is a local minimum if A[n] ≤ A[n − 1]
• Forall2≤i≤n−1,A[i]isalocalminimumifA[i]≤A[i−1]andA[i]≤A[i+1]
(a) Prove by way of contradiction that A must contain at least one local minimum.
(b) Devise a divide-and-conquer algorithm to find a local minimum in A and return its index. While A may have multiple local minima, it is sufficient for your algorithm to return only one of them. For simplicity, you may assume that n is a power of 2. Your algorithm should run in O(log n) time. Partial credit will be awarded if your algorithm requires more time than that.
Hint: Check if the middle element is a local minimum. If not, then it is greater than either its left or right neighbour. What does each of those cases imply?
ECE 345 Midterm — Fall 2016 6 Name:
(c) Prove by way of contradiction that your algorithm from part (b) is correct. Your proof from part (a) may give you insight how to prove its correctness.
(d) Write and solve the recurrence that characterizes the worst-case runtime of your algorithm.
ECE 345 Midterm — Fall 2016 7 Name: 3. Dynamic Programming, 15+10 points.
You wish to sell a valuable strip of silk cloth of integer length n. Rather than selling the strip in bulk, it can first be cut into pieces of any integer length 1, 2, …, n. A piece of length k ∈ {1, 2, …, n} can be sold for pk dollars. Your goal is maximize the total sale price of the cloth, possibly by selling it in pieces.
For example, consider a strip of length n = 3, and sale prices of p1 = 150, p2 = 200, p3 = 250 dollars. Selling the entire strip as a single piece will yield a revenue of p3 = 250 dollars, but selling it in smaller pieces of lengths 1 and 2 (in any order) will yield a greater revenue of p1 + p2 = 350 dollars.
Let R[i] be the maximum total sale for a strip of length i.
(a) Give a recurrence relation to compute R[i] in terms of smaller subproblems and pk values. Include any base case(s). Explain in 3-4 lines of English the key idea of what your recurrence computes and why it works.
ECE 345 Midterm — Fall 2016 8 Name:
(b) Give pseudocode for a dynamic programming algorithm to compute the optimal result. It does not need to return the set of chosen lengths, merely the total sale price. What is its time and space complexity? Explain briefly. For full credit, the algorithm should run in O(n2) time and O(n) space.
ECE 345 Midterm — Fall 2016 9 Name: (DO NOT REMOVE – This page left intentionally blank)
ECE 345 Midterm — Fall 2016 10 Name: (DO NOT REMOVE – This page left intentionally blank)