11 a (I).A Way of Comparing Functions That Ignores Constant Factors and Small Input Sizes

Nov-Dec 2011

11 a (i).A way of comparing functions that ignores constant factors and small input sizes (because?)

bO(g(n)): class of functions f(n) that grow no faster than g(n)

bΘ(g(n)): class of functions f(n) that grow at same rate as g(n)

bΩ(g(n)): class of functions f(n) that grow at least as fast as g(n)

Establishing order of growth using the definition:

Definition: f(n) is in O(g(n)), denoted f(n)  O(g(n)), if order of growth of f(n) ≤ order of growth of g(n) (within constant multiple), i.e., there exist positive constant c and non-negative integer n0 such that

f(n) ≤ c g(n) for every n ≥ n0

Examples:

10n is in O(n2)

5n+20 is in O(n)

-notation

Formal definition

•A function t(n) is said to be in (g(n)), denoted t(n) (g(n)), if t(n) is bounded below by some constant multiple of g(n) for all large n, i.e., if there exist some positive constant c and some nonnegative integer n0 such that

t(n)  cg(n) for all n  n0

Exercises: prove the following using the above definition

•10n2(n2)

•0.3n2 - 2n(n2)

•0.1n3(n2)

-notation

Formal definition

•A function t(n) is said to be in (g(n)), denoted t(n) (g(n)), if t(n) is bounded both above and below by some positive constant multiples of g(n) for all large n, i.e., if there exist some positive constant c1 and c2 and some nonnegative integer n0 such that

c2 g(n)  t(n)  c1 g(n) for all n  n0

Exercises: prove the following using the above definition

•10n2(n2)

•0.3n2 - 2n (n2)

•(1/2)n(n+1)(n2)

11)b. (i) Unordered Linear Search

Suppose that the given array was not necessarily sorted. This might correspond, for example, to acollection exams which have not yet been sorted alphabetically. If a student wanted to obtain herexam score, how could she do so? She would have to search through the entire collection of exams,one-by-one, until her exam was found. This corresponds to the unordered linear search algorithm.

Unordered-Linear-Search[A, n, x]

1 for i 1 to n

2 do if A[i] = x

3 then return i

4 else i i+ 1

5 return “x not found”

Note that in order to determine that an object does not exist in the collection, one needs to search

through the entire collection.

Now consider the following array:

i1 2 3 4 5 6 7 8

A 34 16 12 11 54 10 65 37

Consider executing the pseudocodeUnordered-Linear-Search[A, 8, 54]. The variable i would

initially be set to 1, and since A[1] (i.e., 34) is not equal to x (i.e., 54), i would be incremented

by 1 in Line 4. Since A[2] 6= x, i would again be incremented, and this would continue until i = 5.At this point, A[5] = 54 = x, so the loop would terminate and 5 would be returned in Line 3.

Now consider executing the pseudocodeUnordered-Linear-Search[A, 8, 53]. Since 53 does

not exist in the array, i would continue to be incremented until it exceeded the bounds of the for

loop, at which point the for loop would terminate. In this case, “x not found” would be returned

in Line 5.

Ordered Linear Search

Now suppose that the given array is sorted. In this case, one need not necessarily search through

the entire list to find a particular object or determine that it does not exist in the collection. For

example, if the collection of exams were sorted by name, one need not search beyond the “P”s

to determine that the exam for “Peterson” does or does not exist in the collection. A simple

modification of the above algorithm yields the ordered linear search algorithm.

Ordered-Linear-Search[A, n, x]

1 for i 1 to n

2 do if A[i] = x

3 then return i

4 elseifA[i] < x

5 then i i+ 1

6 else return “x not found”

7 return “x not found”

Note that the search can now be terminated early if and when it is determined that A[i] > x in

Line 6.

Now consider the following array, the sorted version of the array used in our previous example:

i1 2 3 4 5 6 7 8

A 10 11 12 16 34 37 54 65

Consider executing the pseudocodeOrdered-Linear-Search[A, 8, 54]. The variable i would

initially be set to 1, and since A[1] (i.e., 10) is not equal to x (i.e., 54), a test would be performedin Line 4 to see if A[1] is less than x. Since A[1] is less than x, i would be incremented by 1 inLine 5. Since A[2] < x, i would again be incremented, and this would continue until i = 7. At thispoint, A[7] = 54 = x, so the loop would terminate and 7 would be returned in Line 3.

