Standard 5: Divide and Conquer 2: Algorithms

Short description: Construct and execute D&C algorithms; give counterexamples for incorrect algorithms.

Relevant notes: Topic B: Divide and Conquer.

Full description

Construct Divide and Conquer algorithms for problems related to those studied in class; briefly justify correctness. Execute Divide and Conquer algorithms on example inputs. Give counterexamples for incorrect Divide and Conquer algorithms and explain the reason for failure.

Example problem 1

Part a.

Prove that the following sorting algorithm is incorrect using a counterexample.


// Try to Mergesort
1 try_to_mergesort(A):
2     if len(A) <= 1:
3         return A
4     let i = int(len(A)/2)
5     let B = try_to_mergesort(A[0:i])
6     let C = try_to_mergesort(A[i+1:end])
7     return (B,C)                    // list B followed by list C

Part b. Prove that the following sorting algorithm is incorrect using a counterexample. Here merge is the same subroutine from the original mergesort algorithm.


// Try Harder to Mergesort
1 try_harder_to_mergesort(A):
2     if len(A) <= 1:
3         return A
4     let i = int(len(A)/2)
5     let B = try_harder_to_mergesort(A[0:i])
6     let C = A[i+1:end]
7     return merge(B,C)

Sample solution

Part a.

Consider the input A = [8,3]. We claim that the algorithm outputs [8,3], which is not sorted, so it is an incorrect output.

On input A = [8,3], the algorithm first splits [8] and [3] and recursively calls itself on each, resulting in B = [8] and C = [3]. It then concatenates them together, resulting in B followed by C, which is [8,3].

Part b.

Consider the input A = [1,2,4,3]. We claim the output will be [1,2,4,3], which is not correctly sorted.

First, the algorithm divides A into [1,2] and [4,3]. Then, it recursively calls itself on B, which we can check will return B = [1,2]. Then it will merge B = [1,2] and C = [4,3]. Recalling how merge works, it will start from the beginning of each array and take the smaller element, so it will produce [1,2,4,3].

Rubric

Rubric.

Both parts of the problem must be passed successfully for the problem to be a pass.

To pass, a solution must follow the course requirements for writing and proofs.

For both parts, the counterexample must be correct, i.e. an input where the algorithm produces an incorrect output. The counterexample must be small and the reasoning must be easy to follow. If the counterexample is very large and takes a lot of time and effort to verify, then even if it is ultimately correct, the solution will not pass. The explanation must be clear. It may briefly summarize parts of the algorithm, but should not skip major steps or hand-wave the algorithm's behavior.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): small, correct example; perfectly clear, no mistakes, all steps of solution included, no excess writing.
3 (Pass, Proficient): small, correct examples; clear, easy to follow, little to no excess writing, very little skipped or handwaved.
2 (Fail, Progress): may give an example that is too large or too difficult to verify. May give an explanation that is difficult to follow or lacks enough detail or precision to follow. May give too much unrelated information or commentary that does not directly relate to the behavior of the algorithm on the specific example.
1 (Fail, Wrong Track): May not give any concrete example, only discussing the issues with the algorithm at a high level.

Example problem 2

Part a. How many times does this function print "Hello, World"? You may suppose $n$ is a power of 4. Briefly show your work. Hint: you may want to draw a tree.


1 printer(n):
2     print("Hello, World")
3     if n <= 1:
4         return
5     printer(n/4)
6     printer(n/4)

Part b. What is the full output of this function on the input "Algo"? Briefly justify your answer.


1 printer2(s):       // s is a string
2     let n = len(s)
3     print s[0]     // print the first character of s
4     if n <= 1:
5       return
6     printer2(s[0:n/2 - 1])
7     printer2(s[n/2:end])

Sample solution

Part a.

Let $n = 4^k = (2^{k})^2$. If we draw the call tree, then at level 0, there is one node; at level $1$, there are two nodes; at level $2$, there are four nodes, etc. So at each level $t=0,\dots,k$ there are $2^t$ nodes. Every node prints "Hello, World" once. So the answer is:

\begin{align*} \sum_{t=0}^k 2^t &= 2^{k+1} \\ &= 2(2^k) \\ &= 2\sqrt{n} . \end{align*}

Part b.

First, we call printer2("Algo") and print "A" before recursively calling printer2("Al") and printer2("go"). The call to printer2("Al") first prints "A", then calls printer2("A") and printer2("l"). The call to printer2("go") first prints "g", then calls printer2("g") and printer2("o"). Putting it all together:

Input	prints
Algo	A
Al	A
A	A
l	l
go	g
g	g
o	o

Rubric

Rubric.

Both parts of the problem must be passed successfully for the problem to be a pass.

To pass, a solution must follow the course requirements for writing and proofs.

Part a. To pass, the answer must be at least $O(\sqrt{n})$ if not the exact answer. It must give correct reasoning for arriving at the solution, presumably a tree-based argument.

Part b. To pass, the output must be fully correct and the reasoning and description must be clear. However, the reasoning can be brief.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): Eactly correct on both parts; perfectly clear, no arithmetic mistakes, all steps of solution included, no excess writing.
3 (Pass, Proficient): Part a correct up to big-O and includes a clear, brief argument. Part b perfectly correct and briefly, clearly explained.
2 (Fail, Progress): may get the wrong answer for Part a or not clearly describe the steps. May not get Part b correct, or may not briefly explain the steps for Part b. May contain excess irrelevant writing.
1 (Fail, Wrong Track): May not use a correct approach to Part a such as the tree method. May appear to misunderstand the algorithm in Part b.