This class will introduce students to algorithmic thinking.
TODAY'S AGENDA
No sections found on this page yet.
Algorithms vs. Programs
The idea comes before the code
An important distinction is that an algorithm is not the same thing as a program.
An algorithm is the underlying procedure for solving the problem. A program is one implementation of that algorithm in a particular programming language.
For example, the algorithm for finding the largest number does not care whether we implement it in Python, JavaScript, C++, Java, or some future programming language that hasn't been invented yet.
The algorithm is the idea.
The program is the implementation.
Here is one Python implementation of the largest-number algorithm:
largest_number.py · python
def find_largest(numbers):
largest = numbers[0]
for number in numbers:
if number > largest:
largest = number
return largest
scores = [7, 12, 4, 19, 3, 15]
print(find_largest(scores))
Finding the largest value in a list The important thing is that the algorithm existed before we wrote this particular implementation.
You could implement exactly the same algorithm in another language without changing the underlying idea.
Pseudocode
Programming without worrying about syntax
Before writing actual code, computer scientists often use pseudocode to describe an algorithm.
Pseudocode is deliberately informal. It lets us focus on the logic instead of worrying about whether we remembered a semicolon or used the correct syntax for a particular programming language.
For example, the algorithm for finding the largest number can be summarized as:
Start with the first number as the largest so far.
Look at each remaining number.
If the number is larger than the current largest, update the largest value.
Return the largest value.
Once we understand that logic, translating it into Python becomes relatively straightforward.
This separation between algorithm and implementation is important. If you start coding before you understand the algorithm, you can easily end up debugging code that was based on a flawed idea.
Linear Search
The simplest search algorithm
SEARCHING
Let's say we have a list: We want to find .
A linear search simply starts at the beginning and checks each item.
Here is a Python implementation:
linear_search.py · python
def linear_search(numbers, target):
for i in range(len(numbers)):
if numbers[i] == target:
return i
return -1
numbers = [14, 7, 23, 4, 18, 9, 31]
print(linear_search(numbers, 18))
print(linear_search(numbers, 100))
Searching through a list one item at a time The first search returns the position of . The second returns because is not in the list.
In the worst case, we might have to inspect every item.
If there are items, the maximum number of comparisons is approximately: This is a linear-time algorithm.
Binary Search
Throwing away half the problem
SEARCHINGDIVIDE-AND-CONQUER
Now imagine that our list is sorted: We want to find .
Instead of starting at the beginning, we can look at the middle.
The middle value is .
Since , we immediately know that 38 cannot be anywhere in the left half of the list.
Searching a sorted list by repeatedly eliminating half the possibilities The key idea isn't simply "look at the middle." The important idea is eliminating half of the remaining possibilities after every comparison.
Comparing the Searches
Same problem, radically different strategy
Let's put the two algorithms side by side.
Linear search: Look at items one at a time until you find the target.
Binary search: Look at the middle item and eliminate half of the remaining possibilities.
We can even write a small program that compares the number of comparisons:
search_comparison.py · python
def linear_search_count(numbers, target):
comparisons = 0
for number in numbers:
comparisons += 1
if number == target:
return comparisons
return comparisons
def binary_search_count(numbers, target):
low = 0
high = len(numbers) - 1
comparisons = 0
while low <= high:
middle = (low + high) // 2
comparisons += 1
if numbers[middle] == target:
return comparisons
elif numbers[middle] < target:
low = middle + 1
else:
high = middle - 1
return comparisons
Counting comparisons made by linear and binary search For small lists, the difference may seem unimportant.
For enormous lists, the difference can become the difference between a computation that finishes almost instantly and one that takes a very long time.
Big-O in Code
Connecting programs to complexity
We can now start recognizing Big-O directly in programs.
Consider this function:
linear_example.py · python
def process(numbers):
for number in numbers:
print(number)
A loop whose work grows with the input If the list contains items, the loop runs approximately times. We say this algorithm runs in time, or "Big-O of n."
Now consider:
quadratic_example.py · python
def compare_every_pair(numbers):
for first in numbers:
for second in numbers:
print(first, second)
Nested loops create quadratic growth The outer loop runs times, and for every iteration of the outer loop, the inner loop also runs times.
Therefore the total work is approximately , or
"Big-Oh" notation might seem a bit vague to you, so here is a more precise mathematical definition:
For two functions and , is in if there exist positive constants and such that
is the algorithm: This function represents the actual number of operations (time) or memory units (space) your code uses for an input of size n.
is the complexity class: This is a simplified baseline function (like , , or ) used to categorize the algorithm.
ignores small inputs: Algorithms often act weirdly with tiny inputs due to setup costs. The threshold means we only care about performance when the input gets large.
The constant ignores hardware: Different computers run at different speeds. The constant acts as a buffer that absorbs hardware differences, compiler optimizations, and minor code details.
Constant Time
When input size doesn't matter
Consider a list and an operation that accesses one particular element:
constant_time.py · python
def get_first(numbers):
return numbers[0]
Accessing an array element Whether the list contains 10 items or 10 million items, this operation performs essentially the same amount of work.
We describe this as: Constant time does not mean "takes exactly one second." It means that the amount of work does not grow with .
The Complexity Zoo
From friendly to terrifying
Here is a useful mental model for the most common growth rates:
Complexity
Name
Example
Constant
Accessing an array element
Logarithmic
Binary search
Linear
Linear search
Linearithmic
Efficient sorting algorithms
Quadratic
Comparing every pair
Exponential
Some brute-force algorithms
You don't need to memorize all of these today. The important thing is to start recognizing the general shapes of these growth rates.
A Mini Algorithm Lab
Find the duplicate
Let's return to the problem from earlier.
You have a list of student scores and need to determine whether any two students received exactly the same score.
For example: There are two students with a score of 92, so the answer should be yes.
One straightforward solution is to compare every pair:
duplicates_slow.py · python
def has_duplicate(numbers):
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] == numbers[j]:
return True
return False
Checking every pair of scores This works, but notice the nested loops.
That should immediately make you suspicious of:
A Faster Approach
Use a data structure to remember what you've seen
Instead of comparing every pair, we can remember the scores we have already encountered.
In Python, a set is useful for this:
duplicates_fast.py · python
def has_duplicate(numbers):
seen = set()
for number in numbers:
if number in seen:
return True
seen.add(number)
return False
Using a set to detect duplicates Conceptually, we are doing something very different:
Look at a score.
Ask whether we've already seen it.
If yes, we found a duplicate.
If no, remember it and continue.
This approach can run in approximately: assuming the set provides approximately constant-time membership checks.
But notice the tradeoff: we are using additional memory to make the algorithm faster.
The Algorithmic Thinking Workflow
A repeatable method for solving problems
PROBLEM-SOLVING
When you encounter a new programming problem, try using this workflow:
Understand the problem. What are we actually being asked to accomplish?
Identify the inputs. What information do we have?
Define the output. What does a correct answer look like?
Break the problem apart. What smaller problems can we solve independently?
Design an algorithm. Describe the steps before writing code.
Test the algorithm. Try ordinary cases, unusual cases, and edge cases.
Analyze the algorithm. How much time and memory does it require?
Implement it. Only now should we worry about programming syntax.
This workflow is going to become a habit over the next six classes.
Quiz//Question 1 OF 4
SCORE: 0
Q1. What is the Big-O complexity of a function containing one loop that processes every item in a list?
Final Challenge: Design Before You Code
Putting it all together
Your final challenge is deliberately open-ended.
Imagine you are given a list containing the temperatures recorded by a weather station over several years.
You need to answer three questions:
What was the highest temperature?
What was the lowest temperature?
Did any temperature occur more than once?
You could solve all three problems using separate passes through the data. Or you might design one algorithm that answers all three questions during a single pass.