Midterm exam 24 October 2018, questions and answers PDF

Preview

Summary

Download Midterm exam 24 October 2018, questions and answers PDF

Description

CS4335 Design and Analysis of Algorithms (Midterm) Question 1. (20 points) (a) (10 points) For the interval scheduling problem, the set of jobs (si, fi) are as follows: (0, 2), (1, 3), (3, 6), (3, 4), (6, 9) (4, 12), (5, 8), and (6, 7). Use a greedy algorithm to compute the maximum number of compatible jobs. You should give main steps. What is the running time of the greedy algorithm? Solution: Step 1: Sort all the jobs by their finishing time: (0, 2), (1, 3), (3, 4), (3, 6), (6, 7), (5, 8), (6, 9), (4, 12) Step 2: Select the first job, and choose the rest jobs one by one if one is compatible with the former job: (0, 2), (3, 4), (6, 7) The running time of the greedy algorithm is

.

(b) (8 points) For the interval partitioning problem, the set of lectures (s i, fi) are as follows: (0, 1), (0, 3), (1, 4), (2, 6), (3, 4), (4, 5) and (5, 8). Use a greedy algorithm to compute the minimum number of classrooms to accommodate all the lectures. You should give main steps. Solution: Step 1: Sort all the jobs by their starting time: (0, 1), (0, 3), (1, 4), (2, 6), (3, 4), (4, 5) and (5, 8). Or another sorting method is also correct: (0, 3), (0, 1), (1, 4), (2, 6), (3, 4), (4, 5) and (5, 8). Step 2: The scheme of first sorting method:

The scheme of the second sorting method:

The minimum number of classroom from the greedy algorithm is 3. (c) (2 points) For the interval partitioning problem given in (b), what is the depth of the problem? Solution: The depth is 3. According to the definition of the DEPTH: the depth of a set of intervals to be the maximum number that pass over any single point on the time-line. From the scheme above, we can see the depth of this problem is 3, such as any points in (2, 4).

Question 2. (20 points) (a)

Solution: 5

b

a

20

16 1

s

10 0

9

v

13

8 d

c 15

(1) the 1st step

a 、 5 、 /

16 1

s 13

(2) the 2nd step

b 10 0

9 d

16

2 0

13

1 6

s 13

5

d

1 6

b 10 0

9 c

2 0

10 0

d

v 8

c 15

20

1

b

9

15

a 、 、 /

5

1

s

v 8

c

a 、 、 /

s v

8

13

a 、 、 /

5

b 20

1

10 0

9 d

c

v 8

15

15 (3) the 3rd step

(4) the 4th step

20

(5) the 5th step

(6) the 6th step

(7) the last step a 、 、 /

16

13

s 13

b 20 10

1

s

1 6

5

v

9

d

、 /

c 15

1

10 0

9 d

c 15

a 、 、 /

8

5

1 6 v

8

s 13

5

b 20

1

10 0

9 d

c

v 8

15

(b) (10 points) Use the dynamic programming algorithm in the lecture to solve the following Manhattan Tourist Problem. Backtracking is required.

Question 3. (15 points) Use Dijkstra’s algorithm to compute a shortest path from s to v in the following graph. You should give main steps.

5 b

a

20

16 10 10

s

4

v

9

13 d

4

c 15

Solution: Initialize: Q d π S = {}

s 0 NIL

a inf NIL

b inf NIL

c inf NIL

d inf NIL

v inf NIL

Step1: Q d π S = {s}

s 0 NIL

a inf NIL

b inf NIL

c inf NIL

d inf NIL

v inf NIL

Step2: Q d π S = {s, d}

s 0 NIL

a 16 s

b inf NIL

c inf NIL

d 13 s

v inf NIL

Step3: Q d π S = {s, d, a}

s 0 NIL

a 16 s

b inf NIL

c 28 d

d 13 s

v inf NIL

Step4: Q s d 0 π NIL S = {s, d, a, b}

a 16 s

b 21 a

c 28 d

d 13 s

v inf NIL

Step5: Q s d 0 π NIL S = {s, d, a, b, d}

a 16 s

b 21 a

c 28 d

d 13 s

v 41 b

Step6: Q s d 0 π NIL S = {s, d, a, b, d, v}

a 16 s

b 21 a

c 28 d

d 13 s

v 32 c

Backtracking: v ← c ← d ← s A shortest path from s to v is s → d → c → v with total weight 32.

Question 4 (15 points) (a) (10 points) For the list: 15, 1, 5, 8, 9, 10, 4, 7, 6, 13, 14, and 11. Suppose we have sorted the two halves as list1: 1, 5, 8, 9, 10, 15; and list2: 4, 6, 7, 11, 13, 14. Calculate the number of inversions with one number in list1 and the other number in list2 using O(n) operations. Immediate steps are required. (b) (5 points) Suppose T(1)=1, T(2)=1, and T(n)=T(n-2)+n for k= 3, 4, ….. What is T(n) in terms of big O notation? Solution: (a) i=6 ↓ 1 5 8

