Data Structures and Algorithms in Python
Analyse, implement and test the core data structures and algorithms in Python, from hash tables and heaps to graph search and dynamic programming.
Intermediate · Computer Science · about 19 hours · 5 modules · certificate on completion
Taught by Bintà Yusupovà, Kaimànà Kahananùi, AI Learning Companions.
About this course
Data structures and algorithms are the toolkit behind fast, dependable software: knowing what a dictionary lookup costs, when a heap beats sorting, or how to turn an exponential recursion into a quick table is what separates code that copes with real data from code that grinds to a halt. This course teaches that toolkit in Python, with analysis and testing throughout. You'll learn Big-O and check it with doubling tests, see what Python's lists, dictionaries and sets really cost, and build the classic structures yourself: linked lists, stacks and queues, binary search trees and binary heaps. Then you'll explore graphs with breadth-first and depth-first search, topological sort and Dijkstra's algorithm, and finish with sorting, binary search, recursion and dynamic programming.
Every module has a lab in which you implement the ideas and prove them with pytest, and each lab counts the work done, so you see quadratic, linear and logarithmic growth for yourself instead of taking it on trust. The capstone, a tested journey planner for a transit network, brings it all together: graph search for routes, binary search over timetables, a heap for the busiest stops and dynamic programming for the cheapest fares. The course builds on Python Programming with PyCharm; afterwards, System Design Fundamentals: Scale, Caching and Load Balancing applies these structures to whole systems, and Concurrency and Asynchronous Programming in Python covers doing work in parallel.
What you'll learn
- Analyse running time and memory with Big-O, and check the analysis with doubling tests
- Choose the right Python structure (list, dict, set, deque or heap) and predict what it costs
- Implement and test linked lists, binary search trees and binary heaps
- Solve problems with two pointers, sliding windows, stacks and binary search
- Find routes with BFS and Dijkstra's algorithm, and order tasks with topological sort
- Design recursive and dynamic programming solutions, and reconstruct their answers
Skills you'll gain
Algorithm analysis (Big-O), Hash tables, Stacks and queues, Linked lists, Trees and heaps, Graph algorithms, Sorting and searching, Recursion, Dynamic programming, Testing with pytest
Tools
Python, pytest
Before you start
Python Programming with PyCharm, or equivalent experience: functions, classes, lists, dictionaries and loops, and running pytest. School algebra (powers and logarithms) helps. Install Python 3.10 or newer and pytest (python -m pip install pytest); any editor works.
Modules
Complexity, arrays and hashing
Learn to reason about how running time and memory grow with the input, then see what Python's lists, dictionaries and sets cost and how hashing turns slow searches into fast lookups.
- Big-O and counting operations (13 min)
- Python lists as dynamic arrays (12 min)
- Hash tables: dictionaries and sets (14 min)
- Hands-on lab: Measure growth and replace nested loops with hashing
Stacks, queues and linked lists
Use stacks and queues for the problems they fit, build a linked list to practise pointer manipulation, and learn the two-pointer and sliding-window techniques that turn quadratic scans into linear ones.
- Stacks and queues (12 min)
- Linked lists (13 min)
- Two pointers and sliding windows (13 min)
- Hands-on lab: Build a linked list and solve problems in linear time
Trees and heaps
Work with hierarchical data: traverse binary trees recursively and iteratively, keep data searchable in a binary search tree, and use binary heaps, and Python's heapq, as priority queues.
- Binary trees and traversals (13 min)
- Binary search trees (13 min)
- Heaps and priority queues (13 min)
- Hands-on lab: Build a binary search tree and a binary heap
Graphs: BFS, DFS and Dijkstra
Model networks as graphs, explore them breadth-first and depth-first, put tasks in order with topological sort, and find the shortest weighted routes with Dijkstra's algorithm.
- Representing graphs, and breadth-first search (13 min)
- Depth-first search and topological sort (13 min)
- Dijkstra's algorithm and weighted shortest paths (14 min)
- Hands-on lab: Plan routes on a ferry network
Sorting, searching, recursion and dynamic programming
Understand how the main sorting algorithms work and when Python's built-in sort is the answer, search sorted data and monotonic questions with binary search, and solve problems with recursion, memoisation and dynamic programming.
- Sorting algorithms (13 min)
- Binary search (12 min)
- Recursion, divide and conquer, and backtracking (13 min)
- Dynamic programming (15 min)
- Hands-on lab: Sort, search and solve with dynamic programming
Project: Build and test a transit journey planner
A city's transit authority wants a journey planner that is fast and demonstrably correct. make_network.py generates its network: stops, the edges between consecutive stops on each line with travel minutes, every departure of every line at every stop, and 20,000 passenger tap-ins. Build planner.py, a library with a small command-line interface, and test it with pytest. It must load the network into an adjacency list; find the route with the fewest rides between two stops (BFS) and the fastest one (Dijkstra, ignoring waiting time); find the next departure from a stop after a given time with binary search over each stop's sorted timetable; list the ten busiest stops from the tap-ins with a heap; and work out the cheapest way to buy at least N rides from single tickets (2.00), 10-ride packs (18.00) and 30-ride packs (50.00) with dynamic programming. As a stretch, compute the earliest arrival with waiting included, using a time-dependent Dijkstra that waits for the next departure at each stop. On the default network your planner should report that S001 to S060 takes three rides and 13 minutes, that the next departure from S001 after 08:00 is line L3 (out) at 08:01, that the busiest stops are S014, S033 and S024, and that 47 rides cost 82.00. Then measure it: generate networks with --stops 200, 400 and 800 (and lines to match), time each operation, and compare the growth with your analysis.
Part of
The products this course names are trademarks of their owners, who haven't made or endorsed it.