Algorithmic complexity and cryptography - KAIN7M04

Goal(s)

1) Know how to model a real-world problem as a graph problem (application to transportation, scheduling, game, assignment, etc.)
2) Know how to solve a graph problem using classical algorithms (whose complexity will be mastered) and justify the optimality of the proposed solution.
3) Know how to reason about discrete structures, particularly how to write a proof, the specific justification of an algorithm, and especially induction.
4) Know how to calculate the complexity of a sophisticated algorithm (recursive, variable-length loops, or using an advanced data structure such as Union-Find)
4) Know how to identify NP-complete problems, prove that they are in NP, and properly perform a polynomial reduction

Content(s)

0) Review on graphs: basic vocabulary and graph representation
1) Review on algorithmic complexity: O(...) notation, complexity of a recursive algorithm, complexity of a variable-length nested double loop, complexity linear in the number of edges on a graph
2) Concepts of connectivity, traversal, and Eulerian graphs
3) Unrooted trees and minimum spanning trees; Kruskal's algorithm with Union-Find implemented as a forest: what is the complexity gain?
4) Coloring and some special classes: bipartite graphs, planar graphs (4-color theorem), interval graphs
5) Matching and transversals; König's theorem in the bipartite case
6) Flows and cuts; Ford-Fulkerson algorithm; max-flow/min-cut theorem
7) P and NP complexity classes

• basic vocabulary of complexity: instance; decision problem versus optimization problem; complexity of a problem versus complexity of an algorithm ; brief mention of the Turing machine for algorithm definition
• NP-difficulty reduction; Cook-Levin theorem
• NP-complete problems, mainly from graph theory or Boolean satisfiability (SAT): Clique, Stable, Vertex Cover, Coloring, Traveling Salesman, Hamiltonian Cycle, 3-SAT and some of its variants, Subset Sum, Knapsack

Basic algorithms; algorithm analysis techniques: time complexity, invariants

Test

Calendar

The course exists in the following branches:

• Curriculum - INFO - Semester 7

Additional Information

Course ID : KAIN7M04
Course language(s):

You can find this course among all other courses.