2110712 Analysis of Algorithms

สัปดาห์ที่ เนื้อหา เอกสาร
1 Introduction  
2 Searching : Jump search, binary search, randomized linear search, interpolation search Compare to What? (Rawlins) : Ch. 2
3 Selection : Finding max, Finding 2nd max, Finding min & Max. Compare to What? (Rawlins) : Ch. 3
4 Sums : Manipulation of sums (changing index, perturbation), Multiple sums, General methods (SLOAN, Guess+Prove, Perturb the sum, build a repertoire, replace sums by integrals, expand and contract, use finite calculus, use generating function), Finite Calculus Concrete Math. (GKP) : Ch. 2
5 Recurrences : Summing factor, Annihilator, Domain & Range transformations Jeff Erickson's notes on solving recurrences
6 Recurrences : Repertoire (Josephus prob), full-history recurrences (quicksort, Spans of fans), Reduction of orders, Divide & Conquer Concrete Math. (GKP) : Ch. 1,
Ana of Algo. (Flajolet & Sedgewick) : Ch. 2
7 Generating Function OGF, Domino &Change, Basic Maneuvers, Solving recurrences (Catalan numbers), EGF, Taylor expansion Concrete Math. (GKP) : Ch. 7
8 Symbolic methods  Unlabelled objects (sum, product, sequence, set) : Binary string, binary trees, general trees, forest, Labelled objects (sum, product, sequence, set, cycle) : permutations & set of cycles, derangement, nonplane labelled tree, Lagrange inversion Ana of Algo. (Flajolet & Sedgewick) : Ch. 3


9 PGF, BGF, CGF :  avg. number of 1-bits in binary strings, avg. number of leaves in binary tree, avg. internal path length in binary tree Ana of Algo. (Flajolet & Sedgewick) : Ch. 3
10 Asymptotic Approximation :  notations, expansions, manipulating techniques, approximation of sums, Euler-Maclaurin summation Ana of Algo. (Flajolet & Sedgewick) : Ch. 4
12 Asymptotic Estimates : recurrence (master's theorem), generating function (radius of convergence, principle of nice singularities) Foundations of Combinatorics ( Bender & Williamson) : Ch.11.4
13 Amortized Analysis : (aggregate, accounting, potential methods), binary counter, dynamic table, binomial heap, lazy binomial heap Intro. to Algo. (CLRS) : Ch. 18, 20
14 Amortized Analysis : Fibonacci heap, disjoint sets Intro. to Algo. (CLRS) : Ch. 21, 22


Herbert S. Wilf
Concrete Mathematics: A Foundation for Computer Science
by Ronald L. Graham, Donald E. Knuth, Oren Patashnik
(ห้องสมุดภาคฯ มี)
An Introduction to the Analysis of Algorithms,
Robert Sedgewick, Philippe Flajolet
(ห้องสมุดภาคฯ มี)
Analysis of Algorithms,
Jr. Paul Purdom
, Cynthia A. Brown
(ถ้าจำไม่ผิด ห้องสมุดภาคคณิตฯ มี)
The Art of Computer Programming Vol. 1
Donald E. Knuth
(ห้องสมุดภาคฯ มี)
The Art of Computer Programming, Vol. 3
Donald E. Knuth
(ห้องสมุดภาคฯ มี)
Selected Papers on Analysis of Algorithms,
Donald E Knuth
(อภินันทนาการจาก อ.ประภาส)
Compared to What?: An Introduction to the Analysis of Algorithms,
Gregory J. E. Rawlins, Gregory J. Rawlins
(อภินันทนาการจาก อ.ธงชัย)
Introduction to Algorithms
Thomas H. Cormen, Ronald L. Rivest, Charles E. Leiserson, Clifford Stein
(ห้องสมุดภาคฯ มี)
Randomized Algorithms
Rajeev Motwani, Prabhakar Raghavan
(ห้องสมุดภาคฯ มี)
Average Case Analysis of Algorithms on Sequences
Wojciech Szpankowski
(อ่าน draft version)



สมชาย ประสิทธิ์จูตระกูล