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

1. Oct 31 - Sequential and Binary Search
2. Nov 7 - Insertion in Binary Search Trees
3. Nov 9 - Deletion in Binary Search Trees
4. Nov 14 - Insertion in Red-Black Tree
5. Nov 16 - Deletion in Red-Black Tree + the Set ADT
6. Nov 21 - Hash Tables
7. Nov 23 - Digital Search
8. Nov 28 - Review
9. 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

• Sequential Search
• Binary Search

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

• Binary Tree
• Binary Search Tree

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

• Deletion in Binary Search Tree
• Merge two binary search trees

Insertion in Red-Black Tree

Key concepts

• A Binary Search Tree is Red-Black 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 Red-Black tree is balanced.
• Insertion in a Red-Black 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

• Red-Black Trees
• Implementation and tutorial

Videos

• Introduction
• Simple rotation
• Double rotation
• Insertion

Deletion in Red-Black 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

• Removal in Red-Black Tree
• Abstract Data Type

Videos

• Deletion patterns
• Examples of node removal

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

• Hash tables
• Separate chaining

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

• Digital Tree
• Radix Tree