An algorithm is a step-by-step process to achieve some outcome. When algorithms involve a large amount of input data, complex manipulation, or both, we need to construct clever algorithms that a computer can work through quickly.
By the end of this course, you’ll have mastered the fundamental problems in algorithms.
Building Blocks: The nuts and bolts of how computer scientists communicate algorithmic ideas.
Pseudocode: Start your study of algorithms by learning about this key aspect of how computer scientists communicate.
Conditional Algorithms: All interesting algorithms perform tests, and react in different ways based on the results of those tests.
Repetition: Performing simple actions repeatedly is at the heart of every interesting algorithm.
Storing Information: Arrays are a fundamental way of storing information.
Manipulating Numbers: Most algorithms store and manipulate numbers using assignable variables.
Arrays: Arrays are critical for understanding algorithms that manipulate collections of information.
Searching an Array: Arrays can store lots of information. To find out what's there, you just have to look!
Array Algorithms: Master repetition through understanding algorithms that manipulate arrays.
Binary Search: Looking in the middle of a sorted array requires a bit of cleverness, but it can save you a lot of work.
Sorting an Array: Sorting an array with selection sort unlocks the power of binary search.
Insertion Sort: There's more than one way to sort an array. Insertion sort is another classic algorithm for sorting.
Stable Matching: You now have the tools to understand and reason about important algorithms, including algorithms that can change the course of people's lives.
The Stable Matching Problem: Discover a simple problem faced by every teaching hospital and medical student every year.
Using Greediness: An individual applicant can make the best decision with a greedy algorithm.
Deferred Acceptance Algorithm: The Gale-Shapley algorithm uses individual greedy decisions to produce a global matching.
Algorithmic Complexity: We will analyze the Gale-Shapley algorithm to show that is correct and always finishes.
Correctness: An algorithm for producing a stable matching is only good if it outputs a stable matching!
Termination: A good algorithm can't just promise that it will do the right thing if it finishes. A good algorithm actually has to deliver.
Variants: Transition from an oversimplified problem to one that's much more like the real world.