Algorithms

1. (a)  Which of the following recurrences solves to O(n)? List all that are correct.
(a/bn means (a/b)*n)

(A) T(n) = T(2/3n) + T(1/3n) + n
(B) T(n) = T(1/3n) + T(1/4n) + n
(C) T (n) = T (0.9n) + O(n)
(D) T(n)=T(n−1)+n
(b)  In terms of storing a graph in computer memory, adjacency list for a dense graph may take more space than adjacency matrix.
True False
(c)  One can easily modify either BFS or DFS algorithm to check connectivity in graphs.
True False
(d)  For a simple undirected graph G and GT has the same adjacency matrix.
True False
2. Order the following functions in the non-decreasing order of growth

3. You are an algorithm designer and wants to design a linear time algorithm for a computational problem on an array. Will the following approach work? Explain your answer.
Divide the array into two equal halves and solve the two sub-arrays recursively and use O(n) time to combine the two solutions to get a solution to the original array. If it does not work, how will you modify the above approach to get a linear time algorithm?

4. The linear-time median-finding algorithm first groups the input into ⌈n/5⌉ groups with 5 elements in each group and then partition the array with respect to the median of medians in each group. Consider running the algorithm on the following input sequence with first 5 elements forming the first group, second 5 the second group, and the rest forming the third group.
10,8,5,1,9,15,14,12,7,4,13,2,11,3,6
(a) Which element is used to form the first partition?
(b) What will be the status of the array after you partition the array around the element you computed in task a) with the procedure PARTITION described in the class?

5. (a) Draw the adjacency list representation where the vertices are indexed in alphabetical order in the list array and that each list is ordered alphabetically.

(b)  Perform DFS to compute the discovery time and finishing time for each of the vertices, using the alphabetical adjacency list representation you stated on Part (a). Mark these times on the picture above.
(c)   Compute GT and perform DFS on GT choosing vertices in the decreasing order of finishing times computed from the first DFS and partition the vertices to strongly connected components (SCC). Show major steps including GT, DFS(GT ), and all the identified SCCs.

 

7. Design an algorithm, which runs in time O(|V | + |E|), that takes as input an undirected graph G = (V,E) in adjacency list format and an edge e ∈ E, and determines whether G has a cycle containing e. Argue your algorithm’s correctness and time complexity.

 

8.Suppose you are managing the construction of billboards on the Stephen Daedalus Memorial Highway, a heavily traveled stretch of road that runs west-east for M miles. The possible sites for billboards are given by numbers x1, x2, . . . , xn, each in the interval [0,M], specifying their position along the highway, measured in miles from its western end. If you place a billboard at location xi, you receive a revenue of ri > 0.
Regulations imposed by the county’s Highway Department require that no two bill- boards may be placed within 5 miles of each other. Your goal is to place bill- boards at a subset of the possible sites to maximize total revenue, subject to the 5-mile restriction. Give an efficient algorithm that takes as input a set of sites X = {x1,x2,…,xn} and a corresponding set of revenues R = {r1,r2,…,rn} and outputs a subset X′ ⊆ X that maximizes total revenue, while satisfying the 5-mile restriction. Argue your algorithm’s correctness and time complexity.