CSE 450 Exam 2

Suppose there is a set of n points each with the same x-coordinate. Obviously, this will cause the closest pair of points algorithm to fail. Since this is the case, what must be the smallest possible asymptotic time complexity required to find the closest pair of pints in this instance?

O(nlogn)

Why? 

• When all points share the same x-coordinate, the 2D closest pair problem becomes 1D on the y-values.

• Sorting the y-values takes O(nlog⁡n), which is the smallest possible asymptotic time unless you assume extra structure.

Suppose we introduce a modified version of the closest pair of points algorithm that maintains s single presorted vector of only y-coordinates. What will be the guaranteed asymptotic time complexity of this variant?

O(nlog²n)

Why: The modified version requires re-filtering the y-sorted array at each level, adding an extra log⁡n factor.

Determine whether the following statement is true or false and explain your reasoning: The divide-and-conquer approach can be applied to any problem that can be expressed as a linear recurrence relation.

False: If the recurrence relation produces subproblems that need to be recalculated over and over, the divide-and-conquer approach will fail.

Consider the following divide-and-conquer algorithm for checking whether an element e exists in a pre-sorted array A.

Divide A into two roughly equal sized subarrays A1,A2 at element e′. If e ≤ e′, recursively check to see if e is in A1​. Otherwise, recursively check to see if e is in A2. Return true if so, and false otherwise. The base case considers an array of size one, where it is trivial to check whether e is the singleton element.

Give the recurrence relation that describes the algorithm above in terms of the number n of elements in A. Assume T(n) = 1 when n = 1.

T(n) = T(n/2) + O(1)

We propose an integer multiplication algorithm that produces the result of multiplying integers a and b, where a and b are each represented by n bits. This algorithm produces its result by adding a to itself b times. What will be the asymptotic time complexity of this algorithm with respect to n?

O(n2ⁿ)

Why?

• The algorithm adds a to itself b times.

• Since b is an n-bit number, it can be up to 2ⁿ.

• Each addition takes O(n), so total time is O(n⋅2ⁿ).

Suppose Volker Strassen had somehow discovered a way to produce the product of two n by n matrices with only six real multiplications and an asymptotically quadratic number of addition and subtraction operations per recursive call to his algorithm. What would have been the asymptotic time complexity of his algorithm?

O(n^2.585)

Identify which of the following statements are true regarding Strassen’s fast matrix multiplication algorithm as applied to matrices of size n by n .

i.) Strassen’s algorithm is the fastest known algorithm for any type of matrix multiplication.

ii.) If n is not a power of 2, adding rows and columns of zero-entries until n is a power of 2 will allow the algorithm to run normally and produce the correct result.

ii. only 

Suppose we modify the combine step of the closest pair of points algorithm such that distance δ from dividing line L is updated immediately to δ’ whenever the distance between two points on either side of L is discovered to be less than δ.

In this sense, we allow the two-dimensional range about L wherein we compare points to assume multiple areas (getting smaller as δ becomes updated) during the same combine step for each recursive call.

Determine whether the following statement is true or false and explain your reasoning: The time complexity of the closest pair of points algorithm is guaranteed to be improved by constant factor.

False: If δ is reduced only after the last pair of points sorted by y-coordinate within δ of L is compared, then no additional benefit will be gained.

Identify the reason why the combine step of the closest pair of points algorithm can be solved in linear time.

The number of comparisons made between points within distance δ of dividing line L can be shown to be a constant.

We propose the following divide-and-conquer algorithm for solving the minimum spanning tree problem for a connected, weighted graph G = (V, E). Recursively, we divide the set of vertices in roughly half to obtain vertex sets V1, V2. We recursively compute the minimum spanning trees T1, T2 over V1 and V2, respectively. To combine the subproblems, we add the smallest edge such that T1, T2 now form a single component. What is the primary difficulty of achieving an efficient implementation under this framework?

The divide step: Partitioning the vertices in two equal-sized components such that each component is connected may require considering all vertex subsets of size n/2

Identify which of the following statements are true regarding the Karatsuba multiplication algorithm.

i.) The Karatsuba algorithm is asymptotically less complex than merge-sort with respect to the number of operations it requires to terminate.

