Advanced Algorithm Design and Analysis (2011.2 ~ 2011.6)

Instructor: Dr. Jiaheng Lu
Department of Computer Science, Renmin University of China

Course Goals

This course will be taught in English. It will introduce master and PhD students to some advanced topics in algorithm, mainly in theory. Students will learn topics about graph algorithm, computing complexity, lanuage and formal grammar. Significant reading, reviewing, and writing will be required, and students will be expected to participate actively in class discussions, to give an English presentation.

Time and Place

Thursday 6:00-8:15PM , Information Building 0125

Textbooks

Many online tutorials.

Grading Policy

Presence in class 20
In-class Quizzes 40
Final Examination 40
Total 100%

Lecture Notes

Lecture Number Topic Notes
01 Overview of Class and graph algorithm Lec01
02 Heap Algorithms Lec02
03 Amortized Analysis (1) Lec03, heapExample
04 Amortized Analysis (2) and Binomial Heaps Lec04
05 Fibonacci heaps Lec05, Fibonacci heaps
06 NP-complete Lec06
07 Cook Theorem Lec07, TM Example
08 NP-hard and Big-O notation Lec08, Big-O notation
09 Approaximation algorithm 1 Lec09
09 Approaximation algorithm 2 Lec10

Reading material

  • Computing complexity Wiki site
  • Student name list

    • For any problems, questions or suggestions about this page, please contact jiahenglu + AT + gmail.com Rev. Tuesday, Feb 13, 2010