Problem 1. (20 points) Consider the following edge weighted undirected graph:

C

H

2

Your task is to run Dijkstra’s algorithm, Prim’s algorithm, and Kruskal’s algo- rithm on this graph and indicate their outputs:

a) Indicate the order in which the edges are added when running Dijkstra’s

[5 points] [2 points]

c) Indicate the order in which the edges are added by Prim’s algorithm, starting

at B.                                                                                                   [5 points]

d) What is the cost of the MST computed by Prim’s algorithm?            [2 points]

e) Indicate the order in which the edges are added by Kruskal’s algorithm.     [5 points]

f)  What is the cost of the MST computed by Kruskal’s algorithm?       [工 points]

(You do not have to explain your answer.)

Problem 2. (10 points) Consider the following instance of the fractional knapsack problem on 9 items:

Your task is to:

a) Compute the set of items, along with the fraction in which they are used, with maximum total benefit of weight at most W = 21 and also give the total benefit of this set.                                                                              [7 points]

b) List the order in which the items are considered by the greedy algorithm from the lecture that returns the optimal solution.                                    [3 points]

(You do not have to explain your answer.)

Problem 3. (15 points)

Given an array of n (distinct) numbers A, an index 1  ≤ i  ≤ n − 2 is a local minimum if A[i] < A[i + 1] and A[i] < A[i − 1]. Your task is to design an algorithm that finds a local minimum in a given array A.

a) Give an algorithm with time complexity O(n).

b) Give a (better) algorithm with time complexity O(log n).

c) Analyse the time complexity of the second algorithm.

You do not need to prove the correctness of your algorithms. Hint for b): divide-and-conquer.

[3 points] [7 points] [5 points]

Problem 4. (15 points) Consider the following problem: you are given a set of n people, and need to divide them in two groups (not necessarily of equal size). But there is a catch:  some people really do not like each other, and refuse to be in the same group: specifically, you are also given a list of m conditions of the form “person i hates person j”(for 1 ≤ i, j ≤ n), and you must make sure that people who hate each other are not put in the same group.

Your task is to design an algorithm which, given n people and a set of m con- straints of that sort, determines if there exists a way to divide them in two groups while satisfying all the constraints. The algorithm must run in time O(n + m).

a) Provide an algorithm to solve this problem..

b) Analyse the time complexity of the algorithm.

c) Prove correctness of the algorithm.

[7 points] [4 points] [4 points]

Hint: transform the problem into a problem about graphs. You can use anything seen during the lectures and tutorials without justification.