See the course description at study.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 day-to-day 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 A-3, 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 mini-projects 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, Mc-Graw Hill.
ISBN-13:
978-0071244749, ISBN-10: 0071244743
Course structure (NOTE: THE
PLAN IS TENTATIVE!)
|
# |
Day |
Curriculum |
Pages |
Assignments |
Hand-in |
|
1 |
Tuesday 8/3 |
1.1 and slides propositional logic |
1-16 |
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 10/3 |
1.2 |
21-27 |
1.1.51, 1.2.5, 1.2.7, 1.2.9, 1.2.11, 1.2.15, 1.2.42, 1.2.61 |
|
|
3 |
Tuesday 15/3 |
Priest’s
chapter. Intro to
Mini-project 1 |
Assignments
sent by email |
1.1.50, 1.2.6, 1.2.14 |
|
|
4 |
Thursday 17/3 |
1.3 and slides predicate logic |
30-46 |
1.3.1, 1.3.5, 1.3.7, 1.3.17, 1.3.25, 1.3.51, 1.3.59 |
Assignments
sent by email. |
|
5 |
Tuesday 22/3 |
1.4 |
50-58 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 |
1.3.12abcd, 1.3.18abc, 1.3.50, 1.3.56 |
|
6 |
Thursday 24/3 |
1.5, 1.6, 1.7 |
63-72, 75-85, 86-94 |
1.5.1, 1.5.3cd, 1.5.5, 1.5.13ab, 1.6.1, 1.6.15, 1.6.39 |
|
|
7 |
Tuesday 29/3 (compressed) |
2.1, 2.2, 2.3 and brief Prolog intro |
111-128, 133-142 |
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, 2.3.4a, 2.3.19ab, 2.3.25, 2.3.28, 2.3.29, 2.3.35, 2.3.38a, 2.3.76 |
|
|
8 |
Thursday
31/3 |
3.1, A-3 Intro to
Mini-project 2 |
167-172 A10-A15 |
A-3.1,
A-3.3, 3.1.1, 3.1.3, 3.1.9, 3.1.13 |
1.5.24,
1.6.16, 2.1.4, 2.1.34a, 2.2.16a |
|
9 |
Tuesday
5/4 |
Work on
mini-projects on your own |
|||
|
10 |
Thursday
7/4 ONLINE
SEE EMAIL |
3.2 (A-2
if needed) |
180-190 |
3.2.1abcd,
3.2.3, 3.2.17, 3.2.19ab |
|
|
11 |
Tuesday 12/4 |
3.3 |
193-199 not ex. 5, 6 |
3.3.13, 3.3.23, 3.3.27 |
2.3.18ab
(cf. page 138), A-3.2, 3.1.6, 3.1.24 (cf. page 136) |
|
|
Wednesday
13/4 |
|
|
|
Hand in
mini-project 1 |
|
|
No
teaching 14/4 (Easter) |
|
|
|
|
|
12 |
Tuesday 19/4 |
4.1, 4.2 and
Prolog intro. Intro to Mini-project 3 |
263-270 278-279 283-288 |
4.1.3,
4.1.9 (use ex. 1), 4.1.47, 4.2.42 |
3.2.2abd, 3.2.18, 3.2.20b, 3.3.4, 3.3.12ab. |
|
13 |
Thursday
21/4 |
4.3, 4.4
and Prolog intro |
294-308 311-317 |
4.3.1ab, 4.3.7ac, 4.3.25a, 4.3.26ac, 4.4.7, 4.4.18, 4.4.21 |
Hand in mini-projekt 2 |
|
14 |
Tuesday 26/4 |
12.1 |
785-793 |
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) |
|
15 |
Thursday 28/4 |
12.5 |
827-837 not ex. 2 |
12.5.1, 12.5.3, 12.5.7, 12.5.11, 12.5.15 |
|
|
|
Sunday 1/5 |
|
|
|
Hand in
mini-projekt 3 |