9

10

15

↓ 4

6

7

11

13

14

two sorted halves

auxiliary array Total: i=6 ↓ 1

5

8

9

10

15

↓ 4

6

7

11

13

14

two sorted halves

1

auxiliary array Total:

1

i= 5 ↓ 5

8

9

10

15

↓ 4

6

7

11

13

14

1

two sorted halves

auxiliary array Total:

1

i= 5 ↓ 5

8

1

4

9

10

15

↓ 4 5

6

7

11

13

14

two sorted halves

auxiliary array Total: 5

1

i= 5 ↓ 5

8

1

4

9

10

15

4 5

↓ 6

7

11

13

14

two sorted halves

auxiliary array Total: 5

1

i= 5 ↓ 5

8

9

1

4

5

10

15

4 5

↓ 6

7

11

13

14

two sorted halves

auxiliary array Total: 5

i= 4

1

5

↓ 8

9

1

4

5

10

15

4 5

↓ 6

7

11

13

14

two sorted halves

auxiliary array Total: 5

1

5

i= 4 ↓ 8

9

10

1

4

5

6

15

4 5

↓ 6 4

7

11

13

14

two sorted halves

auxiliary array Total: 5+4

1

5

i= 4 ↓ 8

9

10

1

4

5

6

15

4 5

6 4

↓ 7

11

13

14

two sorted halves

auxiliary array Total: 5+4

1

5

i= 4 ↓ 8

9

10

15

1

4

5

6

7

4 5

6 4

↓ 7 4

11

13

14

two sorted halves

auxiliary array Total: 5+4+4

1

5

i= 4 ↓ 8

9

10

15

4 5

6 4

7 4

↓ 11

13

14

two sorted halves

1

4

5

6

7

auxiliary array Total: 5+4+4

1

5

i= 4 ↓ 8

9

10

15

1

4

5

6

7

4 5

6 4

7 4

↓ 11

13

14

8

two sorted halves

auxiliary array Total: 5+4+4

1

5

8

i= 3 ↓ 9

1

4

5

10

15

6

7

4 5

6 4

7 4

↓ 11

13

14

8

two sorted halves

auxiliary array Total: 5+4+4

1

5

8

i= 3 ↓ 9

1

4

5

10

15

6

7

4 5 8

6 4

7 4

↓ 11

13

14

9

two sorted halves

auxiliary array Total: 5+4+4

1

5

8

9

i= 2 ↓ 10

1

4

5

6

15

7

4 5 8

9

6 4

7 4

↓ 11

13

14

two sorted halves

auxiliary array Total: 5+4+4

1

5

8

9

i= 2 ↓ 10

1

4

5

6

15

7

8

4 5

6 4

9

10

7 4

↓ 11

13

14

two sorted halves

auxiliary array Total: 5+4+4

1

5

8

9

10

i= 1 ↓ 15

1

4

5

6

7

4 5 8

6 4

7 4

↓ 11

13

14

9

two sorted halves

auxiliary array Total: 5+4+4

1

5

8

9

10

i= 1 ↓ 15

1

4

5

6

7

8

4 5

6 4

9

11

7 4

↓ 11 1

13

14

two sorted halves

auxiliary array Total: 5+4+4+1

1

5

8

9

10

i= 1 ↓ 15

1

4

5

6

7

8

4 5

6 4

9

11

7 4

11 1

↓ 13

14

two sorted halves

auxiliary array Total: 5+4+4+1

1

5

8

9

10

i= 1 ↓ 15

4 5

6 4

7 4

11 1

↓ 13 1

14

two sorted halves

1

4

5

6

7

8

9

11

13

auxiliary array Total: 5+4+4+1+1

1

5

8

9

10

i= 1 ↓ 15

1

4

5

6

7

8

4 5

6 4

7 4

9

11

13

11 1

13 1

↓ 14

two sorted halves

auxiliary array Total: 5+4+4+1+1

1

5

8

9

10

i= 1 ↓ 15

1

4

5

6

7

8

4 5

6 4

7 4

11 1

9

11

13

14

13 1

↓ 14 1

two sorted halves

auxiliary array Total: 5+4+4+1+1+1

1

5

8

9

10

i= 1 ↓ 15

1

4

5

6

7

↓

8

4 5

6 4

7 4

11 1

9

11

13

14

13 1

14 1

two sorted halves

auxiliary array Total: 5+4+4+1+1+1

1

5

8

9

10

i= 1 ↓ 15

1

4

5

6

7

↓

8

4 5

6 4

