2.Getting Started
Check list for learning algorithm
- Idea.
- Pseudocode.
- Argue that it is correctly works.
- Analyze its running time.
Problem
- Input: A sequence of n elements $ A = < a_{1}, a_{2}, ... ,a_{n} > $.
- Output: The permutation(reordering) $ A = < a_{1}^{\prime},a_{2}^{\prime},...,a_{n}^{\prime} > $ of the input sequence such that satisfies $ a_{1}^{\prime} \le a_{2}^{\prime} \le ... \le a_{n}^{\prime} $.
Insertion sort
Idea
- Idea: incremental approach.
- increment sorted array.
- insert current item into the sorted array A[1..j - 1]
- HowTo:
- Start from sorted length 1 array.
- Until conditions meet - i > 0 and A[i] > key
- Move i to one step back.
- Decrease i.
- Insert current item in A[i + 1]
Pseudocode
Pursue clean and concise
INSERATION-SORT(A)
1 for j = 2 to A.length
2 key = A[j]
3 // Insert A[j] into the sorted sequence A[1..j - 1]
4 i = j - 1
5 while i > 0 and A[i] > key
6 A[i + 1] = A[i]
7 i = i - 1
8 A[i + 1] = key
Tip
- Use "i" as a important loop variable name.
- Use simple condition first when there is logical concatenation.
- Use left as variable and right as almost constant value when compare two numbers.
- Make it simple as possible
Argue that it is correctly works
Guess
- I will use loop invariants.
- It keeps from start to terminate.
- I'll claim sub-array is always sorted.
loop invariant:
The sub-array A[1..j-1] consists of the elements originally in A[1..j-1], but in sorted order.
It is similarity to the mathematical induction. We say an algorithm has true loop invariant on some properties.
When the three properties hold, the loop invariant is true.
- Initialization: It is true prior to the first iteration of the loop.
- Maintenance: If it is true before an iteration of the loop,it remains true before the next iteration.
- Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
Initialization
When j = 2, The subarray A[1..j-1] consists of just one element A[1], which is in fact the original element in A[1]. Moreover, the subarray is sorted(trivially, of course).
Maintenance
The body of for loop works by moving A[j-1], A[j-2], A[j-3], and so on by one position to the right until it finds the proper position for Aj, at which point it inserts the value of aj. The subarray A[1..j] then consists of the elements originally in A[1..j],but it sorted order. Incrementing j for the next iteration of the for loop then preserve the loop invariant.
Termination
The condition causing the for loop to terminate is that j > A.length = n. Because each loop iteration increase j by 1, we must have j = n + 1 at that time. Substituting n + 1 for j in the wording of loop invariant, we have that the subarray A[1..n] consists of the element originally in A[1..n], but in sorted order.
Pseudocode conventions
- We use the keyword to when a for loop increments its loop counter.
- We use the keyword downto when a for loop decrements its loop counter.
- When the loop counter changes by an amount greater then 1, the amount of change follows the optional keyword by.
- We shall not use global variables without explicit indication.
- The notation .. is used to indicate a range of values within an arrary. Thus, A[1..j] indicates the subarray of A consisting of the j elements A[1],A[2],...,A[j].
- We organize compound date into objects, which are composed of attributes.
- We treat a variable represent arrary and object as a point to the date representing the arrary or object. For all attributes f of an object x, setting y = x causes y.f to equal x.f. Moreover, if we now set x.f = 3, then afterward not only dose x.f equal 3, but y.f equals 3 as well. In other words, x and y point to same object after the assignment y = x.
- We pass parameter to a procedure by value. When object passed, the pointer to the data representing object is copied.
- We allow multiple values to be returned by a single return statement.
- The boolean operators "and" and "or" are short circuiting.
Exercise
2.1-1
Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the Arrary A = <31, 41, 59, 26, 41. 58>
2.1-2
Rewrite the Insertion-sort procedure to sort into nonincreasing instead of nondescreasing.
INSERATION-SORT(A)
For j = 2 to A.length
key = A[j]
i = j - 1
while i > 0 and A[i] < Key
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key
2.1-3
Consider the searching problem: - Input: A sequence of n numbers $ A = < a_{1}, a_{2},...,a_{n} > $ and a value v. - Output: An index i such that v = A[i] or the special value NIL if v dose not appear in A.
Write pseudocode for linear search, which scan trough the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
pseudocode
LINEAR-SEARCH(A, v)
i = NIL
For j = 1 to A.length
if A[j] == v
i = j
loop invariants
i is NIL or 1 <= i <= A.length. If A[j] == v then i = j.
Initialization: i is NIL. Before prior iteration. Maintenance: When j increase loop invariants hold before iteration and remain true before next iteration. Termination: When the loop terminate it give us a solution that is true.
2.1-4
Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of two integers should be stored in binary form in an (n+1)-element arrary C. State the problem formally and write pseudocode for adding two integers
- Input: A and B are n-bit binary integers, stored in two n-element arrary A and B. (A,B[i] = 0, 1)
- Output: C are n+1 bit binary integer, stored in (n+1) element arrary.
ADD(A, B)
carry = 0
For A.length downto 1
sum = A[i] + B[i] + carry
C[i + 1] = sum % 2
carry = sum / 2
C[1] = carry
Analyzing Algorithms
- Predicting the resources that the algorithm required.
- We want to the performance measure of an algorithms to find best solution with machine-independent.
Measuring Resources
- Computational time
- Memory
- Communication Bandwidth
Model of implementation
- A generic one processor.
- random-access machine(RAM): instructions are executed one after another, with no concurrent operations.
- We assume our RAM is almost identical with real machine. (also computational time of instructions.)
Analysis of insertion sort
Running time of a program as a function of the size of its input. $$ f(\text{size of input}) = \text{Running time}$$ - input size: depends on the problem being studied. We shall indicate which input size measures is being used with each problem we study. - running time: the number of primitive steps or operations executed. It is convenient to define the notion of step so it is as machine-independent as possible. - We shall assume that each execution of the $i$th line takes time $c_{i}$, where $c_{i}$ is a constant. - We let $t_{j}$ denote the number of times the while loop test in line 5 is executed for that value of j.
INSERATION-SORT(A) cost times
1 for j = 2 to A.length c1 n
2 key = A[j] c2 n-1
3 // ... 0 n-1
4 i = j - 1 c4 n-1
5 while i > 0 and A[i] > key c5 \sum_{j=2}^{n} t_{j}
6 A[i + 1] = A[i] c6 \sum_{j=2}^{n} (t_{j} - 1)
7 i = i - 1 c7 \sum_{j=2}^{n} (t_{j} - 1)
8 A[i + 1] = key c8 n-1
The running time of algorithm is the sum of running time for each statement executed; $$ T(N) = c_{1}n + c_{2}(n-1) + c_{4}(n-1) + c_{5}\sum_{j=2}^{n} t_{j} + c_{6}\sum_{j=2}^{n} (t_{j} - 1) + c_{7}\sum_{j=2}^{n} (t_{j} - 1) + c_{8}(n-1)$$ The best occurs if the array is already sorted.
$$ \begin{align} T(N) & = c_{1}n + c_{2}(n-1) + c_{4}(n-1) + c_{5}(n-1) + c_{8}(n-1) \\ & = (c_{1} + c_{2} + c_{4} + c_{5} + c_{8})n - (c_{2} + c_{4} + c_{5} + c_{8}) \\ & = an + b \end{align} $$
It is thus a liner function of n. The worst occur if the array is in reversed order. We must compare each element A[j] with each element in the entire sorted subarray $A[1..j-1]$ and so $t_{j}$ for $ j = 2, 3, .., n$ $$ t_{1},..t_{j} = 2,..,n $$
Summation $$ \begin{align} 1 + 2 + ... + n & = \sum_{k=1}^{n} k \\ & = \frac{1}{2}n(n+1) \\ \end{align} $$
Apply to above equations
start from 2 not from 1 $$ \sum_{j=2}^{n}t_{j} = \sum_{j=2}^{n}j = \frac{n(n+1)}{2} - 1$$ 1 + 2 = 3, (1 - 1) + (2 - 1) = 1, because 1 - 1 = 0 we don't need to subtract 1. $$ \sum_{j=2}^{n}(t_{j} - 1) = \sum_{j=2}^{n}(j - 1) = \frac{n(n-1)}{2}$$
$$ \begin{align} T(N) & = c_{1}n + c_{2}(n-1) + c_{4}(n-1) + c_{5}\Biggl( \frac{n(n+1)}{2} - 1 \Biggr) + c_{6}\Biggl( \frac{n(n-1)}{2} \Biggr) + c_{7}\Biggl( \frac{n(n-1)}{2} \Biggr)+ c_{8}(n-1) \\ & = \biggl(\frac{c_{5}}{2} + \frac{c_{6}}{2} + \frac{c_{7}}{2}\biggr)n^{2} + \biggl( c_{1} + c_{2} + c_{4} + \frac{c_{5}}{2} - \frac{c_{6}}{2} - \frac{c_{7}}{2} + c_{8}\biggr)n - (c_{2} + c_{4} + c_{5} + c_{8}) \\ & = an^{2} + bn + c \end{align} $$
It is a quadratic function of n $an^{2} + bn + c$
Worst-case and average-case analysis
Worst-case is the longest time for any input of size n. - It provide guarantee that the algorithm will never take any longer. - The worst case occurs fairly open - The "average case" is often roughly as bad as the worst case.
Order of growth
We use some simplifying abstractions to ease our analysis of the algorithm running time. - Ignore the actual costs of each statement.(e.g. $c_{i}$) - Ignore the abstract costs of $c_{i}$s (e.g. a, b, c in $an^{2} + bn + c$) - Rate of growth or order of growth is considering only the leading term of a formula (e.g. $an^{2}$) $$\Theta(n^{2}) = \text{theta of n-squred}$$
- We usually consider one algorithm to be more efficient than another if its worst-case learning time has a lower order of growth.
Exercises
2.2-1
Express the function $n^{3}/1000 - 100n^{2} - 100n + 3$ in terms of $\Theta-notation.$ $$\Theta(n^{3})$$
2.2-2
Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[i]. Then find the second smallest element of A, and exchange it with the element in A[2]. Continue in this manner for the first $n-1$ element of A.
Generalize problem.
- Input: Sequence of n elements $A = < a_{1}, a_{2}, ... , a_{n} >$
- Output: Permutation (ordered) $A = < a_{1}^{\prime},a_{2}^{\prime},...,a_{n}^{\prime} >$ of the input sequence such that satisfies $ a_{1}^{\prime} \le a_{2}^{\prime} \le ... \le a_{n}^{\prime} $.
Write pseudocode for this algorithm, which is known as selection sort.
SELECTION-SORT(A)
n = A.length
For j = 1 to n - 1
smallest = j
for i = j + 1 to n
if A[i] < A[smallest]
smallest = i
exchange A[j] with A[smallest]
# temp = A[j]
# A[j] = A[smallest]
# A[smallest] = temp
What loop invariant dose this algorithm maintain?
Loop Invariant:
The sub-array A[1..j] consists of the elements originally in A[1..j]. But in sorted order.
Initialization:
- It is true prior to the first iteration of the loop.
- When j = 1, The subarray A[1..j] consists of just 1 element A[1], which is in fact originally element in A[1]. Moreover the subarray is sorted(trivially of course).
maintenance:
- It is true before an iteration, it remains true before the next iteration.
- Before an iteration A[1..j - 1] is in sorted order. In iteration we insert minimum value to A[j], A[1..j] will remains sorted order. Incrementing j for the next iteration of the for loop then preserve the order.
termination:
- When the loop terminate, the invariant give us a useful property that helps show that the algorithm is correct. The condition causing that the loop terminate is that j > A.length = n. Because each loop iteration increase j by 1, we must have j = n + 1 at that time. Substituting n + 1 for j in the wording of loop invariant, we have that the sub-array A[1..n] consists of elements originally in A[1..n], but in sorted order.
Why dose it need to run for only the first n - 1 elements, rather than for all n elements?
The subarray A[1..j-1] consists of the smallest elements 1-n elements, and therefore element A[n] must be the largest element.
Give the best-case and worst case running times of selection sort in $\Theta-$notation.
SELECTION-SORT(A) | cost | time
1 n = A.length | c1 | 1
2 For j = 1 to n - 1 | c2 | n
3 smallest = j | c3 | n-1
4 for i = j + 1 to n | c4 | \sum_{j=1}^{n} t_{j}
5 if A[i] < A[smallest] | c5 | \sum_{j=1}^{n} (t_{j} - 1)
6 smallest = i | c6 | \sum_{j=1}^{n} (t_{j} - 1)
7 exchange A[j] with A[smallest] | c7 | n-1
8 # temp = A[j]
9 # A[j] = A[smallest]
10 # A[smallest] = temp
Best case & worst case is same
$$ \begin{align} T(n) & = c_{1} + c_{2}n + c_{3}(n-1) + c_{4}\Biggl( \sum_{j=1}^{n} t_{j} \Biggr) + c_{5}\Biggl( \sum_{j=1}^{n} (t_{j} - 1) \Biggr) + c_{6}\Biggl( \sum_{j=1}^{n} (t_{j} - 1) \Biggr) + c_{7}(n-1) \\ & = c_{1} + c_{2}n + c_{3}(n-1) + c_{4}\Biggl( \frac{n(n+1)}{2} \Biggr) + c_{5}\Biggl( \frac{n(n-1)}{2} \Biggr) + c_{6}\Biggl( \frac{n(n-1)}{2} \Biggr) + c_{7}(n-1) \\ & = (\frac{c_{4}}{2} + \frac{c_{5}}{2} + \frac{c_{6}}{2})n^{2} + (c_{2} + c_{3} + \frac{c_{4}}{2} - \frac{c_{5}}{2} - \frac{c_{6}}{2} + c_{7})n + (c_{1} - c_{3} - c_{7}) \\ & \approx \Theta(n^{2}) \end{align} $$
2.2-3
Consider linear search again (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element begin searched for is equally likely to be any element in the array?
LINEAR-SEARCH(A, v)
i = NIL
For j = 1 to A.length
if A[j] == v
i = j
simplify problem
We have input sequence <1, 2>. We assume search for 1,2 as equally likely When we search 1, what is the probability it is at A[0]? $ \frac{1}{2}$ When we search 1, what is the probability it is at A[1]? $ \frac{1}{2}$ How many elements of the input sequence need to be checked on the average? $$ E(n) = 1 * 1/2 + 2 * 1/2 = 1/2 + 1 = 1.5$$
Generalize problem
$$ \begin{align} E(n) & = \sum_{k=1}^{n} (k * 1/n) \\ & = \frac{1}{n} \sum_{k=1}^{n}k \\ & = \frac{1}{n}\frac{n(n+1)}{2} \\ & \approx \Theta(n) \end{align} $$
How about in the worst case?
n
running times
What are the average-case and worst-case running times of linear search in ‚$\Theta$-notation? Justify your answers. - When average-case running time is $\Theta(n)$ (refer to Generalize problem). - When worst-case same, running time is n, it is $\Theta(n)$ - Then both case running time in $\Theta$-notation is $\Theta(n)$.
2.2-4
How can we modify almost any algorithm to have a good best-case running time? Good best-case only possible some special case of input so it is impossible in general.
2.3 Designing algorithms
2.3.1 The divide-and-conquer approach
To solve a given problem, they call themselves recursively one or more times to deal with closely related sub-problems. These algorithms follows a divide-and-conquer approach: they break down the problem into several subproblems recursively, and then combine these solution to create a solution to the original problem.
The divide-and-conquer paradigm involves three steps at each level of recursion:
General approach
Divide ####
the problem into smaller problems that are the smaller instance of the same problem.
Conquer ####
the subproblems by solving them. If its size small enough, however, just solve the subproblems in a straightforward manner.
Combine
the solution to the subproblems into the solution for a original problem
Merge Sort approach
The merge sort algorithm follows divide-and-conquer approach.
Divide
Divide the n-element sequence into two subsequence of n/2-elements each.
Conquer
Sort the subsequences using merge sort.
Combine
Merge the two sorted subsequences to produce the sorted answer
Pseudo code
Parameters
- A is array.
- p,q,r are indices into the array such that $p \leq q \lt r$
- The procedure assumes that the subarray A[p..q] and A[q+1..r] are in sorted order.
- It merges them to form a single sorted subarray that replace the current subarray A[p..r].
Idea
- There is sequence which sorted in specific ranges.
- Break down into new two sorted temp sequences.
- Add infinite to end of two temp arrays.
- Merge and copy two sorted array into original array.
// A = [1,4,2,3]
// MERGE(A, 2, 3, 4)
1 MERGE(A, p, q, r) // in alphbet o,p,q,r,..
2 lenL = q - p + 1
3 lenR = r - q
4 for i = 1 to lenL
5 L[i] = A[p + i - 1]
6 for j = 1 to lenR
7 R[j] = A[q + j]
8 L[lenL + 1] = infin
9 R[lenR + 1] = infin
10 i = 1
11 j = 1
12 for k = p to r
13 if L[i] <= R[j]
14 A[k] = L[i]
15 i = i + 1
16 else
17 A[k] = R[j]
18 j = j + 1
Prove
Loop invariant
At the start of each iteration of the for loop of lines 12-18, the subarray A[p..k-1] contains the k-p smallest elements of $L[1..n_{1} + 1]$ and $R[1..n_{2} + 1]$, in sorted order. Moreover L[i] and L[j] are the smallest elements of their arrays that have not been copied back into A.
Initialization
Prior to the first iteration of the loop, we have k = p, so that the subarray A[p..k-1] is empty. This subarray contains k - p = 0 elements of L and R. Since j = i = 1, both L[i], R[j] are the smallest elements of their arrays that has not been coped back into A.
Maintenance
To see that each iteration maintains the loop invariant, let us suppose $L[i] \leq R[j]$. Then $L[i]$ is the smallest element not yet copied back into A. Because $A[p..k - 1]$ contains the k - p smallest elements, after line 14 copies L[i] into A[k]. Incrementing k and i reestablishes the loop invariant for the next iteration.
Termination
At termination, k = r + 1. By the loop invariant, the subarray $A[p..k-1]$, which is $A[p..r]$, contains the $k - p = r - p + 1$ smallest elements
// A = 5,3, 4,1
//
// 1,3,4,5
// / \
// 3,5 1,4
// / \ / \
// 3 5 1 4
//MERGE-SORT(A, 1, A.length)
MERGE-SORT(A,p,r)
if p < r
q = lower((p + r)/2)
MERGE-SORT(A, p, q)
MERGE-SORT(A, q + 1, r)
MERGE(A, p, q, r)
2.3. Analyzing divide-and-conquer algorithms
Recurrence equation, recurrence
Describe the overall running time on a problem of size n in terms of running time of smaller inputs. $$ T(n) = \begin{cases} \Theta(1), & \text{if $n \leq c$,} \\ aT(n/b) + D(n) + C(n), & \text{otherwise.} \end{cases} $$
Divide
$D(n) = \Theta(n)$
Conquer
$2T(n/2)$
Combine
$C(n)=\Theta(n)$ $$ T(n) = \begin{cases} c, & \text{if $n = 1$,} \\ 2T(n/2) + cn, & \text{$n \gt 1$,} \end{cases} $$
T(n) cn cn
/ \ / \
T(n/2) T(n/2) cn/2 cn/2
/ \ / \
T(n/4) T(n/4) T(n/4) T(n/4)
A cn --> cn
| / \
| cn/2 cn/2 --> cn
lgn / \ / \
| ....
| | | | ... | |
V c c c c c --> cn
\______________________/
n
Level of tree: lg n + 1
Total = (lg n + 1 ) * cn = lg n * cn + cn
Worst case is $\Theta(n \log n)$
Exercises
2.3-1
Using Figure 2.4 as a model, illustrate the operation of merge sort on the array. A = <3, 41, 52, 26, 38, 57, 9, 49>
3,9,26,38,41,49,51,57
/ \
3,26,41,51 9,38,49,57
/ \ / \
3,41 26,51 38,57 9,49
/ \ / \ / \ / \
3 41 52 26 38 57 9 49
2.3-2
Rewrite the MERGE procedure so that is dose not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of other array back into A.
MERGE()
2.3-3
Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence $$ T(n) = \begin{cases} 2, & \text{if $n = 2$,} \\ 2T(n/2) + n, & \text{if $n = 2^{k}$, for $k > 1$} \end{cases} $$ is $T(n) = n \log n$
From
- https://mitpress.mit.edu/books/introduction-algorithms-third-edition