Now consider executing the pseudocodeOrdered-Linear-Search[A, 8, 53]. Since 53 does not

exist in the array, i would continue to be incremented until i = 7, at which point A[i] (i.e., 54) is

no longer less than x (i.e., 53) so the loop would terminate in Line 6 returning “x not found.”

(b) iiA Short Tutorial on Recurrence Relations

The concept: Recurrence relations are recursive definitions ofmathematical functions or sequences. For example, the recurrencerelation

g(n) = g(n-1) + 2n -1

g(0) = 0

defines the function f(n) = n^2, and the recurrence relation

f(n) = f(n-1) + f(n-2)

f(1) = 1

f(0) = 1

defines the famous Fibanocci sequence 1,1,2,3,5,8,13,....

Solving a recurrence relation: Given a function defined by a recurrencerelation, we want to find a "closed form" of the function. In other words,we would like to eliminate recursion from the function definition.

There are several techniques for solving recurrence relations.The main techniques for us are the iteration method (also called expansion,or unfolding methods) and the Master Theorem method. Here is an exampleof solving the above recurrence relation for g(n) using the iteration

method:

g(n) = g(n-1) + 2n - 1

= [g(n-2) + 2(n-1) - 1] + 2n - 1

// because g(n-1) = g(n-2) + 2(n-1) -1 //

= g(n-2) + 2(n-1) + 2n - 2

= [g(n-3) + 2(n-2) -1] + 2(n-1) + 2n - 2

// because g(n-2) = g(n-3) + 2(n-2) -1 //

= g(n-3) + 2(n-2) + 2(n-1) + 2n - 3

...

= g(n-i) + 2(n-i+1) +...+ 2n - i

...

= g(n-n) + 2(n-n+1) +...+ 2n - n

= 0 + 2 + 4 +...+ 2n - n

// because g(0) = 0 //

= 2 + 4 +...+ 2n - n

= 2*n*(n+1)/2 - n

// using arithmetic progression formula 1+...+n = n(n+1)/2 //

= n^2

Applications: Recurrence relations are a fundamental mathematicaltool since they can be used to represent mathematical functions/sequencesthat cannot be easily represented non-recursively. An exampleis the Fibanocci sequence. Here we are mainly interested in applicationsof recurrence relations in the design and analysis of algorithms.

Recurrence relations with more than one variable: In some applicationswe may consider recurrence relations with two or more variables. Thefamous Ackermann's function is one such example. Here is another examplerecurrence relation with two variables.

T(m,n) = 2*T(m/2,n/2) + m*n, m > 1, n > 1

T(m,n) = n, if m = 1

T(m,n) = m, if n = 1

We can solve this recurrence using the iteration method as follows.

Assume m <= n. Then

T(m,n) = 2*T(m/2,n/2) + m*n

= 2^2*T(m/2^2,n/2^2) + 2*(m*n/4) + m*n

= 2^2*T(m/2^2,n/2^2) + m*n/2 + m*n

= 2^3*T(m/2^3,n/2^3) + m*n/2^2 + m*n/2 + m*n

...

= 2^i*T(m/2^i,n/2^i) + m*n/2^(i-1) +...+ m*n/2^2 + m*n/2 + m*n

Let k = log_2 m. Then we have

T(m,n) = 2^k*T(m/2^k,n/2^k) + m*n/2^(k-1) +...+ m*n/2^2 + m*n/2 + m*n

= m*T(m/m,n/2^k) + m*n/2^(k-1) +...+ m*n/2^2 + m*n/2 + m*n

= m*T(1,n/2^k) + m*n/2^(k-1) +...+ m*n/2^2 + m*n/2 + m*n

= m*n/2^k + m*n/2^(k-1) +...+ m*n/2^2 + m*n/2 + m*n

= m*n*(2-1/2^k)

= Theta(m*n)

Analyzing (recursive) algorithms using recurrence relations: For recursivealgorithms, it is convinient to use recurrence relations to describethe time complexity functions of the algorithms. Then we can obtainthe time complexity estimates by solving the recurrence relations. Youmay find several examples of this nature in the lecture notes and the books,

such as Towers of Hanoi, Mergesort (the recursive version), and Majority.These are excellent examples of divide-and-conquer algorithms whoseanalyses involve recurrence relations.

Here is another example. Given algorithm

