Final Exam Rubric

True/False 6pts each (48 pts total)

General grading instructions for T/F

• In general, (-4) points for correct true/false but no/irrelevant reasoning provided.
  • Possibly (-1) point if reasoning provided is really wrong.
• (-1 to -3) If student gets wrong T/F answer but shows some significant understanding
  • (-4) Same if student only shows some very basic understanding.

A. [True/False] 3SAT is an NP-complete problem. To show that some other problem Q is also NP-complete, it is sufficient to show that there is a polynomial time reduction from Q to 3SAT and that Q is in NP.

Example Solution:
False. A reduction from A to B shows that B is at least as hard as A. So to find new NP-Hard problems, we reduce a known NP-Complete problem to the candidate in order to show that the candidate problem must be at least as hard as any NP-Complete problem. Then to further show the candidate is NP-Complete, we'd show that it's also in NP.

Student Answers:

• (-2) If student based their answer on correct definitions of NP-Complete and polytime reduction, but thought it was true.
• (-4) If student answers wrong but showed some basic understanding about NP-Complete and polytime reductions.

B. [True/False] $2^{\log n} \in \mathcal{O}(n)$ for $n \geq 1$

Example Solution:
True. We stated that we would assume base 2 for all logs in the class unless otherwise noted. So, for example, $2^{\log_2 n} = n$. So, $2^{\log n} \in \mathcal{O}(n)$.
Answer can also be false if student considered a base less than 2. Recall that difference in log base is a constant factor difference. A constant factor exponent difference gives us a different asymptotic complexity!

Student Answers:

• (-0) If student answers False. If they considered that a log base $<2$ in the exponent will be worse than $\mathcal{O}(n)$.
• (-3) If student had some other reasonable but wrong idea for why they thought $2^{\log_2 n} = n$ grows faster than $C \cdot n$ for some $C$.

C. [True/False] Every connected weighted graph contains a unique minimum spanning tree.

Example Solution:
False. A graph may have multiple distinct minimum spanning tree. Answer needs to be a counterexample, so consider a complete graph with 3 vertices, A, B, and C and equal edge weights between them. A spanning tree for this graph contains 3 vertices and two edges. This graph contains 3 distinct minimum spanning trees, since there are 3 different spanning trees and they are all equally minimum. [A-B, B-C], [B-C, C-A], and [C-B, B-A].

Student Answers: Apparently a tough reading comprehension question. However, it is a question we answered in class and is in the posted week 8 notes.

• (-3) If student answers True. Two distinct graphs have two distinct (unique) minimum spanning trees. Some students didn't appear to understand what this question was asking and had trouble understanding the phrase 'contains a unique MST'. Instead they appear to have understood the question as asking whether two unique graphs can have unique MSTs. That's trivially a tautology and doesn't make a whole lot of sense as an exam question.
• (-3) If student answers True because every connected graph has a minimum spanning tree. Likely another misreading of "a unique MST".

D. [True/False] A graph with $v$ vertices and $e$ edges is represented by an adjacency list. A trivial lower bound for deciding if the graph is complete or fully connected is $\Omega(v + e)$.

Example Solution:
True. Trivially, for any graph, we'd need to look at each vertex and edge to determine if it's complete. A counting function to do this just needs to count the number of vertices and edges: if there are $\frac{v(v-1)}{2}$ nondirected edges, then the graph is complete.

Student Answers:

• (-2) If student answers false. In the best cases, where the tree is sparse, we wouldn't have to check all the vertices. e.g. find a vertex early that's not connected to all the other ones we can stop. While correct reasoning, this assumes best case and that's not the question.
• (-2) If student answers true, but gives an example without reasoning. A single example can't prove the general statement.

E. [True/False] NP-Hard problems are at least as hard as any problem in NP. An NP-hard problem cannot in general be reduced to 3SAT, which is NP-Complete.

Example Solution:
True. Given that NP-Hard problems are at least as hard as any problem in NP, it follows that NP-hard problems cannot generally be reduced to 3SAT, which is NP-complete. Some problems in NP-Hard can be reduced to 3SAT, i.e. any NP-complete problems can be reduced to any other NP-complete problems and NP-complete problems are also NP-Hard. However, this can't be generally done, and the key phrase here is 'in general'.

Student Answers:
(-2) If student answers false. Definition of NP-Hard is correct and correctly identifies that some NP-Hard problems can be reduced to 3SAT. However, this can't be done in general.

F. [True/False] A problem that can be solved by an algorithm whose running time is in $\mathcal{O}(n^{\log n})$ is intractable.

