上浒充通大学 SHANGHAI JLAO TONG UNIVERSITY Computer Algorithm Design and Analysis Lecture 2/Week 12:Divide and Conquer Yongxin ZHU,Weiguang SHENG 强 具是 3合 SHANG 1日G
Computer Algorithm Design and Analysis Lecture 2/ Week 12: Divide and Conquer Yongxin ZHU, Weiguang SHENG
上游充通大粤 Recursive algorithms SHANGHAI JIAO TONG UNIVERSITY General idea: Divide a large problem into smaller ones ·By a constant ratio By a constant or some variable Solve each smaller one recursively or explicitly Combine the solutions of smaller ones to form a solution for the original problem Divide and Conquer 3/12/2022 2
3/12/2022 2 Recursive algorithms General idea: • Divide a large problem into smaller ones • By a constant ratio • By a constant or some variable • Solve each smaller one recursively or explicitly • Combine the solutions of smaller ones to form a solution for the original problem Divide and Conquer
上浒充通大学 Divide-and-Conquer SHANGHAI JIAO TONG UNIVERSITY Divide-and-conquer. Break up problem into several parts. e Solve each part recursively. Combine solutions to sub-problems into overall solution. Most common usage. Break up problem of size n into two equal parts of size vn. Solve two parts recursively. Combine two solutions into overall solution in linear time. ©Consequence. ·Brute force:n2. Divide et impera. Veni,vidi,vici. Divide-and-conquer:n log n. Julius Caesar
3 Divide-and-Conquer Divide-and-conquer. • Break up problem into several parts. • Solve each part recursively. • Combine solutions to sub-problems into overall solution. Most common usage. • Break up problem of size n into two equal parts of size ½n. • Solve two parts recursively. • Combine two solutions into overall solution in linear time. Consequence. • Brute force: n2. • Divide-and-conquer: n log n. Divide et impera. Veni, vidi, vici. - Julius Caesar
上游充通大学 SHANGHAI JLAO TONG UNIVERSITY Divide and Conquer Example1:Merge Sort 强 LAMAANAMA A学 SHANG 1日G
Divide and Conquer Example1: Merge Sort
上游充通大学 Sorting SHANGHAI JLAO TONG UNIVERSITY Sorting.Given n elements,rearrange in ascending order. Obvious sorting applications. Non-obvious sorting applications. List files in a directory. Data compression. Organize an MP3 library. Computer graphics. List names in a phone book. Interval scheduling. Display Google PageRank Computational biology. results. Minimum spanning tree. Supply chain management Problems become easier once Simulate a system of particles. sorted. Book recommendations on Find the median. Amazon. Find the closest pair. Load balancing on a parallel Binary search in a computer. database. Identify statistical outliers. Find duplicates in a mailing list
5 Obvious sorting applications. List files in a directory. Organize an MP3 library. List names in a phone book. Display Google PageRank results. Problems become easier once sorted. Find the median. Find the closest pair. Binary search in a database. Identify statistical outliers. Find duplicates in a mailing list. Non-obvious sorting applications. Data compression. Computer graphics. Interval scheduling. Computational biology. Minimum spanning tree. Supply chain management. Simulate a system of particles. Book recommendations on Amazon. Load balancing on a parallel computer. . . . Sorting Sorting. Given n elements, rearrange in ascending order