COL 106 : Data Structures and Algorithms

Semester II, 2022-23, IIT Delhi

Practice Sheet - 1 (Time complexity)

1. Binary Search Let T (n) be time to perform binary search on a sorted integer array of size n.
Prove that T (n) = T (n/2) + Θ(1). Use this recurrence relation to argue T (n) = O(log n).

2. Insertion Sort Write a pseudocode to perform Insertion Sort on linked-lists storing integers.
Let T (n) be time complexity of your code. Prove that T (n) = T (n − 1) + O(n). Use this recur-
rence relation to argue T (n) = O(n2 ).

3. Merge Sort Consider a variation of Merge Sort that partitions a list of size n ⩾ 3 into
three lists of size respectively +n/3,, +n/3,, n − 2+n/3,. Write pseudocode for the modified
version of the problem, and prove that the time complexity of your code follows the relation
T (n) = 3T (n/3) + O(n). Use this recurrence relation to show T (n) = O(n log n).

4. Unbalanced Merge Sort Consider a variation of Merge Sort that partitions a list of size n ⩾ 4
into two lists of size respectively +n/4,, n − +n/4,. Prove that the time complexity follows the re-
lation T (n) = T (n/4)+T (3n/4)+O(n). Use this recurrence relation to show T (n) = O(n log n).

5. Asymptotic bounds For each pair of functions f (n) and g(n) in the table below, write O,
Ω, or Θ in the appropriate space, depending on whether f (n) = O(g(n)), f (n) = Ω(g(n)),
or f (n) = Θ(g(n)). If there is more than one relation between f (n) and g(n), write only the
strongest one. The first line is a demo solution.

n n log2 n n2
n log22 n Ω
2log2 n
log2 n!
log2 nlog2 3

1
6. Radix Sort Argue that the Radix sort algorithm always take linear time if the elements to be
sorted are integers in the range {1, . . . , n8 }. How will time complexity change if the integers are
in the range {1, . . . , nd }, for some constant d?

7. Count Sort Suppose that an array contains n numbers, each of which is −1, 0, or 1. Then,
argue that the array can be sorted in O(n) time in the worst case.

8. Stacks and Queues Consider an implementation of Stacks using linked-list that takes O(1)
time for Push and Pop operations. Your task is to use two Stacks to implement a Queue.
What will be time complexity of Enqueue, Dequeue operations as a function of queue length (n)?

9. Quick Sort Consider a variation of Quick Sort, wherein, we recursively compute a random
pivot until we come across an element having rank in range [n/4, 3n/4]. After finding such a pivot
we split input list into child lists L1 and L2 , sort these child lists recursively, and finally concatenate
them to obtain sorted L.

Algorithm 1: QUICKSORT(L)
1 Let n = SIZE (L);
2 if n ⩽ 10 then
3 Sort L using Insertion-sort and return sorted L;
4 else
5 Let L1 , L2 be two empty lists and let RANK = −1;
6 while RANK ∈ / [n/4, 3n/4] do
7 PIVOT = element of list L;
8 Compute RANK = Number of elements in L whose value is at most PIVOT;
9 foreach (x ∈ L \ {PIVOT}) do
10 if (x ⩽ PIVOT) then
11 L1 .append( x )
12 else
13 L2 .append( x )
14 Return QUICKSORT(L1 ) ·PIVOT· QUICKSORT(L2 )

Prove that the expected time complexity of above algorithm is T (n) = O(n log n).

2
 COL 106 : Data Structures and Algorithms
Semester II, 2022-23, IIT Delhi
Practice Sheet - 2

1. Stack and Queue Basics

(a) Consider a stack S initially contain 0 elements. What will the stack contain after perform-
ing following operations: Push(10), Push(20), Pop(), Push(30), Push(40), Pop(), Push(50),
Push(60), Pop().

(b) Consider a queue Q initially contain 0 elements. What will the queue contain after per-
forming following operations: Enqueue(10), Enqueue(20), Dequeue(), Enqueue(30), En-
queue(40), Dequeue(), Enqueue(50), Enqueue(60), Dequeue().

2. Queue using circular arrays

Given a circular array-based queue Q capable of holding 10 objects. Suppose we execute the
following code. Then, what will be the final structure of queue, and which cells of underline array
will correspond to the queue.

1 for (int k = 0; k < 10; k = k + 1) do

2 Q.enqueue(k);
3 end
4 for (int k = 0; k < 5; k = k + 1) do
5 Q.enqueue(Q.dequeue());
6 Q.dequeue();
7 end

