This course (30540) is an introduction to the techniques of theoretical compter science for the design and analysis of algorithms, and for the study of computational complexity.
Instructors: Giulio Malavolta and Laura Sanitá.
Lectures (Sarfatti 25, Aula 4):
Tuesday 13:45 - 16:15
Thursday 8:30 - 10:00
Friday 13:45 - 16:15
Office Hours: By appointment.
This course is primarily based on the book Algorithms (Dasgupta, Papadimitriou, and Vazirani).
The following lecture notes are provided for your convenience, and they have not been scrutinized. Use at your own risk.
Lecture 1: Introduction
Lecture 2: Multiplying Numbers and Sorting Arrays
Lecture 3: Randomized Algorithms, Matrix Multiplication, and a Master Theorem for Divide-and-Conquer
Lecture 4: The Fast Fourier Transform
Lecture 5: Graphs and Depth-First Search Explorations
Lecture 6: Topological Sorting
Lecture 7: Shortest Paths
Lecture 8: Minimum Spanning Trees
Lecture 9: Huffman Codes and Set Cover
Lecture 10: Even Shorter Paths via Dynamic Programming
Lecture 11: Longest Subsequence, Edit Distance, Knapsack, and More Matrix Multiplication
Lecture 12: Linear Programs
Lecture 13: Duality of Linear Programs and the Minimax Theorem for Zero-Sum Games
Assignment 1: Repeated Matrix Multiplication and Greatest Common Divisor
Assignment 2: Fast Modular Multiplication and Graph Coloring