ES242 · Data Structures and Algorithms IIT Gandhinagar

Final Assignment

19 November, 2024

Answer on Google Classroom.

Due: 23 November, 2024, 23∶59 IST.

Page 1 of 9 Please turn the page

ES242 · Data Structures and Algorithms IIT Gandhinagar

Problem 1. Total: 5
(1.a) (1 point) Items 7, 3, 11, 9, and 13 are inserted into an AVL tree. What happens when 12 is inserted?
□ no rotation is needed
□ a single rotation between some node and its left child is performed
□ a single rotation between some node and its right child is performed
□ a double rotation with a node, its left child, and a third node is performed
□ a double rotation with a node, its right child, and a third node is performed

(1.b) (1 point) If every node in a binary tree has either 0 or 2 children, then the height of the tree is Θ(log 𝑛).
Justify your answer with an argument (if true) or an example (if false).
□ True □ False

(1.c) (1 point) Let 𝑇 be a BST and let 𝑣 be a node in 𝑇 . We say that 𝑣 satisfies property 𝑃 if the heights of the
trees rooted at its left child and right child differ by at most one. We say that 𝑣 satisfies property 𝑄 if
the sizes of the trees rooted at its left child and right child differ by at most one. Which of the following
statements is true?
□ If 𝑣 satisfies property 𝑃 then it satisfies property 𝑄.
□ If 𝑣 satisfies property 𝑄 then it satisfies property 𝑃 .
□ The two properties are equivalent.
□ Neither property implies the other.

(1.d) (1 point) An AVL tree is balanced, therefore a median of all elements in the tree is always at the root or
one of its two children.
□ True □ False

(1.e) (1 point) The following algorithm takes as input an array, and returns the array with all the duplicate
elements removed. For example, if the input array is {1, 3, 3, 2, 4, 2}, the algorithm returns {1, 3, 2, 4}.
S = new empty set
A = new empty dynamic array
for every element x in input array
if not S.member(x) then
S.insert(x)
A.append(x)
return A

What is the complexity of this algorithm, if the set is implemented as an AVL tree? In the options below,
𝑛 denotes the size of the input array, and 𝑚 is the number of unique elements in the input array.
□ 𝑂(𝑚 log 𝑚) □ 𝑂(𝑛 log 𝑚) □ Θ(𝑛 log 𝑛) □ Θ(𝑛𝑚)

Page 2 of 9 Please turn the page

ES242 · Data Structures and Algorithms IIT Gandhinagar

Problem 2. Total: 10
A topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge
𝑢𝑣 from vertex 𝑢 to vertex 𝑣, 𝑢 comes before 𝑣 in the ordering.
(2.a) (2 points) Which of the following is not a topological ordering of the following graph?

Figure 1: A given graph 𝐺.

□ 123456 □ 132456 □ 132465 □ 324165

(2.b) (2 points) A directed path on 𝑛 vertices.

(2.b)

(2.c) (2 points) A directed cycle on 𝑛 vertices.

(2.c)

(2.d) (2 points) A graph on 𝑛 vertices with no edges.

(2.d)

(2.e) (2 points) An oriented star with 𝑛 − 1 leaves, as shown in the figure below.

𝑣1 𝑣2 ⋯ 𝑣𝑛−1

Page 3 of 9 Please turn the page

ES242 · Data Structures and Algorithms IIT Gandhinagar

Problem 3. Total: 30
A number of bacteria lie on an infinite grid of cells, each bacterium in its own cell.
Each second, the following transformations occur (all simultaneously):
• If a bacterium has no neighbor to its north and no neighbor to its west, then it will die.
• If a cell has no bacterium in it, but there are bacteria in the neighboring cells to the north and to the
west, then a new bacterium will be born in that cell.
Upon examining the grid, you note that there are a positive, finite number of bacteria in one or more rectan-
gular regions of cells.
The goal here is to determine how many seconds will pass before all the bacteria die.
Here is an example of a grid that starts with 6 cells containing bacteria, and takes 6 seconds for all the bacteria
to die. ’1’s represent cells with bacteria, and ’0’s represent cells without bacteria.

