Past lectures autumn 2007

Lecture 1

Keywords: Introduction to combinatorial thinking.
References: No references.

Lecture 2

Keywords: Set theory: sets, set operations, describing sets by rules of inclusion, the multiplication principle.
References: [J] 2.1, 4.1, study guide for Block 1, Lecture Notes p. 1 - 16.

Lecture 3

Keywords: Partitions, the addition principle, the principle of inclusion-exclusion, permutations and combinations.
References: [J] 4.1, 4.2, 4.3, study guide for Block 1, Lecture Notes p. 17 - 21f.

Lecture 4

Keywords: Sequences, recursive definition and definition by general term. Fibonacci numbers, strings. Sigma notation.
References: [J] 2.2, 5.1, study guide for Block 2, Lecture Notes p. 22 - 33.

Lecture 5

Keywords: Recap + more about Sigma notation, product notation. The Division algorithm, positional number systems, change of number base.
References: [J] 2.2, 2.3, study guide for Block 2, Lecture Notes p. 29 - 43.

Lecture 6

Keywords: Integers and divisibility, multiples, factors, units, primes and composite numbers, a simple primality test, linear combinations, greatest common divisors, Euclid's algorithm.
References: [J] 3.3, 3.4, study guide for Block 3, Lecture Notes p. 44 - 56.

Lecture 7

Keywords: Greatest common divisors and Euclid's algorithm (forwards and backwards). The Fundamental Theorem of Arithmetic.
References: [J] 3.4, study guide for Block 3, Lecture Notes p. 55, 57 - 66.

Lecture 8

Keywords: Modular arithmetic.
References: Study guide for Block 4, Lecture Notes p. 67-75.

Lecture 9

Keywords: Modular arithmetic and solving equations modulo n.
References: Study guide for Block 4, Lecture Notes p. 73, 76-85.

Lecture 10

Keywords: Relations on a set.
References: [J] 2.4, 2.5, study guide for Block 4, Lecture Notes p. 86-94.

Lecture 11

Keywords: Recap: relations on sets. Relations between two sets, functions. The 1-1 and onto properties for functions.
References: [J] 2.8, study guide for Block 4, Lecture Notes p. 87-105.

Lecture 12

Keywords: Recap: one-to-one, onto and bijective functions. Inverse functions. Introduction to mathematical thinking and logic.
References: [J] 2.8, study guides for Blocks 4 & 5, Lecture Notes p. 100-108.

Lecture 13

Keywords: Introduction to mathematical thinking and logic: primitive propositions, negations, conjunctions and disjunctions. The IF-THEN statement and its importance for proofs. Examples of 'bad' logic.
References: Study guide for Block 5, Lecture Notes p. 109-122.

Lecture 14

Keywords: Introduction to proof techniques: direct proof, contrapositive proof, proof by contradiction, proving biconditional statements, finding counterexamples. The induction principle.
References: Study guide for Block 5, Lecture Notes p. 120-125.

Lecture 15

Keywords: More on proof techniques: One more proof by contradiction, proving biconditional statements, finding counterexamples. The induction principle. Examples of proof by induction.
References: Study guide for Block 5, Lecture Notes p. 122-132.

Lecture 16

Keywords: One more proof by induction. Recap of assignments 3 and 4. Solution of linear homogeneous recurrence relations.
References: Study guide for Block 5, Lecture Notes p. 132(a)-132(g).

Lecture 17

Keywords: An introduction to graph theory. Terminology: graphs, simple graphs, digraphs, subgraph of a graph, complement of a graph, the degree of a vertex, the degree sequence of a graph. The Handshaking Lemma and how to use it. Adjacency matrix, incidence matrix of a graph.
Special graphs: regular graphs, the complete graphs K_n, bipartite graphs, complete bipatite graphs K_m,n.
References: [J] 6.1, 6.5, Study guide for Block 6, Lecture Notes p. 133-152.

Lecture 18

Keywords: More graph theory: Paths, simple paths, cycles, simple cycles, connected graphs, components. Isomorphisms of graphs: the formal definition, how to spot isomorphic graphs, how to construct an isomorphism between two graphs known to be isomorphic, how to prove that two graphs are non-isomorphic.
Trees: the definition of a tree, proof that a tree on n vertices has n-1 edges, rooted trees and their terminology. Spanning trees, in particular breadth-first search and depth-first-search spanning trees.
References: [J] 6.2, 6.6, 7.1, 7.2, 7.3, Study guide for Block 6, Lecture Notes p. 153-158e.

Lecture 19

Keywords: More graph theory: Weighted graphs, Dijkstra's shortest path algorithm, Kruskal's and Prim's algorithms for finding a minimal (i.e. minimum weight) spanning tree in a weighted graph.
Hamiltonian and Eulerian cycles.
References: [J] 6.4, 7.4, 6.3, Study guide for Block 6, Lecture Notes p. 159-165.

Lecture 20

Keywords: The traveling salesperson problem.
References: [J] 6.3, Study guide for Block 6, Lecture Notes p. 166-167.

Lecture 21

Keywords: Revision (in particular combinatorics).
References: Revision Notes.