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 | Best & Worst Case Analysis Explained |
| Step-by-Step Analysis of Insertion Sort | ||
| Week 2 | Asymptotics | Asymptotic Analysis Explained |
| Week 3 | Divide and conquer | Recurrence Relations & Recurrence Tree Method |
| Master Theorem Explained with Examples | ||
| Week 4 | Quick sort and probability analysis | Understanding Quicksort |
| Average-Case Complexity, Expected Value & Randomized Quicksort | ||
| Week 5/6 | Heaps | Understanding Heap Properties |
| Insert & Peek Methods Explained | ||
| Delete Method Explained | ||
| Building a Heap & Mastering Heap Sort | ||
| Week 7 | Hashtables | How Hash Functions Work |
| Understanding Open Addressing | ||
| Understanding Chaining | ||
| Week 8 | Binary search trees | Search Operation & Time Complexity Explained |
| The Insert Method Explained | ||
| The Delete Method Explained | ||
| Traversal | ||
| Week 9 | Amortized analysis | Aggregate Method Explained with Examples |
| Accounting Method Explained with Examples | ||
| Potential Method Explained with Examples |