Home

Question 1 : 25 points
A valid Red-Black tree should possess the following properties:
1. Every node is either red or black.
2. The root is black.
3. Every leaf is NULL and black.
4. If a node is red, then both its children are black.
5. All paths from a node x to any leaf have same number of black nodes in between (i.e.,
their Black-Height(x) is the same)
After insertion of a new key x to the tree, properties 3 and 5 may be violated causing the
tree to be become unbalanced. These violations can be overcome by rotating the tree around
certain nodes and updating their colors, as described in the slides.
(a) [10 points] Consider the Red-Black Tree given above. Insert the key 36 into it. Which
cases from the slides are you going to encounter? What rotations would you need to over-
come these problematic cases? What will the final tree look like? Explain your answer.
(Note: You must show the final state in picture and also explain which violation caused
you to use which rotation on which node as your progressed through the rebalancing of the
tree)
(b) [10 points] Asymptotic cost of inserting a new key to a red-black tree is O(log n). Why?
Explain your answer by showing the math.
(c) [5 points] Where would you use red-black trees? Why?
Question 2 : 25 points
Answer the following questions about graphs.
(a) [7 points] What is the maximum number of edges that can exist in an undirected graph?
What is the maximum number of edges that can exist in a digraph (a.k.a., directed graph)?
Explain how you came up with the answer in both cases.
(b) [8 points] Given a digraph G, its inverse GT is defined as digraph where all the edges of
the original graph are inverted. That is, ∀ (u, v) ∈ G.E, ∃ (v, u) ∈ GT .E. Describe a
non-empty digraph G such that G = GT .
(c) [10 points] A strongly connected component (SCC) of a digraph G is a maximal set
of vertices C ⊆ V such that for each pair of vertices, we have both u ↝ v and v ↝ u; that
is, vertices u and v are mutually reachable from one another.
One algorithm to calculate SCCs in a graph uses DFS as a subroutine twice; once on G and
once on GT . This is known as Kosaraju’s Two-Pass algorithm. Explain the intuition be-
hind how the DFS subroutine is able to help the algorithm discover the SCCs of a digraph.
(Hint: Don’t overthink it. This question can be answered in 3-4 sentences. Try to be
precise)
Question 3 : 20 points
The Computer Science program at Drexel University has a very complex course structure. As
you already know, certain courses are prerequisites for others. For example, you cannot take
CS260 before you take CS265 as the latter is a prerequisite for the former. For some reason, the
department has called upon you to help them figure out certain intricacies about the structure
of the program they themselves designed.
(a) [10 points] Is there any sequence of course that is not possible to take due to its, possibly,
unreasonable prerequisite requirements? Specify a graph algorithm, in plain English bullet
points, to answer this question by considering the following questions.
ˆ What will be the input to your algorithm? What will be the nodes and edges of your
graph?
ˆ How do you determine whether such an forbidden sequence exists?
ˆ What is the time complexity of your algorithm?
(b) [10 points] Assuming that a forbidden sequence of the form mentioned in part (a) doesn’t
exist, specify an algorithm, in plain English bullet points, that will output a permissible sequence of courses for a student to follow. Also, analyse your algorithm’s time complexity.
Question 4 : 30 points
Consider your path to success, which is pretty much like climbing a ladder. Very frequently in
life, as it is strictly the case for this problem, there are two choices in front of you: you either
step to the next step of the ladder, or skip the middle one and step on the second step. And
each step comes with a certain level of success (or failure), which is quantified by an integer
for this problem.
More formally, you are given an array of integers that represents the ladder and the values
stored in the array represents the contribution of landing on this step to your success.
Considering the costs of each step of the ladder, you are expected to suggest a strategy (i.e.,
an algorithm) that will provide the optimal steps to be taken to maximize the success by the
time you reach the pinnacle of your career.
(Disclaimer: once they reach the pinnacle, human beings either die and conclude their success
story in dust, or fall from there before they die and still end their story in dust!!! Moral of the
story: Success in career shouldn’t be the end goal…)
(a) [15 points] Suggest an algorithm for this problem (in bullet points) that utilizes binary
trees as part of its solution. Explain the runtime of your algorithm.
(b) [15 points] Suggest a more efficient algorithm that uses graphs instead of binary trees.
explain the runtime of your algorithm.