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.