As another example, if we have only one bacteria in the initial state, then the answer is one second, and if we
have two bacteria in a row adjacent to each other, the answer is two seconds.
We also remark that North is in the direction of decreasing Y coordinate and West is in the direction of decreas-
ing X coordinate. Observe that the grid can be partitioned into two types of diagonals: a “type 1” diagonal
is a southwest/northeast diagonal and a “type 2” diagonal is a northwest/southeast diagonal. You can refer
Figures 2 and 3 below. Note that a type 1 diagonal is specified by an equation* of the form 𝑥 + 𝑦 = 𝐶, while
a type 2 diagonal is given by the equation* 𝑥 − 𝑦 = 𝐶.
(3.a) (2 points) Consider the example where we have 42 bacteria on a single row arranged next to each other.
In the notation of zeros and ones, the configuration is:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

How many seconds will pass before all the bacteria die?

(3.b) (2 points) Consider the configuration shown in Figure 4, where the green cells depict the ones that have
bacteria in them. How many seconds will pass before all the bacteria die?

(3.c) (2 points) Consider the configuration shown in Figure 5, where the green cells depict the ones that have
bacteria in them. How many seconds will pass before all the bacteria die?

Page 4 of 9 Please turn the page

ES242 · Data Structures and Algorithms IIT Gandhinagar

Figure 2: The type 1 diagonals x + y = 3 (red) and x + y = 5 (blue).

Figure 3: The type 2 diagonals x - y = 2 (red) and x - y = 3 (blue).

Page 5 of 9 Please turn the page

ES242 · Data Structures and Algorithms IIT Gandhinagar

Figure 4: Figure for part (b).

Figure 5: Figure for part (c).

Page 6 of 9 Please turn the page

ES242 · Data Structures and Algorithms IIT Gandhinagar

Figure 6: Figure for part (d).

(3.d) (2 points) Consider the configuration shown in Figure 6, where the green cells depict the ones that have
bacteria in them. How many seconds will pass before all the bacteria die?

(3.e) (3 points) Define a graph on the bacteria. Two bacteria are neighbors if they are adjacent on the grid
via a horizontal line, a vertical line, or a type 1 diagonal.
For this question, we will refer to the initial configuration as the “old state”, and we will consider the
configuration obtained after one turn, and call this the “new state”. The graphs corresponding to the
old state and new state are denoted by 𝐺 and 𝐻 respectively.
For each bacterium in the new state, let us consider the reason why it is there. If it was in the old state,
we credit the reason for its existence to the set of itself and its north and/or west neighbor. If it was not
in the old state, we credit the reason for its existence only to the set of its north and west neighbors. In
both cases, we call such a set the credit set for that single bacterium.
Suppose we have two bacteria 𝑝 and 𝑞 who are neighbors in the new state (i.e, the vertices corresponding
to 𝑝 and 𝑞 are adjacent in 𝐻). Further, suppose they have credit sets 𝑃 and 𝑄 respectively. Note that 𝑝
and 𝑞 may or may not have existed in the old state. Which of the following is true?
□ The vertices corresponding to bacteria in 𝑃 may belong to different connected components
of 𝐺.
□ The vertices corresponding to bacteria in 𝑄 may belong to different connected components
of 𝐺.
□ The vertices corresponding to bacteria in 𝑃 ∪ 𝑄 may belong to different connected compo-
nents of 𝐺.
□ It must be true that 𝑃 ∩ 𝑄 = ∅.
□ It must be true that 𝑃 ∩ 𝑄 ≠ ∅.
□ None of these

(3.f) (3 points) To begin with, suppose we have a configuration whose corresponding graph has at least two
non-trivial connected components (a connected component is non-trivial if it has at least two vertices).
Further, let 𝐻 denote the graph corresponding to the configuration obtained from the original one after
one second. Can 𝐻 have at most one connected component? In other words, can the evolution merge
two connected components from a previous step?
□ Yes □ No

Page 7 of 9 Please turn the page

ES242 · Data Structures and Algorithms IIT Gandhinagar

(3.g) (3 points) Let the graph on the bacteria be defined as before. For this question, and for all the remaining
parts of this question, assume that the starting configuration is such that its graph has exactly one con-
nected component with at least two vertices. Let us use 𝐺 to denote this graph. Further, let 𝐻 denote
the graph corresponding to the configuration obtained from the original one after one second. What
can we say about 𝐻?
□ 𝐻 may have two or more connected components.
□ 𝐻 has exactly one connected component.
□ 𝐻 may be empty.
□ 𝐻 is non-empty if and only if 𝐺 has two bacteria adjacent along a row or a column.

(3.h) (3 points) Let us denote the type 1 diagonal given by 𝑥 + 𝑦 = 𝐶 as 𝐷𝐶 , and let us say that this diagonal
has value 𝐶. Consider all the type 1 diagonals that have at least one bacteria, and among them, fix the
one with the smallest value. In one step of evolution, what can we say about all the bacteria on this
diagonal?
□ They all die after the first second.
□ They all survive after the first second.
□ They may contribute to the creation of new bacteria after the first second.
□ They cannot contribute to the creation of new bacteria after the first second.

