- Meeting 01 : Mon, Jul 31, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Introduction to the course. The Party organization problem, formulation, a greedy solution, attempt to prove correctness, counter examples.
Course Grading policy, other announcements.
- Meeting 02 : Tue, Aug 01, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Sorting problem, Quick sort recap, Partition function.
References: | Chapter 7, CLRS.
|
- Meeting 03 : Wed, Aug 02, 09:00 am-09:50 am
References | |
Exercises | |
Reading | |
Proving correctness of Quicksort via loop invariants.
Analysis of quicksort.
Model of computation, RAM model, Asymptotic time complexity. Best case versus worst case.
What happens when we have an unbalanced partition in Quick-sort, which is not necessarily the worst case partition?
- Meeting 04 : Thu, Aug 03, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
What happens when we have an unbalanced partition in Quick-sort, which is not necessarily the worst case partition?
Intuition for average case. Solving the recurrence for T(n) = T(n/c) + T((c-1)n/c) + O(n) using guess and verify method.
Why does guess O(n) as the solution not work?
Proving that the guess O(n log(n)) does work for a suitable choice of constants.
References: | Chapter 7, CLRS.
|
- Meeting 05 : Mon, Aug 07, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Lower Bound for Comparison Based Sorting algorithms.
Analogy to 20 Questions game. Type of questions asked versus type of operations allowed by the algorithm. Decision trees based argument for the Omega (n log(n)) lower bound.
References: | CLRS Chapter 8
|
- Meeting 06 : Tue, Aug 08, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Randomized Quick Sort. Meaning of expected running time. What is the sample space? How many comparisons do we expect to see on a random run?
Defining Random variables, examples, expectation of a random variable. Breaking down a random variable into simpler indicator random variables.
References: | Chapter 7 CLRS
|
- Meeting 07 : Wed, Aug 09, 09:00 am-09:50 am
References | |
Exercises | |
Reading | |
Examples on random variables and computing expectation continued. Number of fixed points in a random permutation, number of inversions in a random permutation.
Back to Analyzing the expected running time of Quick Sort. Probability that two elements in the sorted order get compared.
References: | CLRS Chapter 7,
|
- Meeting 08 : Thu, Aug 10, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Completing the analysis of randomized quicksort.
Expected running time of Quick-sort is O(n log(n)).
Randomized select. What is the sample space? How is it different from the one in randomized quicksort?
- Meeting 09 : Mon, Aug 14, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Randomize select and its analysis. Setting up the random variables and breaking it into indicator random variables.
- Meeting 10 : Tue, Aug 15, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Deterministic Selection algorithm. Intuition about diving the elements into constant sized groups. Analyzing where does the median of median fall in the sorted set?
The algorithm for randomized selection.
- Meeting 11 : Wed, Aug 16, 09:00 am-09:50 am
References | |
Exercises | |
Reading | |
Deterministic Selection: running time analysis using guess and check method. Note that the constants indeed turn out to be large.
Other methods to solving recurrences. The master theorem with a simplified case f(n) = n^d. Proof of the master theorem for this simplified case.
- Meeting 12 : Thu, Aug 17, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 13 : Tue, Aug 22, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Solving Recurrences using Master method when f(n) is not of the form n^d. Statement of the cases with connections to the special case when f(n) = n^d.
Introducing the definition little-oh. If f(n) = little-oh(g(n)) does it imply f(n) = big-Oh(g(n))? How about the converse? Examples. Exercise: Definition of little-omega and examples.
Discussion on comparing functions asymptotically. If f(n) = big-Oh(g(n)) does it imply 2^f(n) = big-Oh(g(n))? Counter examples for the same.
References: | Section 4.5 CLRS for Masters method.
Section 3.1 CLRS for Asymptotic notation.
|
- Meeting 14 : Wed, Aug 23, 09:00 am-09:50 am
References | |
Exercises | |
Reading | |
Maximum Subarray problem. Problem Definition and a brute force solution. Discussion on possible solution ideas. Does the solution have to contain all positive elements? Does the solution have to contain the maximum element in the array?
A simpler problem: maximum subarray with a given index included. How does it help solving the general case?
A divide and conquer solution. Recurrence for the same and running time.
References: | Chapter 4, Section 4.1, CLRS.
|
- Meeting 15 : Thu, Aug 24, 12:00 pm-12:50 pm
References | |
Exercises | |
Reading | |
Discussion on SE1 + Lower bound arguments.
Proving that computing maximum of n distinct elements requires Omega(n) comparisons.
- Meeting 16 : Mon, Aug 28, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Closest Pair of Points, problem definition, an incorrect lower bound of Omega(n^2).
The 1D case is solvable via sorting.
2D case a divide and conquer approach.
What happens when Theta(n) points lie inside the "small strip" that we constructed? Can we examine constant number of points for every point in the strip?
References: | Chapter 33, Section 33.4, CLRS.
|
- Meeting 17 : Tue, Aug 29, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Completing the Closest Pair of points.
Discussion on a divide and conquer approach for Matrix Multiplication. Brief discussion on Strassen's improvement.
Majority Problem (in Problem Sheet 1) discussion of O(n log(n)) solution.
References: | Section 33.4 of CLRS for Closest Pair of Points.
Section 2.5 of DPV for Strassen's Matrix Multiplication.
|