Advanced Data Structures and Algorithm Analysis
分享
课程详情
课程评价
spContent=Still feel hungry after finishing the fundamentals of Data Structures? Want more challenge on writing more complicated programs? Here is the right place for you! As a matter of fact, all the lectures were recorded during the COVID-19 pandemic, starting from February, 2020, when everyone was in quarantine and we, the instructors, were asked to teach online. I decided to record my lectures for the convenience of my students, so they could study at anywhere and at anytime they wanted. I did this also because I was so optimistic to think that everything would get back to normal in a month, and that I would only have to record three or at most four lectures… Anyway, here we are. If you are curious about how it feels like as a ZJU student taking this advanced course, come on in.
—— 课程团队
课程概述

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 DesignJon Kleinberg, Eva Tardos, Addison Wesley, 2005