Algorithm Test(A[1..n], B[1..n], C[1..n]);

if n= 0 then return;

For i := 1 to n do

C[1] := A[1] * B[i];

call Test(A[2..n], B[2..n], C[2..n]);

If the denote the time complexity of Test as T(n), then we can express T(n)recursively as an recurrence relation:

T(n) = T(n-1) + O(n)

T(1) = 1

(You may also write simply T(n) = T(n-1) + n if you think of T(n)

as the the number of multiplications)

By a straighforward expansion method, we can solve T(n) as:

T(n) = T(n-1) + O(n)

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

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

= T(n-3) + O(n-2) + O(n-1) + O(n)

...

= T(1) + O(2) + ... + O(n-1) + O(n)

= O(1 + 2 + ... + n-1 + n)

= O(n^2)

Yet another example:

Algorithm Parallel-Product(A[1..n]);

if n = 1 then return;

for i := 1 to n/2 do

A[i] := A[i]*A[i+n/2];

call Parallel-Product(A[1..n/2]);

The time complexity of the above algorithm can be expressed as

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

T(1) = 1

We can solve it as:

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

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

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

= T(n/2^3) + O(n/2^3) + O(n/2^2) + O(n/2)

...

= T(n/2^i) + O(n/2^i) +...+ O(n/2^2) + O(n/2)

= T(n/2^log n) + O(n/2^log n) +...+ O(n/2^2) + O(n/2)

// We stop the expansion at i = log n because

2^log n = n //

= T(1) + O(n/2^log n) +...+ O(n/2^2) + O(n/2)

= 1 + O(n/2^log n +...+ n/2^2 + n/2)

= 1 + O(n*(1/2^log n +...+ 1/2^2 + 1/2)

= O(n)

// because 1/2^log n +...+ 1/2^2 + 1/2 <= 1 //

Using recurrence relations to develop algorithms: Recurrence relations areuseful in the design of algorithms, as in the dynamic programming paradigm. For this course, you only need to know how to derive an iterative (dynamicprogramming) algorithm when you are given a recurrence relation.

12.(a) Binary Search

Now consider the following idea for a search algorithm using our phone book example. Select a pageroughly in the middle of the phone book. If the name being sought is on this page, you’re done.If the name being sought is occurs alphabetically before this page, repeat the process on the “firsthalf” of the phone book; otherwise, repeat the process on the “second half” of the phone book.Note that in each iteration, the size of the remaining portion of the phone book to be searched isdivided in half; the algorithm applying such a strategy is referred to as binary search. While thismany not seem like the most “natural” algorithm for searching a phone book (or any ordered list),it is provably the fastest. This is true of many algorithms in computer science: the most naturalalgorithm is not necessarily the best!

3

Binary-Search[A, n, x]

1 low 1

2 high n

3 while low _ high

4 do mid b(low + high)/2c

5 if A[mid] = x

6 then return mid

7 elseifA[mid] < x

8 then low mid + 1

9 else high mid − 1

10 return “x not found”

Again consider the following array:

i1 2 3 4 5 6 7 8

A 10 11 12 16 34 37 54 65

(b) Merge and Quick sort

Merge Sort

Time complexity (Average): O(n log n)

Time complexity (Worst): O(n log n)

(Occurs when list is sorted) Stable sort

Not dependent on any factors
Average case = Worst CaseNot a stable sort

Dependent on randomness of list Memory: O(n)

Quick Sort

Time complexity (Average): O(n log n)

Time complexity (Worst): O(n^2)

Additional memory space requiredMemory: O(log n)
Memory Complexity (Best): O(1)
Little additional memory space required

Analysis merge sorting

DIVIDE: Partition the n-element sequence to be sorted into two subsequences of n/2

Elementseach.

CONQUER: Sort the two subsequences recursively using themergesort.

COMBINE: Merge the two sorted sorted subsequences of size n/2 each to produce

the sortedsequenceconsisting of nelements.

Note that recursion "bottoms out" when the sequence to be sorted is of unit length.

Since every sequence of length 1 is in sorted order, no further recursive call is

necessary. The key operation of the mergesort algorithm is the merging of the two

sorted "combine step". Toperform the merging, we use an auxilliary procedure Merge(A,p,q,r), where A is anarray and p,q and r are indices numbering elements of the array such that dureassumes that the subarrays A[p..q] and A[q+1...r] are in sorted order.It mergesthem to form a single sorted subarray that replaces the current subarray A[p..r].Thus finally,we obtain the sorted array A[1..n], which is the solution.

For quick sort follow these steps

Analysis of Quick sort

The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:

1. Choose a pivot value. We take the value of the middle element as pivot value, but it can

be any value, which is in range of sorted values, even if it doesn't present in the array.

2. Partition. Rearrange elements in such a way, that all elements which are lesser than

the pivot go to the left part of the array and all elements greater than the pivot, go to

the right part of the array. Values equal to the pivot can stay in any part of the

array. Notice, that array may be divided in non-equal parts.

3. Sort both parts. Apply quicksort algorithm recursively to the left and the right parts.

Partition algorithm in detailThere are two indices i and j and at the very beginning of the partition algorithm i points tothe first element in the array and j points to the last one. Then algorithm moves i forward,until an element with value greater or equal to the pivot is found. Index j is movedbackward, until an element with value lesser or equal to the pivot is found. If i _ j then theyare swapped and i steps to the next position (i + 1), j steps to the previous one (j - 1).Algorithm stops, when i becomes greater than j.

After partition, all values before i-th element are less or equal than the pivot and all values afterj-th element are greater or equal to the pivot.

The steps are used to arrange the values in the given problem

3)Explain Multistage graphs with an example and how it is implemented using dynamic programming

