Advanced Topics in Algorithms 2020/2021 (CC4020)

#01 - Binary Search Trees [41m23s]
Binary search trees: motivation, notation, concepts, searching, inserting and removal operations, execution cost, visualization, unbalanced trees, balancing strategies and a perfect BST.

Class #02 (18 Feb)

#02 - AVL Trees [38m31s]
Tree rotations; AVL Trees: concept, invariant, insertions, removals, worst case and complexity, advantages and disadvantages, visualization.

#03 - Red-Black Trees [45m44s]
Red-Black Trees: history and motivation, concept and invariant, worst case, proof of height, insertions, visualization, advantages and disadvantages.

Class #03 (24 Feb)

#04 - Self Adjusting Linked Lists and Amortized Analysis [1h17m2ss]
The concept of self-adjusting data structures. Revisiting amortized analysis and potential functions. Self organizing lists: classical rearrangement strategies - move to front (MTF), transpose and frequency count; amortized analysis of MTF strategy and its 2-competitiveness on a simple cost model.

Class #04 (25 Feb)

#05 - Splay Trees [1h00m39s]
Splay trees: motivation, concept, splaying, zig, zig-zag and zig-zig operations, intuitions on its behaviour, amortized analysis, advantages and disadvantages.

Class #05 (3 Mar)

(video to be added)
The concept of probabilistic data structures. The treap data structure: concept, operations and expected complexities. Random binary search trees and their relationship with treaps.

Class #06 (4 Mar)

(video to be added)
The skip list data structure: concept, operations, expected number of levels and complexities; the bloom filter data structure: motivation, concept, operations and expected false positive rate.

Class #07 (10 Mar)

#09 - Quadtrees and Variants [1h04m38s]
Spatial Data Structures and some typical tasks: searching, nearest neighbour queries, range queries; Quadtrees and variants: point-region quadtrees, matrix quadtrees, point quadtrees, balanced quadtrees, height lemma.

Class #08 (11 Mar)

#10 - KD-trees and Range Trees [1h13m36s]
KD-Trees and variants: inserting, deleting, producing a balanced tree, simple nearest neighbor, incremental generalized k-nearest neighbour with priority queues, range queries and an upper bound on the number of stabbed cells. 2D range trees: range search and fractional cascading.

Class #09 (17 Mar)

#11 - LCA and RMQ (buckets, sparse tables, cartesian trees) [1h34m12s]
LCA and RMQ problems; reductions between both problems; sqrt buckets for RMQ, sparse tables for RMQ; a faster and general linear algorithm for RMQ.

Class #10 (18 Mar)

#12 - Segment Trees and Lazy Propagation [42m14s]

#13 - Cumulative sums and Fenwick Trees [36m13s]
Segment trees, variants and their application to practical problems; lazy propagation on trees; binary indexed trees (also known as fenwick trees) for cumulative frequency tables and their application so practical problems.

Class #11 (24 Mar)

#14 - String Matching: naive, KMP, Rabin-Karp [1hm29m19s]
String Matching problem; naive algorithm; Knuth-Morris-Pratt algorithm; Rabin-Karp algorithm.

Class #12 (25 Mar)

#15 - String Matching: Suffix Trees and Suffix Arrays [49m43s]
Tries; compressed prefix trees; suffix trees; suffix arrays; applications.