Computer Science Department / FCUP |
Advanced Topics in Algorithms 2019/2020
|
1st Half of the Material |
Important: carefully read the following page with changes made because of the ongoing pandemy
Information about Distance Learning in this Course (UPDATED)
All "face to face" classes suspended at the University of Porto!
(see official communication)
Instructors: |
Main Link |
In italic it is just a draft of the planned classes, that are subject to change and will be being confirmed as we keep moving forward.
Date | Class | Description |
---|---|---|
10/02 | #01 | Course Presentation; Balanced Search Trees I (intro and concepts) |
12/02 | #02 | Balanced Search Trees II (AVL, red-black) |
17/02 | #03 | Self-Adjusting Data Structures I (self organizing lists, amortized analysis, intro to splay trees) |
19/02 | #04 | Self-Adjusting Data Structures II (splay trees); Probabilistic Data Structures I (intro to treaps) |
24/02 | #05 | Probabilistic Data Structures II (treaps and skip lists) |
26/02 | #06 | Probabilistic Data Structures III (bloom filters); Spatial Data Structures I (intro, quadtrees) |
02/03 | #07 | No class given |
04/03 | #08 | Spatial Data Structures II (quad-trees, kd-trees) |
09/03 | #09 | Spatial Data Structures III (kd-trees, range trees, fr. cascading); LCA and RMQ I (buckets, sparse tables) |
11/03 | #10 | LCA and RMQ II (+/-1 case, cartesian tree); 1D Problems I (segment trees, lazy propagation) |
16/03 | #11 | Informations about new situation (COVID-19); supporting the project |
18/03 | #12 | String Matching I (naive, KMP and rabin karp) |
23/03 | #13 | String Matching II (tries, suffix trees, suffix arrays) |
25/03 | #14 | 1D Problems II (fenwick trees); supporting the project |