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.

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.

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.

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.

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.

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.

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.

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.