Algorithms and Data Structures

• Profs: J. Lengler, D. Steurer
• Website: None but you can use Vorlesungsverzeichnis
• Moodle: Moodle
• Admin: Admin
• Material: Material
• Video: Videos ETHZ
• Cheatsheet: cheatsheet.pdf

This course focuses on algorithms and data structures, covering topics like searching, sorting, dynamic programming (e.g., knapsack, edit distance, LIS), and graph theory. Key graph topics include DFS, BFS, shortest path algorithms (SSSP, ASSP), topological sort, and spanning trees. Emphasis is placed on efficiency using Big O notation and selecting optimal data structures for problem-solving.

Lecture Notes

• 01 Intro To Algorithms
• 02 Star Search
• 03 Max Subarray Sum
• 04 Searching and Sorting
• 05 Sorting, Data Structures
• 06 Abstract Data Types, Binary AVL Search Trees
• 07 Dynamic Programming, Jump Game, Longest Common Subsequence, Edit Distance
• 08 Subset Sum, Knapsack, Longest Increasing Subsequence
• 09 Graph Theory, Eulerian Cycle Algorithm
• 10 Topological Ordering, Directed Graphs, Representing Graphs on Computers, Topological Sort Algorithm
• 11 Shortest Path Algorithms, Cheapest Walks in Weighted Graphs, Acyclical Graphs and Topological Sort, Dijkstra’s Algorithm
• 12 Cheapest Path Problem, Negative Cost, Bellman-Ford, Minimum Spanning Trees, Boruvka’s Algorithm, Prim’s Algorithm, Priority Queues
• 13 Kruskal’s Algorithm, Union Find, Self-Adapting Data Structures and Amortized Analysis
• 14 All Source Shortest Paths, Floyd-Warshall, Johnson’s Algorithm, Matrices and Graphs, Connected Components in Digraphs, Efficient Matrix Operations

Study Notes (WIP)

Fundamentals

• Intro to General Algorithms
• Comparing Algorithms and Properties

Growth

• Asymptotic Notation
• Master Theorem

Algorithms

Search and Sort

• Searching Algorithms
• Sorting Algorithms

Graph Theory

• Fundamental Concepts in Graph Theory