CSCI 3160: Formal languages and automata theory Tutorial 9

CSCI 3160: Formal languages and automata theory Tutorial 9

CSCI 3160 Design and Analysis of Algorithms Tutorial 5 Chengyu Lin Outline Dynamic programming Chain Matrix Multiplication Longest increasing subsequence (LIS) Goal: help understand the lecture materials further Dynamic programming A method for solving complex problems by breaking them down into simpler subproblems (from Wikipedia) Three steps Find the optimal substructure Formulate the problem recursively Compute the values bottom up Chain Matrix Multiplication You want to multiply N matrices A1, , AN Suppose the cost of multiplying an m-by-n matrix with an n-by-l matrix is mnl. The product is an m-by-l matrix What is the minimum total cost to get the product of the N matrices P = A1AN?

Chain Matrix Multiplication Each order of multiplication corresponds to a parenthesization ((A1(A2A3))(A4((A5A6)A7))) Optimal substructure If the above parenthesization is optimal, then (A1(A2A3)) is optimal for multiplying A1, , A3 (A4((A5A6)A7)) is optimal for multiplying A4, , A7 ((A5A6)A7) is optimal for multiplying A5, , A7 Every subparenthesization of an optimal parenthesization is optimal Chain Matrix Multiplication Recurrence Let C(i,j) be the optimal cost of multiplying Ai, Aj C(i,i) = 0 for any i (No multiplication needed) C(i,j) = mini k j-1 { C(i,k) + C(k+1,j) + mi-1mkmj } for i j-1 Build an N-by-N matrix to store the C(i,j)s Our optimal value is then C(1,N) mi mi-1 (Ai) Example

Let A1 be a 5-by-20 matrix, A2 be a 20-by-10 matrix, A3 be a 10-by-3 matrix, A4 be a 3-by-2 matrix m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 i\j 1 2 3 1 0 2 - 0 3 - - 0

4 - - - 4 0 Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(1,2) = C(1,1) + C(2,2) + m0m1m2 = 5 20 10 = 1000 C(2,3) = , C(3,4) = . i\j 1 2 3 1 0

1000 2 - 0 3 - - 0 4 - - - 4 0 Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2

C(1,2) = C(1,1) + C(2,2) + m0m1m2 = 5 20 10 = 1000 C(2,3) = 600, C(3,4) = 60. i\j 1 2 3 4 1 0 1000 2 - 0 600 3 -

- 0 60 4 - - - 0 Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(1,3) = min { C(1,1) + C(2,3) + m0m1m3, C(1,2) + C(3,3) + m0m2m3 } = min { 0 + 600 + 300, 1000 + 0 + 150 } = 900 i\j 1 2 3

4 1 0 1000 900 2 - 0 600 3 - - 0 60 4

- - - 0 Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(2,4) = min { C(2,2) + C(3,4) + m1m2m4, C(2,3) + C(4,4) + m1m3m4 } = min { 0 + 60 + 400, 600 + 0 + 30 } = 460 i\j 1 2 3 4 1 0 1000 900

2 - 0 600 460 3 - - 0 60 4 - - - 0

Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(1,4) = min { C(1,1) + C(2,4) + m0m1m4, , } = min { 0 + 460 + 200, , = . } i\j 1 2 3 4 1 0 1000 900

2 - 0 600 460 3 - - 0 60 4 - - - 0

Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(1,4) = min { C(1,1) + C(2,4) + m0m1m4, C(1,2) + C(3,4) + m0m2m4, C(1,3) + C(4,4) + m0m3m4 } = min { 0 + 460 + 200, 1000 + 60 + 100, 900 + 0 + 30 } = 660. i\j 1 2 3 4 1 0 1000 900 660 2

- 0 600 460 3 - - 0 60 4 - - - 0 Example Hence, the optimal cost of computing

P = A1A4 is 660. i\j 1 2 3 4 1 0 1000 900 660 2 - 0 600

460 3 - - 0 60 4 - - - 0 Analysis Space complexity = O(N2) Time complexity = O(N3) A for loop (k = i .. j-1) is run every time we compute the value of a table entry Longest increasing subsequence (LIS) Given a sequence of N integers a1, , aN, find a