3. String Operations
Write a pseudo-code to perform following operations on strings using Stacks and Queues.

(a) Reversal: If input is s = abc, then the output must be cba.

(b) Odd-Even Splitting: If input is s = axbycz, then the output must be two strings abc, xyz.

1
4. Balanced parenthesis
Recall the algorithm for balanced parenthesis that uses stack. What will be the maximum stack
size during the execution of the algorithm when the input is the following string:

s = “{ [ { [ ] } ] { [ ] } } [ ]”.

Can you compute this maximum value for any input string s without using stack data structure?

5. Two stacks using an array

You need to implement two stacks in an algorithm. It is given that at any time instance there will
be a sum total of at most n elements in both the stacks. Write steps to implement the 2 stacks using
a single array.

6. Sorting
You are given an array containing n integers. Each integer lies in the range [0, n2 ]. Give an O(n)
time algorithm to sort them in increasing order.

7. Hash Table
Consider the hash function f (x) = ((2x ∗ (5 − x mod 5)) mod 7). Draw the hash table you
will obtain after insertion of elements 76, 93, 40, 47, 33, 75 assuming that you use chaining as
collision resolution technique.

8. Printer Wait list

Suppose a printer maintains a wait list where jobs that have been on the wait list longer are pro-
cessed earlier. Sometimes users decide to cancel their job(s), so the printer must remove them from
the wait list. Assume each job has a different integer id (alphanumeric string of length 18), and no
two jobs are added to the wait list at the exact same time.
Design a data-structure to help printer maintain its wait list supporting the following operations,
each in O(1) expected time.

(a) Build(): initialize an empty list.

(b) Add(j): add job j to the back of the wait list.

(c) Remove(j): remove job j from the wait list.

(d) Print(): remove and return the job from the front of the wait list.

The size of your data-structure must be linear in the number of jobs.

2
9. Solving Maze using Queues
Let M be a maze represented by a binary matrix of size n × n. The starting position can be any
cell from the set {(i, 0) | M [i, 0] = 0, i < n}, and the destination cell is (n − 1, n − 1).

Present an algorithm to compute shortest route using queue data-structure. Argue that the time
complexity of your algorithm is O(n2 ).

10. Deque implementation using Stack

Describe how to implement the deque data-structure using two stacks as the only instance vari-
ables. What is the running times of different methods involved?

11. Stack implementation using Queue

Describe how to implement the stack data-structure using a single queue Q as an instance variable,
and only constant additional local memory within the method bodies. What is the running time of
the push(), pop(), and top() methods for your design?

12. Deque implementation using Array

Describe how to implement the double-ended queue data structure using an array A. What is the
running time for each operation?

3
 COL 106 : Data Structures and Algorithms
Semester II, 2022-23, IIT Delhi
Practice Sheet - 3

1. Merging BSTs
Prove or disprove the following statement: “Two BSTs of size n can be merged into a single BST
in O(n) time”.

2. Tree Traversals
Insert in a BST elements in the following order: 90, 22, 5, 65, 8, 31. What is the sequence of
elements generated by an in-order, a pre-order and a post-order traversal?

3. AVL Trees
What is minimum number of nodes in an AVL tree of height 12?

4. Height of 2-3-4 Tree

Prove that two consecutive deletions in a 2-3-4 Tree can decrease its height by at most one.
That is, suppose k + 2 updates are made to a 2-3-4 Tree of height h such that the first and last
updates are deletions and remaining k (⩾ 0) updates are insertions, then argue that the height of
the resultant tree must be at least h − 1.

5. B-trees of order Four

Consider a B-Tree of order 4 initially containing zero elements. Suppose the following keys are
inserted in the given order: 1, 2, 3, . . . , 18. Then, what is the maximum number of nodes that can
be present in the B-Tree (assuming that tree is left biased)? Also, what is the height of the B-tree?

6. Merging two Heaps

Can you merge two max-heaps of size n and m, respectively, into a single max-heap in O(m + n)
time? Explain.

7. Area under n Boxes

There are n boxes in x − y plane such that for the ith box the x-coordinates are ai , bi , and y-
coordinates are 0, ci . Design a heap-based algorithm to find the total area covered by these n
boxes. Analyse the time complexity of your algorithm.

1
8. Insertion in Kd trees
What is the worst-case time complexity to perform single insertion in a Kd-tree wherein axis-
aligned splitting planes are computed by taking medians? Explain.

