See the course description at kursus.ruc.dk for a brief and
formal description of the course. Practical information can be found at the Moodle page of the
course (requires login). All daytoday information will be sent via Moodle
to your RUC email account, so please read your RUC email regularly.
This page
describes the content and structure of the course. In the following, the main subjects of the
course are described; a detailed description of the structure of the course can
be found further down the page.
·
Sets and functions Two course days cover sections 2.1  2.3 in the
book, which concern sets, set operations (union, intersection, powerset,
Cartesian product, ...) and functions between sets (injections, surjections,
inverse functions, ...). This is mainly high school material, formulated more
rigeously.
·
Algorithms and complexity Three course days covers sections 3.1  3.3 as
well as Appendix A3, which concern algorithms, pseudocode, and the
computational complexity of algorithms.
·
Induction and recursion Two course days cover sections 4.1  4.4 in the
book, which concern mathematical induction, structural induction, recursive
definitions, and recursive algorithms. The principle of mathematical induction
can be used to prove a tremendous variety of mathematical results.
Understanding how to read and construct proofs by mathematical induction is a
key goal of this part of the course.
·
Modeling computation Two course days covers sections 12.1 and 12.5
in the book. Section 12.1 concerns formal languages and different types of
grammars, providing models for both natural languages, such as English, and for
programming languages, such as Java. Section 12.5 concerns Turing machines,
which are general mathematical models of computers, invented by the British
mathematician Alan Turing.
During the
course three mini projects are carried out, based on a handed out problem
formulation. One of the miniprojects may optionally involve use of the
programming language Prolog (Programming in logic), which will be briefly
introduced at the course.
All
references below are to the textbook, which can be bought at Amazon:
Kenneth H.
Rosen, Discrete Mathematics and Its Applications, International Version, 6th
edition, McGraw Hill.
ISBN13:
9780071244749, ISBN10: 0071244743
Course structure (TENTATIVE)
# 
Day 
Curriculum 
Pages 
Assignments 
Handin 
1 
Tuesday 13/3 
1.1 and slides propositional logic 
116 
1.1.1, 1.1.3, 1.1.5, 1.1.7, 1.1.13, 1.1.25, 1.1.27, 1.1.44, 1.1.49 

2 
Thursday 15/3 
1.2 
2127 
1.1.51, 1.2.5, 1.2.7, 1.2.9, 1.2.11, 1.2.15, 1.2.61 

3 
Tuesday 20/3 
1.3 and slides predicate logic 
3046 
1.3.1, 1.3.5, 1.3.7, 1.3.17, 1.3.25, 1.3.51, 1.3.59 
1.1.50, 1.2.6, 1.2.14, 1.2.42 
4 
Thursday 22/3 
1.4 
5058 not ex. 8, 16 
1.3.55, 1.4.1, 1.4.9, 1.4.19ac, 1.4.27ac, 1.4.29ac, 1.4.33abc 
Miniprojekt 1 start 
5 
Tuesday 27/3 
1.5, 1.6, 1.7 
6372, 7585, 8694 
1.5.1, 1.5.3cd, 1.5.5, 1.5.13ab, 1.6.1, 1.6.15, 1.6.39 
1.2.60a,
1.3.12abcd, 1.3.18abc, 1.3.50, 1.3.52, 1.3.56abc, 1.4.52 

No teaching 29/3
(Easter) 




6 
Tuesday 3/4 
2.1, 2.2 
111128 
2.1.7, 2.1.15, 2.1.17, 2.1.21, 2.1.29, 2.1.33a, 2.2.3, 2.2.13, 2.2.45 

7 
Thursday 5/4 
2.3 
133142 
2.3.4a,
2.3.19ab, 2.3.25, 2.3.28, 2.3.29, 2.3.35, 2.3.38a, 2.3.76 
1.5.24,
1.6.16, 2.1.34a, 2.1.38, 2.2.20, 2.2.46 
8 
Tuesday
10/4 
3.1, A3 
167172 A10A15 
A3.1,
A3.3, 3.1.1, 3.1.3, 3.1.9, 3.1.13 
Miniprojekt
1 to be handed in 1315 
9 
Thursday 12/4 
3.2 (A2 if needed) 
180190 
3.2.1abcd, 3.2.3, 3.2.17, 3.2.19ab 
2.3.18ab,
A3.2, 3.1.6, 3.1.24, 1.3.56de Miniprojekt
2 and 3 start 
10 
Tuesday
17/4 
3.3 and
Prolog intro 
193199 not ex.
5, 6 
3.3.13,
3.3.23, 3.3.27 

11 
Thursday
19/4 
4.1, 4.2 
263270 278279 283288 
4.1.3, 4.1.9 (use ex. 1), 4.1.33, 4.1.47, 4.2.42 
3.2.2ab, 3.2.6, 3.2.18, 3.3.4, 3.3.12ab 
12 
Tuesday 24/4 
4.3, 4.4 and Prolog intro 
294308 311317 
4.3.1ab, 4.3.3ab, 4.3.7ac, 4.3.25a, 4.3.26ac, 4.4.7, 4.4.18, 4.4.21 
Miniprojekt
2 to be handed in. Extended to 26/4 
13 
Thursday
26/4 
12.1 and
Prolog intro 
785793 
12.1.7,
12.1.8, 12.1.13, 12.1.20, 12.1.21ab 
4.1.56,
4.3.24a, 4.4.2, 4.4.10 (compare to algorithm page 169). Extended to 30/4 
14 
Tuesday 1/5 
12.5 
827837 not ex. 2 
12.5.1, 12.5.3, 12.5.7, 12.5.11, 12.5.15 

15 
Thursday 3/5 
Miniprojekt
3 to be handed in 

Intensive period 

Tuesday 5/6 or Wednesday 6/6 
Questioning
hour. More info sent via Moodle 


Monday 11/6 and Tuesday 12/6 
Exam.
More instructions sent via Moodle 
Please remember to bring your miniprojects! 