CSC236H5 Lecture Notes - Lecture 6: Binary Logarithm, Quicksort, Merge Sort
8 Nov 2017
School
Department
Course
Professor
Document Summary
Lst[ 0 ] <= lst[ 1 ] middle = len(lst) // left = is_sorted(lst[:middle]) right = is_sorted(lst[middle:]) return . The list does not consider the middle element to be sorted or the list is considered sorted if both sides are sorted. True if middle = len(lst) // left = is_sorted(lst[:middle+ 1 ]) There are many problems that are solved by divide and conquer. Divide: divide the problem into two or more smaller instances of the same problem. Conquer: if the subproblem i small, solve it directly. Combine: combine the solutions to the subproblems to solve the original problem. Eg. max segment sum of [2, -5, 8 - 6, 10] is 12. The maximum segment sum is the maximum sum of any segment in the list. What should we define as the max segment sum of an empty list: 0 b. c, undefined. None of the above. let"s look at two examples.
