Approximate overview
Dictionary or Map?Will there be regular readings?
The goal is that you do the readings on a topic after we cover the topic.
Can you work through the in-place swapping for question 1?
I can try. We need an array. Here goes.
0 1 2 3 4 5 6 7 8 9 10
+---+---+---+---+---+---+---+---+---+---+---+
| B | G | C | C | E | Z | D | A | Q | C | A |
+---+---+---+---+---+---+---+---+---+---+---+
There are two ways to rearrange the array. We can split it into two parts (<= pivot; > pivot) or into three parts (< pivot, = pivot, pivot).
The assignment asks for the second.
I need a model of the array. I have four parts (ignoring the pivot). The stuff < pivot, the stuff equal to the pivot, the stuff > pivot, the stuff I haven’t looked at yet.
s e i l
| smaller | equal | unknown | larger
+---+---+---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+
I need names for all of those.
smarks the start of the values I know are smaller,emarks the start of the values I know are equal,imarks the start of the unprocessed values,lmarks the start of the values I know are larger.
Initially, we’re going to put the pivot at the beginning of the array (or subarray). We’ll need to swap it to the correct place later.
0 1 2 3 4 5 6 7 8 9 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | G | C | C | E | Z | D | A | Q | B | A |
+---+---+---+---+---+---+---+---+---+---+---+
Let’s initialize all of our variables.
s,e,i l
0 | 1 2 3 4 5 6 7 8 9 10|
+---+---+---+---+---+---+---+---+---+---+---+
| C | G | C | C | E | Z | D | A | Q | B | A |
+---+---+---+---+---+---+---+---+---+---+---+
Key idea is to look at each value in turn, swapping things around as necessary, and maintaining those three barriers.
iwill allow us to do that.
Look at the thing at position
i. It’sG
It’s greater than the pivot (
C).
So we want to put it at the end. We swap A and G.
And we can reducel
s,e,i l
0 | 1 2 3 4 5 6 7 8 9 | 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | A | C | C | E | Z | D | A | Q | B | G |
+---+---+---+---+---+---+---+---+---+---+---+
We look at the thing at position
iagain. We see anA, which is smaller than the pivot. We incrementeandi.
s e,i l
0 | 1 | 2 3 4 5 6 7 8 9 | 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | A | C | C | E | Z | D | A | Q | B | G |
+---+---+---+---+---+---+---+---+---+---+---+
We look at the thing at position
iagain. We see aC, which is equal to the pivot. We incrementiby one.
s e i l
0 | 1 | 2 | 3 4 5 6 7 8 9 | 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | A | C | C | E | Z | D | A | Q | B | G |
+---+---+---+---+---+---+---+---+---+---+---+
The next thing is C, so we do the same thing again (i.e., increment
i).
s e i l
0 | 1 | 2 3 | 4 5 6 7 8 9 | 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | A | C | C | E | Z | D | A | Q | B | G |
+---+---+---+---+---+---+---+---+---+---+---+
The next thing is
E, which is larger. Swap to the end and decrementl.
s e i l
0 | 1 | 2 3 | 4 5 6 7 8 | 9 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | A | C | C | B | Z | D | A | Q | E | G |
+---+---+---+---+---+---+---+---+---+---+---+
The next thing is
B. This looks hard. What should we do to maintain all of our goals. Swap with the first C and increment e. Also increment i, since we know that we have an equal thing at position i.
s e i l
0 | 1 2 | 3 4 | 5 6 7 8 | 9 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | A | B | C | C | Z | D | A | Q | E | G |
+---+---+---+---+---+---+---+---+---+---+---+
The next thing is
Zwhich is large. Swap into position 8 and decrementl.swap (i, --l);in C.
s e i l
0 | 1 2 | 3 4 | 5 6 7 | 8 9 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | A | B | C | C | Q | D | A | Z | E | G |
+---+---+---+---+---+---+---+---+---+---+---+
The next thing is
Q, which is also large. Swap
s e i l
0 | 1 2 | 3 4 | 5 6 | 8 9 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | A | B | C | C | A | D | Q | Z | E | G |
+---+---+---+---+---+---+---+---+---+---+---+
The next thing is
A, which is small. Swap positioniwith positioneand then increment e and i.swap(e++, i++);
s e i l
0 | 1 2 3 | 4 5 | 6 | 7 8 9 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | A | B | A | C | C | D | Q | Z | E | G |
+---+---+---+---+---+---+---+---+---+---+---+
The next thing is
D, which is large. Decrementland swap withi
s e i,l
0 | 1 2 3 | 4 5 | 6 7 8 9 10
+---+---+---+---+---+---+---+---+---+---+---+
| C | A | B | A | C | C | D | Q | Z | E | G |
+---+---+---+---+---+---+---+---+---+---+---+
There are no unknown/unprocessed elements left. We’re almost done. Swap the thing at position 0 with the thing at position e-1 and decrement both s and e.
swap(--s, --e).
s e i,l
| 0 1 2 | 3 4 5 | 6 7 8 9 10
+---+---+---+---+---+---+---+---+---+---+---+
| A | A | B | C | C | C | D | Q | Z | E | G |
+---+---+---+---+---+---+---+---+---+---+---+
Now we’re ready for the next step.
Congratulations, you’ve now solved the Dutch National Flag problem.
Your goal is to turn that algorithm into code.
While you are used to loop counting for iterative algorithms, recursive algorithms generally require a different strategy.
We define a function, T(n), that represents the running time on inputs of size n. (We might also define M(n) for the memory usage, although that’s usually not as complicated to determine.)
We write a recursive formulation of T(n) based on the behavior of the algorithm. For examples, I might say that because merge sort requires two recursive calls on half the size plus about n work to merge, T(n) <= 2*T(n/2) + n. I also know that T(1) = 1. Does it matter whether we use n or cn? We’ll see.
We attempt to convert that relation to a “fixed form” that does not involve recursion. There are many ways to do so.
Some common (or otherwise interesting) recurrence relations, not necessarily in order.
There are five main techniques people use when they encounter a recurrence relation.
We’ll look at the first three today and the last one next class.
Is there a pattern?
Pattern: T(n) is (2^k)*T(n/(2^k)) + kn
Let 2^k = n (k = log2n)
Pattern: T(n) is n*T(1) + (log2n)n
We know T(1) is 1
So T(n) is n + n(log2n) which is in O(nlog2n)
See whiteboard.
In this case, there are log2(n) levels in the tree, each of which has a cost of n, so we can see that it’s O(nlog2n).
Do we have to prove our results?
We could, probably using induction.
But we won’t. I care more that you can do the informal analysis.
You will be divided into four groups. Each group will try a different strategy on each problem. You can assume T(1) = 1 unless it’s more convenient to assume T(1) = c or T(0) = c.