ii.) Each call to this algorithm produces three additional recursive calls on roughly half the number of bits as the previous call.

ii. only

Why?

• Time complexity for Karatsuba multiplication is O(n^log₂3) = O(n^1.585), while merge-sort has a time-complexity of O(nlogn). Logn grows more slowly than any polynomial exponent.

Identify which of the following statements are true regarding the Karatsuba multiplication algorithm. Let n be the number of bits used to represent both the multiplicand and multiplier.

i.) Each recursive call to the algorithm will produce O(n^1.585) addition, subtraction and shift operations.

ii.) Each recursive call to the algorithm will produce four real multiplications

Neither of these are true

Why?

• The total time complexity is O(n^1.585), not per recursive call.

• The core idea of Karatsuba is to reduce the number of multiplications from 4 to 3 using a clever trick. So Karatsuba only performs 3 recursive multiplications, not 4.

Identify which of the following statements are true regarding Strassen’s fast matrix multiplication algorithm.

i.) Time required to form sub-matrices per recursive call is asymptotically quadratic.

ii.) For each recursive call, the size of the matrix being operated upon is 75% smaller than that of the previous call.

i. and ii.

Why?

• In Strassen's algorithm, each recursive call involves:

  • Dividing each matrix into four submatrices of size n/2 * n/2

  • Performing additions and subtractions of these submatrices

  • This results in O(n²) time for additions per recursive call.

• The naive method does 8 recursive multiplications for submatrices.

• Strassen does only 7 recursive multiplications, which results in a time complexity of approximately O(n^log₂7) ≈ O(n^2.81) instead of O(n³).

• This 7 instead of 8 multiplications gives roughly a 12.5% reduction per level, which translates to working with 75% of the total work (because 7 is ~87.5% of 8), hence the size of computation per level is effectively reduced by 25%.

Consider the following divide-and-conquer algorithm used to find the maximum element of an unsorted array A:

Divide A into two roughly equal parts A1​ and A2. Recursively find the maximum elements e1,e2 of their respective subarrays. Return max⁡(e1,e2).

Identify the asymptotic running time of the combine step in terms of the number n of elements in A.

O(1)

Sequential matrix-vector multiplication can be completed in O(n²) steps given an n by n matrix and a vector of length n. We introduce a recursive matrix-vector multiplication algorithm and we “Strassenize” it, i.e. we reduce the number of real multiplications per recursive call. Determine whether the following statement is true or false and explain your answer: This algorithm will accomplish matrix-vector multiplication in sub-quadratic time.

False: It will require Ω(n²) time just to read the values of the matrix.

Suppose we have a modified version of Merge-Sort that at each recursive level splits the array into two parts each of size ¼ and ¾ respectively. Also, assume the size of any given input array is a power of four. Give the asymptotic time complexity of this Merge-Sort variant.

O(nlogn)

Why is memoization useful for implementing the dynamic programming algorithm for the Weighted Interval Scheduling problem?

To avoid recomputing earlier, known results of M-compute-opt(j) at a later point.

For the Knapsack problem’s running time, which is O(nW), why is it not a polynomial time algorithm?

Because the size of W is logarithmic in the number of W itself. In other words, as W increases, the number of bits required to represent it grows, making the overall complexity exponential in terms of the input size.

The second case for the Knapsack problem for OPT(i, w) says that OPT(i, w) = OPT(i-1, w) if w_i > w. Why is this?

If the weight of the i-th item is larger than the current weight limit, then it cannot be inserted into the knapsack

Algorithmic Paradigms: Greedy

Build up a solution incrementally, myopically optimizing some local criterion.

Algorithmic Paradigms: Divide-and-Conquer

Break up a problem into disjoint sub-problems, solve each sub-problem independently, combine solution to sub-problems to form solution to original problem.

Algorithmic Paradigms: Dynamic Programming

Break up a problem into a series of overlapping sub-problems, and build up solutions to larger sub-problems.

Some famous dynamic programming algorithms:

• Viterbi for hidden Markov models

• Unix diff for comparing two files

• Smith-Waterman for sequence alignment

• Bellman-Ford for shortest path routing networks

