Course page for IT-math, Spring 2003 (F2003)

The Curriculum for the course is adequately reflected in the description of the contents of the Episodes and the corresponding reading material below. Remember however that it is the students' problem-solving skills that are the direct object of the examination.

The real exam takes place on June 10, 9.00-13.00 in room 0.10. Our external censor is Lars Kristiansen from Oslo University College.

Test Exam, now complete with solutions, is available.

Teachers: Carsten Butz, room 1.17, office hours Monday 12.00-13.00; Volodya Shavrukov, room 2.09, office hours Thursday 14.45-15.45.

Textbook: S.Washburn, T. Marlowe, C.T. Ryan. Discrete Mathematics. Addison-Wesley 2000. ISBN 0-201-8836-8.

Newsgroup: it-c.courses.ITM on news.it-c.dk

Here is a short summary that may help the interested parties with the revision of high-school algebra.

Episode 1, February 4.	Introduction. Discussion of a sample proof. Pascal triangle. Inductive (or recursive) definitions. The method of mathematical induction. Binomial coefficients.	Homework Exercises, and Selected solutions.	Parts of sections 1.1, 1.2, 1.5, and 5.1 from our textbook are relevant to this episode's material.
Episode 2, February 11.	Key theorems on binomial coefficients. The number of edges in a complete graph on n vertices. Proofs by induction. Splitting a proof into cases. The ∑ notation for sums. Application: A proof of program correctness.	Classroom and Homework Exercises (corrected February 18, 2003), and Selected solutions.	Sections 1.1, 1.2, the very beginning of 4.1, and the subsection `Application' in 6.3. Here is also some supplementary material on program correctness, and on binomial coefficients.
Episode 3, February 18.	Sets and subsets. Set-theoretical operations: union, intersection, difference, complement. Venn diagrams. The power set. Cardinality of (=the number of elements in) a finite set. (Ordered) pairs and n-tuples. Cartesian products.	Classroom and Homework Exercises (corrected February 24, 2003), and Selected solutions (corrected March 7, 2003).	Sections 1.3 and 1.4 in the textbook.
Episode 4, February 25.	Integers and divisibility. Primes and prime factorizations. Strong (aka complete) induction. The least number (aka the well-ordering) principle. Division with remainder. The greatest common divisor. Euclid's Algorithm. Uniqueness of prime factorization. Infinitude of primes. Proofs by contraposition and by contradiction.	Classroom and Homework Exercises, and Selected solutions.	Section 2.1 in the textbook. Supplementary material on gcd's and Euclid's Algorithm.
Episode 5, March 4.	Modular arithmetic.	Classroom and Homework Exercises, and Selected solutions.	Section 2.3 in the textbook.
Episode 6, March 11.	Base n (aka radix n) representation of integers. Integer arithmetic in Java. Relations. Reflexivity, irreflexivity, symmetry, antisymmetry, transitivity. The digraph of a binary relation on a set A. Partially ordered sets.	Classroom and Homework Exercises (corrected March 14, 2003), and Selected solutions.	Section 3.1, starting with definition 3.1.4. Supplementary material on base-n representations of integers.
Episode 7, March 18.	Examples of partially ordered sets. Hasse diagrams. Matrices of binary relations. Equivalence relations, equivalence classes, and partitions.	Classroom and Homework Exercises (corrected March 31, 2003), and Selected solutions (updated March 31, 2003).	Section 3.1, starting with definition 3.1.4; section 2.1, starting with definition 2.1.3; and The Sum Rule in section 3.2. Also, supplementary material on matrices of relations.
Episode 8, March 25.	Functions. Arrow diagrams. Hashing. Functions and counting. The Pigeon-hole Principle. One-to-one and onto functions.	Classroom and Homework Exercises (corrected April 7, 2003), and Selected solutions.	Sections 3.1 and 3.2. Supplementary material on functions.
Episode 9, April 1.	Bijections, composition, and inverse functions. Using bijections for calculating the number of elements of a set. The number of bijections between two n-element sets.	Classroom and Homework Exercises (corrected April 7, 2003), and Selected solutions.	Sections 3.1 and 3.2, up to and including Example 8.
Episode 10, April 8.	The formula for binomial coefficients. Rates of growth of functions: Big O, Ω, and Θ, small o. First properties of growth rates. How long does Euclid's Algorithm work?	Classroom and Homework Exercises, and Selected solutions (corrected May 5, 2003).	Supplementary material on growth rates of functions (corrected April 28, 2003). One might also take a look at Section 8.3.
Episode 11, April 22.	The rates of growths of logarithms versus polynomials versus exponents. The rate of growth of logn! How much does an algorithm have to work to sort a list? Introduction to automata and languages.	Classroom and Homework Exercises (corrected April 28, 2003), and Selected solutions.	Supplementary material on growth rates of functions (corrected April 28, 2003) and on complexity of sorting algorithms. For automata and languages, look at section 10.2 up to and including Example 2.
Episode 12, April 29.	Operations on languages: Boolean operations, concatenation, the Kleene star. Regular expressions. Context-free and regular grammars. Backus-Naur normal form. Non-deterministic automata. Characterizations of regular languages (via regular expressions, regular grammars, and non-deterministic automata).	Classroom Exercises.	Sections 10.1 and 10.2. Supplementary material on automata, regular expressions, and grammars, and Backus-Naur forms.