Design and Analysis of Algorithms

(CS/AI 2102)
Assignment-1
Please adhere to these instructions:
1. If you feel any question is ambiguous, clearly state your assumption(s) and solve it accordingly.

2. Submit your written assignment by September 10th, 2024 in IT2 Block.

No late submissions are allowed.

3. You can discuss with peers, but you must write in your own words. Avoid plagia-
rism at all costs.

1. In each of the following situations, check if f = O(g), or f = Ω(g), or both (in which case,
f = Θ(g)).

(a) f (n) = 100n log n , g n ) = n + (log(n))2

(b) f (n) = log2 (n), g(n) = log3 (n)
(c) f (n) = 10 log(n), g(n) = log(n2 )
n
(d) f (n) = (log(n))log(n) , g(n) = log(n)
√
(e) f (n) = n, g(n) = (log(n))3
(f) f (n) = n!, g(n) = 2n

2. Show that, if c is a positive real number, then g(n) = 1 + c + c2 + . . . + cn is:

(a) Θ(1) if c < 1.

(b) Θ(n) if c = 1.
(c) Θ(cn ) if c > 1.

3. Solve the following recurrence relations and give a bound for each of them in big-O notation.

(a) T (n) = 2T (n/3) + 1

(b) T (n) = 5T (n/4) + n
(c) T (n) = 7T (n/7) + n
(d) T (n) = 9T (n/3) + n2
(e) T (n) = 8T (n/2) + n3
(f) T (n) = 49T (n/25) + n3/2 log n
(g) T (n) = T (n − 1) + 2
(h) T (n) = T (n − 1) + nc , where c ≥ 1 is a constant
(i) T (n) = T (n − 1) + cn , where c > 1 is some constant
(j) T (n) = 2T (n − 1) + 1

1
 4. Suppose you are choosing between the following three algorithms:

(a) Algorithm A solves problems by dividing them into five subproblems of half the size,
recursively solving each subproblem, and then combining the solutions in linear time.
(b) Algorithm B solves problems of size n by recursively solving two subproblems of size n − 1
and then combining the solutions in constant time.
(c) Algorithm C solves problems of size n by dividing them into nine subproblems of size n/3,
recursively solving each subproblem, and then combining the solutions in O(n2 ) time.

What are the running times of each of these algorithms (in big-O notation), and which one
would you choose and why?

5. 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 the array. Show how to remove all duplicates from the
array in O(n log n) time.

6. You are given an infinite array A[⋅] in which the first n cells contain integers in sorted order
and the rest of the cells are filled with ∞. You are not given the value of n. Describe an
algorithm that takes an integer x as input and finds a position in the array containing x, if
such a position exists, in O(log n) time. (If you are disturbed by the fact that the array A has
infinite length, assume instead that it is of length n, but that you don’t know this length, and
that the implementation of the array data type in your programming language returns the error
message ∞ whenever elements A[i] with i > n are accessed.)

7. Given a sorted array of distinct integers A[1, . . . , n], you want to find out whether there is an
index i for which A[i] = i. Give a divide-and-conquer algorithm that runs in time O(log n).

8. A k-way merge operation. Suppose you have k sorted arrays, each with n elements, and you
want to combine them into a single sorted array of kn elements.

(a) Here’s one strategy: Using the merge procedure discussed in the class, merge the first two
arrays, then merge in the third, then merge in the fourth, and so on. What is the time
complexity of this algorithm, in terms of k and n?
(b) Give a more efficient solution to this problem, using divide-and-conquer.

9. You are given two sorted lists of size m and n. Give an O(log m + log n) time algorithm for
computing the k-th smallest element in the union of the two lists.

10. An array A[1...n] is said to have a majority element if more than half of its entries are the
same. Given an array, the task is to design an efficient algorithm to tell whether the array has a
majority element, and, if so, to find that element. The elements of the array are not necessarily
from some ordered domain like the integers, and so there can be no comparisons of the form
“is A[i] > A[j]?”. (Think of the array elements as GIF files, say.) However, you can answer
questions of the form: “is A[i] = A[j]?” in constant time.

