This course is based on the fundamentals of data structures. We are going to continue investigating the definitions, implementations, and algorithms related to non-numerical data objects. The content of this course consists of two parts: the first part is for advanced data structures, such as the variations of binary search trees and the inverted file index for searching big data sets, and various optimizations of the priority queues and the amortized analysis; the second part is for classical algorithms, such as back tracking, divide and conquer, dynamic programming, greedy, together with approximation methods, local search, and randomized algorithms. Parallel algorithms and external sorting will be introduced as well. Students are supposed to learn how to solve complicated problems with advanced programming skills, and how to give the performance a mathematical analysis, and hence build a firm foundation for studying further theories in computer science.
This advanced course was designed for the sophomore students in Zhejiang University, with the course “Fundamentals of Data Structures” being its prerequisite. To the general audiences, these are the knowledge points that I would suggest you to master, before taking this course: knowledge on integrals and probability theory, the concept of abstract data type, linear lists, trees, graphs, and some fundamental algorithms for sorting and searching (i.e. hashing). Especially, if you are a college student who has studied these data structures, then you are ready to go.
1. Introduction to Algorithms, 3rd Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. The MIT Press. 2009
2. Data Structure and Algorithm Analysis in C, 2nd Edition, M.A.Weis. Addison Wesley Longman, 1997
3. Algorithm Design,Jon Kleinberg, Eva Tardos, Addison Wesley, 2005