Algorithmics and Programming II: on-line material

Graphs: Connectivity

PowerPoint

• Introduction and Graph Representation (Audio, Slides 1-19, 27:27)
• Reachability and Depth-First Search (Audio, Slides 20-27, 22:24)
• Connected Components, DAGs and Topological Sort (Video, 32:10)
• Strongly Connected Components (Video, 28:19)

Priority Queues

PowerPoint and Video (33:22)

Graphs: Shortest paths

PowerPoint

• Breadth First Search (Video, 23:05)
• Shortest paths: Dijkstra (Video, 27:46)
• Shortest paths: Bellman-Ford and DAGs (Video, 28:56)

Graphs: Minimum Spanning Trees and Maximum Flows

PowerPoint

• Minimum Spanning Trees (Video, 50:36)
• Maximum Flows (Video, 43:51)

Trees

PowerPoint

• Trees (Video, 42:22)

Sets and Dictionaries

PowerPoint

• Binary Search Trees (Video, 34:08)
• AVL Trees (Video, 32:25)

Hashing

• PowerPoint and Video (38:38)

Cryptography

PowerPoint

• Public and Secret Key Protocols (Video, 20:23)
• RSA (Video, 39:35)

Fast Fourier Transform

PowerPoint

• Polynomial representations and roots of unity (Video, 38:10)
• The FFT algorithm (Video, 33:07)

Graphs: Lab classes

Here is a youtube channel, by Jordi Petit, with some examples on how to solve some of the graph problems proposed for the lab sessions.