This course is offered by NYU Tandon school of Eningeering(All the concepts are the same as Design and Analysis of Algorithms I(Tandon Engineering)/ Fundamental Algorithms(Courant CDS)/ Fundamental Algorithms(Courant CS)). I took this course at 2021 Fall semester with Liu Yong as the instructor. This course has the same schedule and course materials as the MIT advanced data structure. I post all the course materials and exam paper to this repository.
• Week 1: Introduction to algorithm: correctness and performance. Best-, worst-, and average-case performance. Asymptotic notation: big-O, big-Ω, and big-Θ; little-o, and little-ω.
• Week 2: Recurrence and solving methods: iteration, substitution and master theorem
• Week 3: Divide and conquer algorithms, introduction to sorting: insertion sort, bubble sort
• Week 4: Sorting: MergeSort, Heap and HeapSort,
• Week 5: Sorting: quick sort, randomized algorithms, lower bound for comparison sorting, counting sort and radix sort, order statistics and selection
• Week 6: Hashing and Universal Hashing, Binary search trees
• Week 7: Binary search trees (cont.d), midterm review
• Week 8: Midterm Exam
• Week 9: Graph basics, Breath-First Search, Depth-First Search
• Week 10: Directed-acyclic graph and topological ordering, strongly connected components,
• Week 11: Intro to dynamic programming, greedy algorithm
• Week 12: Greedy algorithm, Huffman coding, Minimum Spanning Tree
• Week 13: Single-source shortest paths, all-pairs shortest paths
• Week 14: NP-Completeness and Final Review
• Week 15: Final Exam
Great professor and well scheduled lectures. 12 Assignments help you get more familiar with the concepts. Great mid/final exam papers combining easy questions(Basic concepts) and extremly difficult questions together(Last two questions eg: Dynammic Programming, graphic data structure proof, analysis of new data structure).
All the algorithm and code are pseudocode. Personally, I think this course will be better to reduce the assignments and replace them to Java implementation/LAB of the data structure.
Only 10% student get A in Liu Yong's course.