Algorithm Fundamentals

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.