# Discrete mathematics

## 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

## Previous exam problems

From 2015 (included), the majority of the problems in the exam will be multiple choice problems. Below, you will find an example of such exam problems.

• 2014

## Q&A-sessions

We offer assistance with the exam preparation in both calculus and linear algebra at all three campi. The concept consists of two parts. First, a teacher will solve a number of exercises on the blackboard. Afterwards, there will a Q&A-session, where it is possible to ask questions within the syllabus and receive help in solving concrete exercises. During this session, it is also possible solve exercises on your own, and then ask for hints if you get stuck. The session takes as its starting point the old exam questions, which may be found here at first.math.aau.dk. We recommend that you solve as many as you can beforehand, such that you know where you come short. Note that the teaching assistants will not visit you in your group rooms. Instead, everyone will be solving exercises individually or in small groups in the rooms specified below.

We urge you to participate from the beginning in order not to disturb during the first part of the session.

Dates for the Q&A-sessions will be decided towards the end of the semester.