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).
Lecture 9
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)
- Russell's Paradox: 29
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:
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:
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:
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:
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.
- 2019 spring
- 2018 spring
- 2017 spring
- 2016 spring
- Trial exam problems 2015
- 2015
Exam problems with few or none multiple choice (from 2015, more multiple choice problems will be included in the exam, see above)
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.
Dansk
English