7 4

11 1

13 1

9

11

13

14

15

14 1

two sorted halves

auxiliary array Total: 5+4+4+1+1+1

i= 0 ↓ 1

5

8

9

10

15

1

4

5

6

7

8

↓ 4 5

6 4

7 4

11 1

13 1

9

11

13

14

15

14 1

two sorted halves

auxiliary array Total: 5+4+4+1+1+1

The number of inversions between the first half and the second half is 5+4+4+1+1+1 = 16.

(b) If n is even T(n)=T(n-2)+n =T(n-4)+2n =… =T(2)+(n/2-1)n =1+n2/2-n Therefore, O(T(n))=n2 If n is odd, T(n)=T(n-2)+n =T(n-4)+2n =… =T(1)+((n+1)/2-1)n =n2/2-n/2+1 Therefore, O(T(n))=n2

Question 5. (15 points) Write a pseudo code for a divide-and-conquer algorithm for finding the largest and second largest numbers in an array of n distinct numbers. The running time of your algorithm should be O(n). Hint: You should treat the input array A as a global variable. The function should have a prototype x, y=f(low, high) where x and y are largest and second largest numbers, respectively, in A[low…high]. iii) To call the function we can do the following x, y = f(1, n). Coping an array of n numbers takes O(n) time. Thus, we should not copy the array many times in order to get the O(n) running time. That is why the function prototype contains two parameters low and high indicating the starting position and ending position of the array, respectively. i) ii)

(a) (8 points) Write the pseudo code for the case where n= 2k for some integer k. (b) (2 points) Write the pseudo code for the case where n >1 is any integer. (c) (5 points) Set up and solve a recurrence relation for the number of comparisons made by your algorithm. (Only divide-conquer approach is acceptable. 0 mark for other methods.) Solution: (a) f(low, high) { if (high-low==1) \\==2 also ok. Depending on the definition of a[i,j]. Return a[high], A[low] If (high-low>1) mid=(high-low+1)/2 // again the formula may be slightly changed. x1, y1=f(low, mid-1) x2, y2=f(mid, high) let x be the larges number among x1, x2, y1, y2 and y the second largest. return x, y }

f(low, high) { If (high-low1) mid=(high-low+1)/2 // again the formula may be slightly changed. x1, y1=f(low, mid-1) x2, y2=f(mid, high) add x1, x2, y1, y2 into an array S and remove nil if necessary. Sort s in decreasing order. Return S[0], S[1] © let g(n) be the number of comparisons required for any array of size n. g(n)=2*g(n/2)+c (c is a conastat, i.e., O(1) = 2{2g(n/2*2)+c}+c=22g(n/22)+2c+c =23g(n/23)+22c+2c+c …. =2kg(n/2k)+2k-1c+…2k-2c+…+c. When k=log n, g(n)=n*g(1)+2kc=O(n), where g(1)=O(1).

Question 6. (15 points) Consider the problem of scheduling n jobs of known durations t1,t2, ..., tn for execution by a single processor. All the n jobs arrive at the same time, i.e., time 0. The jobs can be executed in any order, one job at a time. Design a greedy algorithm to find a schedule that minimizes the total waiting time of the n jobs and prove that your algorithm is correct. The waiting time of a job is the time from 0 to the time when such a job starts. For example, suppose there are 3 jobs in total and t1=3, t2=1, t3=5. If we schedule the three jobs in the following order: job1, job2, job3, the waiting times for job1, job2 and job3 are 0, 3, 4, respectively. If we schedule the three jobs in the following order: job3, job2, job1, the waiting times for job3, job2 and job1 are 0, 5, 6.

If you cannot solve Question 6, solving Question 6a will give you 6 points instead of 15 points for Question 6. Question 6a. (6 points) Describe the greedy algorithm in the lecture to compute the optimal solution of the Interval Scheduling Problem. What is the running time of the algorithm? Prove that the algorithm is correct.

Solution: Algorithm: Sort all the jobs according to the durations in increasing order. Do all the jobs according to this order (shortest job first)

Proof: Let opt =j1, j2, …, jr, jr+1, …jn be an optimal solution and Gre=j1, j2,. …jr, j’r+1…j’n be the solution obtained by our greedy algorithm, where the first r choices of both solutions are in common and (r+1)th choices are different.

Without loss of generality, we assume that jq = j’r+1 (g>r+1). Then we can get a new solution opt’ from opt by swapping jr+1 and jq in opt.

opt’: j1, j2, …, jr jqjr+2…jq-1jr+1,jq+1, …jn

In opt’, the wait times for the green and blue jobs remain the same. (a) The waiting time of jq in opt’ is the same as that of jr+1 in opt and (b) The waiting times of jr+1…jq-1 in opt’ are not longer than their waiting time in opt since tq...