Binary Search

• Know and understand the concept of binary search and its time complexity
• Know and understand the generalization for the yes/no case
• Know and understand the bisection method
• Know how to write/complete code/pseudo-code for a binary search simple, yes/no or with bisection

Abstract Data Types (ADT)

• Understand what an Abstract Data Type (ADT) is
• Know how to create a simple ADT (member types and member functions)
• Understand that there may be several possible implementations for the same ADT, with consequent advantages and disadvantages and different time and memory complexities

ADT: Lists, Stacks and Queues

Linked List Basics

• Understand the notion of node, singly linked list, doubly linked list, circular list (singly and doubly linked)
• Understand the main methods (e.g. size, adding and removing elements)
• Be able to implement simple list methods

Sequential (or linear) ADTs

• Understand the concept of the Stack ADT, the order in which it accesses the elements and the main methods (push and pop)
• Understand the concept of the Queue ADT, the order in which it accesses elements and the main methods (enqueue - C++ STL push and dequeue - C++ STL pop)
• Know the concept of ADT Deque, the order in which it accesses the elements and the main methods (add and remove at the beginning and end)

Some Applications (of sorting and ADTs) to Geometric Problems (*)

• Know and understand how binary search can be used to check if a point belongs to a convex polygon, given the sequence of its vertices (in CCW or CW order) in an array
• Know the algorithm by Graham (Graham's scan) and the incremental algorithm (by Edelsbrunner) to compute the convex hull of a set of points in the plane
• Understand orientation tests (left-turn, right-turn and collinear), their definition using cross product, and application to these problems

ADT: Binary Trees

Tree Basics

• Understand the concept of tree
• Know the basic terminology (e.g. nodes, root, leaves, children, parents, height, depth)

Simple Binary Trees

• Understanding the concept of binary tree
• Learn how to implement a simple binary tree with generic content
• Know how to implement simple recursive methods (e.g. number of nodes, height, write all nodes)
• Understand the concepts of depth-first search (preorder, inorder and postorder) and breadth-first search, knowing how to implement them

ADT: Balanced Binary Search Trees

Concepts and applications

• Understand the concept of binary search trees, including searches, insertions and deletions
• Understand in what cases the tree can become unbalanced
• Know some possible applications of binary search trees and the concepts of set, multiset, map and multimap

AVL Trees

• To understand the concept of AVL trees, their invariants, worst case and height
• Understand and know how to apply the concept of a simple rotation
• Understand the unevenness caused by insertions/removals and how they can be corrected with rotations
• Know some advantages and disadvantages of AVL trees

Red-Black Trees

• To understand the concept of Red-Black trees, their invariants, worst case and height
• Understand the unevenness caused by insertions and how they can be corrected
• Know some advantages and disadvantages of Red-Black trees

ADT: Graphs

Introduction and Terminology

• Know what a graph is (nodes/vertices and edges/arcs/links)
• Understand what nodes and edges of a given graph represent in a some problem model
• Know the usual terminology: directed and undirected graph, degree of a node (in-degree and out-degree), adjacent/neighbor node, loop, multigraph, dense or sparse graph, simple path (and cost), cycle, acyclic graph, distance between two points, diameter of a graph, subgraphs, connected graph and connected components, cliques, triangles, trees and forests, bipartite graph.

Graph Representation

• Know the Adjacency Matrix and Adjacency List data structures and know how they represent a graph.
• Know how to implement them in code.
• Know the advantages and disadvantages of each of these data structures.

Concepts of Graph Traversal

• Know what depth-first search (DFS) and a breadth-first search (BFS) are
• Given a graph, find out in which order the nodes are traversed with DFS or with BFS.
• Be able to produce and/or complete code/pseudo-code for a DFS and for a BFS.
• Understand time and space complexity of DFS and BFS (for graphs supported by adjacency lists or adjacency matrix)

Simple DFS Applications

• Know how to discover connected components in an undirected graph using DFS
• Know what a topological ordering of a directed graph is and how to use DFS to find it
• Know how to use DFS to check/find a cycle in a directed graph

More Advanced DFS Applications

• Know and understand the concept of DFS search tree
• Know how to classify the edges in a DFS visit: tree, back, forward and cross edges
• Know what strongly connected components are
• Know and understand Tarjan's algorithm to discover strongly connected components (*)
• Know what articulation points and bridges are
• Know and understand a linear algorithm with DFS to discover articulation points (*)

BFS Applications

• Know how to discover connected components in an undirected graph using BFS
• Understand how BFS can be used to find minimum distances and shortest paths in unweighted graphs (with path length defined by the number of edges in the path)

ADT: Hash Tables

Concepts and Hash Functions

• Understand the concept of hash table and hash function
• Know the concepts of modular hashing and polynomial hashing
• Know properties an hash function should have
• Know the concepts of collision, table size, load factor, and resizing
• Know the time complexity to retrieve from a hash table if there are no collisions or on simple collisions
• Know some advantages/disadvantages of hash tables vs. balanced search trees

Collision Strategies

• Know what is separate chaining (a.k.a.~open hashing), and some of its advantages/disadvantages
• Know what is open addressing (a.k.a.~closed hashing), linear and quadratic probing, and some of its advantages/disadvantages

ADT: Priority Queues (and Heaps)

Concepts

• Understand the concept of the ADT Priority Queue and the main operations (inserting and removing priority elements)
• Know what a (binary) heap is and how it works, how it stores elements in an array, which invariant it maintains, how it can be used to implement a priority queue and what complexities it guarantees for its operations

Applications

• Understanding why creating a heap from an array takes linear time (*)
• Know the HeapSort algorithm for sorting an array (main idea, correctness and time and space complexity)

Pedro Ribeiro & Ana Paula Tomás (DCC/FCUP) / Last Update: