CSE 101 Winter 2024

Homework 7

Due: Thursday 3/14 at 11:59pm

1. (15 points) You are given a rooted binary tree T on n vertices named 0, . . . , n − 1. The rooted tree is given to you as an adjacency list of children. (You can assume that the vertices are ordered by levels starting from the lowest level (i.e., that vertex n − 1 is the root.)

Each vertex i has a positive value v[i].

You are given an integer k ≤ n. You wish to find the total weight of connected subtree with k vertices with the greatest total sum of weights of its vertices.

Complete the setup for a DP tabulation algorithm for this problem. (You only need to do steps 2-5.

You do not need to include a pseudocode and you do not need to include a runtime analysis. The descriptions of subproblems (Step 1:) are given below:)

Note that this problem requires two arrays to fill:

Let IN[i, j] be the maximum weight connected subtree with exactly j vertices of the subtree hanging from vertex i that includes vertex i

Let OUT[i, j] be the maximum weight connected subtree with exactly j vertices of the subtree hanging from vertex i that excludes vertex i

• Organizer A can read papers on Greedy, DP and DC

• Organizer B can read papers on DP and DC

• Organizer C can read papers on only Greedy.

• Organizer D can read papers on Greedy and DP.

There are 100 submissions: 30 submissions on Greedy algorithms, 50 submissions on DP and 20 submissions on DC.

Each organizer only has time to read 25 papers each.

Is it possible to have all of the papers read?

(Hint, turn this into a network problem: make a bipartite graph with the paper topics on the left and the organizers on the right. Connect the two parts with whatever the organizers can read and weigh the edges with infinity. Add a new vertex s as the source and connect it to each topic according to the number of papers of that topic you have. Add a new vertex t as the sink and connect it from each organizer according to how many papers they have time to read.)