Data Structures and Algorithmic Complexity
Data Structures and Complexity is an intermediate-level course of 5 lessons (about 3 h 10 min), with 15 exercises and 15 quiz questions. Prerequisites: Programming Basics and Algorithms. Exercises run in the browser, with nothing to install.
- Foundations
- Intermediate
- 5 lessons
- 3 h 10 min
- 15 exercises
- Exercises run in the browser
The course in brief
This course teaches you to evaluate the cost of an algorithm and to choose the right data structure for each problem. In Python, you implement binary search, linear-time solutions using hashing, stacks, queues, priority queues and graph traversals. A key skill for technical interviews as well as for applications that need to scale.
What you will be able to do
- Analyze the time and space complexity of an algorithm using Big O notation
- Know the cost of operations on list, dict, set, deque and heapq
- Implement binary search and take advantage of sorting
- Replace quadratic solutions with linear ones using hashing
- Use stacks, queues and priority queues to process items in the right order
- Represent a graph and traverse it breadth-first and depth-first
Syllabus: 5 lessons
- Estimate the number of operations an algorithm performs as a function of input size
- Use Big O notation to compare algorithms
- Measure execution time with timeit
- 02
Lists, Sorting and Binary Search
- Know the cost of common operations on a Python list
- Implement binary search and use the bisect module
- Know when to sort to speed up processing
- 03
Dictionaries and Sets: The Power of Hashing
- Understand the principle of a hash table
- Choose between list, dict and set depending on the use case
- Solve classic problems in O(n) using hashing
- 04
Stacks, Queues and Priority Queues
- Use a stack (LIFO) and a queue (FIFO) with the right Python tools
- Solve a balanced-parentheses problem with a stack
- Manage priorities with the heapq module
- 05
Trees and Graphs: Modeling Relationships
- Represent a tree and a graph with dictionaries and lists
- Traverse a graph breadth-first (BFS) and depth-first (DFS)
- Find the shortest path in an unweighted graph
Final project
Recommendation and Route Engine for a Small City
Build a Python module that manages the transit network of a fictional city (stations and lines created in the code) and a log of rider trips. It must compute the shortest path between two stations, the busiest stations, the riders who traveled together, and a priority queue of incidents to handle. For each function, justify the structure you chose and its complexity.
Deliverables
- A Python script with data generated in the code (at least 15 stations and 1,000 trips)
- The functions plus_court_chemin (BFS), top_stations(k) (heapq or Counter), compagnons_de_trajet (set) and traiter_incidents (heapq)
- assert tests for each function, edge cases included
- A comment on each function stating its time and memory complexity
- A timeit measurement comparing a naive O(n²) version and your optimized version
Assessment criteria
- Results are correct, including when no path exists
- The chosen structures are appropriate (no list.pop(0), no in test on a large list)
- The stated complexities are correct and justified
- The performance measurement confirms the theoretical analysis
- The code is readable, split into functions and commented
Frequently asked questions
Do I need to be good at math to understand complexity?
No. You just need to be able to count how many times a statement runs and recognize a few growth curves. The course relies on concrete examples and measurements.
Why learn data structures with Python?
Python provides ready-made structures (list, dict, set, deque, heapq) whose costs you need to know. The principles you learn then apply to JavaScript, Java or PHP.
Does this course prepare me for technical interviews?
Yes, it covers the most frequently asked topics: Big O, hashing, binary search, stacks, queues and graph traversals, with classic exercises that are graded automatically.
What level do I need to take this course?
You need to know the basics of programming: variables, conditions, loops, functions, and simple lists and dictionaries, as covered in the Programming Fundamentals and Algorithmics course.
This course, told for your job
Say what you want to be able to do: “Data Structures and Complexity” takes its place in your path, with examples from your field. The concepts stay those of the course.