Algoritmos e Estruturas de Dados II
Todos os exemplos vistos em aula, bem como as notas de aula, estão
disponíveis em um repositório
git.
Para clonar o repositório, use o seguinte comando:
git clone https://github.com/pronesto/AEDs_II.git
.
O repositório está dividido em diretórios.
Cada diretório contém um arquivo
ClassNotes.txt
contendo o assunto coberto em aula.
Índice de Aulas

Oct 31  Sequential and Binary Search

Nov 7  Insertion in Binary Search Trees

Nov 9  Deletion in Binary Search Trees

Nov 14  Insertion in RedBlack Tree

Nov 16  Deletion in RedBlack Tree + the Set ADT

Nov 21  Hash Tables

Nov 23  Digital Search

Nov 28  Review

Nov 30  Final Exam.
Sequential and Binary Search
Key concepts

Sequential search is O(n), where n is the number of cells to traverse.

Binary search is O(log n), where n is the number of cells to traverse.

Binary search requires the input to be sorted.
Discussion

Find the largest integer in the C programming language.

Solve these exercises.
Reading
Insertion in Binary Search Trees
Key concepts

Binary Tree: an element is a tree. An element and two trees is a tree.

Binary Search Tree: an element is a tree. An element E and two trees, T1 and T2,
form a search tree if every element in T1 is less than E, and every element
in T2 is greater than E.

Insertion and search are O(log n) on average, where n is the number of elements
in the tree.

Insertion and search are O(n) on the worst case.
Discussion

Reconstruct a tree, given its pre and in order traversals.

Solve these exercises.
Reading
Deletion in Binary Search Trees
Key concepts

Deletion is O(log n) in the average case, and O(n) on the worst case, where
n is the number of elements in the tree.

A balanced binary search tree is a binary search tree with the additional
property that the number of elements in T1 and T2 differs by at most one.

We can transform a binary search tree into a balanced binary search tree in
O(n).

We can perform the union of two binary search trees in O(n).
Discussion

Generate a balanced binary search tree in O(n), given a binary search tree with
n nodes.

Solve these exercises.
Reading
Insertion in RedBlack Tree
Key concepts

A Binary Search Tree is RedBlack if, in addition to the properties of
BSTs, it has the following three properties:

Every node is red or black

Every red node has only black children

Every path from any node till a leaf has the same number of black nodes.

A RedBlack tree is balanced.

Insertion in a RedBlack tree is O(log n), where n is the number of nodes
already in the tree.
Discussion

Write a program to compute the black height of a RB Tree.
The binary height is the number of black nodes in any path from the root till
a leaf.

Solve these exercises.
Reading
Videos
Deletion in RedBlack Tree and the Set Abstract Data Type
Key concepts

Deletion is O(log n) in a RB Tree.

An Abstract Data Type is a type described by its properties, instead of
simply listing its elements.

The type is abstract because we abstract away details on how each operation is
implemented.
Discussion

Implement a set as a sorted array.
When do you sort the array?

Solve these exercises.
Reading
Videos
Hash tables
Key concepts

If the number of elements in the set is known, we can implement a perfect
hashing system.

Insertion, query and deletion are all O(1)

The drawback is memory: we might need plenty of it.

Bit maps reduce the memory requirement.

A hash table needs to use a method to handle collisions.

Separate chaining consists in using separate sets per hash bucket.
Discussion

Implement a sorting algorithm with a bit map.

Solve these exercises.
Reading
Digital Trees
Key concepts

Number of keys is known beforehand.

The height of the tree is limited by the number of bits in the keys.

We can adapt the tree to handle strings. In this case, path denotes prefix of
the string.
Discussion

Can you generate any finite language with a trie automaton?

Solve these exercises.
Reading