Assignment 4 - Due March 29, 2022

  1. In class we went through all five problems on the dynamic programming problem practice sheet (provided both on a printout in class and in a Canvas announcement on Feb 23). Pick any one of these, and write out a solution up to and including a recursive formula for the optimal objective function value. Make your answer concise and to the point: You’ll need to define some notation for variables and functions, and the define the recursive formula. None of those should require more than one or two sentences of explanation, so do not submit any answer that is more than one page long. In particular, you do not have to write up the actual dynamic programming algorithm - just the recursive formula for the optimal objective function value.

  2. Consider the following input to the fractional knapsack problem (as in Section 16.2), for a knapsack that can hold at most \(W=50\) pounds:

    \(i\) 1 2 3 4 5
    \(v_i\) 9 5 7 12 3
    \(w_i\) 18 15 28 50 6

    Give a step-by-step explanation of how the greedy algorithm from Section 16.2 would solve this problem, showing values at each step and the final answer computed by the algorithm.

  3. You have decided to pursue a small-job gig work career, and accept jobs that each take exactly one day to complete. Days and jobs are numbered starting at 1, and there are \(n\) potential jobs (numbered \(1\) to \(n\)). Each job has a deadline \(d_i\) by which it must be completed in order for you to get paid (so if you schedule job \(i\) on day \(s_i\), then you get paid if and only if \(s_i\leq d_i\)).

    1. If all jobs pay the same amount, then your goal is to maximize the number of jobs you complete by the deadline. The following greedy strategy works: On day 1, pick an uncompleted job with the earliest possible deadline and finish that (if there is a tie – multiple jobs with the same earliest possible deadline – pick the lowest numbered job). State and prove the greedy choice property for this algorithm. Do not give a full proof of correctness for the algorithm – only prove the greedy choice property.

    2. Consider a variation in which each job also has a payoff, so completing job \(j\) by deadline \(d_j\) results in you being paid \(p_j\) dollars. Now you want to maximize how much you are paid, which might not be the same as completing the maximum number of jobs. You could just ignore the payoffs, and use the greedy algorithm from part (a) to maximize the number of jobs completed. Give a counter-example to show that this does not maximize your pay. (Hint: Don’t over-complicate this – there is an example with just two jobs that shows that the algorithm in part (a) doesn’t work.)

    3. What if you chose the highest payoff job for day 1, and ignored the deadlines? Give a counter-example to show that this does not always give an optimal solution. (Hint: There is a two-job counter-example for this part too. If you want to be particularly clever, there’s a single three-job case that is a counter-example to both parts b and c!).

    4. The following greedy strategy does work: Find a maximum payoff job, and schedule it as late as possible before its deadline (you can break ties however you like, but for concreteness you can assume you always pick the lowest numbered job if there’s a tie). In other words, if job \(j\) is the first maximum payoff job that you select, then schedule it at time \(d_j\). State and prove the greedy choice property for this algorithm.

  4. Give an example showing that the \(\pi\) values computed in a Breadth-First-Search (see page 595) depend on the specific ordering of vertices in the adjacency lists. In other words, give a single graph \(G\), two adjacency list representations of \(G\), and then show that BFS finds different \(\pi\) values for the two representations.

  5. Give a clear explanation of why the \(d\) values computed in a BFS do not depend on the adjacency list ordering of the input graph. This does not need to be a formal proof, but it does need to apply to all graphs (not just a single example graph) and it should be clear and precise reasoning. Your explanation should be no more than three sentences.

  6. Perform a depth-first search of the following graph, showing the final result with the discovery and finishing times for each vertex, and the classification of each edge (tree, forward, back, or cross). Vertices are always explored in alphabetical order, whether in the overall vertex list or in any adjacency list. Your result should be in a form similar to Figure 22.5(a) in the book. Note that you only need to give the final result – you don’t need to show your work or any intermediate steps.

  7. Programming challenge: Installing a new software package on a system might require that other packages be installed first (on Debian-based Linux systems, this is called a “Pre-Depends” relation between packages). You should write a program that reads in information about these Pre-Depends requirements, and then either outputs an order in which the packages can be installed, or outputs “impossible” if there is no order that will work.

    Program Input: The input to this problem consists of two integers \(n\) and \(m\) on the first line, where \(n\) is the number of packages to install (with \(1\leq n\leq 949\)) and \(m\) is the number of pre-depends relations (with \(1\leq m\leq 450,000\)). This is followed by \(m\) lines, each with two numbers \(x\) and \(y\) (with \(1\leq x,y\leq n\)) such that package number \(x\) must be installed before package \(y\). Here is a simple example with three packages:

    3 2
2 1
3 1

    Program Output: The output should consist of either a single line with the word “impossible” (exactly like that!), or \(n\) lines that give an order in which packages can be installed that satisfies all pre-depends requirements. Note that there can be multiple correct outputs for any input, and any of them are acceptable. The following is one example of a correct output for the sample input shown above:

    2
3
1

    Note that if the input had contained a third requirement of “3 2” then this would not be a correct solution any more, as package 3 would have to be installed before package 2.

    Time Limit: Your program must run in under 5 seconds on any input that meets the size bounds described above.

    Example 2: Here is another example input to consider:

    3 3
2 1
3 2
1 3

    For this input, the correct output should be:

    impossible