6CS9

6CS9 DESIGN AND ANALYSIS OF ALGORITHMS (Common to Comp. Engg. & Info. Tech)

Objectives: Upon successful completion of this course, students should be able to:
• Prove the correctness and analyze the running time of the basic algorithms for those classic problems in various domains;
• Apply the algorithms and design techniques to solve problems;
• Analyze the complexities of various problems in different domains.

Suggested Tools: For implementation and estimation of running time on various sizes of input(s) or output(s) as the case may be, Linux platform is suggested.

Suggested Exercises:
A. It is expected that teachers will assign algorithms to the students for estimation of time & space complexity. Algorithms reported in various research journals may be chosen by the teachers.
B. Problem on designing algorithms to meet complexity constraints may be assigned. For example, a problem on design, analysis and implementation for transposing a sparse matrix requiring not more than one pass from the original matrix may be assigned.
C. A guide to such problems is given below:
1. Exploring a Binary Heap: Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x. You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage.
2. Merging two search trees: You are given two height balanced binary search trees T and T', storing m and n elements respectively. Every element of tree T is smaller than every element of tree T'. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)?
3. Complete binary tree as an efficient data-structure:
You are given an array of size n (n being a power of two). All the entries of the array are initialized to zero. You have to perform a sequence of the following online operations :
1. (i) Add(i,x) which adds x to the entry A[i].
2. (ii) Report sum(i,j) = sum of the entries in the array from indices i to j for any 0 < i < j <= n.

It can be seen easily that we can perform the first operation in O(1) time whereas the second operation may cost O(n) in worst case. Your objective is to perform these operations efficiently. Give a datastructure which will guarantee O(log n) time per operation.
4. Problems on Amortized Analysis
a. Delete-min in constant time!!! Consider a binary heap of size n, the root storing the smallest element. We know that the cost of insertion of an element in the heap is O( log n) and the cost of deleting the smallest element is also O( log n). Suggest a valid potential function so that the amortized cost of insertion is O( log n) whereas amortized cost of deleting the smallest element is O( 1).
b. Implementing a queue by two stack
c. Show how to implement a queue with two ordinary stacks so that the amortized cost of each Enqueue and each Dequeue operation is O(1).
5. Computing a spanning tree having smallest value of largest edge weight: Describe an efficient algorithm that, given an undirected graph G, determines a spanning tree of G whose largest edge weight is minimum over all spanning trees of G.
6. Shortest Path Problems:
i. From a subset of vertices to another subset of vertices
a. Given a directed graph G(V,E), where edges have nonnegative weights. S and D are two disjoint subsets of the set of vertices. Give an O(|V| log |V| + |E|) time algorithm to find the shortest path among the set of paths possible from any node in S to any node in D.
ii. Paths in Directed Acyclic Graph
a. Counting the number of paths
Given two nodes u,v in a directed acyclic graph G(V,E). Give an O(|E|) time algorithm to count all the paths from u to v.
b. Path passing through a subset of nodes
Given two nodes u,v and a set of vertices w1, w2,...,wk in a directed acyclic graph G(V,E). Give an O(|E|) time algorithm to output a path(if exists) from u to v which passes through each of the nodes w1,...,wk. If there is no such path then your algorithm must report that "no such path exists".
7. Searching for a friend:
You are standing at a crossing from where there emerge four roads extending to infinity. Your friend is somewhere on one of the four roads. You do not know on which road he is and how far he is from you. You have to walk to your friend and the total distance traveled by you must be at most a constant times the actual distance of your friend from you.
In terminology of algorithms, you should traverse O(d) distance, where d is the distance of your friend from you.
8. A simple problem on sorted array: Design an O(n)-time algorithm that, given a real number x and a sorted array S of n numbers, determines whether or not there exist two elements in S whose sum is exactly x .
9. Finding the decimal dominant in linear time: You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.
10. Finding the first one: You are given an array of infinite length containing zeros followed by ones. How fast can you locate the first one in the array?
11. Searching for the Celebrity: Celebrity is a person whom everybody knows but he knows nobody. You have gone to a party. There are total n persons in the party. Your job is to find the celebrity in the party. You can ask questions of the form Does Mr. X know Mr. Y ?. You will get a binary answer for each such question asked. Find the celebrity by asking only O(n) questions.
12. Checking the Scorpion: An n-vertex graph is a scorpion if it has a vertex of degree 1(the sting) connected to a vertex of degree two (the tail) connected to a vertex of degree n-2 (the body) connected to the other n-3 (the feet). Some of the feet may be connected to other feet. Design an algorithm that decides whether a given adjacency matrix represents a scorpion by examining only O(n) entries.
13. Endless list: You are having a pointer to the head of singly linked list. The list either terminates at null pointer or it loops back to some previous location(not necessarily to the head of the list). You have to determine whether the list loops back or ends at a null location in time proportional to the length of the list. You can use at most a constant amount of extra storage.
14. Nearest Common Ancestor:
Given a rooted tree of size n. You receive a series of online queries: "Give nearest common ancestor of u, v ". Your objective is to preprocess the tree in O(n) time to get a data structure of size O(n) so that you can answer any such query in O(log n) time.