# Diskret matematik

## Plan

### Lecture 1

• 1.1: Propositional logic
• 1.2: Applications of propositional logic
• 1.3: Propositional equivalences

### Lecture 2

• 1.4: Predicates and quantifiers
• 1.5: Nested quantifiers
• 1.6: Rules of inference

### Lecture 3

• 1.8: Introduction to proof
• 1.9: Proof method and strategy
• 2.1: Sets

### Lecture 4

• 2.2: Set operations
• 2.3: Functions
• 2.4: Sequences and summation

Appendix 2: Exponential and logarithmic functions

### Lecture 5

• (Appendix 3: Pseudocode)
• 3.1: Algorithms
• 3.2: The Growth of functions

### Lecture 6

• 3.3: Complexity of algorithms
• 4.1: Divisibility and modular arithmetic

### Lecture 7

• 4.2: Integer representation and algorithms
• 4.3: Primes and greatest common divisors

### Lecture 8

• 5.1: Mathematical induction
• 5.2: Proofs using the well-ordering property (Page 335-336).

• 3.2
• 3.3

### Lecture 10

• 5.2: Strong induction (Page 328-333)
• 5.3: Recursive definitions (Page 339-346)

### Lecture 11

• 5.3: Structural induction (Page 347-351)
• 5.4: Recursive algorithms

### Lecture 12 (Self-study)

• (4.3: Extended Euclidean algorithm)
• 4.4: Chinese remainder theorem
• (4.5: Applications of Congruences).

### Lecture 13

• 5.5: Loop invariants (Page 367-369)
• 10.1: Graphs and graph models
• 10.2: Graph terminology and special types of graphs (Page 627-631 and page 639-640)
• 10.3: Representing graphs (Page 643-646line 23)
• 10.4: Connectivity (Page 652-656)

### Lecture 14

• 10.5: Euler and Hamilton paths
• 10.6: Shortest path problems

### Lecture 15

• 11.1: Introduction to trees
• 11.4: Page 753-755
• 11.5: Minimum spanning trees

### Lecture 16

• 2.5: Cardinality of sets
• 6.1: The basics of counting
• 6.2: The pigeon-hole principle
• 6.3: Permutations and combinations

### Lecture 17 (Self-study)

• 11.2: Applications of trees
• 11.4: Spanning trees

### Lecture 18

• 6.4: Binomial coefficients and identities
• 8.1: Applications of recurrence relations
• 8.2: (Page 497 - 501line 8) Solving linear recurrence relations

### Lecture 19

• 8.3: Divide-and-conquer algorithms and recurrence relations (Example 4 is part of miniproject 4)
• 9.1: Relations and their properties

### Lecture 20

• 2.6: Zero-one matrices (Page 184-186)
• 9.3: Representing relations
• 9.4: Closure of relations
• (9.5)

### Lecture 21 (Self-study)

• 4.6: Cryptography
• 8.3.Example 4: Karatsuba

### Lecture 22

• 9.5: Equivalence relations
• 9.6 (Page 597-598)

## Exercises

### Lecture 1

From Rosen 1.1:

• Propositions and their truth value: 1, 6, 7, (14)
• Determine the truth value of conditional statements: 11, 12
• Construct truth tables
19, 21a-d, 22a,c,e, 23a,c,e, (25)
• An important proof method: 34
• Conditional statements in computer programs: 28

### Lecture 2

From Rosen 1.3:

• Use truth tables to verify logical equivalences and tautologies: 3, 5, 9
• Verify tautologies without using truth tables: 7

Rosen 1.2:

• Translate English sentence: 3
• Logic puzzle: 9
• Logic circuit: 23

Rosen 1.3:

• Compound propositions in special form: 19, 20, 21, (22, 23)
• Satisfiability: 37, (39)

### Lecture 3

From Rosen 1.4

• Translate between mathematical statements and English sentences: 1, 4, 5, (7)
• Determine truth value of mathematical statements: 9, (19)
• Prove logical equivalence: (27)
• Prove not equivalent: (30)

Rosen 1.5

