Foundation of Computer Science

Week 1: Basic concepts of combinatorics: permutations, variations, combinations, binomial coefficient, nimonial theorem

Week 2: Basic concepts of graph theory (vertex, edge, degree, isomorphism). Path, circuit, connectivity, trees.

Week 3: Shortest path, BFS, Dijkstra, Ford, Floyd algorithms, widest paths in directed and undirected graphs

Week 4: DFS, directed cycles, fundamental system of cycles and cuts, PERT

Week 5:  Euler- and Hamiltonian circuits, sufficient and necessary conditions for the existence. Dirac, Ore theorems,

Week 6: Graph coloring problems (vertex, edge and map coloring). Bipartite graphs. Flows, Ford-Fulkerson theorem, algorithm to find a maximal flow. Integral maximum flow lemma.

Week 7:  Multiple source flows, vertex capacities, undirected flows.

Week 8: Bipartite graphs, matchings, Hall's theorem, algorithm to find a maximal matching. Independent and covering vertex and edge sets, König's and Gallai's theorems. 

Week 9: Planar graphs, duality. Euler's Theorem, Kuratowski's theorem, four color theorem.

Week 10: Basic concepts of algorithms and complexity. Polynomially solvable and NP-complete problems, coNP.

Week 11: Karp-reduction, Cook-Levin theorem, famous NP-complete problems: SAT, HAM, 3-COLOR, k-COLOR, MAXSTABLE, MAXCLIQUE, HAMPATH.

Week 12:  Basic concepts in number theory: divisibility, primes,  fundamental theorem of number theory, number of divisors, distribution of primes

Week 13: Congruences, diophantine equations, Euler-Fermat theorem,

Week 14: Algorithms in number theory: prime tests, public key cryptography, RSA.