1. (20 points) Solve the following recurrence relations using any method (substitution, recursion tree
or Master theorem):
(a) T(n) = 3T(n
) + √
n, T(1) = 1
(b) T(n) = 9T(n
) + 5n
, T(1) = 1
(c) T(n) = T(n
) + T( 2n
) + cn
, T(1) = 1
2. (20 points) All airlines are mandated to conduct an additional security check at the departing gate
for each international flight headed to USA. This check involves a passport and document check. After
checking, passengers queue to board the aircraft.
In order to perform the security check, there are k security counters, each with its own queue. Due
to space constraints, only up to n passengers can stand in a queue. The airline determines the value of k
depending on equipment, size of gate, etc. Each incoming passenger has a priority, according to different
things (e.g. family size, enrollment in the federal verification program, etc.). In each queue, passengers
stand in decreasing order of priority (highest priority first, and so on).
The process is as follows: airline officials span a queue, checking documents. After all queues have been
processed, passengers are released into the secure area of the gate where they form a single line to board
the aircraft. This line is also arranged in decreasing order of priority.
You are a programmer employed by the airline, tasked with performing a discrete-event simulation of
this process. Your aim is to specifically simulate the process of forming a single boarding queue from the
security queues. You use arrays to represent the queues.
(a) A simple algorithm is to merge the first queue with the second, and then the result with the third
and so on. This way ensures that only some queues are released at a time. Perform an efficiency
analysis of the time taken by this algorithm.
(b) Provide an alternative algorithm that can create the boarding queue from the security queues in
O(kn lg k) time. Your algorithm can be in pseudo-code form, or a numbered sequence of clear,
concise steps. You do not need to provide a proof of correctness of the algorithm, but must prove
that it works in the given time.
3. (20 points) You are provided with a set of n intervals (si
, ti), such that si < ti . You can further assume that all si and ti are distinct. Provide an algorithm that determines whether any two intervals overlap each other, that runs in O(n lg n) time. (a) Write the algorithm in pseudo-code or a numbered sequence of clear, concise steps. (b) Prove that your algorithm works correctly. (c) Prove an analysis of the efficiency of your algorithm in time and space. (Hint: use divide-and-conquer) 4. (25 points) The mergesort algorithm from class can be termed as a “top-down” algorithm: start with the original array and keep dividing it into smaller sub-arrays, and merge on your way up. One can visualize this in the form of a recursion tree whose root is the original array, intermediate nodes are subarrays and leaves are 1-element pieces. Thus, this algorithm starts at the root and recurses to the leaves, merging on its way back up the tree. An alternative is to start at the leaves. We complete all merges of the leaves into 2-element subarrays, and then go a level up the tree. We then merge all subarrays at that level, before climbing up a level. This process continues until we merge two half-arrays into an array of the original size. Effectively this algorithm is a sequence of strategic merges. This is a “bottom-up” version of the same algorithm. You must implement this algorithm in Java. Some starter code and data sets have been provided to you. The code is a program ready to be run (Type “javac SortCheck.java” to compile and “java SortCheck -i
Your objective is to implement this algorithm so that the program uses your implementation instead of
what is currently using. The program automatically verifies whether the sorting was correctly performed.
You will be graded on (a) correctness of your implementation (b) neatness of your code (indentation,
proper use of variable names, etc.) (c) documentation, in the form of useful comments above and in the
sorting method, and (d) answering the following questions about this algorithm.
(i) Provide a proof that this bottom-up algorithm also works in O(n lg n) time
(ii) Provide at least one advantage and one disadvantage of this algorithm vs the traditional top-down
version. Your advantages should make sense for a programmer who is trying to choose between these
alternatives. Assume that the data sets are large.