Evaluation:
Assignments 50%, quizzes 20%, final exam 30%
Copying is fatal
Teaching assistant: Rebhu Johymalyo Josh
Submit all assignment solutions via Moodle.
Algorithm Design by Jon Kleinberg and Eva Tardos, Chapters 3–6.
Algorithms by Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, Chapters 2–6.
The stuff I write during class, to jog your memory.
Declarative vs procedural programming, quick introduction to Python via gcd
Names and values in Python: basic data types, dynamic typing, strings, lists, immutable vs mutable
Slicing a list; Control flow: if, for, while; Defining functions; range(); type converstion
Tuples, dictionaries; Python program structure; Map, filter, list comprehension; Function with optional arguments
Exception handling; Basic input/output; File input/output
File input/output; Abstract datatypes
Abstract datatypes; Classes and objects; Linked lists
Linked lists: insert, append, delete
Linked lists: delete, other functions; Special functions in classes: __str__, __add__ etc; Search trees: find, insert, delete
Search trees: delete; Height-balanced (AVL) trees
Search trees: slope; Algorithmic complexity: O(), worst-case, recurrences; Binary search; Sorting: insertion sort, selection sort, merge sort
Merge sort: analysis; Quicksort: analysis, average-case, in-place partitioning; Stable sorting
Modelling with graphs; Adjacency matrix; Breadth-first search
BFS: adjacency lists, distance, BFS tree, detecting cycles
DFS: pre/post numbering, detecting cycles, DFS on directed graphs; Directed acyclic graphs: topological sort
Directed acyclic graphs: topological sort, longest path
Directed graphs: Computing strongly connected components; Weighted graphs: introduction
Weighted graphs: Single source shortest paths, Dijkstra's algorithm
Heaps: definition, insert, delete_max, update
Heaps: building a heap, heap sort; Minimum cost spanning trees: Prims's algorithm, correctness, Kruskal's algorithm (implementation)
Minimum cost spanning trees: Kruskal's algorithm, Union-Find data structure
Greedy algorithms: Interval scheduling
Greedy algorithms: Deadline scheduling; Limitations of greedy approach: weighted scheduling
Divide and conquer: Counting inversions, nearest pair of points
Inductive solutions and overlapping subproblems: memoization, dynamic programming; weighted interval scheduling, grid paths with obstructions
Dynamic programming: longest common subword, longest common subsequence; recovering a witness
A C-like language: variable declarations, memory words, memory stack, array storage
A C-like language: dynamic memory allocation, garbage collection, parameter passing