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: