Lecture9

Introduction to Algorithms Lecture 9

By: Andrey Bogdanchikov

Revision of contest

•So clever to add empty cycles

•Poor participation

•Try to solve yourself, this questions can be on finals.

Outline(Dynamic algorithms)

•Dynamic programming statements

•Fibonacci numbers

•Longest increasing subsequence

•Flag coloring problem

•Money problem

Dynamic algorithms

Is algorithms where next step is calculated from results of previous steps.

Fibonacci numbers

•In fibonacci series all next values are evaluated from two previous values.

•Formula:

•F0 = 0; F1 = 1;

•Fx = Fx-1 + Fx-2

•This formula can be calculated by recursion, but in this case we will do same calculations multiple times and it will consume time.

•If all results are stored in array in this case we can find any value by adding previous two values.

Algorithm of fibonacci

•Create array A.

•A[0] = 0

•A[1] = 1

•For i from 2 to N do

•A[i] = A[i-1]+A[i-2]

•Output A[N]

	1	2	3	4	5	6	7	8	9
	4	6	2	5	1	7	5	8	4
	1	2	1	2	1	3	2	4	2
	-1	1	-1	3	-1	4	5	6	5

Longest increasing subsequence

* B[i] will store number of elements till i.

* C[i] will store index whose element is smaller and has larger numbers in sequence

Longest increasing subsequence O(n2)

•Create array A  read values

•Create array B and C

•For i = 1 to length(A) do

•B[i] = 1, C[i] = -1

•For j = i-1 downto 1 do

•	if A[j] < A[i] and B[j]+1 > B[i] then
•	B[i] = B[j]+1, C[i] = j

•index = FindMaxAndReturnIndexIn(B)

•While index>0 do

•stack index

•index = C[index]

•While size(stack)>0 do

•output A[stack.pop()]

Flag coloring problem

Flags should satisfy the following conditions:

1.Stripes of the same color cannot be placed next to each other.

2.A blue stripe must always be placed between a white and a red or between a red and a white one.

Flag solution in Python

1.a[0] = {'RW':0 , 'WR':0, 'BR':0, 'BW':0}

2.a[1] = {'RW':1 , 'WR':1, 'BR':0, 'BW':0}

3.for i in xrange(2,n+1):

4.a[i] = {'RW':0 , 'WR':0, 'BR':0, 'BW':0}

5.a[i]['RW'] = a[i-1]['WR']+a[i-1]['BR']

6.a[i]['WR'] = a[i-1]['RW']+a[i-1]['BW']

7.a[i]['BR'] = a[i-2]['RW']+a[i-2]['BW']

8.a[i]['BW'] = a[i-2]['WR']+a[i-2]['BR']

10.output.write("%d"%(a[n]['RW']+a[n]['WR']

11. +a[n]['BR']+a[n]['BW']))