CS701-CS801 - Spring 2020 Midterm Exam March 24th, 2020
Question: 1 2 3 4 5 6 7 Total
Points: 10 10 10 10 10 10 10 70
Score:
Your Name:
Guidelines:
This exam must be submitted in Blackboard on or before March 25th 2019, 6:10 pm ET. NO LATE SUB-
MISSIONS WILL BE ACCEPTED. You can submit multiple times, only the last attempt will be graded.
THE SUBMISSION FORMAT IS ONE PDF FILE. Name your file as your last name.pdf. Include your full
name in the document as well. You can prepare your submission any way you want, you can even use a
scanned manuscript and/or photos. You need to include at least this front page signed. Please, do not attach
comments to your submission in Blackboard. Write everything in your submission document. Nothing else
will be graded.
When appropriate, a solution must start with a summary paragraph explaining in words the techniques
used and the assumptions made (if any). When you write an algorithm, give an English description of
the main idea. Use pseudocode only if necessary. WRITE UP YOUR SOLUTIONS CLEARLY AND
CONCISELY. Unclear answers will not get any credit. If needed, give examples, draw figures. Do not
explain algorithms or proofs that are known, just cite the sources (book or any other). Make sure you cite
the source so that anyone can find it.
The exam is open-book but it must be your individual work. NO COLLABORATION IS ALLOWED.
Until March 25th 2019, 6:10 pm, you cannot discuss any aspect of the exam with any other person. You
cannot ask for clarifications/explanations to any person, forum, etc. It is a violation of this policy to submit
a problem solution that you cannot explain orally to the instructor. Please sign above that you agree to
these guidelines.
YOUR EXAM MAY BE CHECKED FOR
PLAGIARISM ON TURNITIN
CS701-CS801 - Spring 2020 Midterm Exam, Page 2 of 8 March 24th, 2020
Questions:
1. Consider the complete ternary-tree network with 9 inputs and 9 outputs shown below where packets are
routed randomly. The route each packet takes is the shortest path between input and output. Let T be
a random variable for the number of packets passing through the dashed edge.
⌅
7Final Exam
Noelle,and11choicesforCobeni.Andonceagain,thereare40choicesfortheextra
cardinKirari’shand.Sointotal,thereare13⇤ 12⇤ 11⇤ 40⇤ 3waysforfour-of-a-kind
tohappeninthiscase.
Intotal,thereare4(13⇤ 12⇤ 11⇤ 40) waystomakefour-of-a-kindhandsinthisformat.
Sotheprobabilityofeveryonegettingafour-of-a-kindis
4⇤ 13⇤ 12⇤ 11⇤ 40⇤ (39!4!4!4!)
52!
Problem4. [15points] PacketRacket!
Considerthecompleteternary-treenetworkwith9inputsand9outputsshownbelow
wherepackets are routed randomly. The route eachpacket takes is the shortest path
betwe ninputandoutput.LetI0,I1,andI2beindicatorrandomvariablesforthe vents
thatapacketoriginatingatin0,in1,andin2,respectively,crossesthedashededgeinthe
figure. LetT = I0+ I1+ I2 be a randomvariable for thenumberofpacketspassing
throughthedashededge.
in
0
out
0
in
1
out
1
in
2
out
2
in
3
out
3
in
4
out
4
in
5
out
5
in
6
out
6
in
7
out
7
in
8
out
8
(a) [10pts]Supposethateachinputsendsasinglepackettoanoutputselecteduniformly
atrandom; thepacketdestinationsaremutuallyindependent. (Notethatoutputsmay
receivepacketsfrommultipleinputsincludingtheircorrespondinginput.)
WhataretheexpectationandvarianceofT?
Solution.Apacketwillpassthroughthedashededgeifitoriginatesininputs0–2and
isdestinedforoutputs3–8. For j 2 {0, 1, 2} Let Ij beanindicatorrandomvariablefor
theeventthatapacketleavinginputj passesthroughthedashededge.Theprobability
ofthiseventis23 .Itfollowsthat:
(a) (5 points) Suppose that each input sends a single packet to an output selected uniformly at random;
the packet destinations are mutually independent. What is the expected value of T? Briefly justify
your answer. No points without justification.
Solution: A packet will pass through the dashed edge if it originates in inputs 0–2 and is
destined for outputs 3–8. For j ∈ {0, 1, 2}, let Ij be an indicator random variable for the event
that a packet leaving input j passes throug the dashed edge. The prob bility of this event is
2/3 . It follows that:
T = I0 + I1 + I2
E(T ) = E(I0) + E(I1) + E(I2)
= 2.
(b) (5 points) Now consider the situation where a permutation of inputs to outputs is chosen uniformly
at random; each input sends a packet to a distinct output. What is the expected value of T? Briefly
justify your answer. No points without justification.
Solution: We know that E[Ij ] = 2/3 still, because each input is equally likely routed to any
of the outputs (even when we only restrict ourselves to permutations). Thus, E[T ] = 2.
CS701-CS801 - Spring 2020 Midterm Exam, Page 3 of 8 March 24th, 2020
2. Assume you are creating an array data structure that has a fixed size of n. You want to backup this
array after every so many insertion operations. Unfortunately, the backup operation is quite expensive,
it takes n time to do the backup. Insertions without a backup just take 1 time unit.
(a) (5 points) How frequently can you do a backup and still guarantee that the amortized cost of
insertion is O(1)?
Solution: You can backup the array after Ω(n) insertions.
(b) (5 points) Prove that you can do backups in O(1) amortized time. Use the potential method for
your proof.
Solution: We do backups every n insertions. For the ith insertion, let φi = i mod n. Then,
when i mod n = 0, it is ĉi = ci + φi − φi−1 = n + 0 − (n − 1) = 1. When i mod n 6= 0, it is
ĉi = 1 + (i mod n)− ((i− 1) mod n) = 2.
CS701-CS801 - Spring 2020 Midterm Exam, Page 4 of 8 March 24th, 2020
3. Design a data structure to maintain a set S of n distinct integers that supports the following two
operations:
• INSERT(x,S): insert integer x into S.
• REMOVE-BOTTOM-HALF(S): remove the smallest dn/2e integers from S.
(a) (5 points) Describe your algorithm for each of those operations and give the worse-case time com-
plexity of the two operations. You can assume that you have a median finding linear algorithm.
Solution: Use a singly linked list to store those integers. To implement INSERT(x,S), we
append the new integer to the end of the linked list. This takes O(1) time. To implement
REMOVE-BOTTOM HALF(S), we use the median-finding algorithm to find the median number,
and then go through the list again to delete all the numbers smaller or equal than the median.
This takes O(n) time.
(b) (5 points) Carry out an amortized analysis using the potential method to make INSERT(x,S) run
in amortized O(1) time, and REMOVE BOTTOM-HALF(S) run in amortized 0 time.
Solution: Suppose the runtime of INSERT(x,S) is 1 and the runtime of REMOVE-BOTTOM-HALF(S)
is bounded by c|S|, for some constant c. Let the potential function be φi = 2c|S| after the ith op-
eration. Therefore, the amortized cost of an insertion is ĉi = 1+φi−φi−1 = 1+2c ∈ Θ(1). The
amortized cost of REMOVE-BOTTOM-HALF(S) is ĉi = c|S|+φi−φi−1 = c|S|+2c|S|/2−2c|S| = 0.
CS701-CS801 - Spring 2020 Midterm Exam, Page 5 of 8 March 24th, 2020
4. (a) (5 points) Van Emde Boas Sort (where we insert all numbers, find the min, and then repeatedly
call successor) can be used to sort n = log u numbers in O(log u log log log u) time. True or False?
Briefly justify your answer. No points without justification.
Solution: False. Inserting into the tree and then finding all the successors will take n log log u
time, which in terms of u is log u log log u.
(b) (5 points) Van Emde Boas Trees on n integers between 0 and u − 1 supports successor queries in
O(log log u) worst-case time using O(n) space. True or False? Briefly justify your answer. No points
without justification.
Solution: False. VEB trees use Θ(u) space.
CS701-CS801 - Spring 2020 Midterm Exam, Page 6 of 8 March 24th, 2020
5. (10 points) Develop and analyze a dynamic set that supports insert, delete, successor and predecessor
in O(log log u) worst-case time, where [0, u] is the range of numbers that may be stored. Your data
structure should use O(u) bits of space. Note that the van Emde Boas Tree studied use Θ(u) words of
space, and thus Θ(u log u) bits of space. Briefly explain the algorithm for each of the operations: insert,
delete, successor and predecessor and their running times. Then explain why it takes O(u) bits of space.
No credit if you do not analyze running times and space, or if your implementation does not achieve the
running times required.
Solution: We can shave off a factor of O(log u) bits of space dividing the universe into chunks of
size log u, corresponding to the last log log u bits of the word (the least significant). We will maintain
a van Emde Boas structure over the first log u− log log u bits (the most significant). For each chunk,
we maintain a single word to represent it. That is, all operations on a word can be done in constant
time. To insert into a chunk, simply set the corresponding bit to 1, and to delete, set it to 0. To
find a successor or predecessor in a chunk, shift out the corresponding query bit and then find the
least significant or most significant bit.
Whenever we insert an element, insert its first log u − log log u bits into the summary vEB. When
we delete, if the chunk we delete from empties, then we delete from the summary structure as well.
To find a successor, first check the corresponding chunk for a successor, and if one exists return it,
otherwise search the summary structure for the successor chunk and return the smallest element in
it.
All operations run in O(log log u) time since they take a constant number of operations in the vEB
structure and all work in the chunks take constant time. The summary vEB takes O(u log u/ log u) =
O(u) bits of space, and the chunks take O(u) bits of space since there are u/ log u chunks, and each
takes log u bits. Thus, the total structure takes O(u) bits of space.
CS701-CS801 - Spring 2020 Midterm Exam, Page 7 of 8 March 24th, 2020
6. (a) (5 points) We know that a sequence of n union/find operations using weighted union and path com-
pression takes time O(nα(n)) where α(n) grows extremely slowly. What if all the union operations
are done first? Show that a sequence of n unions followed by m finds takes time O(n+m).
Solution: Consider a sequence of n unions such that we add one singleton set to the rest each
time. Then, from any given item there is only one link to the root. The time for a find operation
is proportional to the number of links that it changes. So, each union and each find takes O(1),
which yields overall O(n+m).
(b) (5 points) Prove (be precise) that if weighted union is used for all unions, the length of the path
from the root to the deepest node is O(log n) in the worst case, where n is the number of items in
the data structure.
Solution: We prove that the height of the tree is at most log n by induction on the size of
the union. In the base case it is n = 2, which by definition of the data structure is a tree
of height 1 = log 2. For the inductive step, consider two sets of sizes n1 and n2, and heights
h1 ≤ log n1 and h2 ≤ log n2 by inductive hypothesis. The union has size n1 + n2. We consider
the following two cases. If the trees have different height, say h1 > h2, then the height of the
union is h1 ≤ log n1 ≤ log(n1 + n2). For the case h1 = h2, assume without loss of generality
that n1 ≤ n2. Then, the height of the union is h1 + 1 ≤ log n1 + 1 ≤ log(2n1) ≤ log(n1 + n2).
CS701-CS801 - Spring 2020 Midterm Exam, Page 8 of 8 March 24th, 2020
7. (10 points) Show how union/find using weighted union and path compression, can be modified to support
the following operations with specified running times. Be sure to explain how the union operation is
affected by the need to maintain this additional information. The union operation should still run in
constant time. It should not be necessary to modify the find operation. Briefly explain the running
times.
• MIN(r): Find the smallest element in the set with root r. Time Θ(1).
• MAX(r): Find the largest element in the set with root r. Time Θ(1).
• ENUMERATE(r): List the elements in the set with root r. Time Θ(n).
Solution: At the root of each tree, keep a record of the min, max, and a linked list of the elements
with pointers to front and end. When two trees are merged, set the min to be the lesser of the two
mins, the max to be the greater of the two maxes, and splice the two lists.