Information for the Written Exam
Date, Time and Place ("Normal Season", a.k.a. "Época Normal")
- Date: January 17th (friday)
- Time: 14:30
- Duration: 2h (+30m "tolerance")
- Rooms: B232, B231, B227, B229, B120, B119 [see allocation to rooms]
Valuation:
As you know as can be seen on the evaluation page or on Sigarra, the exam is worth 70% of the grade on this course (the other 30% come from the practical grade - check your grade here)
Exam Sample Questions:
The following PDF contains a sample of example exam questions (we want to give you an idea of some the types of questions we can ask on the exam). The number and difficulty of questions of the real exam will be calibrated for its duration.
Goals for the Final Exam
Items marked with an asterisk (*) are for valorization, that is, aimed at students who want to get a grade above 18.
Correctness
Correctness and Loop Invariants
- Understand the concept of loop invariant
- Be able to prove a loop invariant (checking Initialization and Maintenance, and the condition at Termination)
- Be able to prove that a simple algorithm using loops is correct using invariants
- Be able to prove that a simple recursive algorithm is correct, based on recursion invariants (e.g.: quicksort, mergesort, counting nodes in a binary tree, ...)
Asymptotic Analysis
Notation for orders of Growth
- Know the asymptotic notation (O, Ω and Θ) and its formal meaning
- Know how to compare functions using this notation
- Know how to justify why the relationship is O, Ω or Θ
- Know what worst-case, best-case and average-case analysis mean
- Know the usual complexity classes (constant, linear, logarithmic, linearithmic, quadratic, ...)
Analysis of the Complexity of a Program
- Know how to analyze the time cost of a simple program with loops and without recursion
- Know how to solve simple sums to calculate the time of a loop
- Know how to analyze a simple recursion (e.g.: which arises from a divide and conquer strategy) by writing the recurrence and using a recurrence tree
- Be able to characterize and compare space complexity
- Know how to estimate the complexity of a program by knowing the time it takes for a set of inputs
- Know how to predict the execution time of an algorithm when we know its complexity
Sorting (and Searching)
Concepts and Applications
- Understand the sorting problem and know the difference between comparison and non-comparison algorithms
- Know the worst case lower bound for any comparison sorting algorithm [Ω(n log n)] and know why such a limit does not apply for non-comparison sorting algorithms
- Know some applications of sorting (e.g.: computing frequency, select k-th number, union and intersection of sets, find out anagrams)
- Know the definition of stable sort algorithm
Algorithms
- Know the the algorithms MergeSort, BubbleSort, InsertionSort, SelectionSort and QuickSort, and CountingSort for arrays/vectors
- understand main ideas supporting their correctness
- know their time and space complexity
- be able to write them in code/pseudo-code (completely or excerpts)
- Understand the main ideas of RadixSort
Sequential Search
Know and understand the concept of sequential search and its time complexity
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)