- Meeting 01 : Tue, Jul 31, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Role of algorithms in computing.
Correctness and Resource utilization in the analysis
of an algorithm.
References: | Cormen, Leiserson, and Rivest - 2nd Edition
|
Reading: | Chapters 1 and 2 in CLR,
Art of Computer Programming - D.E. Knuth
Volume 3 (sorting and Searching) |
- Meeting 02 : Wed, Aug 01, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
No Class
References: | Comparison of Functions
|
Reading: | CLR chapter 3. |
- Meeting 03 : Thu, Aug 02, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
The key steps in proving correctness of an algorithm to compute a function. A function is associated with each problem, implicitly. An algorithm encodes invariants
discovered to represent this function to be computed.
Correctness is the task of proving that that the algorithm indeed computes the function.
Following correctness, identify functions that estimates the resources utilized by the algorithm.
References: | CLR chapters 1, 2, 3.
|
Reading: | Fundamental Algorithms by Knuth. |
- Meeting 04 : Fri, Aug 03, 02:00 pm-02:50 pm
References | |
Exercises | |
Reading | |
This one happened between 8-9am. Completed asymptotic notation,
the relationships among them, and pointed out that there are incomparable functions under the asymptotic relationships. Then introduction to solving recurrences. Study of T(n)=aT(n-1)+b as an A.P, and the recurrence of T(n)=T(n-1)+T(n-2) solution can be guessed by
vieweing it as a G.P.
References: | CLR chapter 3
Monday Chapter 4.
|
- Meeting 05 : Mon, Aug 06, 02:00 pm-03:00 pm
References | |
Exercises | |
Reading | |
Steps in solving recurrences. Guessing solutions and methods of coming up with educated guesses. Rewriting recurrences to simplify them, and then guess. Leading to the master theorem.
- Meeting 06 : Tue, Aug 07, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
Master Theorem: Guessing a solution by the recursion tree method, and then comparing f(n) with contribution with the number of leaves.
References: | CLR chapter 4.
|
- Meeting 07 : Wed, Aug 08, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
Completing the Master Theorem.
- Meeting 08 : Mon, Aug 13, 10:00 am-10:15 am
References | |
Exercises | |
Reading | |
Introduction to average case analysis.
Average case analysis of insertion sort.
Definition of a probability distribution, random variable, expectation. Calculation of the expected
number of comparisons by insertion sort, over the uniform distribution on the set of permutations on the numbers 1 to n.
References: | Chapter 5 of CLR.
|
- Meeting 09 : Tue, Aug 14, 11:00 am-12:00 pm
References | |
Exercises | |
Reading | |
Completed the average case analysis of insertion sort.
Connection to the hiring problem: probability of
getting an element of rank i-j+1 as the i-th element in
a random permutation of i distinct elements.
References: | CLR chapter 5
|
Reading: | STudy the hiring problem and under the random variables set-up and analysed. |
- Meeting 10 : Thu, Aug 16, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
Introduction to Randomized Algorithms and expectation.
Analysis of MAX-CUT, Indicator variables, and
Birthday paradox.
- Meeting 11 : Tue, Aug 21, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 12 : Wed, Aug 22, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 13 : Thu, Aug 23, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 14 : Fri, Aug 24, 02:00 pm-02:50 pm
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 15 : Wed, Aug 29, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 16 : Thu, Aug 30, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 17 : Fri, Aug 31, 02:00 pm-02:50 pm
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 18 : Tue, Sep 04, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 19 : Thu, Sep 06, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 20 : Wed, Sep 12, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 21 : Thu, Sep 13, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 22 : Tue, Sep 18, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 23 : Wed, Sep 19, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 24 : Fri, Sep 21, 02:00 pm-02:50 pm
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 25 : Wed, Sep 26, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 26 : Fri, Sep 28, 02:00 pm-02:50 pm
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 27 : Thu, Oct 04, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 28 : Tue, Oct 09, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 29 : Wed, Oct 10, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 30 : Fri, Oct 12, 02:00 pm-02:50 pm
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 31 : Tue, Oct 16, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 32 : Thu, Oct 18, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 33 : Tue, Oct 23, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 34 : Wed, Oct 24, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 35 : Thu, Oct 25, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 36 : Fri, Oct 26, 02:00 pm-02:50 pm
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 37 : Tue, Oct 30, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 38 : Thu, Nov 01, 08:00 am-08:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 39 : Fri, Nov 02, 02:00 pm-02:50 pm
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 40 : Tue, Nov 06, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 41 : Wed, Nov 07, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 42 : Fri, Nov 09, 02:00 pm-02:50 pm
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 43 : Tue, Nov 13, 11:00 am-11:50 am
References | |
Exercises | |
Reading | |
To Be Announced
- Meeting 44 : Wed, Nov 14, 10:00 am-10:50 am
References | |
Exercises | |
Reading | |
To Be Announced