MTL342 -  Design and Analysis of Algorithms  -  Assignment 1 - Solved

Question 1.1
Here are two different definitions for the big-Oh notation. Assume that the functions f and g are non-negative and are defined for every natural number.

Definition 1. f(n) = O(g(n)) if there exists a constant C such that for all n ∈ N, the inequality f(n) ≤ C · g(n) holds.

Definition 2. f(n) = O(g(n)) if there exist constants n0 and C such that for all n ≥ n0, the inequality f(n) ≤ C · g(n) holds.

(i)        Show that the above two definitions are equivalent.

(ii)      For each of the following, decide whether they are true or not. Give reasons to support your answer.

(a)     n2 = O(n2 lnn)

(b)    If f(n) = O(g(n)) then 2f(n) = O(2g(n)).

 

(iii)    (Optional) Find two nondecreasing functions f and g defined for all natural numbers such that neither f(n) = O(g(n)), nor g(n) = O(f(n)).

[3 points]

Question 1.2
The distance between a pair of vertices u and v in an unweighted graph is the length (number of edges) of the shortest path between u and v. The diameter of a graph is the maximum distance between any pair of vertices. Give a linear-time algorithm to compute the diameter of a tree.

[3 points]

Question 1.3
Suppose that an n-vertex undirected unweighted graph G = (V,E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all paths between s and t. Give an algorithm with running time O(m + n) to find such a node v. [3 points]

Question 1.4
Consider the following two change-making problems.

a)    The input to this problem is an integer L. The output should be the minimum cardinality collection of coins required to make L paisa of change (that is, you want to use as few coins as possible). The coins are worth 1, 5, 10, 20, 25, and 50 paisa. Assume that you have an unlimited number of coins of each type. Formally prove or disprove that the

1

greedy algorithm (that takes as many coins as possible from the highest denominations) correctly solves the Change Problem. So for example, to make a change for 234 paisa the greedy algorithms would take four 50 paisa coins, one 25 paisa coin, one 5 paisa coin, and four 1 paisa coins.

b)    The input to this problem is an integer L. The output should be the minimum cardinality collection of coins required to make L nibbles of change (that is, you want to use as few coins as possible). Now the coins are worth 1, 2, 4,, 8, ..., 21000 nibbles. Assume that you have an unlimited number of coins of each type. Prove or disprove that the greedy algorithm (that takes as many coins of the highest value as possible) solves the Change Problem.

[3 points]

Question 1.5
Consider the following problem. The input consists of the lengths l1,...,ln and access probabilities p1,...,pn for n files F1,...,Fn. The problem is to order these files on a tape so as to minimize the expected access time. If the files are placed in the order Fs(1),...,Fs(n), then the expected access time is . Note that the term ) is the probability that you access the ith file times the length of the first i files. For each of the below algorithms, either give a proof that the algorithm is correct using an exchange argument, or a proof that the algorithm is incorrect.

a)    Order the files from shortest to longest on the tape. That is, li < lj implies that s(i) < s(j).

b)    Order the files from most likely to be accessed to least likely to be accessed. That is, pi < pj implies that s(i) > s(j).

c)     Order the files from the smallest ratio of the length over access probability to the largest ratio of the length over access probability. That is, li/pi < lj/pj implies that s(i) < s(j).

[5 points]

Question 1.6
Consider the following problem. The input is a collection A = a1,...,an of n points on the real line. The problem is to find a minimum cardinality collection S of unit intervals that cover every point in A. For each of the below two strategies, either show that they always produce an optimal solution, or prove that they do not do so.

a)    Let I be the interval that covers the most number of points in A. Add I to the solution set S. Then recursively continue on the points in A not covered by I.

b)    Let aj be the smallest (leftmost) point in A. Add the interval I = (aj,aj+1) to the solution set S. Then recursively continue on the points in A not covered by I.

[3 points]

Question 1.7
(Optional) For the problem “Deep Down Below” described here, design an algorithm that finds the smallest possible power the hero must start the level with to be able to enter all the caves in some order and beat all the monsters.