Basics - Analyzing Algorithms Part II
In this lesson, we’ll dry run insertion sort and count the instructions executed on an array of length 5.
Formal Analysis Tools - Functions and Their Growth
This lesson discusses the building blocks for analyzing algorithms.
Basics - Problem Set 1
Practice problems to hone analysis skills.
Basics - Analyzing Algorithms Part III
In this lesson, we will work out a generalization for the number of instructions executed for an array of length n
Basics - Introduction
This chapter lays the groundwork for the material covered in the course and sets out the expectations for the readers.
Basics - Need for Speed
This chapter discusses analogies from real life to draw a parallel between algorithmic complexity and comparisons we make in day to day situations.
Recursive - Problem Set 3
Questions to understand recursive complexity analysis
Recursive - Dynamic Programming
This chapter works on a sample dynamic programming problem to show how complexity for this class of problems can be worked out.
Recursive - Binary Search - Recursive Implementation
This chapter details the reasoning behind binary search’s time complexity
Recursive - Recurrence Part II
This chapter continues the discussion on analyzing the complexity of recursive algorithms.
Recursive - Permutations
This chapter shows how one can reason about recursive problems without extensive mathematical knowledge
Formal Analysis Tools - Problem Set 2
Practice problems relating to analysis notations.
Recursive - Recurrence
This chapter introduces recursive algorithms and how they can be analyzed.
Probabilistic Analysis - The Tinder Problem
This lesson discusses a sample problem and works out the complexity using probabilistic analysis.
Probabilistic Analysis - Expected Value of a Random Variable
This chapter discusses the expected values of random variables and how to calculate them.
Amortized Analysis - Solution Set 5
Solutions to problem set 4
Amortized Analysis - Fancy Stack
In this chapter, we discuss the complexity of various operations of a stack which supports a multipop operation.
Probabilistic Analysis - Quantifying Chance & Randomness
This chapter discusses pre-requisite concepts for undertaking probabilistic analysis.
Probabilistic Analysis - Random Variables
This chapter discusses random variables.
Recursive - Solution Set 3
Solutions to problem set 3
Amortized Analysis - Dynamic Array
This chapter discusses the time complexity of insert operations on a dynamic array.
Amortized Analysis - Problem Set 5
Questions to practice amortized analysis.
Probabilistic Analysis - Probability Distribution
This chapter discusses the concept of probability distribution.
Complexity Theory - Between P and NP ?
Do any problems exist that aren’t NP-complete and not in P?
Complexity Theory - Problem Set 6
Questions to test understanding of P/NP problems.
The End - Epilogue
Have questions about Epilogue? Go for it!
Complexity Theory - NP-Complete and NP-Hard
In this chapter we further the discussion on complexity theory with NP-complete and NP-hard complexity classes.
Basics - Analyzing Algorithms
We start our journey into the world of complexity by analyzing the insertion sort algorithm.
Formal Analysis Tools - Theta Notation
We formally introduce theta notation, which forms the basis of mathematical analysis of algorithms.
Recursive - Top Down and Bottom Up Approaches
This chapter continues the discussion on the complexity of dynamic programming problems.
Formal Analysis Tools - Solution Set 2
Solutions to problem set 2.
Complexity Theory - Why should I bother?
This chapter gives an introduction to complexity theory.
Complexity Theory - P and NP classes
In this lesson, we discuss the two most important complexity classes P and NP.
Formal Analysis Tools - Big O and Big Omega Notations
Discusses the Big O notation with examples
Data-Structures - Linked List
This lesson discusses the complexity of operations on a linked list.
Data-Structures - Array
This lesson talks about the complexity of operations on an array.
Data-Structures - Hash Table
This chapter discusses operations on hash tables.
Data-Structures - Doubly Linked List
This section explores operations on a doubly linked list
Data-Structures - Stacks and Queues
This lesson talks about operations on stacks and queues.
Data-Structures - Solution Set 4
Solutions to problem set 4.
Data-Structures - Problem Set 4
Have questions about Problem Set 4? Go for it!
Data-Structures - Tree Structures
This lesson is a general discussion on reasoning about space and time complexity of tree structures
Complexity Theory - Get Rich with Complexity
In this lesson, we discuss the famous is P=NP dilemma.
The End - Cheat Sheet
This is a compilation of worst-case complexities for various data-structures and algorithms.
Amortized Analysis - Cost Over Sequence of Operations
This chapter introduces the reader to aggregate analysis of algorithms.
Formal Analysis Tools - Small omega and Small o Notations
In this lesson, we discuss notations which imply loose bounds.