Main Page for Algorithms (ALG)
Modifications to the schedule, grades and other info will be located also at FIB.
- Teaching staff
-
Christian Blum
Campus Nord, Edif. Omega, Desp. 112
E-mail: cblum at lsi.upc.edu
-
Maria Serna (Responsible)
Campus Nord, Edif. Omega, Desp. 235
E-mail: mjserna at lsi.upc.edu
- Calendar
- Final exam june 15th 2011
- Compulsory assignments
- Exams
- Course Roadmap
- 0. Course overview (slides
)
- 1. Overview of basic algorithmic techniques
- Divide and conquer: counting the number of inversions, computing the closests pair of points.
Sections 5.3 and 5.4 [Kleinberg Tardos], section 33.4
[Cormen et al. 2nd ed.].
- Exhaustive search: Max Cut. Knapsack. Traveling
Salesperson. (slides
)
Chap 7 [Skiena 2nd edition]
- Dynamic programming
Section 6.1 [Kleinberg Tardos] more examples Chap 15 [CLRS]
-
Exercises and
problems
- 2. Graph algorithms
- Elementary graph algorithms. BFS and DFS. Topological sort. Comnnected componnents. Chap 22 [CLRS,3rd edition]
- Minimum Spanning tree. Kuskal's and Prim's algorithms. Chap 23 [CLRS,3rd edition]
- Shortests paths. Algorithms: Bellman-Ford, Floyd-Warshall, Johnson. Sections 24.1, 25.2 and 25.3 of [CLRS,3rd edition]
- Maximum Flow. Ford Fulkerson and Edmonds-Karp algorithms. Sections 26.1 and 26.2 of [CLRS,3rd edition]
-
Exercises
-
Exercises(2)
- 3. Introduction to approximation algorithms
- Problems and solutions. Optimization problems and complexity classes for approximation,
- Overview of basic approximation algorithms. Slides
- Scheduling, section 11.1 de [KT]. Vertex Cover, section 11.4 de [KT]. Knapsack, section 11.8 de [KT].
-
Exercises
- 4. Introduction to randomized and web algorithms
- Basics on randomized algorithms slides
- Basics on Game theory for strategic games slides
- Random walks in graphs. Page Rank and Hits algorithms.
- 5. Heuristics and local search
- Some links that might be useful