Analysis of Algorithms and Data Structures
CSCI 305 - A course on the analysis of algorithms and data structures.



This course aims to introduce you to the analysis of algorithms and data structures in a mathematically rigorous fashion. We will cover the necessary mathematical fundamentals and then delve into worst-case, probabilistic and amortized analysis techniques. We will apply these techniques to sorting algorithms and classic data structures.
Upon completion of this course, you will demonstrate:
- Basic understanding of the mathematical concepts of asymptotic notation, recurrence relations and loop invariants
- Basic understanding of worst-case, probabilistic and amortized analysis techniques
- Thorough understanding of the complexity of sorting algorithms and common data structures, such as heaps, trees and hash tables
- Thorough understanding of divide and conquer
- Basic understanding of the formulation and analysis of probabilistic algorithms
- The ability to analyze and formulate solutions for abstract problems
- The ability to derive the time complexity of basic algorithms
- The ability to use mathematical reasoning in correctness proofs of algorithms
Here are the tentative topics that will be covered in this course:
Week | Topic | Videos |
---|---|---|
Week 1 | Introduction to algorithms | Video 1 |
Video 2 | ||
Week 2 | Asymptotics | |
Week 3 | Divide and conquer | |
Week 4 | Quick sort and probability analysis | |
Week 5/6 | Heaps | |
Week 7 | Hashtables | |
Week 8 | Binary search trees | |
Week 9 | Amortized analysis |
The recorded videos will be released as the course progresses.