• Cocke-Kasami-Younger for parsing context-free grammars

What is memoization?

Storing the results of each sub-problem in a cache and lookup as needed.

Why (informally) does the greedy algorithm for the unweighted interval scheduling problem seen in lecture fail for weighted interval scheduling, in general?

A job that finishes early with potentially low weight can be chosen, preventing other higher weight jobs of being selected by the algorithm

Which of the following is the sub-problem for Weighted Interval Scheduling’s dynamic programming algorithm?

The maximum of v_j + OPT(p(j)) and OPT(j-1)

In Case 1, which involves picking job j, the slide says that you cannot use the jobs p(j) + 1, …, j - 1. Why is this?

Because these jobs are incompatible with job j.

Which of the following is a sub-problem for the Shortest Path problem’s dynamic programming algorithm?

The minimum of OPT(i-1, v) and the minimum of OPT(i-1, w) + l_vw over all edges vw.

Given a graph G=(V,E) containing negative edge weights and a unique shortest path P, does increasing each edge weight by a constant factor such that all edge weights are positive (or zero) necessarily yield P when Dijkstra's algorithm is applied to it?

No. The total weights of paths containing more edges will vary more significantly than those with paths containing fewer edges.

Suppose that the weights are at most polynomial in the number of items given for the Knapsack problem. What can we say about the run-time of the dynamic programming algorithm for this problem?

It is polynomial-time.

Which of the following is a recursive call of the OPT(i, w) function for the dynamic programming algorithm for Knapsack?

The maximum of OPT(i-1, w) and v_i + OPT(i-1, w-w_i)

Which of the following explains why the Knapsack algorithm seen in lecture only runs in pseudo-polynomial time?

The size of W is the number of bits required to represent it, which is logarithmic in the value of Wand not the actual value itself, leading to a run-time dependent on the numerical value rather than just the number of items.

The principle of optimality states that the solution for the tail subproblem of any optimal solution is also optimal. Which of the following examples illustrates this concept best?

Suppose the shortest route R from Phoenix to Atlanta includes passing through Austin, Texas. Then the shortest route from Austin to Atlanta will be a sub-route of R.

Can the greedy algorithm from the unweighted version of Interval Scheduling ever work for some instances of the Weighted Interval Scheduling problem, and why/why not?

Yes, if all weights of jobs are equal.

Does the dynamic programming algorithm for Weighted Interval Scheduling always pick the job of highest weight? Why/Why not? (Assume all weights are distinct)

No, if this job is incompatible with all jobs.

What does OPT(i, v) mean in the context of the dynamic programming algorithm for the Shortest Path problem?

The length of the shortest v-t path using at most i edges

Which of the following is an informal description of OPT(i, w) for the Knapsack problem?

The maximum profit subset of items 1, …, i with weight limit w.

Why does memoization improve the exponential run-time of the original algorithm to be much faster (polynomial time)?

Because each possible sub-problem is only computed once, and there are polynomially many of them.

What does the dynamic programming algorithm for Weighted Interval Scheduling return as the final result?

The highest weight of a subset of jobs to pick.

If in the dynamic programming algorithm for Knapsack it discards item i at some point, does that mean that item i will never be chosen in the future, and why/why not?

No, calculating future subproblems that allow for more items in the knapsack may produce a solution that includes i.

What is a “negative-cost cycle” in the context of the Bellman-Ford algorithm?

A cycle in a graph where the sum of the edge weights is less than zero, allowing for infinitely decreasing path costs.

In other words, a cycle in a graph with total weight that is negative.

In the implementation of Bellman-Ford, what did the structure successor[i, v] represent?

A pointer to the next node on a shortest v-t path using using at most i edges.

What is the running time (in the worst case) of Bellman-Ford if there are n nodes and m edges?

O(mn)

Suppose Anatolii Karatsuba had somehow discovered a way to produce the product of two n-digit integers x and y with only two real multiplications of n/2 digit integers and an asymptotically linear on n number of adding, subtracting and shifting operations per recursive call to his algorithm. What would have been the asymptotic time complexity of his algorithm if x and y are each represented by n bits?  (Hint: Read the supplementary document about non-binary recursive trees carefully before answering.)

O(nlogn)