CSC 373 — Assignment 1
Due October 5th, 4:00pm. Give the assignment to me in person, or put it in my mailbox. To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources
(people, print, electronic) outside the course and lecture notes, that you consulted.
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity. Answers that are technically correct but that are hard to understand, messy, unorganized, etc., may not receive full marks. Mark values for each question are contained in the [square brackets].
- Consider a long stretch of rural road with farms distributed sparsely along it. This road is given as a list where each value in the list conveys the location of a farm at that distance. For example, the list [4,8,9,20] denotes a straight road with farms at distances 4km, 8km, 9km, and 20km down the road. You want to build cell towers along the road such that all the farms are covered. A farm is covered if it is within 5km of a cell tower. Moreover, you want to build as few cell towers as possible. Propose a greedy algorithm to this problem, give it in pseudo-code where the function takes in a list of integers denoting the farm locations, and returns a list of integers denoting the cell tower locations. Formally prove your algorithm is correct using induction and showing that it “agrees” with an optimal solution. [10]
- Consider the following problems and greedy algorithms. For each greedy algorithm, prove or disprove its optimality.
- (a) Consider scheduling a set of jobs on a single resource, where each job has a size, si, and a deadline, di. Once you’ve determined a schedule each job will have a finish time fi. The lateness of job i is defined to be li = max(0, fi − di). Here, our goal is to minimize the total lateness of all n jobs. That is, we wish to minimize
n li.
i=1
Prove or disprove the optimality of scheduling Earliest Deadline First. [5] - (b) Consider a list of n unique ordered integers, where you are allowed to remove m of them. The goal is to maximize the distance between the remaining closest numbers. As an example, consider the list [1, 4, 5, 6, 8, 9], where we are allowed to remove two numbers. Here, an optimal solution would be to remove the numbers 5 and 8, leaving us with the list [1, 4, 6, 9]. The distance between the closest remaining numbers is 2 (between 4 and 6). The proposed greedy algorithm to this problem is to take a pair of numbers which are currently closest together and remove the one which would result in the better solution. Using [1,4,5,6,8,9] again as an example, the greedy
- (a) Consider scheduling a set of jobs on a single resource, where each job has a size, si, and a deadline, di. Once you’ve determined a schedule each job will have a finish time fi. The lateness of job i is defined to be li = max(0, fi − di). Here, our goal is to minimize the total lateness of all n jobs. That is, we wish to minimize
1
algorithm would look at one of the closest pairs of numbers (4,5), (5,6) or (8,9). Without loss if generality assume it examines the pair (4,5), 5 is closer to 6 than 4 is to 1, so the algorithm would choose to remove 5, leaving the list [1,4,6,8,9]. The algorithm would then look again at a closest pair of numbers, (8,9) and remove 8, terminating to the solution [1, 4, 6, 9]. Prove or disprove the optimality of this algorithm. [8]
3. Prove or disprove the following statements:
(a) If all edge weights on a connected graph are unique/distinct, then there exists a unique/distinct minimum spanning tree. [4]
(b) Consider a graph, G = (V,E) and two weight functions w1(e) and w2(e), where w1(e) = (w2(e))2. You may assume all edge weights are unique and positive.
Under both weight functions, Kruskal’s algorithm will return the same minimum spanning tree. [2]
Under both weight functions, Dijkstra’s algorithm will return the same shortest path. [2]
2