9. Axis parallel Range Query √

Explain why querying an axis-parallel range in a balanced 2d tree takes O( n + m) time, where
m is the number of the reported points.

10. Edges in (s, t)-shortest path

Let s and t be a pair of vertices in an unweighted directed graph G = (V, E). Design an O(m + n)
time algorithm to compute the set of all edges e ∈ E that lie on some (s, t)-shortest path in G.

11. Graph Colouring

An undirected graph G = (V, E) is said to be k-colourable if there exists a mapping c : V →
{1, 2, . . . , k} such that for every edge (u, v) ∈ E we have c(u) ̸= c(v). Argue that a graph G is
2-colourable iff all cycles in G are of even length.

2
 COL 106 : Data Structures and Algorithms
Semester II, 2022-23, IIT Delhi
Practice Sheet - 4

Question 1 Prove that any n vertex undirected graph contains at most n − 1 bridge-edges. Also
present examples to show that this bound is tight.

Question 2 Let G = (V, E) be a undirected graph. Design an O(m + n) time algorithm to com-
pute a partitioning P = (V1 , . . . , Vk ) of V such that for any two vertices x, y ∈ V , vertices x and
y are bi-connected if and only if they lie in same partition in P.

Question 3 A vertex x in an undirected graph G is said to be a cut vertex if the number of con-
nected components of G − {x} is greater than the number of connected components of G.

Complete the pseudo-code below to obtain an O(|V | + |E|) time algorithm for computing
cut-vertices of an n-vertex undirected (possibly unconnected) graph G = (V, E).

1 VISITED [v] ← True;

2 HIGH - POINT [v] ← LEVEL [v];
3 foreach w ∈ N (v) do
4 if (VISITED[w] = False) then
5 Set PARENT[w] ← v and LEVEL[w] = 1 + LEVEL[v];
6 Invoke DFS(w) ;
7 HIGH - POINT [v] ← min{ HIGH - POINT [w], HIGH - POINT [v]} ;
8 if HIGH - POINT[w] ⩾ LEVEL[v] then
9 I S - CUT- VERTEX[v] ← True ;
10 end
11 else if (w ̸= PARENT[v]) then
12 HIGH - POINT [v] ← min{ LEVEL [w], HIGH - POINT [v]} ;
13 end
14 end
Procedure DFS(v)

1
 1 Let (v1 , . . . , vn ) be any ordering of vertices of G;
2 for i = 1 to n do
3 VISITED [vi ] ← False and I S - CUT- VERTEX [vi ] ← False ;
4 end
5 for i = 1 to n do
6 if (VISITED[vi ] = False) then
7 LEVEL [vi ] ← 0;
8 Invoke DFS(vi );
9 if (vi has one child) then I S - CUT- VERTEX[vi ] ← False ;
10 end
11 end
Procedure Compute-Cut-vertices(G)

Question 4 Provide a pseudocode for computing topological ordering of a DAG on m edges and
n vertices in O(m + n) time that uses DFS traversal.

Question 5 Let y, z be any two vertices in a directed acyclic graph G. If there is a path from y to
z, then prove that FINISH - TIME(z) < FINISH - TIME(y) for each DFS traversal carried out in G.

2
Solution to Question 3

1 VISITED [v] ← True;

2 HIGH - POINT [v] ← LEVEL [v];
3 foreach w ∈ N (v) do
4 if (VISITED[w] = False) then
5 Set PARENT[w] ← v and LEVEL[w] = 1 + LEVEL[v];
6 Invoke DFS(w) ;
7 HIGH - POINT [v] ← min{ HIGH - POINT [w], HIGH - POINT [v]} ;
8 if HIGH - POINT[w] ⩾ LEVEL[v] then
9 I S - CUT- VERTEX[v] ← True ;
10 end
11 else if (w ̸= PARENT[v]) then
12 HIGH - POINT [v] ← min{ LEVEL [w], HIGH - POINT [v]} ;
13 end
14 end
Procedure DFS(v)

1 Let (v1 , . . . , vn ) be any ordering of vertices of G;

2 for i = 1 to n do
3 VISITED [vi ] ← False and I S - CUT- VERTEX [vi ] ← False ;
4 end
5 for i = 1 to n do
6 if (VISITED[vi ] = False) then
7 LEVEL [vi ] ← 0;
8 Invoke DFS(vi );
9 if (vi has one child) then I S - CUT- VERTEX[vi ] ← False ;
10 end
11 end
Procedure Compute-Cut-vertices(G)