Example Solution:
False. Tractable problems are by definition solvable in polynomial-time (i.e. in class P). An algorithm that runs in O(n^(log n)) is not polynomial-time. However, that doesn't preclude the possibility that there is an algorithm that solves it in polynomial-time.

Student Answers:
Definition 1 in chapter 11.3 defines tractable problems as those in complexity class P, i.e. solvable in polynomial time. And intractable problems all problems not in P. In particular, we don't know whether problems in NP are tractable or not, since we don't know whether P=NP.

• (-0) If student answers true, but they can correctly explain why even if one algorithm to solve a problem runs in O(x) time, it doesn't follow just from this that there can't exist another algorithm that solves it faster.
• (-2) If student answers false, but they don't quite have the right definition for intractable.
• (-2) If student answers true, but have some idea of what complexity class the algorithm is in, i.e. worse than polytime.

G. [True/False] Any algorithm with a pair of nested loops has a complexity of $\mathcal{O}(n^2)$

Important to be careful about the reasoning for their answer.

Example Solution:
False. The inner loop could do more than constant work, for instance, which would result in worse than $\mathcal{O}(n^2)$ time.

For i in 1...n:
	For j in 1...n:
		insert(<i, j>) into list(A)  # where insert is O(n)-time operation.

Student Answers:

• (-2) If student answers false, but it's clear they mixed up $\mathcal{O}$ with $\Omega$, i.e. they mixed up upper bound with lower bound. We had the lower bound example in class and it's also on Dan's practice final. Checking to see if they are reading/thinking carefully.
• (-2) If student answers true because they thought straightforwardly that nested loops will get $\mathcal{O}(n^2)$ time.

H. [True/False] Dynamic programming and greedy algorithms both require the problems they solve to have optimal substructure.

Example Solution:
True. Dynamic programming and greedy algorithms both require that the problem has optimal substructure. This is because both strategies need to be able to take the optimal solutions to subproblems to generate optimal solutions to the whole problem.

Student Answers:

• (-3) If student answers incorrectly but shows understanding of the techniques, e.g., that one of these techniques requires optimal substructure.
• (-3) If student answers incorrectly but shows understanding of what optimal substructure is.

{Problem 2} (7 pts) If we define sparse graphs as graphs for which $|E| \in \mathcal{O}(|V|)$, which implementation of DFS will have a better time efficiency for such graphs, the one that uses an adjacency matrix or the one that uses an adjacency list? Explain your answer.

Example Solution:
The adjacency list will be more efficient. If a sparse graph has on the order of $|V|$ edges, then DFS with an adjacency list will have $\mathcal{O}(|V|)$ complexity. The efficiency of DFS depends on your graph representation, i.e. what data structure you need to traverse. For an adjacency list, the complexity is $\mathcal{O}(|V| + |E|)$ and if $|E| \in \mathcal{O}(|V|)$, then we get $\mathcal{O}(|V|)$ for searching a sparse adjacency list. On the other hand, an adjacency matrix is a $|V| \times |V|$ 2d array. To traverse this thing, even if the graph it represents is sparse, requires $\mathcal{O}(|V|^2)$ time.

Student Answers:

• (-2) to (-3) Depending on how clear it is that the student mixed up adjacency matrix with adjacency list. For example, if the student states that neighbors can be accessed in constant time for a sparse graph for an adjacency matrix since the linked list will be short. This indicates they probably have the two names mixed up, since that's the exact opposite of what happens to them.

• (-5) If student answered adjacency list but thought that DFS or BFS have different running times based on something other than the data structure that holds the graph, e.g. student thought that DFS is more efficient with adjacency lists but BFS is more efficient with an adjacency matrix.

{Problem 3} (8 pts) For the bottom-up dynamic programming algorithm for the knapsack problem, explain in detail why its time efficiency is $\mathcal{O}(nC)$.

Example Solution:
The bottom-up (or tabulation) dynamic programming algorithm for the knapsack problem stores the results of all subproblems in an $n \times W$ table. It must iterate through each field in the table to calculate all sub-results, so the efficiency is $\mathcal{O}(nW)$.

Student Answers:
Key idea to the answer is that the tabulation method requires setting up an $n \times W$ 2d array and must iterate through each index.

• (-1) to (-4) If student gets it wrong but shows understanding of the components of the bottom-up dynamic programming algorithm for the knapsack problem.

{Problem 4} (10 pts) Briefly describe the way Kruskal's algorithm constructs a minimum spanning tree and its asymptotic complexity.