subsequence ai1, , aik (1 i1 < < ik N) such that Increasing: ai1 < < aik Longest: its length k is maximum among all increasing subsequences Example: 3, 1, 6, 0, 8 Can you give another LIS? Longest increasing subsequence (LIS) We can construct a graph 3 1 6 0 8 Optimal substructure If ai1, , aik is an LIS ending at position ik, then ai1, , aij is an LIS ending at position ij for any jk In the language of longest paths: a subpath of a longest path is longest Longest increasing subsequence (LIS) Add an imaginary node - at the front

- 3 1 6 0 8 Recurrence Let L(j) be the length of the LIS ending at position j L(0) = 0 L(j) = 1 + maxi : ai < aj L(i), for j 1 Our longest length is then maxj L(j) Example Use a linear array to store the values - 3 1 6

0 8 j 0 1 2 3 4 5 L(j) 0 Example - 3 1

6 0 8 j 0 1 2 3 4 5 L(j) 0 1 Example -

3 1 6 0 8 j 0 1 2 3 4 5 L(j) 0 1

1 Example - 3 1 6 0 8 j 0 1 2 3 4 5

L(j) 0 1 1 2 Example - 3 1 6 0 8 j 0 1

2 3 4 5 L(j) 0 1 1 2 1 Example - 3 1 6

0 8 j 0 1 2 3 4 5 L(j) 0 1 1 2 1

3 Example - 3 1 6 0 8 j 0 1 2 3 4 5

L(j) 0 1 1 2 1 3 Length of LIS = maxj L(j) = 3 Analysis Space complexity = O(N) O(N2) if you store the graph, since there can be (N) arrows pointing to a node Time complexity = O(N2) Each arrow is gone through once End Questions

Recently Viewed Presentations

  • World Religions

    World Religions

    The term dharma (Sanskrit: dhárma, Pā ḷ i dhamma), is an Indian spiritual and religious term, that means one's righteous duty or any virtuous path in the common sense of the term.
  • Brown Bag Session - Fairfax

    Brown Bag Session - Fairfax

    Pets. Disabilities, Access & Functional Needs. Home / Car. IS-700.A: National Incident Management System, An Introduction. January 2009 Page 2. Home / Car Emergency Kits (1 of 2) Water—one gallon per person, per day (3-day supply for evacuation, 2-week supply...
  • Chapter 1 - The Internet Has Arrived

    Chapter 1 - The Internet Has Arrived

    Chapter 8 - Internet: The Early Years The Desirability Of A Single Network The Department Of Defense Had Multiple Networks Connecting Disconnected Machines The Internet Emerges ARPA funded research to investigate ways to solve the problem of incompatible networks.
  • Ending the HIV Epidemic: Reaching the Unsuppressed and

    Ending the HIV Epidemic: Reaching the Unsuppressed and

    Four Pillars of Ending the HIV Epidemic. Diagnose. All people with HIV as early as possible. Treat. People with HIV rapidly and effectively to reach sustained viral suppression.
  • Learning event - scottishclubsport.co.uk

    Learning event - scottishclubsport.co.uk

    The sporting system shows how . resources are invested by various organisations (partners) to promote sport and develop the people and places that create sporting opportunities which are delivered in the schools and education, clubs and communities and performance sport...
  • Anticoagulation Safe prescribing &amp; Counselling

    Anticoagulation Safe prescribing & Counselling

    Rationale for anticoagulation in AF. AF most common sustained cardiac arrhythmia; 1-2% general population. Prevalence increases with age (5-15% of 80 year olds)
  • Exodus &amp; Wandering in the Wilderness - Eastside church

    Exodus & Wandering in the Wilderness - Eastside church

    Numbered and Organized. Soldiers Numbered & Organized : Counting the soldiers Num 1:1-46. 1 month after tabernacle set up. Every male, above 20, able to war. Moses & Aaron to count; one prince from each tribe to assist
  • The Bohr Model

    The Bohr Model

    Bohr Diagrams. Bohr diagrams are a simplified way to represent atoms. The key features of a Bohr diagram are: Electron shells. Electron placement within the shells. A simplified nucleus to show what element it is (this can be done in...