• Translate statements into English: 1, 3
• Express mathematical statements using predicates, quantifiers, logical connectives: 11
• Rewrite statements with negations and quantifiers: 17
• Determine truth value of statements about all integers: (13)
• Find counterexamples: (21)

Rosen 1.6

• What rule of inference is used: 1, 2, 5
• Find the error(s) in an argument: 17, (16)

### Lecture 4

From Rosen 1.8

• Use direct proof: 1,  (4)
• Odd and even integers: 9, 15, (10)
• Some days on the same day of a week: (14)
• Prove equivalence of statements: 21

Rosen 1.9

• Proof by cases: 3
• Triangle inequality: (4)
• Prove no integer solution to equation: 17
• Tile a checkerboard: 21

Rosen 2.1

• Some small sets: 1, 4, 13
• Power sets: 15, 17, (16)
• Cartesian products: 22, (21)

### Lecture 5

From Rosen 2.2

• Prove set identities: 5, (9)
• Venn diagrams: 14
• Union and intersection: 27
• Inclusion-exclusion: (26)

Rosen 2.3

• Is $f$ a function: 3
• One-to-one and onto functions: 14
• Find values
5a,c,g

Appendix 2:

• Exponential and logarithmic function: 1, 2, 3, (4, 5, 6)

Rosen 2.4

• Sequences
7, 9a,b
• Sums
17, 19a,c,
• Products: 29, (30)

### Lecture 6

From Rosen 3.2

• Determine whether $f(x)$ is $\mathcal{O}(g(x))$: 1, (11, 17)
• Prove that $f(x)$ is $\mathcal{O}(g(x))$: 3, 5, 9, (18)
• Give good big-O estimates: 7, (15)
• Big $\Theta$;  (Theta): 25
• $f(x,y)$ is $\mathcal{O}(g(x,y))$: (39)

Rosen 3.1

• Describe an algorithm that solves a problem: 3, 5, (6, 15)
• List the steps of an algorithm: 11
• Bubble sort: 29
• Greedy change-making: 46

### Lecture 7

From Rosen 3.3

• Exactly how many multiplications and additions are used: 9, (10)
• The largest size of a problem that can be solved in 1 second: 11
• Complexity of greedy change-making algorithm (Algorithm 6 in section 3.1): 26
• Complexity of search (sort)
27, (28a,b)

Rosen 4.1

• Divisibility. Quotient and remainder
1, 9a,b,c, 17
• Addition and subtraction modulo 24: 11
• Prove properties of divisibility: 6, (5, 13)
• Congruence modulo 17: 22

### Lecture 8

From Rosen 4.2

• Convert between decimal, binary and hexadecimal expansion: 1, 2, 6
• Modular exponentiation: 15

Rosen 4.3

• Is this integer a prime?: 1
• Prime factorization : 3, 4
• Euler $\varphi$-function: 17
• Greatest common divisor without Euclidean algorithm: 20
• Greatest common divisor with Euclidean algorithm
24a,c,e, 25, 29a,b,d,g
• Proofs: 9, (15)

Rosen 4.2

• Two's complement (Read text after exercise 25):
26, 27
Suppose you let $x=2^{30}$ on a computer using a 32 bit two's complement representation of integers. What is the result if you compute $3x$ on this computer. Try it on your own computer.

### Lecture 9

Self-study session 1

### Lecture 10

From Rosen 5.1:

• Prove formulas using induction.: 3, 5, 7, 11
• Find formula and prove by induction.: 9
• Other induction proofs and "proofs": 39, 56, 65

From Rosen 5.2:

• Prove well-ordering of $\mathbb{N}$: (31)
• Greatest common divisor: (28)

### Lecture 11

From Rosen 5.2:

• Proof by strong induction: 3, 7, (10)

Rosen 5.3:

• Recursive definitions of sequences: 3, 4
• Proof by induction: 12
• A recursively defined set: 21, 29, (19)
• Reversal of strings: 24, 25

Rosen 5.2:

• Understanding proof by induction: 19, 21

### Lecture 12

Self-study session 2

### Lecture 13

From Rosen 5.3:

• Recursive definition and structural induction: 18, 33, (27, 31)