Example Solution:
Kruskal's builds a minimum spanning tree by iterating through edges in nondecreasing order by weight. We begin with a forest of trees, where every vertex is a tree with just a root. With each edge considered, we add it if and only if the two vertexes of that edge are parts of different trees, making them part of the same tree. To decide if two vertices are part of the same tree, we use a union-find or disjoint set data structure. When all edges have been considered, the vertices along with edges we added constitute a MST.

Kruskal's runs in $\mathcal{O}(E \log E)$ time or equivalently $\mathcal{O}(E \log V)$ time, since $E$ is at most $V^2$ so $\log E < 2 \log V$. This is because we can sort the edges in $\mathcal{O}(E \log E)$ time, so considering an edge with min weight can operate in constant time. Deciding whether two vertices are part of the same tree requires $\mathcal{O}(V)$ operations total. Using a union-find or disjoint set data structure, we can do this in $\mathcal{O}(V \log V)$ time. So Kruskal's runs in $\mathcal{O}(E \log E)$ or the tighter bound $\mathcal{O}(E \log V)$ time.

Student Answers:

• 5 pts for describing Kruskal's correctly
  Key points:

  • Begin with a forest of trees, each with one node.
  • Iterate through edges, sorted in nondecreasing order.
  • Add edges unless the vertices are already part of the same tree (anti-cycle condition).

• 5 pts for describing the complexity correctly
  Key points:

  • Understand that sort is $\mathcal{O}(E \log E)$
  • Optionally understand that $E$ is at most $V^2$ so $\log E < 2 \log V$. Then we can get a tighter bound of $\mathcal{O}(E \log V)$
  • Understand that this dominates the other operations.
    • You can give them partial credit for showing understanding of the complexity of the other operations.

{Problem 4} (15 pts total) Consider the following algorithm:

def unknown(n):
	if n = 1:
		return 1
	else
		return unknown(floor(n/2)) + 1

a. (3 pts) What does this algorithm compute?

Example Solution:
It computes the number of digits in a binary representation of $n$, i.e. floor$(\log_2 n) + 1$

b. (3 pts) What's the basic operation for this algorithm?

Example Solution:
Floor, division, addition are all reasonable picks. Division or floor probably represent the most costly basic operations.

c. (3 pts) Is the best case different from the worst case?

Example Solution:
No, they are the same. The input is some number $n$ and there's no variance for a given input size.

d. (6 pts) Find the worst case asymptotic complexity for this algorithm?

Example Solution:
Solve $T(n) = T(\frac{n}{2}) + 1$, for $n>1$, where $T(1) = 0$. That ends up being $\mathcal{O}(\log n)$ or $\Theta(\log n)$. Rigorous proof, solving the recurrence relation using backward or forward substitution, or using the master theorem are good solutions, a good informal explanation for the asymptotic complexity is also acceptable.

Student Answers:

• Similar grading to the midterm algorithm and find complexity problems.

{Problem 5} (12 pts total) Greedy Job Scheduling

Consider the problem of scheduling n jobs of known durations $t_1, t_2, . . . , t_n$ for execution by a single processor. The jobs can be executed in any order, one job at a time. You want to find a schedule that minimizes the total time spent by all the jobs in the system. (The time spent by one job in the system is the sum of the time spent by this job in waiting plus the time
spent on its execution.)

a. (6 pts) Describe a greedy algorithm for this problem. (Primarily looking a greedy rule.)

Example Solution:
Sort them in nondecreasing order by their duration $t_i$, then schedule along this order. The greedy rule is to pick the shortest duration first. Idea is that if the shorter jobs are executed first, then later jobs wait less. So we want the minimize the time waiting. Notice that the total execution time for the $n$ jobs is the same no matter the order. But the amount of time that each job waits to be executed is not.

Student Answers:

• (-3) If student thought that order doesn't matter, with evidence that they misunderstood how to calculate total time spent by all jobs in the system, i.e. the parenthetical tells them how to calculate total time.
• (-2 to -3) If student gets the greedy rule right, but has incorrect reasoning.

b. (6 pts) Does the greedy algorithm always yield an optimal solution? Explain.

Example Solution:
Yes, it's optimal. Optimal in this case refers to the total time spent executing jobs in addition to each job's time waiting to be executed. So picking the shortest duration jobs first means that other jobs wait less before they get executed. That will minimize the total amount of time in execution and waiting.

Student Answers:

• (-0) If student thought that order didn't matter in part a, then any order will be optimal.
• (-2 to -3) If the student had some wrong but reasonable explanation for why it's not optimal, e.g. perhaps it's clear they misunderstood the question.