Week 1 kicked off the course with a series of lectures on some fundamental concepts in algorithm design and analysis, which should provide a foundation for the rest of the course. Topics covered include what an algorithm actually is, how to analyze an algorithm, pseudocode conventions, and common data structures we’ll be using, like graphs and trees.
What an algorithm is
While there is no universally-agreed definition for what an algorithm actually is, the textbook provides the following:
An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time.
From this definition, we can extract five properties of an algorithm:
- It solves a problem
- It takes a well-defined input
- It produces a well-defined output
- It requires a finite amount of time to run
- It is comprised of a sequence of clear instructions
One thing to keep in mind is that there is a difference between an algorithm and a procedure. A procedure may contain vague instructions, but an algorithm leaves nothing ambiguous; every step in an algorithm must be clearly defined.
Introduction to Algorithm Analysis
Algorithm analysis considers both time and space, but for this course, we will focus on time complexity. We care mostly about the order of growth. The handout presents eight common time efficiency classes.
| Name | Sample Function | Example |
|---|---|---|
| Constant time | 1 | Looking up an item in a hash table |
| Logarithmic time | log n | Binary search in a sorted array with n numbers |
| Linear time | n | Summing n numbers in an array |
| Linearithmic time | n * log n | Merge sort |
| Quadratic time | n² | Bubble sort |
| Cubic time | n³ | Multiplication of two n x n matrices |
| Exponential time | 2ⁿ | Tower of Hanoi problem with n disks |
| Factorial time | n! | TSP (Traveling Salesman Problem) using a brute-force approach |
Homework
Finding the shortest distance between two numbers
This homework problem involved reading a list of distinct integers and finding the smallest distance between any two of them.
The brute-force approach would compare all pairs against each other, which would take quadratic time. The trick to solving this problem efficiently is to sort the numbers first, so that once the numbers are in order, the closest pairs are adjacent.
Java’s Arrays.sort contributes n log n to the running time, making it the algorithm’s basic operation. Once the array of integers is sorted, the closest pair can be found in linear time.
Finding the intersection of a set of ranges
This homework problem involved reading a set of integer ranges and finding their intersection. To solve this problem, you need to find the maximum lower bound and the minimum upper bound of the input sets. If the maximum lower bound is less than or equal to the minimum upper bound, then there is a valid intersection, otherwise there is no valid intersection. This only takes a single pass, running in linear time.