ECS 122A Midterm 2 Solutions
Question 1 [0 pt]
What is the current time including seconds, add the digits together i.e. 3:14 21 secs pm sum = 3 + 1 + 4 + 2 + 1 = 11
Take the number above % 3 + 2, let that be y. What is your y?
We will use y = 3 throughout the solutions. Question 2 [40 pts]
Generate a random array indexed 1 to 4 with 4 integers using https://www.google.com/search? q=random+number between 10y and 30y.
What is your array?
A = [33, 52, 78, 57]
Let the array above be the pricing array p[i]= price for selling rod of length i rod cutting problem.
Part 1 [10 pts]
Find the optimal solution using the dynamic rod-cutting algorithm from class on paper (do not code it), keeping track of both r[i] and s[i].
Solution:
//Initialize r and s, then set r[0] to 0
r = [−1,−1,−1,−1,−1] and s = [−1,−1,−1,−1,−1] r = [0,−1,−1,−1,−1] and s = [−1,−1,−1,−1,−1]
j=1
q = −∞
i=1
− ∞ < 33 + 0 ? Yes
q = 33
s = [−1, 1, −1, −1, −1] r = [0, 33, −1, −1, −1]
j=2
q = −∞
i=1
− ∞ < 33 + 33 ? Yes
q = 66
s = [−1,1,1,−1,−1]
i=2
66 < 52 + 0 ? No
r = [0, 33, 66, −1, −1]
1
j=3
q = −∞
i=1
− ∞ < 33 + 66 ? Yes
q = 99
s = [−1,1,1,1,−1]
i=2
99 < 52 + 33 ? No
i=3
99 < 78 + 0 ? No
r = [0, 33, 66, 99, −1] j=4
q = −∞ i=1
− ∞ < 33 + 99 ? Yes q = 132
s = [−1,1,1,1,1]
i=2
132 < 52 + 66 ? No
i=3
132 < 78 + 33 ? No
i=4
132 < 57 + 0 ? No
r = [0, 33, 66, 99, 132] Final arrays for r and s r = [0, 33, 66, 99, 132]
s = [−1,1,1,1,1]
Part 2 [30 pts]
In the homework “printing neatly problem” assume we are required that every line must have an even number of words (you may assume n is divisible by 2 otherwise there is no solution).
(a). Create a recurrence for the optimal solution.
Solution: Let c(i, j) denote the cost of printing word i to word j in a single line. Since we require that every line must have an even number of words, j − i has to be odd, otherwise, there’s no solution. Thus,
∞ if (j − i) ≡ 0
∞ if(j−i)≡1andM−j+i−jk=ilk <0 c(i,j)= j
0 if(j−i)≡1andM−j+i− k=ilk ≥0andj=n (M − j + i − jk=i lk)3 otherwise
(mod 2).
2
The recurrence for the optimal solution is as follows: 0
s(j) = ∞
min0≤i
c[i][j] = 0
else
c[i][j] = (M – j + 1 – sum(l[i…j]))^3
Create an array of length (n+1) s[] s[0] = 0
forj=1:n
if j%2 == 1
return Infty
else
s[j] = min_{0 <= i < j} (s[i] + c[i+1][j])
return s[n]
The pseudocode above should be self-explanatory. Line 3-13 will take O(n2) time while Line 16-20 takes O(n) time. Therefore, the overall time complexity is O(n2). Note that the cost of sum() and min() may vary depending upon how we implement them, we assume that both are done in constant time.
(c). Prove the greedy approach would not work for the original printing neatly problem.
Solution: A greedy approach would always try to put the words on the same line if it has space. We will use the example of ”Eating pie makes me want turkey” and M = 10 to show that a greedy approach would not work for the original printing neatly problem.
A greedy approach would have the solution of
Eating pie
makes me
want
turkey
Thiswillresultinacostof03+23+63 =224. A dynamic approach would have a solution of
3
Eating
pie makes
me want
turkey
This will result in a cost of 43 + 13 + 33 = 92 and since 224 > 92, the greedy approach would not yield and optimal solution the the printing neatly problem.
4
Question 3 [15 pts]
Suppose you are a cable guy and are sent out for jobs to complete in a single day. Given job ji each has a start time si and finish time fi. Your goal is to complete the most number of jobs assigned. The only requirement is you are allowed to start a job at the exact moment another one finishes, but no jobs may overlap. We prove this algorithm is optimal. Note all you need to do is prove the suboptimality property of this algorithm because in quiz 4 you already proved the greedy choice. So just suboptimality proof, please.
Solution: Let J be the set of jobs assigned and OPT ⊆ J be the optimal set of jobs such that the number of jobs in OPT is maximal and all jobs oi ∈ OPT are compatible. OPT = {o1, o2, o3, …, ok}.
Prove A = OPT − {oi} is optimal for Joi = J− (all activities not compatible with oi).
Proof. Assume for contradiction that A is not optimal for Joi. =⇒ ∃ an optimal solution B for Joi
=⇒ |B|>|A|
=⇒ |B+{oi}|>|A+{oi}|
Contradiction with the given that OPT is optimal. =⇒ A is optimal for Joi
∴ Optimal substructure property holds.
5
Question 4 [20 pts]
Create a random 3 by 3 matrix containing 0 or 1 values. To make this easy you may use this tool:
https://catonmat.net/tools/generate-random-matrices
Assume this matrix represents the adjacency matrix for vertices A, B, C. What is your adjacency matrix?
A B C A 1 1 0 B 1 1 0 C101
(a). draw the graph represented by the adjacency matrix above.
AB
C
(b). create the adjacency list for the matrix above.
→ → →
(c). What is the asymptotic run-time for answering the following question in both adjacency matrix vs. adjacency list representation. How many vertices are adjacent to vertex C? Explain your answer
Solution: Θ(|V |) for adjacency matrix and O(|V |) for adjacency list. Using an adjacency matrix, finding vertices adjacent to vertex C will loop through every value in the row for C, which is all vertices in the graph, thus Θ(|V |). (Then by definition O(|V |) is acceptable as well.) Using an adjacency list, you will iterate only over values that are adjacent to C, which is Θ(|Adj[u]|). We consider then as C becomes more connected (i.e. as the graph gets denser) the number of vertices adjacent to C can be up to |V | vertices, thus O(|V |)
(d). Which representation is better for a sparse graph given you ask question (c) often. Explain your answer.
A
B
A
A
B
B
A
C
C
6
Solution: The adjacency list representation is better for a sparse graph if (c) is asked often. An adjacency list will only have to loop through all adjacent vertices of C, which will be close to minimal in size, while an adjacency matrix will have to loop through all vertices regardless of if they are adjacent to C or not.
7
Question 5 [15 pts]
Please provide the runtime and explanation for the run-time of the pseudocode below. Given boo(n)=Θ(n2) Given funds and pricing are arrays.
Assume funds[0]=0 and array pricing is given prior.
for (j = 1 to n)
funds[j]= Solution:
mini∈[1..j /2] {funds[j-i]+pricing[i]+boo(j)}
n j/2
T (n) = (Θ(1) + Θ(1) + Θ(n2 ))
j=1 i=1
2n j
(1 + 2 + · · · + 2 ) n (1 + j ) j
= n
=n2 22
j=1
2
j=1
n 2 n j 2 j
= 2
= 2 (4(1 +2 +···+n )+ 2(1+2+···+n))
(4 +2) n2122 21
j=1
= O(n4) Remark: You may take this for granted:
n
i2 = 12 + 22 + · · · + n2 i=1
= n(n+1)(2n+1), 6
Which can be proved by mathematical induction.
8