Definition: multistage graph G(V,E)

ό A directed graph in which the vertices are partitioned into k≥2 disjoint sets Vi, 1≤i≤k

ό If <u,v> E, then u Vi and v Vi+1 for some I, 1≤i<k

ό |V1|= |Vk|=1, and s(source) V1 and t(sink) Vk

όc(i,j)=cost of edge <i,j

Definition: multistage graph problem

όFind a minimum-cost path from s to t

ό

όe.g., Figure 5.2 (5-stage graph)

Many problems can be formulated as multistage graph problem

όAn example: resource allocation problem

n units of resource are to be allocated to r projects

N(i,j) = net profit when j units of resource allocated to project i

όStage 2

cost(2,2) = min {4+cost(3,6), 2+cost(3,7), 1+cost(3,8)} = 7 cost(2,3) = min {2+cost(3,6), 7+cost(3,7)} = 9

cost(2,4) = min {11+cost(3,8)} = 18

cost(2,5) = min {11+cost(3,7), 8+cost(3,8)} = 15

όStage 1

cost(1,1) = min {9+cost(2,2), 7+cost(2,3), 3+cost(2,4), 2+cost(2,5)} = 16

όImportant notes: avoiding the recomputation of cost(3,6), cost(3,7), and cost(3,8) in computing cost(2,2)

όRecording the path

όd(i,j) = value of l (l is a vertex) that minimizes c(j,l)+cost(i+1,l) in equation (5.5)

όIn Figure 5.2

d(3,6)=10; d(3,7)=10; d(3,8)=10

d(2,2)=7; d(2,3)=6; d(2,4)=8; d(2,5)=8 d(1,1)=2

όWhen letting the minimum-cost path 1,v2,v3,…,vk-1,t, v2 = d(1,1) = 2

v3 = d(2,d(1,1)) = 7

v4 = d(3,d(2,d(1,1))) = d(3,7) = 10

So the solution (minimum-cost path) is 1◊2◊7◊10◊12 and its cost is 16

Algorithm void Fgraph (graph G, int k, int n, int p[] )

•The input is a k-stage graph G = (V,E) with n vertices indexed in order

•of stages. E is a set of edges and c[i][j] is the cost of <i, j>.

•p[1 : k] is a minimum-cost path.

{

float cost[MAXSIZE]; int d[MAXSIZE], r; cost[n] = 0.0;

for (int j=n-1; j >= 1; j--) { // Compute cost[j]. let r be a vertex such that <j, r> is an edge of G and c[j][r] + cost[r] is minimum; cost[j] = c[j][r] + cost[r];

d[j] = r;

}

// Find a minimum-cost path. p[1] = 1; p[k] =n ;

for ( j=2; j <= k-1; j++) p[j] = d[ p[ j-1 ] ];

}

13(b)Binary search tree

In binary search trees most of the operations' average computational complexity is given as O(NlogN). Below is a text snippet from Algo's book:

Average of internal path length is D(n) = O(n log n). Thus, the expected depth of any node is O(log n). As an example, the randomly generated 500-node tree has nodes at expected depth 9.98.

