Spring 2024 — 30540 Computer Science 2

General information

Lectures:

• Tuesdays 13:45-16:15
• Thursdays 8:30-10:00
• Fridays 13:45-16:15

Office hours:

• Fabrizio Iozzi: see Bocconi Web Page
• Laura Sanità: by appointment via email

Textbooks and other readings

• S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. Algorithms

Additional lecture notes will be distributed when the content of the lectures deviates from the book:

Lecture plan

• 2024-02-06: Introduction
  Contents: Preview of some highlights. Mathematical preliminaries: proving things by induction, bounding summations, big-Oh and little-oh notations, basics of probability
  Readings: Section 0.3
  Instructor: Iozzi
  Suggested Exercises:
  
• 2024-02-08: Divide-and-conquer I
  Contents: Addition & Multiplication
  Readings: Sections 1.1 and 2.1
  Instructor: Iozzi
  Suggested Exercises:
  
• 2024-02-9: Divide-and-conquer II
  Contents: Integer multiplication in O(n^{log_2 3}) time, Master Theorem. Remarks on Sorting. Median in linear time
  Readings: Sections 2.2, 2.3 and 2.4
  Instructor: Iozzi
  Suggested Exercises: 2.14, 2.16, 2.22
  
• 2024-02-13: Graph Decomposition I
  Contents: Graphs, representations of graphs, directed and undirected graphs, paths, connected components. Exploring undirected graphs.
  Readings: Sections 3.1 and 3.2
  Instructor: Iozzi
  Suggested Exercises:
  
• 2024-02-14, 12:00-13:30: Graph Decomposition II
  Contents:DFS in undirected graphs. Connectivity in Undirected Graphs.
  Readings: Section 3.2
  Instructor: Iozzi
  Suggested Exercises:
  
• 2024-02-15: Graph Decomposition III
  Contents: Linearization, DFS finds linearization
  Readings: Section 3.3 and Notes on topological sort
  Instructor: Iozzi
  Suggested Exercises:
  
• 2023-02-16: Graph Decomposition III
  Contents: Strongly Connected Components
  Readings: Section 3.4
  Instructor: Iozzi
  Suggested Exercises:
  
• HOMEWORK 1 (turn in on Tue Feb 20 in class)
• 2024-02-20: Shortest Paths I
  Contents: BFS and shortest paths in unweighted graphs
  Readings: Sections 4.1 and 4.2
  Instructor: Iozzi
  Suggested Exercises:
  
• 2024-02-23: Shortest Paths II
  Contents: Dijkstra's algorithm, priority queue implementation as unsorted lists and as heaps
  Readings: Sections 4.3, 4.4 and 4.5
  Instructor: Iozzi
  Suggested Exercises:
  
• 2024-02-27: Shortest Paths III
  Contents: Dijkstra's algorithm proof of correctness, Asn 1 Review
  Readings: Sections 4.3 and 4.4 notes
  Instructor: Iozzi
  Suggested Exercises:
  
• 2024-02-29: Greedy Algorithms I
  Contents: Dijkstra's algorithm proof of correctness (cont'd). Minimum spanning tree problem, Kruskal's algorithm
  Readings: Section 5.1
  Instructor: Iozzi
  Suggested Exercises:
  
• 2024-03-01: Greedy Algorithms II
  Contents: Kruskal's algorithm proof of correctness. Prim's algorithm.
  Readings: Section 5.1
  Instructor: Iozzi
  Suggested Exercises:
  
• HOMEWORK 2 (turn in on Tue Mar 5 in class)
• 2024-03-05: Greedy Algorithms III
  Contents: Union-find data structure. Prim's algorithm and its correctness. Prefix codes, Huffman coding
  Readings: Section 5.2, notes
  Instructor: Iozzi
  Suggested Exercises:
  
• 2024-03-08: Greedy Algorithms IV. Review.
  Contents: Set Cover. Review before the midterm.
  Readings:
  Instructor: Iozzi
  Suggested Review Exercises from DPV:2.4, 3.11, 3.24, 4.4, 4.20, 5.5
  
• MIDTERM
• 2024-03-20: Dynamic Programming I
  Contents: Shortest (and longest) paths in DAGs (also with negative weights)
  Readings: Section 6.1
  Instructor: Polak
  
• 2024-03-21: Dynamic Programming II
  Contents: Edit distance, knapsack
  Readings: Section 6.3, 6.4
  Instructor: Polak
  
• 2024-03-22: Dynamic Programming III
  Contents: All-pairs shortest paths, Floyd–Warshall algorithm
  Readings: Sections 6.6
  Instructor: Polak
  Suggested Exercises:30540_Dynamic_programming_exercises.pdf
  
• 2024-04-09: Flows I
  Contents: Flows in networks, Cuts in networks, residual network, examples
  Readings: https://homepages.cwi.nl/~lex/files/dict.pdf (4.2 and 4.3)
  Instructor: Sanità
  
• 2024-04-12: Flows II
  Contents: Ford-Fulkerson algorithm, Max flow min cut theorem, analysis of Edmonds-Karp
  Readings: https://homepages.cwi.nl/~lex/files/dict.pdf (4.3 and 4.4)
  Instructor: Sanità
  
• HOMEWORK 3 (turn in on Tue Apr 23 in class)
• 2024-04-16: Linear Programming I
  Contents: Introductory examples, formalization
  Readings: 30540_2.pdf (Chapter 1)
  Instructor: Iozzi
  
• 2024-04-18: Linear Programming II
  Contents: The simplex algorithm
  Readings: 30540_2.pdf (Chapter 2)
  Instructor: Iozzi
  
• 2024-04-19: Linear Progamming III
  Contents: Introduction to Duality
  Readings: 30540_2.pdf (Chapter 3)
  Instructor: Iozzi
  
• 2024-04-23: Linear Programming IV
  Contents: More on Duality
  Readings: 30540_2.pdf (Chapter 4)
  Instructor: Iozzi
  
• 2024-04-30: Linear Programming V
  Contents: Exercises
  Readings: 30540_2.pdf (Chapter 5)
  Python example code for LP: lp_example.py
  Instructor: Iozzi
  
• 2024-05-03: NP-completeness I
  Contents: Classes P and NP, reductions
  Readings: Sections 8.1,8.2,7.3
  Instructor: Sanità
  
• 2024-05-07: NP-completeness II
  Contents: Examples of Reductions
  Readings: Section 8.3
  Instructor: Sanità
  
• 2024-05-09: NP-completeness III
  Contents: Examples of Reductions
  Readings: Section 8.3
  Instructor: Sanità
  
• 2024-05-10: NP-completeness IV
  Contents: NP-completeness of SAT
  Readings: Sections 7.7, 8.3
  Instructor: Sanità