CSC3160: Design and Analysis of Algorithms Week 5: Dynamic Programming Instructor: Shengyu Zhang 1
Instructor: Shengyu Zhang 1
About midterm Time:Mar 3,2:50pm -4:50pm. Place:This lecture room. Open book,open lecture notes. But no Internet allowed. Scope:First 6 lectures 2
About midterm ◼ Time: Mar 3, 2:50pm – 4:50pm. ◼ Place: This lecture room. ◼ Open book, open lecture notes. ❑ But no Internet allowed. ◼ Scope: First 6 lectures 2
Dynamic Programming A simple but non-trivial method for designing algorithms Achieve much better efficiency than naive ones. A couple of examples will be exhibited and analyzed. 3
Dynamic Programming ◼ A simple but non-trivial method for designing algorithms ◼ Achieve much better efficiency than naïve ones. ◼ A couple of examples will be exhibited and analyzed. 3
Problem 1:Chain matrix multiplication 4
Problem 1: Chain matrix multiplication 4
Suppose we want to multiply four matrices We want to multiply four matrices:A×B×C×D. Dimensions:A5ox20,B20x1,C1x10,D10x100 ■ Assume:cost (Xmxn X Ynxi)=mnl. The order matters! ▣A×(B×C)×D):20×1×10+20×10×100+50×20×100 120,200 A×(B×(C×D):1×10×100+20×1×100+50×20×100= 103,000 口(A×B)×(C×D):50×20×1+1×10×100+50×1×100=7,000 口(A×B)×C)×D:50×20×1+50×1×10+50×10×100=51,500 0 (A×(B×C)×D:20×1×10+50×20×10+50×10×100=60,200 Question:In what order should we multiply them? 5
Suppose we want to multiply four matrices ◼ We want to multiply four matrices: 𝐴 × 𝐵 × 𝐶 × 𝐷. ◼ Dimensions: 𝐴50×20, 𝐵20×1 , 𝐶1×10, 𝐷10×100 ◼ Assume: cost (𝑋𝑚×𝑛 × 𝑌𝑛×𝑙 ) = 𝑚𝑛𝑙. ❑ 𝐴 × 𝐵 × 𝐶 × 𝐷 : 20 × 1 × 10 + 20 × 10 × 100 + 50 × 20 × 100 = 120,200 ❑ 𝐴 × 𝐵 × 𝐶 × 𝐷 : 1 × 10 × 100 + 20 × 1 × 100 + 50 × 20 × 100 = 103,000 ❑ 𝐴 × 𝐵 × 𝐶 × 𝐷 : 50 × 20 × 1 + 1 × 10 × 100 + 50 × 1 × 100 = 7,000 ❑ 𝐴 × 𝐵 × 𝐶 × 𝐷: 50 × 20 × 1 + 50 × 1 × 10 + 50 × 10 × 100 = 51,500 ❑ 𝐴 × 𝐵 × 𝐶 × 𝐷: 20 × 1 × 10 + 50 × 20 × 10 + 50 × 10 × 100 = 60,200 ◼ Question: In what order should we multiply them? The order matters! 5