Algorithms I
CS-250
Media
CS-250 Algorithms
CS-250 Algorithms I | Wednesday | Spring 25
28.05.2025, 14:04
CS-250 Algorithms I | Wednesday | Spring 25
21.05.2025, 13:50
CS-250 Algorithms I | Wednesday | Spring 25
14.05.2025, 13:52
CS-250 Algorithms I | Wednesday | Spring 25
07.05.2025, 13:52
CS-250 Algorithms I | Wednesday | Spring 25
30.04.2025, 13:49
CS-250 Algorithms I | Wednesday | Spring 25
23.04.2025, 13:45
CS-250 Algorithms I | Wednesday | Spring 25
16.04.2025, 13:51
CS-250 Algorithms I | Wednesday | Spring 25
09.04.2025, 13:50
CS-250 Algorithms I | Wednesday | Spring 25
02.04.2025, 13:49
CS-250 Algorithms I | Wednesday | Spring 25
26.03.2025, 13:53
CS-250 Algorithms I | Wednesday | Spring 25
19.03.2025, 13:55
CS-250 Algorithms I | Wednesday | Spring 25
12.03.2025, 13:50
CS-250 Algorithms I | Wednesday | Spring 25
05.03.2025, 13:51
CS-250 Algorithms I | Wednesday | Spring 25
26.02.2025, 13:50
CS-250 Algorithms I | Wednesday | Spring 25
19.02.2025, 13:44
CS-250 Algorithms I | Wednesday | Spring 25
19.02.2025, 13:50
CS-250 Algorithms I | Tuesday | Spring 25
27.05.2025, 15:51
CS-250 Algorithms I | Tuesday | Spring 25
20.05.2025, 15:50
CS-250 Algorithms I | Tuesday | Spring 25
13.05.2025, 15:54
CS-250 Algorithms I | Tuesday | Spring 25
06.05.2025, 15:52
CS-250 Algorithms I | Tuesday | Spring 25
29.04.2025, 15:48
CS-250 Algorithms I | Tuesday | Spring 25
22.04.2025, 15:47
CS-250 Algorithms I | Tuesday | Spring 25
15.04.2025, 15:51
CS-250 Algorithms I | Tuesday | Spring 25
08.04.2025, 15:49
CS-250 Algorithms I | Tuesday | Spring 25
25.03.2025, 15:52
CS-250 Algorithms I | Tuesday | Spring 25
18.03.2025, 16:00
CS-250 Algorithms I | Tuesday | Spring 25
11.03.2025, 15:51
CS-250 Algorithms I | Tuesday | Spring 25
04.03.2025, 15:52
CS-250 Algorithms I | Tuesday | Spring 25
25.02.2025, 15:54
CS-250 Algorithms I | Tuesday | Spring 25
18.02.2025, 15:47
CS-250 Algorithms I | Tuesday | Spring 25
18.02.2025, 15:55
CS-250 Algorithms I Summer 2014 Wednesday session
29.05.2024, 13:55
CS-250 Algorithms I Summer 2014 Wednesday session
22.05.2024, 13:52
CS-250 Algorithms I Summer 2014 Wednesday session
15.05.2024, 13:52
CS-250 Algorithms I Summer 2014 Wednesday session
08.05.2024, 13:51
CS-250 Algorithms I Summer 2014 Wednesday session
01.05.2024, 13:51
CS-250 Algorithms I Summer 2014 Wednesday session
24.04.2024, 13:55
CS-250 Algorithms I Summer 2014 Wednesday session
17.04.2024, 13:32
CS-250 Algorithms I Summer 2014 Wednesday session
10.04.2024, 13:46
CS-250 Algorithms I Summer 2014 Wednesday session
03.04.2024, 13:10
CS-250 Algorithms I Summer 2014 Wednesday session
27.03.2024, 13:42
CS-250 Algorithms I Summer 2014 Wednesday session
27.03.2024, 13:47
CS-250 Algorithms I Summer 2014 Tuesday session
28.05.2024, 15:53
CS-250 Algorithms I Summer 2014 Tuesday session
21.05.2024, 15:51
CS-250 Algorithms I Summer 2014 Tuesday session
14.05.2024, 15:52
CS-250 Algorithms I Summer 2014 Tuesday session
07.05.2024, 15:50
CS-250 Algorithms I Summer 2014 Tuesday session
30.04.2024, 15:52
CS-250 Algorithms I Summer 2014 Tuesday session
23.04.2024, 15:51
CS-250 Algorithms I Summer 2014 Tuesday session
16.04.2024, 15:48
CS-250 Algorithms I Summer 2014 Tuesday session
09.04.2024, 15:46
CS-250 Algorithms I Summer 2014 Tuesday session
02.04.2024, 15:10
CS-250 Algorithms I Summer 2014 Tuesday session
26.03.2024, 15:13
CS-250 Algorithms I Summer 2014 Tuesday session
26.03.2024, 15:51
CS-250 Algorithms I Lecture 10 2024
20.03.2024, 13:41
CS-250 Algorithms I Summer 2014 Wednesday session
20.03.2024, 13:48
CS-250 Algorithms I Lecture 9 2024
19.03.2024, 15:42
CS-250 Algorithms I Summer 2014 Tuesday session
19.03.2024, 15:47
CS-250 Algorithms I Lecture 8 2024
13.03.2024, 13:42
CS-250 Algorithms I Summer 2014 Wednesday session
13.03.2024, 13:48
CS-250 Algorithms I Lecture 7 2024
12.03.2024, 15:40
CS-250 Algorithms I Summer 2014 Tuesday session
12.03.2024, 15:47
CS-250 Algorithms I Lecture 6 2024
06.03.2024, 13:10
CS-250 Algorithms I Summer 2014 Wednesday session
06.03.2024, 13:46
CS-250 Algorithms I Lecture 5 2024
05.03.2024, 15:11
CS-250 Algorithms I Summer 2014 Tuesday session
05.03.2024, 15:46
CS-250 Algorithms I Lecture 4 2024
28.02.2024, 13:40
CS-250 Algorithms I Summer 2014 Wednesday session
28.02.2024, 13:46
CS-250 Algorithms I Lecture 3 2024
27.02.2024, 15:40
CS-250 Algorithms I Summer 2014 Tuesday session
27.02.2024, 15:47
CS-250 Algorithms I Lecture 2 2024
21.02.2024, 13:10
CS-250 Algorithms I Summer 2014 Wednesday session
21.02.2024, 13:45
CS-250 Algorithms | Lecture 1 2024
20.02.2024, 15:11
CS-250 Algorithms I Summer 2014 Tuesday session
20.02.2024, 15:54
100, Recap before Algorithms exam 2021
20.01.2022, 13:21
50, Lecture 25 Part 2 (2021)
23.12.2021, 21:25
Counting sort
Cool stuff
49, Lecture 25 Part 1 (2021) Sorry for technical problems
23.12.2021, 21:23
Recap quicksort
Why always n log (n) for sorting?
48, Lecture 24 Part 2 (2021)
17.12.2021, 16:06
Quick sort analysis
Finding k smallest
47, Lecture 24 Part 1 (2021)
17.12.2021, 16:04
Recap Hash tables
Quick sort algorithm
46, Lecture 23 Part 2 (2021)
13.12.2021, 16:16
Hash tables analysis
Problem solving
45, Lecture 23 Part 1 (2021)
13.12.2021, 16:15
Birthday paradox
Hash tables
44, Lecture 22 Part 2 (2021)
10.12.2021, 15:29
Probabilistic Analysis
The Hiring Problem
43, Lecture 22 Part 1 (2021)
10.12.2021, 15:28
Bellman-Ford Recap
Dijkstra
42, Lecture 21 Part 2 (2021)
06.12.2021, 16:11
Bellman-Ford
41, Lecture 21 Part 1 (2021)
06.12.2021, 16:10
Minimum Spanning Trees
Beginning of shortest path
40, Lecture 20 Part 2 (2021)
05.12.2021, 10:56
Prim's algorithm (correctness and implementation)
Kruskal's algorithm
39, Lecture 20 Part 1 (2021)
05.12.2021, 10:53
Union-Find (disjoint sets)
Prim's algorithm for minimum spanning trees
38, Lecture 19 Part 2 (2021)
30.11.2021, 16:01
Union-Find
Minimum Spanning Trees (start)
37, Lecture 19 Part 1 (2021)
30.11.2021, 15:59
Flows Recap
Union-Find data structure (Disjoint-sets)
36, Lecture 18 Part 2 (2021)
26.11.2021, 20:03
Max flow = min cut
Applications of flows
35, Lecture 18 Part 1 (2021)
26.11.2021, 19:57
Flow networks
Ford-Fulkerson Method
34, Lecture 17 Part 2 (2021)
22.11.2021, 21:01
Flow networks
Flows
Ford-Fulkerson Method
33, Lecture 17 Part 1 (2021)
22.11.2021, 20:54
DFS
Topological Sort
Strongly connected components
32, Lecture 16 Part 2 (2021)
19.11.2021, 15:31
DFS continuation
Topological sort
Briefly bly connected components
31, Lecture 16 Part 1 (2021)
19.11.2021, 15:29
Recall BFS
DFS
30, Lecture 15 Part 2 (2021)
15.11.2021, 16:18
Graphs
Breadth-First Search
Depth-First Search
29, Lecture 15 Part 1 (2021)
15.11.2021, 16:18
Optimal Binary Search Tree
28, Lecture 14 Part 2 (2021)
13.11.2021, 21:08
Optimal Binary Search Tree
27, Lecture 14 Part 1 (2021)
13.11.2021, 21:04
Longest Common Subsequence
26, Lecture 13 Part 2 (2021)
05.11.2021, 16:45
Solving midterm 2019 (2nd part) and a few other problems
25, Lecture 13 Part 1 (2021)
05.11.2021, 16:35
Solving Midterm 2019 (first part)
24, Lecture 12 Part 2 (2021)
02.11.2021, 10:44
Longest Common Subsequence
23, Lecture 12 Part 1 (2021)
02.11.2021, 10:26
Matrix Chain Multiplication
22, Lecture 11 Part 2 (2021)
29.10.2021, 15:19
Matrix chain multiplication
21, Lecture 11 Part 1 (2021)
29.10.2021, 15:19
Rod cutting, change making
20, Lecture 10 Part 2 (2021)
26.10.2021, 09:10
Rod cutting and problem solving
19, Lecture 10 Part 1 (2021)
26.10.2021, 08:55
Top-down and bottom-up
Start with rod cutting
18, Lecture 9 Part 2 (2021)
22.10.2021, 15:35
Introduction to Dynamic Programming
17, Lecture 9 Part 1 (2021)
22.10.2021, 15:33
Binary search trees
16, Lecture 8 Part 2 (2021)
19.10.2021, 12:14
Binary search trees
15, Lecture 8 Part 1 (2021)
19.10.2021, 12:13
Stacks
Queues
Linked Lists
14, Lecture 7 Part 2 (2021)
15.10.2021, 15:32
Stacks and queues
13, Lecture 7 Part 1 (2021)
15.10.2021, 15:31
Heaps, Heapsort, Priority queues
12, Lecture 6 Part 2 (2021)
11.10.2021, 16:19
Heapsort and priority queues
11, Lecture 6 Part 1 (2021)
11.10.2021, 16:18
Recall divide-and-conquer
Heaps and Heapsort
10, Lecture 5 Part 2 (2021)
08.10.2021, 15:27
Matrix multiplication (Strassen's algorithm)
Start of heaps
9, Lecture 5 Part 1 (2021)
08.10.2021, 15:25
Maximum subarray
and start of matrix multiplication.
8, Lecture 4 Part 2 (2021)
05.10.2021, 09:59
Maximum subarray problem
7, Lecture 4 Part 1 (2021)
05.10.2021, 09:46
Solving recurrences
6, Lecture 3 Part 2 (2021)
04.10.2021, 08:07
Solving recurrences
Master method
5, Lecture 3 Part 1 (2021)
04.10.2021, 08:06
Recall Merge Sort
Start to analyze recurrences
4, Lecture 2 Part 2 2021
28.09.2021, 10:43
Divide and Conquer
Merge sort
In this course you will get familiar with the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, the design of algorithms by induction, Sorting and searching, Merge sort, quicksort, heapsort, binary search, graph algorithms and data structures, graph traversals, shortest paths, spanning trees, matching, network flows, and elements of the theory of NP-completeness.
This is a course for second year students of both the systèmes de communication and informatique sections. The lectures will be in English, but you are free to choose to write your solutions to the final exam in either English or French.
For more details see the official couse book here.
Lectures and exercise sessions
Lectures will be given on campus. The lecture rooms are
- RLC E1 240 on Tuesdays 13-15
- RLC E1 240 on Wednesdays 11-13
The recording of the lectures are published here: https://mediaspace.epfl.ch/channel/CS-250+Algorithms/
The exercise sessions occur on Fridays 10-12 in rooms CM1, CM1100, CM1104, CM1105, CM1106. Please try to spread out optimally.
Grading
The course will consist of the following graded moments:
- Quizzes
- One midterm that will be in the middle of the course (April 1st).
- One algorithmic implementation assignments in May/June.
- A final exam during the exam session.
The final grade will be calculated based on the maximum of
- 10% quizzes + 30% midterm + 10% algorithm implementation assignment + 50% final exam.
- 100% final exam.
Week-by-week material
(The exact dates of the different topics are subject to change.)
- February 18, February 19: Basic concepts and analysis + Insertion Sort. Sections 2.1, 2.2 + Review of Chapter 1,3 and Appendix A
- February 25, February 26: Divide-and-Conquer, Merge-sort, solving recurrences, maximum-sub-array problem. Sections 2.3, 4.1, 4.3-4.5
- March 4, 5: Strassen's algorithm for matrix multiplication, solving recurrences. Sections 4.2, 4.4, 4.5 + Review of Section 4.3
- March 11, 12: Heaps and Heapsort. Chapter 6
- March 18, 19: Data structures: queues, linked lists, binary search trees. Sections 10.1, 10.2, 12.1, 12.2, 12.3
- March 25, 26: Dynamic programming: rod cutting matrix chain multiplication. Sections 15.1, 15.2
- April 1, 2: More Dynamic Programming: formalization, longest common subsequence, optimal binary search trees. Sections 15.3, 15.4, 15.5
- April 8, 9: Elementary graph algorithms: BFS, DFS, Sections 22.1, 22.2, 22.3 + Review of Appendix B
- April 15, 16: Topological sort, flows. Sections 22.4, 26.1, beginning of 26.2
- April 29, May 30: Flows continued and bipartite matching. Sections 26.2 continued, 26.3
- May 6, 7: Data structure disjoint sets + minimum spanning trees. Sections 21.1, 21.2, 21.3, Chapter 23
- May 13, 14: Bellman-Ford, probabilistic analysis. Sections 24.1, 5.1, 5.2
- May 20, 21: Hash tables, Sections 11.1, 11.2, 8.1, 8.2 + Discussion of Quicksort
- May 27, 28: TBD
Reading
The textbook for the course is:
- Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to algorithms, Third Edition, MIT Press, 2009.
Forums
Week 1: Feb 17 - 23
Basic concepts and analysis + Insertion Sort.
- Slides of Lecture 1 (File)
- Slides of Lecture 1 (with animations) (File)
- Slides of Lecture 2 (File)
- Slides of Lecture 2 (with animations) (File)
- Exercise Set 1 (File)
- Solutions to Exercise Set 1 (File)
Week 2: February 24 - March 2
Divide-and-Conquer, Merge-sort, solving recurrences, maximum-sub-array problem.
- Slides of Lecture 3 (File)
- Slides of Lecture 3 (with animations) (File)
- Slides of Lecture 4 (File)
- Slides of Lecture 4 (with animations) (File)
- Master theorem (File)
- Exercise Set 2 (File)
- Solutions to Exercise Set 2 (File)
Week 3: March 3 - 9
- Slides of Lecture 5 (File)
- Slides of Lecture 5 (with animations) (File)
- Slides of Lecture 6 (File)
- Slides of Lecture 6 (with animations) (File)
- Exercise Set 3 (File)
- Solutions to Exercise Set 3 (File)
Week 4: March 10 - 16
- Slides of Lecture 7 (File)
- Slides of Lecture 7 without animations (File)
- Slides of Lecture 8 (File)
- Slides of Lecture 8 without animations (File)
- Exercise Set 4 (File)
- Solutions to exercise set 4 (File)
Week 5: March 17 - 23
- Midterm 2024 (File)
- Midterm 2024 Solutions (File)
- Midterm 2022 (File)
- Midterm 2022 with solutions (File)
- Midterm 2013 (File)
- Solutions to Midterm 2013 (File)
- Midterm 2014 (File)
- Solutions to Midterm 2014 (File)
- Midterm Exam 2015 (File)
- Midterm 2015 with solutions (File)
- More examples of midterm questions (File)
- Solutions to more midterm example questions (written by TAs) (File)
- Midterm exam 2016 (File)
- Midterm exam 2016 with solutions (File)
- Midterm exam 2017 (File)
- Midterm exam 2017 with solutions (File)
- Midterm exam 2018 (File)
- Midterm exam 2018 with solutions (File)
- Midterm exam 2019 (File)
- Midterm exam 2019 with solutions (File)
- Midterm 2021 Solutions (File)
- Slides of Lecture 9 (File)
- Slides of Lecture 9 (with animations) (File)
- Slides of Lecture 10 (File)
- Slides of Lecture 10 (with animations) (File)
- Exercise Set 5 (File)
- Solutions to Exercise Set 5 (File)
Week 6: March 24 - 30
- Slides of Lecture 11 (File)
- Slides of Lecture 11 (with animations) (File)
- Exercise Set 6 (File)
- Solutions to Exercise Set 6 (File)
- Seat assignments for midterm (File)
- Room plans for midterm (File)
Week 7: March 31 - April 6
- Slides of Lecture 13 (File)
- Slides of Lecture 13 (with animations) (File)
- Exercise Set 7 (File)
- Solutions to Exercise Set 7 (File)
Week 8: April 7 - 13
- Slides of Lecture 14 (File)
- Slides of Lecture 14 (with animations) (File)
- Slides of Lecture 15 (File)
- Slides of Lecture 15 (with animations) (File)
- Exercise Set 8 (File)
- Solutions to Exercise Set 8 (File)
Easter break: April 21 - 27
Week 9: April 14 - 20
- Slides of Lecture 16 (File)
- Slides of Lecture 16 (with animations) (File)
- Slides of Lecture 18 (File)
- Slides of Lecture 18 (with animations) (File)
Week 10: April 28 - May 4
- Slides of Lecture 19 (File)
- Slides of Lecture 19 (with animations) (File)
- Slides of Lecture 20 (File)
- Slides of Lecture 20 (with animations) (File)
- Exercise Set 9 (File)
- Solutions to Exercise Set 9 (File)
Week 11: May 5 - 11
- Solutions to the Midterm Exam (File)
- Slides of Lecture 21 (File)
- Slides of Lecture 21 (with animations) (File)
- Slides of Lecture 22 (File)
- Exercise Set 10 (File)
- Solutions to Exercise Set 10 (File)
- Olas notes (URL)
- Solutions to the Graded Programming Homework (Folder)
Week 12: May 12 - 18
- Slides of Lecture 23 (continuing Lecture 22) (File)
- Slides of Lecture 24 (File)
- Slides of Lecture 24 (with animations) (File)
- Exercise Set 11 (File)
- Solutions to Exercise Set 11 (File)
Week 13: May 19 - 25
- Slides of Lecture 25 (File)
- Notes of Lecture 26 (File)
- Live notes of Lecture 26 (URL)
- Exercise Set 12 (File)
- Solutions to Exercise Set 12 (File)
Week 14: May 26 - June 1
- Live notes Lecture 28 (URL)
- Live notes Lecture 27 (URL)
- Notes of Lecture 27 (File)
- Exercise Set 13 (File)
- Solutions to Exercise Set 13 (File)
- Final Exam 2023-2024 (File)
- Final Exam 2023-2024 with solutions (File)
- Final exam 2022-2023 solutions and grading schemes (File)
- Final exam 2022-2023 MCQ solutions (File)
- Final exam 2022-2023 (File)
- Final Exam 2021 with solutions (File)
- Final Exam 2021 (File)
- Final exam 2020 with solutions (File)
- Final Exam 2020 (File)
- Final Exam 2019 with solutions (File)
- Final Exam 2019 (File)
- Final Exam 2018 with solutions (File)
- Final Exam 2018 (File)
- Final Exam 2017 with solutions (File)
- Final Exam 2017 (File)
- Final Exam 2016 with Solutions (File)
- Final Exam 2016 (File)
- Final Exam 2015 with Solutions (File)
- Final Exam 2015 (File)
- Final Exam 2014 with solutions (File)
- Final Exam 2014 (File)
- Final Exam 2013 with solutions (File)
- Final Exam 2013 (File)
- Solutions to final exam 2012 (File)
- Final Exam 2012 (File)
- AnswersToFinal2011 (File)
- Problems of Exam 2011 (File)
- Exam 2010 (File)
- Exam 2006 (File)