Here's the marking scheme for quiz: Problem 1: ----------- The general structure of greedy algorithm: 1 point Sorting in non-decreasing order of deadlines: 3 points The "feasibility" condition: 2 points A common mistake in this problem was due to the formulation of the problem. In the lecture notes, it is explicitly stated that the difference between an "activity" and a "job" is in that a job can be scheduled at any time before its deadline. Accordin to this definition, this problem is an activity selection problem, not a job scheduling. Some student has thought that jobs can be executed at any time. Another common mistake is in the feasibility condition. Most student prefer to write pseudo-code (without any explanation) rather than explaining the algorithm in english, and they usually make a lot of mistakes in writing pseudo-code; while they have the correct idea in their mind. For example for the feasibility condition many students compare b_i with e_{i-1}, instead of comparing it with e_j, where j is the last selected job. Problem 2: ----------- part a: 3 points (1 point for R(0,0)=T and 2 points for R(0,i)=F for i>0) part b: 5 points: 2 point for the term R(i-1,j) 2 point for the term R(i-1,j-w_i)&j\ge w_i (1 point for each term) 1 point for having OR between the above two terms. (many students have written the above two terms in the form: "if i in S, then R(i,j) is equal to ... and if i is not in S ..." Such solutions does not get this 1 point part c: 4 points (2 points for justification of each term) Problem 3: ----------- part a: 2 points part b: 6 points: 2 points for the value of A(i,t) in the case that t_min