CS 332 Homework #1 Problem #1 Alice P. Hacker Collaborators: John Doe (worked together), Ben Bitdiddle (I helped him)
1. Examples
This document is an example of how to use LATEX for writing homework solutions. Read the text, commented out by % signs, to get some explanations.
a) This part includes a theorem with a proof and uses mathematical expressions.
Theorem 1.
n n(n + 1)
i= 2
Base case: Prove that the formula is true when n = 1. The LHS is 1
(1)
i = 1, while the RHS is 1(1+1) = 1. 2
Proof. The proof is by induction. Hence, the base case holds.
i=1
i=1
Inductionstep: Foreachk≥1,assumethat(1)istrueforn=k. Weshowthatitistrueforn=k+1. k+1 k k(k + 1) k(k + 1) + 2(k + 1) (k + 1)(k + 2)
i = i + (k + 1) = 2 + (k + 1) = 2 i=1 i=1
where the second equality follows from induction hypothesis that k i=1
= 2 ,
i = k(k+1) . The formula (1) is true
2
for n = k + 1, which proves the theorem.
b) This part has a figure that displays a picture from an external file.
Figure 1: Comparing two sets of jobs
c) This part has an example of writing algorithm psuedocode.
Assume that there are n jobs and the ith job has a start time s(i) and a finish time f(i). These jobs are sorted with respect to their finish time. For simplicity, we assume that the sorted jobs are numbered 1,2,…, n such that f(1) ≤ f(2) ≤ ··· ≤ f(n).
A set of jobs is compatible with a job j if none of the jobs in the set overlaps with j. The algorithm maintains A, a set of selected jobs, which is initially empty. Our intuitive approach is to grow A by choosing a compatible job with the earliest finish time at each step.
Let i1,…,ik be the set of jobs in A in the order they were added to A. Similarly, let the set of jobs in B, which selects jobs in some method other than greedy approach, be denoted by j1,…,jl. One interesting consequence is that the greedy rule stays ahead: f(im) ≤ f(jm) for 1 ≤ m ≤ min(k,l).
1 of 2
CS 332 Homework #1 Problem #1
Collaborators: John Doe (worked together), Ben Bitdiddle (I helped him)
Algorithm 1: Earliest-Finish-Time(L).
input :alistLofnjobs.
output: a maximum set of mutually compatible jobs.
1 Sort jobs by finish times so that f(1) ≤ f(2) ≤ ··· ≤ f(n).
2 Maintain a set A which is initially empty.
3 for i=1tondo
4 If the job i is compatible with A, then include i to A.
end
5 Output A.
Claim 2. For all indices m ≤ min(k,l), f(im) ≤ f(jm).
Alice P. Hacker
Proof. We prove by induction on the index m. For m = 1, the statement is true because the greedy approach selects the job with the earliest finish time. For m > 1, we will assume the statement is true for m = t−1 and prove it for m = t. The tth job in B must start after f(jt−1) since this job is compatible with B. It means f(jt−1) ≤ s(jt). By combining the induction hypothesis f(it−1) ≤ fj(t − 1), it also means f(it−1) ≤ s(jt). So this job is compatible with A too. As the greedy algorithm selects a job with earliest finish time, f(it) is not larger than f(jt). This completes the induction step; therefore, the statement is true.
Proof of Correctness Assume for contradiction that the greedy approach returns a non-optimal solution AwhileanoptimalsetOhasmorejobs. Assumethat|A|=kand|O|=lwithl>k. ByClaim2,wehave f(ik) ≤ f(jk). Let us focus on the (k + 1)th job x in O. The job x starts after the job jk ends and hence after the job ik ends. But the greedy algorithm stops with ik while x is compatible with A – a contradiction.
Implementation Once the input jobs are sorted, an array is enough for the set A. When a new job is checked for compatibility with A, it is enough to compare its start time with the last added job x’s finish time rather than all the jobs’ finish times in A – the resource becomes free after f(x) and the input jobs are sorted.
Time and Space Complexity It takes Θ(nlogn) time to sort the input jobs of size n. Creating an array of size n takes O(n) time. For each job, it takes O(1) time to check whether a job is compatible with the set A, and the array can be updated in constant time if we maintain an end-of-the-array pointer. These operations must be repeated for each job, so the For loop takes O(n) time. Hence, the total running time is O(n log n).
It takes O(n) space to store the input. An in-place sorting takes O(n) space. Finally, the set A can be implemented by an array of size n. Thus, the space complexity is O(n).
2 of 2