TDDD95 Algorithmic Problem Solving

Timetable

Lectures/Seminars

We are back to campus teaching. The lectures are still recorded, the seminars will mainly discuss the exercises.

• Jan 16 8.15-10, Introductory lecture [live slides, recorded slides, recording]
  • Intro to greedy and DP (Lab 1.1)
  • How to solve dynamic programming (DP) problems
  • Tool to calculate APS points collected developed by Henrik Adolfsson: github.com/catears/kattis-cli
  • Companion tool for APS developed by Henrik Adolfsson: github.com/catears/companion
• Jan 17 10-12, Seminar Problem Solving [recorded slides]
  • Kattis problems: Babelfish, CD, Closest Sums, and Mathemagicians
• Jan 26 10-12, Seminar Ex1 and Le2 Data structures [recorded slides, recording]
  • The knapsack problem (lab 1.2)
  • Longest increasing subsequence (Lab 1.3)
  • Union-Find (Lab 1.4)
  • Fenwick tree (Lab 1.5)
  • Slides related to basic data structures including Fenwick Trees by Steven Halim
  • TopCoder tutorial on Fenwick Trees
  • TopCoder tutorial on Range Min Queries including Segment Trees
• Feb 2 10-12, Seminar Ex2 and Le3 Arithmetic [recorded slides, recording]
  • Slides by Adam Smith on the Fast Fourier Transform
  • FFT (Lab 1.6)
  • Gaussian Elimination (Lab 1.7)
• Feb 9 10-12, Seminar Ex3 and Problem solving techniques (DP) [recorded slides, recording]
  • Lecture slides by Kevin Wayne on Greedy Algorithms I (basic techniques)
  • Lecture slides by Kevin Wayne on Divide and Conquer I (sorting and selection)
  • Lecture slides by Kevin Wayne on Dynamic Programming I (basic techniques)
• Feb 16 10-12, Seminar Ex4 and Graphs I (basics, spanning trees and shortest paths) [recorded slides, recording]
  • Dijkstra shortest path algorithm (Lab 2.1, Lab 2.2)
  • Bellman-Ford algorithm (Lab 2.3)
  • Floyd-Warshall all-pairs shortest path algorithm (Lab 2.4)
  • Kruskal's Minimum Spanning Tree algorithm (Lab 2.5)
• Feb 23 10-12, Seminar Ex5 and Graphs II (max flow and min cut) [recorded slides, recording]
  • Maximum Flow algorithms (Lab 2.6)
  • Minimum Cut algorithm (Lab 2.7)
  • Minimum Cost Maximum Flow (Lab 2.8)
• Mar 1 10-12, Seminar Ex6 and Graphs III (matching and covering problems) [old live slides, recorded slides, recording]
  • Slides related to matching and covering problems by Steven Halim
  • Euler path algorithm (Lab 2.9)
• Mar 8 10-12, Seminar Ex7
• Mar 27 13-15, Strings I [old live slides, recorded slides, recording]
  • Knuth-Morris-Pratt algorithm (Lab 3.1)
  • Knuth-Morris-Pratt visualization tool
• Apr 4 8-10, Seminar Ex8 and Strings II [old live slides, recorded slides, recording]
  • Slides related to Suffix Trie/Tree/Array by Steven Halim
• Apr 12 13-15, Seminar Ex9 and Number Theory [old live slides, recorded slides, recording]
• Apr 19 8-10, Seminar Ex10 and Combinatorial Search [recording]
  • Slides concerning combinatorial search by Bob Sedgewick and Kevin Wayne
• Apr 26 13-15, Seminar Ex11 and Computational Geometry [old live slides, recorded slides, recording]
• Example execution of Graham scan algorithm by Bob Sedgewick and Kevin Wayne
• May 3 13-15, Seminar Ex12
• May 8 13-15, Seminar Ex13

Page responsible: Fredrik Heintz
Last updated: 2024-01-22