MA014G
Algebra och Diskret Matematik A
Campuskurs Sundsvall

• This course is now over and these pages will no longer be updated. It has been a pleasure teaching you! Bonus points gained HT08 are no longer valid for omtentor on this course. Omtentor will be announced on the university examination timetable.[090127]


• A set of revision notes, a model exam paper with solutions and a selection of old exam papers, some with full solutions, are now available from the resources bar left. A formula sheet will be attached to your tenta, a copy of this has also been uploaded for your information. [081011]


• Remember to sign up for the tenta. You do this online via the portal. You must sign up at least a week before the tenta date. If you want to sit the tenta at a different place than on campus, you must make arrangements with the external institution and contact Veronica or Viktoria at least three weeks before the tenta date. [081006]


• A note on how the course is organised and my bonus point system for the tenta can be found by clicking here or via the link in the resources bar left. [080811]

Lecture 1: Wednesday 3 September 2008 at 8.15am in M204.

Keywords: Introduction to combinatorial thinking.
References: No references. Please bring your book with you.

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: 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: 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. 95-107.

Lecture 12

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. 108-122.

Lecture 13

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 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: proving biconditional statements, finding counterexamples. The induction principle. Examples of proof by induction. Solution of linear homogeneous recurrence relations.
References: Study guide for Block 5, Lecture Notes p. 122-132, 132(a)-(g)

Lecture 16

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 17

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 18

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 19

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

Lecture 20

Keywords: Revision (in particular sets, proofs, combinatorics).
References: Revision Notes.

Lecture 21

Keywords: Revision (in particular relations and modular arithmetic).
References: Revision Notes.