# Algorithms and Data Structures - Spring 2021

## Lectures and Material

• Course introduction: course organization and policies; Example of the Fibonacci sequence: a bad algorithm and a good algorithm; implementation-independent behaviors and algorithmic complexity.
• Complexity under the RAM model. Asymptotic growth of functions: big-O, Omega, and Theta notations.
• Basic elements for the analysis of algorithms: complexity and correctness of insertion-sort; worst-, best-, and average-case complexity; loop invariants.
• Divide and conquer strategy: binary search, merge, merge sort, recursive multiplication, median and k-smallest selection.
• Quick-sort. Heaps and heap-sort.
• Elementary data structures and hash tables.
• Binary search trees. Randomized binary search trees.
• Review or binary trees. Height of a BST in the average case: simulation and visualization.
• Midterm exam.
• Red-Black trees: introduction.
• Review of BST deletion. Red-black trees: deletion. Exercises. (OPTIONAL)
• B-Trees. Data structures in secondary storage: modeling disk access. Structure, search, and insertion in B-trees. Relation with red-black trees. (OPTIONAL)
• Radix-search. Tries, and ternary search tries. Exercises. (OPTIONAL)
• Exercises from past exams.
• Convex hull: ordering the points, analogy with sorting. (OPTIONAL)
• Randomized Algorithms: randomized variants of already-seen deterministic algorithms, Monte Carlo and Las Vegas algorithms, examples. (OPTIONAL)
• Graphs: representation and elementary algorithms.
• Minimal spanning trees; Disjoint sets. (OPTIONAL)
• Dijkstra's Algorithm.
• Greedy algorithms: general strategy, activity selection, Huffman codes.
• Dynamic programming: examples, and general strategy.
• Basic elements of complexity theory: polynomial-time algorithms and problems; the P complexity class; the NP class; polynomial-time reduction and NP-completeness; satisfiability.
• Exercises.
this page is maintained by Antonio Carzaniga and was updated on June 07, 2021