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

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

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

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

Appendix 2: Exponential and logarithmic functions

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

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

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

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

- 3.2
- 3.3

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

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

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

- 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-646
^{line 23}) - 10.4: Connectivity (Page 652-656)

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

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

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

- 11.2: Applications of trees
- 11.4: Spanning trees

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

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

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

- 4.6: Cryptography
- 8.3.Example 4: Karatsuba

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

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, 21^{a-d}, 22^{a,c,e}, 23^{a,c,e}, (25) - An important proof method: 34
- Conditional statements in computer programs: 28

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)

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)

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)
- Russell's Paradox: 29

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

5^{a,c,g}

Appendix 2:

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

Rosen 2.4

- Sequences

7, 9^{a,b} - Sums

17, 19^{a,c}, - Products: 29, (30)

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

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, (28^{a,b})

Rosen 4.1

- Divisibility. Quotient and remainder

1, 9^{a,b,c}, 17 - Addition and subtraction modulo 24: 11
- Prove properties of divisibility: 6, (5, 13)
- Congruence modulo 17: 22

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

24^{a,c,e}, 25, 29^{a,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.

Self-study session 1

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)

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

Self-study session 2

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

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

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)

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)

Self-study session 3

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)

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 homogenous recurrence relation: 1
- Solve some linear homogenous recurrence relation: 2a, 2b, 2c, (2f)
- Recurrence relation from tiling checkerboards: 5
- Lukas numbers: (9)

From Rosen 8.3:

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

Self-study session 4

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

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.

- 2018 spring
- 2017 spring
- 2016 spring
- Trial exam problems 2015
- 2015

- 2014

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.

There is a Q&A session **Tuesday the 8 ^{th} of May** at

Before the re-exam there will be a Q&A-session on **Monday the 13 ^{th} of August** at