Q1

https://en.wikipedia.org/wiki/Birthday_problem

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,30200.

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)

• n 100 n 200
• 100n + logn n + (logn)²
• log2n log3n
• n2ⁿ 3ⁿ

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 Dijkstras algorithm is run on the following graph, starting at node A.

• Draw a table showing the intermediate distance values all the nodes at each iteration of the algorithm.
• Show the final shortest-path tree.

Q7

Algorithms for Transport Protocols

• 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.

• 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?

• 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

• Describe the algorithmic components of PageRank, which is the search algorithm used by Google.

• Outline and describe the algorithms used for searching in video sharing sites, like YouTube.

• Describe how you might design a framework for searching on youtube?

Some General Comments

• Any code that you present should be well commented, to make it easier to review and evaluate.

• Add plots, where you think it can aid in the understanding of your solution.

• Articulate any assumptions that you may be making, in order to make progress in your solutions.

• Use your discretion to see if your understanding of the problem and any associated solutions may be enhanced via pseudocode, comments, plots, and text which can help explain your thought process to anyone else looking at your work.

• Please share the solutions as a pdf file (generated from jupyter notebook) as well. Please make it as easy as possible for the reviewer to evaluate your work.