Q1
Design a program that can test the Birthday problem, by a series of experiments, on randomly generated birthdays which test this paradox for n = 5,10,15,20,25,30...200.
Q2
In each of the following situations, indicate whether f = O (g),or f = Ω (g),or both (in which case). Justify your answer.
f (n) g (n)
(a) n − 100 n − 200
(b) 100n + logn n + (logn)2
(c) log2n log3n
(d) n2n 3n
Q3
Show that the running time of the merge-sort algorithm on n -element sequence isO(n log n),even when n is not a power of 2.
Q4
Show how to implement a stack using two queues. Analyze the running time of the stack operations.
Q5
You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in array. Show how to remove all duplicates from the array in time O(n log n).
Q6
Suppose Dijkstra’s algorithm is run on the following graph, starting at node A.
(a) Draw a table showing the intermediate distance values all the nodes at each iteration of the algorithm.
(b) Show the final shortest-path tree.
Q7
Algorithms for “Transport Protocols”
(i) Describe the congestion control algorithms for (a) Cubic TCP, and (b) Compound TCP.
Comment on the similarities and the differences between Cubic TCP and Compound TCP.
(ii)What does it mean for a TCP to be fair? And how might one evaluate fairness when TCP operates over a large scale network, like the Internet?
(iii) How might you design the congestion control algorithms of a TCP, where the efficiency (faster download times) and the fairness attributes of your proposal are better than both Cubic and Compound
TCP.
Q8
Algorithms for “Search”
(i) Describe the algorithmic components of PageRank, which is the search algorithm used by Google.
(ii) Outline and describe the algorithms used for searching in video sharing sites, like YouTube.
(iii) Describe how you might design a framework for searching on youtube?
