Final + Sol - Spring 2023
Final + Sol - Spring 2023
Final + Sol - Spring 2023
Q2(a): 3
Q2(b),(c): 12
Q3: 10
Q4: 10
Q5(a): 4
Q5(b),(c): 6
a) A long string consists of five characters Q, W, E, R, T, Y. They appear with the frequency
40, 20, 90, 72, 80 and 2 respectively. Draw the Huffman Tree and write down the Huffman
encoding for these six characters. (No partial marks for this part)
304
0 1
134 170
0
1 0 1
62 R: 72 T: 80 E: 90
0 1
22 Q: 40
0 1
Y: 2 W: 20
As we choose an activity to add to our optimal solution without having to first solve all the
subproblems, the approach mentioned above is a greedy one. Now we show that it yields an
optimal solution.
Let 𝑋𝑋 be a set of activities and let 𝑥𝑥 be an activity with latest start time in 𝑋𝑋. Let 𝑌𝑌 be a
maximum-size subset of mutually compatible activities in 𝑋𝑋; and let 𝑦𝑦 be an activity with
latest start time in 𝑌𝑌. If 𝑦𝑦 is the same activity 𝑥𝑥, we are done. Otherwise, let 𝑍𝑍 = 𝑌𝑌 − {𝑦𝑦} ∪
{𝑥𝑥} be a new set of activities.
The activities in 𝑍𝑍 are disjoint, which follows because the activities in 𝑌𝑌 are disjoint, 𝑦𝑦 is the
last activity in 𝑌𝑌 to start, and 𝑠𝑠𝑦𝑦 ≤ 𝑠𝑠𝑥𝑥 (i.e. start time of 𝑦𝑦 is no later than the start time of 𝑥𝑥).
[Rubric] 1 Mark to show that new solution comprises of maximum number of disjoint
activities; and it includes the already isolated activity with latest start time in the
problem.
a) Give an example of a weighted directed graph, G, with negative-weight edges such that
Dijkstra’s algorithm fails to find the correct shortest path. You must mention the start vertex
and the vertex for which Dijkstra’s algorithm will compute incorrect shortest path. (No partial
marks for this part)
𝑎𝑎
10 start vertex: 𝑠𝑠
𝑠𝑠 -8 𝑎𝑎. 𝑑𝑑 = 10
15 𝛿𝛿(𝑠𝑠, 𝑎𝑎) = 7
𝑏𝑏
b) Suppose that we are given a weighted, directed graph G = (V , E ) in which edges that leave
the source vertex s may have negative weights, all other edge weights are non-negative, and
there are no edges going to the source vertex s. Describe an algorithm (basic idea only) to
find the shortest path from s to all other vertices.
• Your algorithm must be asymptotically better than the Bellman Ford algorithm.
• Justify (informally, i.e without using any formal techniques like loop invariant etc.) the
correctness of your algorithm.
[Rubric] 3 Mark
Justification: As there are no negative weight edges starting from an intermediate vertex on
any path (including the shortest paths), as well as there are no negative weight cycles (as no
edges are going to the source vertex); once we have extracted a vertex 𝑣𝑣, it is not possible
that 𝑣𝑣. 𝑑𝑑 could have been decreased later. Hence, for each vertex 𝑣𝑣 ∈ 𝐺𝐺. 𝑉𝑉, 𝑣𝑣. 𝑑𝑑 = 𝛿𝛿(𝑠𝑠, 𝑣𝑣) at
the time 𝑣𝑣 was extracted.
[Rubric] 2 Mark
A more formal argument (optional): We claim that in the given scenario, for each vertex 𝑣𝑣 ∈
𝐺𝐺. 𝑉𝑉, 𝑣𝑣. 𝑑𝑑 = 𝛿𝛿(𝑠𝑠, 𝑣𝑣) at the time 𝑣𝑣 was extracted. For the sake of contradiction, let’s assume
• If there were some intermediate vertex 𝑧𝑧 ∈ 𝐺𝐺. 𝐴𝐴𝐴𝐴𝐴𝐴[𝑥𝑥] between 𝑥𝑥 and 𝑦𝑦 on that path,
then after 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅(𝑥𝑥, 𝑧𝑧, 𝑤𝑤), 𝑧𝑧. 𝑑𝑑 < 𝑦𝑦. 𝑑𝑑 (as 𝑧𝑧. 𝑑𝑑 = 𝛿𝛿(𝑠𝑠, 𝑧𝑧) < 𝛿𝛿(𝑠𝑠, 𝑦𝑦) < 𝑦𝑦. 𝑑𝑑), hence, 𝑧𝑧
must have been extracted before 𝑦𝑦. But that leads to a contradiction (as 𝑥𝑥 is the last
vertex on that shortest path from 𝑠𝑠 to 𝑦𝑦 that was extracted before 𝑦𝑦).
• If there were no intermediate vertex 𝑧𝑧 ∈ 𝐺𝐺. 𝐴𝐴𝐴𝐴𝐴𝐴[𝑥𝑥] between 𝑥𝑥 and 𝑦𝑦 on that path, then
after 𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅𝑅(𝑥𝑥, 𝑦𝑦, 𝑤𝑤), 𝑦𝑦. 𝑑𝑑 = 𝛿𝛿(𝑠𝑠, 𝑦𝑦), once again leading to a contradiction (as 𝑦𝑦. 𝑑𝑑 =
𝛿𝛿(𝑠𝑠, 𝑦𝑦) → 𝑦𝑦. 𝑑𝑑 ≯ 𝛿𝛿(𝑠𝑠, 𝑦𝑦)).
Hence, no such vertex 𝑦𝑦 exists such that 𝑦𝑦. 𝑑𝑑 > 𝛿𝛿(𝑠𝑠, 𝑦𝑦) at the time 𝑦𝑦 was extracted. In other
words, for each vertex 𝑣𝑣 ∈ 𝐺𝐺. 𝑉𝑉, 𝑣𝑣. 𝑑𝑑 = 𝛿𝛿(𝑠𝑠, 𝑣𝑣) at the time 𝑣𝑣 was extracted.
Describe an 𝑂𝑂(𝑉𝑉) algorithm (basic idea only) for finding the minimum spanning tree in the
modified graph (assume that 𝑤𝑤(𝑥𝑥, 𝑦𝑦) returns the weight of the edge (𝑥𝑥, 𝑦𝑦) in Θ(1) time).
As 𝑢𝑢 is an ancestor of 𝑣𝑣 in 𝑇𝑇, we have to see the edges on the path from 𝑢𝑢 to 𝑣𝑣 in 𝑇𝑇 and find
the edge with maximum weight on that path.
[Rubric] 1 Mark to show that we need to find an edge with maximum weight on the
path from 𝑢𝑢 to 𝑣𝑣 in 𝑇𝑇
As we have only 𝜋𝜋 information of the vertices available at hand, we will traverse this path in
reverse order; i.e. we start at (𝑣𝑣, 𝑣𝑣. 𝜋𝜋) then gor to (𝑣𝑣. 𝜋𝜋, 𝑣𝑣. 𝜋𝜋. 𝜋𝜋) and so on till we reach some
vertex 𝑣𝑣′ such that 𝑣𝑣 ′ . 𝜋𝜋 = 𝑢𝑢, the last edge in this sequence would be (𝑣𝑣 ′ , 𝑢𝑢).
This whole process can be done in 𝑂𝑂(𝑉𝑉) time as there are at most |𝑉𝑉| − 1 edges on this path
and the weight of each edge can be obtained in Θ(1) time.
If weight of (𝑥𝑥, 𝑦𝑦) is not greater than the new (reduced) weight of (𝑢𝑢, 𝑣𝑣), then we do not have
to do anything; 𝑇𝑇 will remain an MST for the modified graph.
[Rubric] 1 Mark to show that MST will remain unchanged if 𝑤𝑤(𝑢𝑢, 𝑣𝑣) ≥ 𝑤𝑤(𝑥𝑥, 𝑦𝑦)
Otherwise, (i.e. (𝑢𝑢, 𝑣𝑣) < 𝑤𝑤(𝑥𝑥, 𝑦𝑦) ), we remove (𝑥𝑥, 𝑦𝑦) from 𝑇𝑇, this will break 𝑇𝑇 into two
components. Adding (𝑢𝑢, 𝑣𝑣) reconnects them and gives us a new MST for the modified graph.
[Rubric] 2 Mark to show how to modify the MST if 𝑤𝑤(𝑢𝑢, 𝑣𝑣) < 𝑤𝑤(𝑥𝑥, 𝑦𝑦)
This can be done by setting the 𝜋𝜋 value of each vertex in the path form 𝑣𝑣. 𝜋𝜋 to 𝑦𝑦 to its child
vertex, e.g. let 𝑎𝑎. 𝜋𝜋 = 𝑏𝑏, then we set 𝑏𝑏. 𝜋𝜋 = 𝑎𝑎. As there are at most |𝑉𝑉| vertices on the path
from 𝑣𝑣. 𝜋𝜋 to 𝑦𝑦, this whole process takes 𝑂𝑂(𝑉𝑉) time. At the end, we make 𝑣𝑣 child of 𝑢𝑢 (i.e we
set 𝑣𝑣. 𝜋𝜋 = 𝑢𝑢) which can be done in Θ(1) time.
In a certain course there is an MCQ exam with help sheet. This help sheet contains L lines.
There are n topics included in the exam. For each topic 𝒊𝒊, it is known that there will be Q[𝒊𝒊]
questions in the exam and the marks for these questions will be guaranteed if the information
about the topic 𝒊𝒊 is included in the help sheet. For any topic 𝒊𝒊, there are H[𝒊𝒊] lines available
and the student can either write all of these H[𝒊𝒊] lines in their help sheet or do not write
anything about that topic. The task at hand is to select the topics whose lines you want to
include in the help sheet such that the marks guaranteed is maximized.
For this question you are required to design a bottom-up dynamic programming algorithm
(iterative algorithm) that calculates the maximum marks guaranteed for the above scenario.
There are two dimensions (parameters) of this problems, namely, # of lines (𝑳𝑳), and # of
topics (𝒏𝒏). The question is about maximum marks using (up to) 𝑛𝑛 topics and (at most) 𝐿𝐿 lines.
So, we would solve this problem in a bottom-up fashion along these two dimensions.
[Rubric] 3 Marks
MaxMarks(L,H,Q)
1 n = H.length
2 let Marks[0…n,0…L] be a new array
3 for i = 0 to n
4 Marks[i,0] = 0
5 for j = 1 to L
6 Marks[0,j] = 0
7 for i = 1 to n
8 for j = 1 to L
9 if H[i]>j
10 Marks[i,j]=Marks[i-1,j]
11 else Marks[i,j] = max(Marks[i-1,j],
Marks[i-1,j-H[i]]+Q[i])
12 return Marks[n,L]
Write an algorithm that prints the mountain labels in the order in which the mountains were
climbed by Mathew. Following information would be available to your algorithm as input:
The variables 𝐬𝐬𝐬𝐬𝐬𝐬𝐬𝐬𝐬𝐬 (the mountain from where he started his adventure) and 𝐞𝐞𝐞𝐞𝐞𝐞 (the
mountain where he finished his adventure), and the 2-D array 𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇[𝟏𝟏 … 𝐧𝐧, 𝟏𝟏 … 𝐧𝐧].
𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇[𝒊𝒊, 𝒋𝒋] = 𝒌𝒌 if mount_k is the highest mountain climbed by Mathew while going
from mount_i to mount_j.
𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇𝐇[𝒊𝒊, 𝒋𝒋] = 𝐍𝐍𝐍𝐍𝐍𝐍 if
Either, he climbed mount_j immediately after mount_i (hence, no intermediate
mountain to climb)
Or, he climbed mount_j before mount_i (hence going from mount_i to mount_j
is not a possibility)
Your algorithm MUST finish in 𝑶𝑶(𝒏𝒏) time.
We first print the starting mountain, then we recursively print all the intermediate
mountains, finally we print the ending mountain.
print “mount_”start
print “mount_”end
[Rubric] 2 Marks
PrintIntermediate(i, j, Highest)
if Highest[i,j]≠NIL
print “mount_”Highest[i,j]
PrintIntermediate(Highest[i,j], j, Highest)
[Rubric] 5 Marks
a) In the radix sort algorithm, what possibly may go wrong if the sorting algorithm used by
the radix sort as subroutine is not a stable sorting algorithm? Explain with the help of an
example. (No partial marks for this part)
It may not correctly sort the input array. Let 𝐴𝐴 = 〈55,53〉, then after the first pass, we have
𝐴𝐴[1] = 53 and 𝐴𝐴[2] = 55 (as 3 < 5). However, in the second pass there would be a tie
between two occurrences of 5. If the subroutine is not a stable sorting algorithm, it may pick
5 corresponding to 55 first and the final output would be 𝐴𝐴 = 〈55,53〉, which is not correct.
b) For the following algorithm, write down the recursive expression for 𝑇𝑇(𝑛𝑛). The first call is
ALGO(A, 1, n), where A is an array of size n.
1 𝑟𝑟𝑟𝑟𝑟𝑟 = 𝑖𝑖
2 𝒊𝒊𝒊𝒊 (𝒊𝒊 ≤ 𝒋𝒋) 𝒕𝒕𝒕𝒕𝒕𝒕𝒕𝒕
3 𝑟𝑟𝑟𝑟𝑟𝑟 = 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴(𝐴𝐴, 𝑖𝑖, (𝑖𝑖 + 𝑗𝑗)⁄2)
4 𝑘𝑘 = (𝑖𝑖 + 𝑗𝑗)⁄2
5 𝒘𝒘𝒘𝒘𝒘𝒘𝒘𝒘𝒘𝒘 (𝑘𝑘 ≤ 𝑗𝑗)
6 𝑟𝑟𝑟𝑟𝑟𝑟 = 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴(𝐴𝐴, 𝑘𝑘, 𝑗𝑗) + 𝑟𝑟𝑟𝑟𝑟𝑟 − 𝑘𝑘
7 𝑘𝑘 = 𝑘𝑘 + 1
2 Marks
8 𝒓𝒓𝒓𝒓𝒓𝒓𝒓𝒓𝒓𝒓𝒓𝒓 𝑟𝑟𝑟𝑟𝑟𝑟
𝑛𝑛
2
𝑛𝑛
𝑇𝑇(𝑛𝑛) = 𝑇𝑇 � � + � 𝑇𝑇(𝑚𝑚) + Θ(𝑛𝑛)
2
𝑚𝑚=1
1 Mark
c)