ECE 345 Algorithms and Data Structures Fall 2017
October 30, 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 9 pages including the cover page; if not, report it to the instructor or TA.
Name:
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
2 25
3 25 Total 100
ECE 345 Midterm — Fall 2017 2 Name:
- [Asymptotics, Recurrences, Combinatorics, Induction, BSTs] Short Answers, 6+14+10+10+10
points.
Answer only in the space provided.
(a) Sort the following four functions from asymptotically smallest to asymptotically largest, indicating ties
if there are any: 4√n, 51000 , (√3)lg n , n. Show the mathematics to prove your work.
(b) Find an asymptotic solution of the following functional recurrences. Express your answer using Θ- notation, and clearly show your work.
(i) T(n) = 2T(n/2)+nlgn
(ii) T(n) = 3T(n/3) +
√
n
ECE 345 Midterm — Fall 2017 3 Name: (c) Give a combinatorial argument to prove that if n ≥ 0,
k=0
(x+y) =
Hint: Consider an alphabet with x digits and y letters.
k xy
n nnkn−k
(d) Use induction to prove that: 2n > 2n for every positive integer n > 2. Clearly show the induction base/hypothesis/step to earn full credit.
ECE 345 Midterm — Fall 2017 4 Name:
(e) Consider the following problem: You are given an unsorted sequence of n integers that contains log n distinct values.
Design an algorithm to sort this sequence using O(n log log n) comparisons, using a binary search tree- type structure. Prove the runtime of your algorithm for full credit.
ECE 345 Midterm — Fall 2017 5 Name: 2. Algorithm Design, 25 points.
The elements of an n × n two-dimensional array A are sorted in ascending order for both rows and columns. Formally: for1≤r,c≤n,A[r][c]>A[i][c],∀i,1≤iA[r][j],∀j,1≤j v?
ECE 345 Midterm — Fall 2017 6 Name: 3. Greedy Algorithms, 8+8+9 points.
Consider the problem of building L meters of streetcar track. Streetcar tracks are built using linear track segments of various lengths. To build L meters of track, you must choose track segments that add up to exactly L meters.
Luckily, the manufacturer has a sale and is selling track segments of length 1 meter, 2 meters, 4 meters, and 8 meters for the same price. You may choose any amount of the given track segment lengths to build the streetcar tracks.
(a) Devise a greedy algorithm that minimizes the number of track segments needed to build streetcar tracks of exactly L meters in length. Write pseudocode or describe it very clearly in plain English. Argue the runtime of your algorithm for full credit.
ECE 345 Midterm — Fall 2017 7 Name:
(b) Greedy Choice: Prove the greedy choice property by showing that there is an optimal solution which, during its first step, selects the same segment as the greedy algorithm.
(c) Optimal Substructure: Explain how the problem is reduced to a smaller subproblem after making the greedy choice. Prove the problem’s optimal substructure by showing that the optimal solution to the smaller subproblem combined with the greedy choice leads to an optimal solution.
ECE 345 Midterm — Fall 2017 8 Name: (DO NOT REMOVE – This page left intentionally blank)
University of Toronto
Department of Electrical and Computer Engineering
Midterm Examination