(3.i) (2 points) As before, let us denote the type 1 diagonal given by 𝑥+𝑦 = 𝐶 as 𝐷𝐶 , and let us say that this
diagonal has value 𝐶. Consider all the type 1 diagonals that have at least one bacteria, and among them,
fix the one with the smallest value. Let this value be 𝑐0 . After one step of evolution, again consider type
1 diagonals that have at least one bacteria, and among them, fix the one with the smallest value. Let this
value be 𝑐1 . What can we say about 𝑐1 ?
□ 𝑐1 = 𝑐 0 + 1
□ 𝑐1 = 𝑐 0 − 1
□ 𝑐1 > 𝑐 0
□ 𝑐1 < 𝑐 0
□ There is no relationship between 𝑐0 and 𝑐1
□ 𝑐1 = 𝑐 0
□ It is possible that 𝑐0 = 𝑐1 , although this need not always be the case

(3.j) (3 points) Let the 𝑥-coordinate of the right-most point containing a bacterium be denoted 𝑥⋆ , and the
bottom-most point containing a bacterium be denoted 𝑦⋆ . After one turn, what can we say about 𝑥⋆
and 𝑦⋆ ?
□ They do not change.
□ 𝑥⋆ may increase, but it cannot decrease.
□ 𝑥⋆ may decrease, but it cannot increase.
□ 𝑦⋆ may increase, but it cannot decrease.
□ 𝑦⋆ may decrease, but it cannot increase.

(3.k) (3 points) As before, let the 𝑥-coordinate of the right-most point containing a bacterium be denoted
𝑥⋆ , and the bottom-most point containing a bacterium be denoted 𝑦⋆ . Consider all the type 1 diagonals
that have at least one bacteria, and among them, consider the one with the smallest value, and let this
value be denoted by 𝑐⋆ . How many seconds will pass before all the bacteria die?
□ 𝑥⋆ + 𝑦 ⋆ − 𝑐 ⋆
□ 𝑥⋆ + 𝑦 ⋆ + 𝑐 ⋆
□ 𝑐⋆
□ 𝑥⋆ + 𝑦 ⋆ − 𝑐 ⋆ + 1
□ max(𝑥⋆ , 𝑦⋆ ) − 𝑐⋆ + 1
□ min(𝑥⋆ , 𝑦⋆ ) − 𝑐⋆ + 1

Page 8 of 9 Please turn the page

ES242 · Data Structures and Algorithms IIT Gandhinagar

□ max(𝑥⋆ , 𝑦⋆ ) − 𝑐⋆
□ min(𝑥⋆ , 𝑦⋆ ) − 𝑐⋆
□ None of these

(3.l) (2 points) What algorithm are you most likely going to use to solve this problem in its full generality
(i.e, when we drop the assumption that the initial configuration corresponds to a graph with a single
connected component)?
□ Weighted shortest path algorithms
□ BFS or DFS
□ An algorithm from DSA-2 (i.e, neither of the above)

Problem 4. (3 points) You have a deck of shuffled cards with positive integer values. There are 2 sub-ordinates
below you and two sub-ordinate below them, and it goes on.

• The job of the sub-ordinate is to split the deck of cards that they received and give it to two sub-ordinate
of them. If they receive a deck of cards from their subordinates, they merge it in ascending order and
give it their higher level.
• If a subordinate received only two cards, then he/she himself/herself arranges them in ascending order
and gives them back to the superior.
• If a subordinate received only one card, then he/she will give back that to the superior.
If the deck of card’s values are [5, 10, 26, 33, 45, 67, 92, 99, 100, 105, 201] then how many people (including
you) are required to sort these cards?

Problem 5. (2 points) Applying for permits to set up a company is a 9-step process. These steps can be per-
formed in parallel but some steps depend on others, as described below.
• Step 1 must be completed before steps 3 and 4 start.¨
• Step 2 must be completed before steps 3, 6 and 7 start.¨
• Step 3 must be completed before step 7 starts.¨
• Step 4 must be completed before step 5 starts.¨
• Step 5 must be completed before step 7 starts.¨
• Step 7 must be completed before steps 8 and 9 start.¨
Each step takes a week to complete. What is the minimum number of weeks required to get all the permits
in place?

Problem 5.

Page 9 of 9 End of the exam