It is tempting to say immediately that this result implies that the average running time of all the operations discussed i.e., insert, find min, find max, delete on binary search tree is O(log n), but this is not entirely true. The reason for this is that because of deletions, it is not clear that all binary search trees are equally likely. In particular, the deletion algorithm described above favors making the left subtrees deeper than the right, because we are always replacing a deleted node with a node from the right subtree. The exact effect of this strategy is still unknown, but it seems only to be a theoretical novelty. It has been shown that if we alternate insertions and deletions O(n2) (i.e., theta of n square) times, then the trees will have an expected depth of theta of square root N.

After a quarter-million random insert/delete pairs, the tree that was somewhat right-heavy looks decidedly unbalanced (average depth = 12.51).

14 (a)The Eight Queens problem

Place 8 queens in a chessboard so that no two queens are in the same row, column, or

diagonal.

3

Formulation :

States: any arrangement of 0 to 8 queens on the board

Initial state: 0 queens on the board

Successor function: add a queen in any square

Goal test: 8 queens on the board, none attacked

Idea of solution:

• Each recursive call attempts to place a queen in a specific

column – A loop is used, since there are 8 squares in the

column

• For a given call, the state of the board from previous placements is known

(i.e. where are the other queens?)

• Current step backtracking: If a placement within the column does not lead to

a solution, the queen is removed and moved "down" the column

• Previous step backtracking: When all rows in a column have been tried, the

call terminates and backtracks to the previous call (in the previous column)

• Pruning: If a queen cannot be placed into column i, do not even try to place

one onto column i+1 – rather, backtrack to column i-1 and move the queen

that had been placed there

• Using this approach we can reduce the number of potential solutions even

more.

Algorithm

voidNQueens(int k, int n)

// Using backtracking, this procedure prints all

// possible placements of n queens on an nXn

// chessboard so that they are nonattacking.

{

for (int i=1;

i<=n; i++) { if

(Place(k, i)) {

x[k] = i;

if (k==n) { for (int j=1;j<=n;j++)

cout< x[j] < ' '; cout

endl;} else NQueens(k+1, n);

}

}

}

bool Place(int k, int i)

// Returns true if a queen can be placed in kth row and

// ith column. Otherwise it returns false. x[] is a

// global array whose first (k-1) values have been set.

// abs(r) returns the absolute value of r.

{

for (int j=1; j < k; j++)

if ((x[j] == i) // Two in the same column

|| (abs(x[j]-i) == abs(j-k))) // or in the same

diagonal return(false);

5

return(true);

}

State Space Tree of the Four-queens Problem

Recursive backtracking in general
(ii) Let's see what a recursive backtracking function generally looks like:

recursive_funtion(level) {
for all possible ways for something {
try it
if solution valid {
if solution complete {
done, show solution
}else{
recursive_function(next_level)
}
}
(revert this try)
}
}

As you can see, this method consists of a level, which we traverse in each recursive call, and a set of local decisions we make at each level. Take a magic square, for example (image from the Wikipedia page):

With the above method, we would define our level as the position in the grid (ranging from 1 to 9, as there are 9 spaces to fill with a number), the decisions at each level would be a number ranging from 1 to 9, our function would be:

recursive_funtion(position) {
for number from 1 to 9, not used elsewhere already {
put this number on this position, make it unavailable
if solution valid {
if solution complete {
done, show solution
}else{
recursive_function(next_position)
}
}
(make this space blank again, and the number available)
}
}

A few remarks:
(1) As each number can only be used once in the whole square, we must keep an array or set somewhere to keep track of the numbers used, which can be easily done in each programming language.
(2) Note that we can check mid-solution, we must not wait until we are at position 9 (the last position) to check if the solution is valid. In fact, we can speed things up a bit by implementing a few optimalizations. For example: after each row is done (at positions 3, 6 and 9), check if this row sums to 15, if it does not, there is no sense continuing towards deeper levels in our tree.
Speaking of trees, I hope you see how the combination of levels and decisions correspond to a tree. If you do not: here is a picture:

(Not all levels, lines and branches are shown, but it should give you a pretty clear idea.) Note that, if we picked e.g. the number 2 for position (level) 1, we cannot use it in the following levels, as shown in the tree.
Now let's see how the function will work, we start at the first level, with the first number: