CC4010 - Algoritmos

2022/2023

Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto

Materials (useful links)

Lectures

16.09.2022


Course introduction: goals, evaluation, a glimpse on the syllabus; Motivation for studying algorithms, their correctness and complexity. Loop invariants and their role in proving correctness of iterative algorithms. Examples of invariants for loops in algorithms for finding the index of the first occurrence of the maximum of an array, under different assumptions on the problem instances.

20.09.2022

Loop invariants and their role in proving correctness of iterative algorithms. Example: problem 2 of the exercise sheet 1 (check Sigarra - "Documents" folder for CC4010).
Introduction to the analysis of time complexity.

23.09.2022

Introduction to the analysis of time complexity. Definition of costs for elementary operations (under the RAM model). Asymptotic complexity. Order of growth and Big-O, Big-Theta, Big-Omega notations. Comparing orders of growth. Selection sort: analysis of loop invariants and worst case and best case time complexity.

27.09.2022

Comparison-based sorting algorithms: recap of selection sort; analysis of insertion sort and mergesort (also, mentioned but not presented in class: heapsort, bubblesort, quicksort). Proof that the recursion T(n) = 2T(n/2) + cn solves to T(n) in Θ(n log n), using the recursion tree, assuming n is a power of 2. Idea of the proof that the worst case time complexity of any comparison-based sorting algorithm, that given a_1, ... a_n, only gets information using questions like " a_i > a_j? ", following a binary decision tree model, is Ω(n log n). Optimality of mergesort (in the worst case).

30.09.2022

Applications of sorting.
Algorithms for computing the convex hull of n points in the plane:
  1. Graham scan algorithm - O(n log n) - based on a rotational sweep; orientation tests (analysis of left-turns and right-turns by cross product)
  2. Jarvis' march (gift-wrapping) - an output sensitive algorithm - O(nh), where h is the number of vertices of the convex hull
  3. An incremental algorithm - O(n log n) - with a preprocessing step to sort the set of points by increasing order of x-coordinate; without sorting in a preprocessing step, but using a O(log n) time algorithm to check whether a point belongs to a n-vertex convex polygon based on binary search.
  4. Idea of the divide and conquer algorithm - O(n log n) - by Preparata and Hong. Computation of lower tangents and upper tangents in O(n)
Proof that the runtime (in the worst case) of any algorithm for computing the convex hull of n points in the plane is Ω (n log n), by reducing the problem of sorting a vector x of n integers to the problem determining the convex hull of the points (x_i, x_i^2), with 1 ≤ i ≤ n.

04.10.2022

Other applications of sorting and/or the divide-and-conquer design pattern: Introduction to the master method for solving recurrences of the form T(n) = a T(n/b) + f (n) , where a ≥ 1, b > 1, and f is asymptotically positive. Analysis based on the recursion tree.

07.10.2022

Quicksort: function partition (loop invariant that justifies its correctness); correctness of quicksort; time complexity in the worst case and best case, and for split ratios (r: 1-r), with 0 < r < 1 (analysis for = 1/2, and r= 1/10). Analysis using the recursion tree.

11.10.2022

Randomized quicksort. Expected running time O(n log n).
Order Statistics: how to select the ith smallest of n elements (the element with rank i)? Examples: the cases i=1 (minimum element), i=n (maximum element) and i = n/2 (median).
Worst-case running time using merge sort. Quickselect: a randomized divide-and-conquer algorithm with O(n) expected running time. Median of medians of five: a worst-case linear-time deterministic algorithm.

14.10.2022

Brief mention to Strassen's Algorithm for computing the product of two nxn in sub-cubic time.
Notion of stable sorting algorithm. Sorting in linear-Time: Counting sort and radix sort.

18.10.2022

Notion of amortized complexity (for a sequence of operations on a data structure): aggregation method, accounting method and potential method. Illustration of the methods: dynamic table (expansion of a vector by a single position and by duplicating the space); Binary Counter; stack (push, pop, multipop).

21.10.2022

Greedy strategies for solving optimization problems.
Applications: Coin changing problem: making an amount using the fewest number of coins; proof of the correctness of the greedy strategy for the set of coin values {1, 2, 5, 10, 20, 50, 100, 200}, assuming the number of coins is infinite; observation that the greedy strategy can fail if the number of coins is finite or for other sets of coins (eg, {1,300,1000}); Interval scheduling problem: analysis of some greedy strategies (not all correct); proof that "earliest finish first" strategy finds an optimal solution.

25.10.2022

The greedy algorithm for finding a maximum weight base of a matroid. Applications: (1) Unit Task Scheduling (sketch of the proof that it gives rise to a weighted matroid). (2) The matroid defined by the set of columns of a matrix (brief reference to an application to traffic count planning for intersections). (3) The graphic matroid M(G) of graph G=(V,E), where M(G) = (E, {F : F is a subset of E such that (V,F) is acyclic}) and the relation to Kruskal algorithm (formal proof that M(G) is a weighted matroid not covered in class).

28.10.2022

Recap of Prim's algorithm for finding a minimum (or maximum) spanning tree of a weighted connected undirected graph. Priority queues implemented by binary heaps. Heap structure. Notion of parent, left child and right child of a node. Minimum heap and maximum heap. Function buildMaxHeap (or buildMinHeap) and MaxHeapify (MinHeapify). Proof that the largest subtree of a heap with n elements has a maximum of 2n/3 elements. Recurrence that defines an upper bound on the complexity of heapify(1). EXTRACT_MIN (EXTRACT_MAX) and DECREASE_KEY (INCREASE_KEY) functions. Heapsort: comparison sort algorithm with optimal temporal and spatial complexity ("in-place" algorithm).

31.10.2022-04.11.2022

No class .

08.11.2022

Introduction to Dynamic Programming. Applications to combinatorial optimization problems: optimal substructure and overlapping subproblems; computing solutions using a bottom-up or top-down (with memoization) strategy. Examples of applications of DP to different problems: Fibonnacci sequence; Number Pyramid; Coin-change (with restrictions); all-pairs shortest paths problem in graphs (Floyd-Warshall algorithm); and a brief mention to Kleene's method for computing a regular expression that describes the language accepted by a finite automaton.

11.11.2022

Review for mid-term test.

15.11.2022

Mid-term test.

18.11.2022

Examples of applications of Dynamic Programming. Counting paths in graphs.
Minimum edit distance between two strings.

22.11.2022

Fundamentals of NP-completeness. Computability and complexity: algorithms; decidability; existence of undecidable problems (example: the halting problem). Complexity of algorithms versus complexity of problems. Brief introduction of some problems: graph coloring (planar 3-color vs planar 4-color); longest path versus smallest path; vertex cover for graphs (bipartite graphs vs generic graphs); set cover.
Polynomial-time reduction of a problem X to another problem Y to characterize the relative complexity of problems (Karp's reductions): X ≤pY; Consequence: if there is a polynomial algorithm that solves Y then there is a polynomial algorithm that solves X; if there is no polynomial algorithm that solves X then there is no polynomial algorithm that solves Y. Example: reduction of vertex cover to set cover. Computational complexity of problems: Classes P, NP and NPC (i.e., NP-complete problems). NP-hard problems. The "P = NP?" problem. Examples of NP complete problems: SAT, 3-SAT, VERTEX COVER, HAMILTONEAN CYCLE, INDEPENDENT SET, SET COVER.

25.11.2022

Copying with intractability. Introduction to approximation algortithms for NPO problems (optimization problems whose decision version belongs to NP). Polynomial time approximation algorithms with known approximation factor. Class APX (i.e, problems that admit constant factor polynomial-time approximation algorithms). Proof that MINIMUM VERTEX COVER belongs to APX (2-approximation based on finding a matching in G and based on LP rounding).

28.11.2022

Polynomial time approximation algorithms with known approximation factor. Proof that an NPO problem is NP-hard by a polynomial-time reduction from a NP-complete (i.e., NPC) problem. Example: proof that TSP (the traveling salesperson problem) is NP-hard by reduction from HAMILTONEAN_CYCLE in undirected graphs.
Metric TSP (i.e., TSP whose distance function satisfies the triangular inequality): 2-approximation algorithm; (3/2)-approximation algorithm by Christofides; proof of correctness of these approximation factors. Inapproximability (unless P = NP) of the generic TSP problem by a polynomial-time algorithm for any polynomial-time computable function α(n) (proof by reduction of HAMILTONEAN_CYCLE to TSP).

02.12.2022

Greedy algorithm for SET COVER (minimum cardinality set cover): idea of the proof that it gives a O(log n) approximation algorithm.
Introduction to guarding problems in polygons: proof by Fisk of a result by Chvátal that n/3 are always sufficient and occasionally necessary for guarding a simple polygon with n vertices. Minimization of the number of guards, for any given instance: statement without proof that the problem is NP-hard; idea of the approximation algorithm by Ghosh (for guards in vertices), based on a reduction from SET COVER.

06.12.2022

Idea of an anytime algorithm for finding an optimal vertex guard set by successive approximations.
A glimpse on two proofs of NP-hardness of variants AGP for two subclasses of orthogonal polgygons (thin orthogonal polygons and generic SCOTS). (Obs: There will be no question about these proofs in the exams)
Some exercises on NP-hardness and approximation algorithms. Definition of PARTITION and statement (without proof) that it is NP-complete. BIN PACKING: proof that it is NP-hard by reduction from PARTITION; proof that it belongs to APX by showing that the "first fit strategy" yields a 2-approximation. Brief mention that "first fit decreasing" strategy gives a 3/2-approximation. Proof of the inapproximability of bin packing for any constant smaller than 3/2, unless P=NP, by reduction from PARTITION.

09.12.2022

Solution to the first question of the mid-term test (2022/2023).

Relationship to the Load-balancing problem. Proof that the greedy algorithm gives a 2-approximation for load-balancing (brief mention, without going to the proof, that if the jobs are sorted in decreasing order of processing time, the greedy algorithm gives a 3/2-approximation).

13.12.2022

Review for the test. Discussion of exam questions from previous years (in particular, 2019/2020) - about load-balancing; the art-gallery problem; minimum-edit distance.
© Ana Paula Tomás, Departamento de Ciência de Computadores, FCUP, Universidade do Porto, 2022-2023