(a) Show how to solve this problem in O(n log n) time. (Hint: Split the array A into two arrays
A1 and A2 of half the size. Does knowing the majority elements of A1 and A2 help you
figure out the majority element of A? If so, you can use a divide-and-conquer approach.)
(b) Can you give a linear-time algorithm? (Hint: Here’s another divide-and-conquer approach:

2
 • Pair up the elements of A arbitrarily, to get n/2 pairs.
• Look at each pair: if the two elements are different, discard both of them; if they are
the same, keep just one of them.
Show that after this procedure there are at most n/2 elements left, and that they have a
majority element if and only if A does.)

11. Design an O(n log n) divide-and-conquer algorithm for the closest pair task.

• Input: A set of points in the plane, {p1 = (x1 , y1 ), p2 = (x2 , y2 ), . . . , pn = (xn , yn )}

• Output: The closest pair of points: that is, the pair pi ≠ pj for which the distance between
pi and pj , that is, √
(xi − xj )2 + (yi − yj )2
is minimized.

12. A binary tree is f ull if all of its vertices have either zero or two children. Let Bn denote the
number of full binary trees with n vertices.

(a) By drawing out all full binary trees with 3, 5, or 7 vertices, determine the exact values of
B3 , B5 , and B7 . Why have we left out even numbers of vertices, like B4 ?
(b) For general n, derive a recurrence relation for Bn .
(c) Show by induction that Bn is Ω(2n ).

13. Explain the basic concept of a greedy algorithm. How does it work, and why does it make
decisions that seem best at the moment? Provide an example where a greedy algorithm is
effective, and discuss how making the locally optimal choice at each step can lead to a globally
optimal solution in that problem.

14. A thief enters a house intending to rob it and can carry a maximum weight of 60 kg in his bag.
Inside the house, there are five items with the following weights and values: item-1 weighs 5 kg
and is worth $30, item-2 weighs 10 kg and is worth $40, item-3 weighs 15 kg and is worth $45,
item-4 weighs 22 kg and is worth $77, and item-5 weighs 25 kg and is worth $90. The thief
can take fractions of any item if needed. What items should the thief take to maximize the
total value he can carry? Explain the strategy the thief should use to determine which items,
or fractions of items, to take in order to achieve the highest possible value within the weight
limit.

15. Given five files with the following number of records: A with 10 records, B with 20 records,
C with 15 records, D with 5 records, and E with 25 records, what is the minimum number of
record movements required to merge these files into a single file? Explain the strategy used to
determine the sequence of merging that results in the least number of record movements.

16. Consider the following problem: You have a collection of coins with denominations of $1, $3,
and $4. You need to make a total of $6 using the minimum number of coins. How would you
use a greedy algorithm to determine the optimal solution? Describe the steps taken to arrive
at the solution and explain why the greedy choice at each step leads to the minimum number
of coins needed. Additionally, are there any scenarios where this greedy approach might not
provide the optimal solution?

3
17. A long string consists of the four characters A, C, G, T ; they appear with frequency 31%, 20%, 9%,
and 40% respectively. What is the Huffman encoding of these 4 characters?

18. Suppose the symbols a, b, c, d, e occur with frequencies 12 , 41 , 18 , 16

1 1
, 16 , respectively.

(a) What is the Huffman encoding of the alphabet?

(b) If this encoding is applied to a file consisting of 1, 000, 000 characters with the given
frequencies, what is the length of the encoded file in bits?

19. We use Huf f man′ s algorithm to obtain an encoding of alphabet {a, b, c} with frequencies
fa , fb , fc . In each of the following cases, either give an example of frequencies (fa , fb , fc ) that
would yield the specified code, or explain why the code cannot possibly be obtained (no matter
what the frequencies are).

(a) Code: {0, 10, 11}, (b) Code: {0, 1, 00}, (c) Code: {10, 01, 00}.

20. Under a Huffman encoding of n symbols with frequencies f1 , f2 , . . . , fn , what is the longest a
codeword could possibly be? Give an example set of frequencies that would produce this case.