Thinking Algorithmically
Develop problem-solving skills: break down problems, write pseudocode, and design solutions.
Prerequisites
An algorithm is a step-by-step procedure for solving a problem. Before writing code, you need to figure out the steps. This skill—breaking problems into solvable pieces—is the core of programming.
Problem Decomposition
Big problems are scary. Small problems are manageable. The trick is breaking the big one into small ones.
Example: Build a program that finds the most common word in a text file.
- Read the file contents
- Split the text into words
- Count how many times each word appears
- Find the word with the highest count
- Return that word
Now each step is a small, solvable problem. You can tackle them one at a time.
Pseudocode
Pseudocode is a way to plan your algorithm in plain English before writing real code:
FUNCTION find_most_common_word(filename):
READ contents of filename
SPLIT contents into list of words
CREATE empty dictionary for word counts
FOR EACH word in words:
IF word is in dictionary:
INCREMENT its count
ELSE:
SET its count to 1
FIND the word with highest count
RETURN that wordNow translating to Python is straightforward:
def find_most_common_word(filename):
with open(filename, "r") as file:
contents = file.read()
words = contents.lower().split()
word_counts = {}
for word in words:
if word in word_counts:
word_counts[word] += 1
else:
word_counts[word] = 1
most_common = max(word_counts, key=word_counts.get)
return most_commonCommon Algorithm Patterns
Accumulator Pattern
Build up a result by processing items one at a time:
# Sum all numbers
total = 0 # Accumulator
for num in numbers:
total += num
# Build a string
result = ""
for word in words:
result += word + " "
# Collect matching items
evens = []
for num in numbers:
if num % 2 == 0:
evens.append(num)Search Pattern
Look through data to find something:
# Find first match
def find_first_negative(numbers):
for num in numbers:
if num < 0:
return num
return None # Not found
# Find all matches
def find_all_negatives(numbers):
result = []
for num in numbers:
if num < 0:
result.append(num)
return result
# Check if any match
def has_negative(numbers):
for num in numbers:
if num < 0:
return True
return FalseTransform Pattern
Convert each item to something else:
# Square each number
def square_all(numbers):
result = []
for num in numbers:
result.append(num ** 2)
return result
# Or with list comprehension
def square_all(numbers):
return [num ** 2 for num in numbers]Working Through a Problem
Let's solve: "Find all pairs of numbers in a list that sum to a target value."
# Step 1: Understand the problem
# Input: [1, 2, 3, 4, 5], target = 6
# Output: [(1, 5), (2, 4)] # pairs that sum to 6
# Step 2: Think of examples
# [1, 2, 3], target = 4 -> [(1, 3)]
# [1, 1, 1], target = 2 -> [(1, 1), (1, 1), (1, 1)]? Or just [(1, 1)]?
# Clarify: do we count duplicates? Let's say yes.
# Step 3: Plan the algorithm
# For each number, check if (target - number) exists in the rest
# If yes, add the pair to results
# Step 4: Write pseudocode
# FOR i from 0 to length-1:
# FOR j from i+1 to length:
# IF numbers[i] + numbers[j] == target:
# ADD (numbers[i], numbers[j]) to results
# Step 5: Implement
def find_pairs(numbers, target):
pairs = []
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] + numbers[j] == target:
pairs.append((numbers[i], numbers[j]))
return pairs
# Step 6: Test
print(find_pairs([1, 2, 3, 4, 5], 6)) # [(1, 5), (2, 4)]
print(find_pairs([1, 2, 3], 4)) # [(1, 3)]
print(find_pairs([1, 1, 1], 2)) # [(1, 1), (1, 1), (1, 1)]Practice Problems
- Find the second largest number in a list (without using sort)
- Check if a list is sorted in ascending order
- Find all duplicate values in a list
- Implement binary search on a sorted list
- Generate all permutations of a string