西安电子科技大学：《算法设计技术 Algorithms Design Techniques》课程教学资源（PPT课件讲稿）Techniques Based on Recursion（Chapter 5 Induction Chapter 6 Divide and Conquer Chapter 7 Dynamic Programming）

What's Recursion? Recursion is the process of dividing the problem into one or more subproblems,which are identical in structure to the original problem and then combining the solutions to these subproblems to obtain the solution to the original problem

What’s Recursion? ◼ Recursion is the process of dividing the problem into one or more subproblems, which are identical in structure to the original problem and then combining the solutions to these subproblems to obtain the solution to the original problem

What's Recursion? There are three special cases of the recursion technique: Induction:the idea of induction in mathematical proofs is carried over to the design of efficient algorithms 。 Nonoverlapping subproblems:divide and conquer Overlapping subproblems:dynamic programming,trading space for time

What’s Recursion? ◼ There are three special cases of the recursion technique: ⚫ Induction: the idea of induction in mathematical proofs is carried over to the design of efficient algorithms ⚫ Nonoverlapping subproblems: divide and conquer ⚫ Overlapping subproblems: dynamic programming, trading space for time

Induction Given a problem with parameter n,designing an algorithm by induction is based on the fact that if we know how to solve the problem when presented with a parameter less than n,called the induction hypothesis, then our task reduces to extending that solution to include those instances with parameter n

Induction Given a problem with parameter n, designing an algorithm by induction is based on the fact that if we know how to solve the problem when presented with a parameter less than n, called the induction hypothesis, then our task reduces to extending that solution to include those instances with parameter n

Radix Sort Let L=ta,a,...an be a list of n numbers each consisting of exactly k digits.That is,each number is of the form dd1...d,where each d,is a digit between 0 and 9. In this problem,instead of applying induction onn, the number of objects,we use induction on k,the size of each integer

Radix Sort ◼ Let L={a1 , a2 , …, an} be a list of n numbers each consisting of exactly k digits. That is, each number is of the form dkdk-1…d1 , where each di is a digit between 0 and 9. ◼ In this problem, instead of applying induction on n, the number of objects, we use induction on k, the size of each integer

Radix Sort ■ If the numbers are first distributed into the lists by their least significant digit,then a very efficient algorithm results. Suppose that the numbers are sorted lexicographically according to their least k-1 digits, i.e.,digits de de2r....a. After sorting them on their kth digits,they will eventually be sorted

Radix Sort ◼ If the numbers are first distributed into the lists by their least significant digit, then a very efficient algorithm results. ◼ Suppose that the numbers are sorted lexicographically according to their least k-1 digits, i.e., digits dk-1 , dk-2 , …, d1 . ◼ After sorting them on their kth digits, they will eventually be sorted

Radix Sort First,distribute the numbers into 10 lists Lo,Li,..., Le according to digit d so that those numbers with d=0 constitute list Lo,those with d=1 constitute list L and so on. Next,the lists are coalesced in the order Lo,L1,..., 9 Then,they are distributed into 10 lists according to digit d,coalesced in order,and so on. After distributing them according to d and collecting them in order,all numbers will be sorted

Radix Sort ◼ First, distribute the numbers into 10 lists L0 , L1 , …, L9 according to digit d1 so that those numbers with d1=0 constitute list L0 , those with d1=1 constitute list L1 and so on. ◼ Next, the lists are coalesced in the order L0 , L1 , …, L9 . ◼ Then, they are distributed into 10 lists according to digit d2 , coalesced in order, and so on. ◼ After distributing them according to dk and collecting them in order, all numbers will be sorted

Radix Sort Example:Sort A nondecreasingly. A1..5]=7467327567929134 1239

Radix Sort Example: Sort A nondecreasingly. A[1…5]=7467 3275 6792 9134 1239

Radix Sort Input:A linked list of numbers L=ta,az,...,a and k,the number of digits. Output:L sorted in nondecreasing order. 1.for 1 to 2. Prepare 10 empty lists Lo,Li,...,L9; 3. while L is not empty 4. anext element in L; 5. Delete a from L; 6. kth digit in a 7. Append a to list Li 8. end while; 9. L←L0; 10. fori←-1to9 11. LL,L;//Append list L;to L 12. end for; 13.end for; 14.return L;

Radix Sort ◼ Input: A linked list of numbers L={a1 , a2 , …, an} and k, the number of digits. ◼ Output: L sorted in nondecreasing order. 1. for j1 to k 2. Prepare 10 empty lists L0 , L1 , …, L9; 3. while L is not empty 4. anext element in L; 5. Delete a from L; 6. ijth digit in a; 7. Append a to list Li ; 8. end while; 9. L L0; 10. for i 1 to 9 11. LL, Li //Append list Li to L 12. end for; 13. end for; 14. return L;

Radix Sort What's the performance of the algorithm Radix Sort? √Time Complexity? √Space Complexity?

Radix Sort ◼ What’s the performance of the algorithm Radix Sort? ✓ Time Complexity? ✓ Space Complexity?

Radix Sort Time Complexity:(n) Space Complexity:(n)

Radix Sort ◼ Time Complexity: (n) ◼ Space Complexity: (n)