Rosen 5.4:

• Trace algorithm: 1, 3
• Merge sort: 29, (28)
• Give a recursive algorithm: 5, 17, (27)

Rosen Supplementary exercises, page 372:

• Use mathematical induction: 24

### Lecture 14

From Rosen 5.5:

• Loop invariant: 7

Rosen 10.1:

• Type of graph: 3, 4, 5
• Intersection graph: 9

Rosen 10.2:

• Degree of vertex: 1, 3, 29, (14, 27)

Rosen 10.3:

• Representation of graph: 1, 3

Rosen 10.4:

• Paths and connectivity: 1, 2, 3, 50, (45)

Rosen Supplementary exercises in Chapter 5, page 371:

• Use mathematical induction: 3

### Lecture 15

From Rosen 10.6:

• Shortest path problems: 1
• Use Dijkstra's algorithm: 2, 3, 5

Rosen 10.5:

• Does the given graph have an Euler circuit/path: 1, 2, 3, 7
• Does the given graph have a Hamilton circuit/path: 20, 21, 22, 23, 24, 25, 28

Rosen 10.6:

• Dijkstra's algorithm: 12, 13, 18
• Floyd's algorithm: (17)

### Lecture 16

From Rosen 11.1:

• Trees: 1, 2
• m-ary trees: 3, 13, 16, 17
• Fibonacci trees: (33, 34)

Rosen 11.4:

• Spanning trees: 1, 3

Rosen 11.5:

• Use Prim's algorithm / Kruskal's algorithm: 1, 2, 4
• Maximum spanning tree: 7
• Proofs: 13, (24)

### Lecture 17

Self-study session 3

### Lecture 18

From Rosen 6.1:

• Counting: 1, 5

Rosen 6.2:

• Pigeon principle: 1, 3
• An example relating to Theorem 3: (17)

Rosen 6.3:

• Permutations: 1, 5
• Combinations: 7
• Permutations and combinations: 17, (21)

Rosen 2.5:

• Finite, countably infinite or uncountable: 1, 3
• Application to computation: (29, 30)

### Lecture 19

From Rosen 6.4:

• Binomial Theorem: 1, 2, 3
• Pascal's triangle: 8, 11
• A combinatorial proof: (21)
• An application of binomial coefficients: (23)

Rosen 8.1:

• Towers of Hanoi: 1, (24)
• Other applications of recurrence relations: 3, 9

Rosen 8.2:

• Is it a linear homogeneous recurrence relation: 1
• Solve some linear homogeneous recurrence relation: 2a, 2b, 2c, (2f)
• Recurrence relation from tiling checkerboards: 5
• Lucas numbers: (9)

### Lecture 20

From Rosen 8.3:

• Recurrence relations: 5, 8, 9
• Divide-and-conquer: 13, 20, (22)

Rosen 9.1:

• Properties of relations: 2, 3, 38
• Combining relations: 22, 23, 24, 25
• Counting relations: 31

### Lecture 21

Self-study session 4

### Lecture 22

From Rosen 2.6:

• Zero-one matrices: 27

Rosen 9.3:

• Matrix representation of relation: 1, 10, (8)
• Graph representation of relation: 15, 16, 21

Rosen 9.4:

• Reflexive and symmetric closure: 5, 9
• Transitive closure: 27,  (23)

Rosen 9.5:

• Is this an equivalence relation : 3, 11, 17-19, (13)

Rosen 9.6:

• Is this a partial ordering: 1, 6-7, (5)

Exam "17. juni 2013":

• Exercises: 1, 3, 4, 6, 13, 14

## Selvstudier

### Selvstudium 1: Store-O notation og kompleksitet af algoritmer

Bemærk at I kan finde nyttige screencasts om Maple i Maple-centret under screencasts. Tryk her for at gå dertil.

### Selvstudium 2: Talteori med anvendelser

Bemærk at I kan finde nyttige screencasts om Maple i Maple-centret under screencasts. Tryk her for at gå dertil.

## Vidcasts

Klik nedenfor for at downloade vidcasts (video-podcasts) med korte forelæsninger om selvindeholdte emner:

#### Kursusgang 01

Video om store O
Algoritmer: lineær søgning og indsætningssortering

#### Kursusgang 02

Logaritmefunktioner
Kompleksitet af algoritmer
Udsagnslogik

#### Kursusgang 03

Modulær aritmetik

#### Kursusgang 06

Udvidet Euklids algoritme, Invers, afsnit 4.3, 4.4.
To kvantorer, afsnit 1.5
Slutningsregler, afsnit 1.6

#### Kursusgang 07

Direkte og indirekte bevis, afsnit 1.8
Bevis ved modstrid afsnit 1.8
Halting: bevis ved modstrid, afsnit 1.8+3.1
Følger og summer afsnit 2.4

#### Kursusgang 09

Mængdeoperationer, afsnit 2.2
Funktioner, afsnit 2.3
Induktionsbevis, afsnit 5.1

#### Kursusgang 10

Fibonacci-tal: beviser ved (stærk) induktion, afsnit 5.1, 5.2

#### Kursusgang 11

Rekursiv defineret talfølge og induktionsbevis, afsnit 5.3
Rekursiv defineret mængde og strukturel induktion, afsnit 5.3

#### Kursusgang 12

Rekursiv algoritme, afsnit 5.4
Merge sort, afsnit 5.4
Invarianter, afsnit 5.5

#### Kursusgang 13

Rekursiv definition af fuldt binært træ, afsnit 5.3

#### Kursusgang 14

Euler-kreds, afsnit 5.5
Korteste veje, afsnit 5.6

#### Kursusgang 15

Prims og Kruskals algoritmer og deres kompleksitet , afsnit 11.5

#### Kursusgang 17

Kardinalitet af (uendelige) mængder , afsnit 2.5
Kardinalitet af endelige mængder: sum- og produkt-regel , afsnit 6.1

#### Kursusgang 18

Kombinatorik: binomialkoefficienter, afsnit 6.4
Rekursionsligninger, afsnit 8.2

#### Kursusgang 19

Binære relationer, afsnit 9.1

#### Kursusgang 21

Relationer og grafer, afsnit 9.3+9.4
Relationer og matricer, afsnit 9.3+9.4

#### Kursusgang 22

Ækvivalensrelationer, afsnit 9.5
Ordningsrelationer, afsnit 9.6

## Pencasts

Nedenstående pencasts er i PDF-format med indlejret Flash. For at kunne se dem interaktivt med lyd, kræves nyeste version af Adobe Reader. Filen skal downloades og herefter åbnes i Adobe Reader for at den interaktive del virker (det virker altså ikke, hvis den åbnes direkte i browseren).

## Gamle eksamensopgaver

Fra og med 2015 vil hovedparten af opgaverne i et eksamenssæt være af formen multiple choice. Du kan se et eksempel på, hvorledes et sådant eksamensæt kan se ud i prøvesættet nedenfor.

• 2019 forår
• 2018 forår
• 2017 forår
• 2016 forår
• Prøveopgaver 2015
• 2015

## Spørgetimer

Der tilbydes hjælp til at forberede sig til den kommende eksamen i både calculus og lineær algebra på alle tre campusser. Konceptet består af to dele. Først vil en underviser gennemregne nogle udvalgte opgaver på tavlen. Herefter vil der være spørgetid, hvor man kan stille spørgsmål indenfor kurset og få hjælp til konkrete opgaver. I spørgetiden kan man også løse opgaver på egen hånd og spørge, når man går i stå. Der tages udgangspunkt i de gamle eksamensopgaver, som er tilgængelige her på first.math.aau.dk, og det anbefales at man regner så mange som muligt på forhånd, så man ved, hvor man har problemer. Det bemærkes at hjælpelærerne ikke kommer rundt i jeres grupperum, men derimod sidder alle samlet og regner opgaver enkeltvis eller i små grupper i lokalerne angivet nedenfor.

Der opfordres til, at man deltager fra begyndelsen, så man ikke kommer og forstyrrer midt i gennemregningen af de udvalgte opgaver.

Datoer for spørgetimerne fastlægges mod slutningen af semestret.