Planeamento

Aulas Laboratoriais

Project Introduction

Aula 1

"Hello World" program in C and input parsing.

Pairing Heap Implementation

Aula 2

Project support. Drawing binomial heaps with graphviz. Loading heaps from a description.

Pairing Heap Implementation

Aula 3

Implementing the Unite operation.

Pairing Heap Implementation

Aula 4

Implementing the ExtractMin operation.

Modeling Second Project

Aula 5

Modeling the airport connection problem.

Implementing Union Find

Aula 6

Implementing the weighted quick-union data structure for the second project.

Kruskal Algorithm

Aula 7

Implementing Kruskal algorithm.

Borůvka's algorithm

Aula 8

Implementing Borůvka's algorithm.

Implementing a Suffix Tree

Aula 9

Discussion of structures for representing nodes.

Implementing Suffix Trees

Aula 10

Implementing tree construction and traversal operations.

Implementing Suffix Trees

Aula 11

Implementing the skip count trick operation. Solving exam exercises.

Implementing Suffix Trees

Aula 12

Debugging Ukkonen's algorithm.

Ukkonen's Algorithm

Aula 13

Final details on implementing Ukkonen's algorithm in linear time.

Aulas Teóricas

Course Introduction

Aula 1

Introduction to the AA course. O notation, see Introduction to Algorithms [CLRS Cap. 3]. Binomial heaps [CLRS Cap. 19].

Amortized Analysis and Fibonacci Heaps

Aula 2

Amortized analysis, binary counter, multipop stack and Binomial Heap unite [CLRS 2nd ED, Cap 18].
Fibonacci Heaps, operation algorithms and amortized analysis with a potential function [CLRS 2nd ED Cap 21].
Master theorem of recurrences [CLRS Cap 4].

Search Trees and graphs

Aula 3

Binary search trees, 2-3 Trees and B-Trees. Graph representation, simple searches on graphs, DFS+BFS. Minimum Spanning trees, algorithms, Prim, Kruskal and Boruvka.

Union-Find and String Matching

Aula 4

Algorithms for Union-Find, quick-Find, quick-Union, Weighted quick-union. Path compression heuristic and the Ackermann Function.
Sub-string search. Naive method, Knuth-Morris-Pratt and Rabin-Karp.

String Algorithms and Data structures

Aula 5

Online matching, Boyer-Moore. Suffix trees, definition, liner space bound, suffix links, Ukkonen's Algorithm.

Applications of Suffix Trees

Aula 6

Generalized suffix trees [Gusfield 7.3]. Longest Common Substring of more than two strings [Gusfield 7.4]. All-pairs suffix-prefix matching [Gusfield  7.10]. Circular string linearization [Gusfield 7.13]. Finding all maximal repetitive structures in linear time [Gusfield 7.12].

Lowest Common Ancestors

Aula 7

Suffix Arrays [Gusfield 7.14]. The Lowest Common Ancestor problem, reduction to Range Minimum Queries. Sparse table solution to RMQ. Optimal solution to RMQ +-1. Optimal solution to general RMQ with Cartesian trees. Finding all maximal palindromes in linear time [Gusfield 9.2].

Probabilistic techniques

Aula 8

Faster methods for tandem repeats [Gusfield 9.6].
Probabilistic techniques [Probability and Computing Chap.1],  verifying polynomial identities, axioms of probability, verifying matrix multiplication, a randomized min-cut algorithm.

Probabilistic Analysis

Aula 9

Random variables, Bernoulli, Binomial, Geometrical. Jensen's inequality, Meldable Heaps. Analysis of QuickSort, Markov's Inequality. Coupon's collector problem.

Markov Chains and Random Walks

Aula 10

Markov Chains definitions, hitting time, commute time and cover time. An algorithm for 2SAT. Stationary distribution. Random walks on undirected graphs. Bounds on commute and cover time. An algorithm for s-t path. Uniform generation of spanning trees.

Linear Time MSTs and Yao's Minimax Principle

Aula 11

Computing a Minimum Spanning Tree in expected linear time. Introduction to game theory and Yao's minimax principle.

Splay trees and Succint data structures

Aula 12

Move to front, competitive analysis. Splay trees, Optimality results. Succinct data structures, rank and select in constant time. Wavelet trees, Burrows wheeler transform and backward search.

Revisions

Aula 13

Solving exam exercises.