Instructions
CSC373 Fall’20 Midterm 1
Due By: 20th October 2020, 6:10pm ET
1. Upload a single PDF with your solutions to MarkUs at https://markus.teach.cs.toronto. edu/csc373-2020-09
2. For handwritten solutions, please make sure that your handwriting is legible, and your scan is high-quality and not distorted.
3. Remember: You will receive 20% for any (sub)question when you leave it blank (or cross off any written solution) and write “I do not know how to approach this problem.”, and 10% if you leave it blank but do not write this or a similar statement.
Q1 [20 Points] The Best Part of a Tree
You are given a rooted tree T with n nodes. Each node v has a weight wv ∈ R. Your goal is to find the maximum total node weight in any connected subgraph of T. (You do not need to find the actual subgraph inducing this weight.)
A subgraph H of T consists of a subset of nodes in T, and it is connected if every pair of nodes in H has a path connecting them in T. Empty subgraph is allowed and has total node weight 0.
Here is an example tree with its maximum-weight connected subgraph highlighted in red.
Design a divide-and-conquer algorithm for the problem. Describe your algorithm (either verbally or through a pseudocode) and provide a brief justification of its correctness and worst-case running time. For full credit, your algorithm must run in O(n) time.
[Hint: Remember that a tree with n nodes has m = n − 1 edges.]
1
Q2 [20 Points] Protect the Paintings
A corridor of a museum is represented by the interval [a,b] (with a < b) and contains valuable paintings. There are n guards stationed along the corridor. Guard i can protect the interval [si,fi], where a ≤ si ≤ fi ≤ b. Your goal is to find a minimum-size subset of guards P ⊆ {1,...,n} who collectively cover the entire corridor (i.e. ∪i∈P [si, fi] = [a, b]); assume that such a subset exists.
Consider the following greedy algorithm, which always looks at the rightmost covered point (initially a) and, among the guards who cover it, selects one whose range goes as much to the right as possible.
• G←∅andt←a • Whilet
You want to form a friendly committee by choosing heads from a subset of houses such that no two heads chosen are enemies. Design a dynamic programming algorithm that takes array A[1 . . . n] as input and computes the maximum number of heads the committee can have. For full credit, your algorithm must run in O(n2) time and use O(n) space.
(a) [2.5 Points] Define an array storing the necessary information from subproblems. Clearly define what each entry means and how you would compute the desired solution given this array.
(b) [2.5 Points] Write a Bellman equation and briefly justify its correctness.
(c) [2.5 Points] In what order would you compute the entries in a bottom-up implementation?
(Pseudocode is not needed.)
(d) [2.5 Points] Analyze the worst-case running time and space complexity of your algorithm.
2