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 pigeonhole 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 homogenous recurrence relation: 1
- Solve some linear homogenous recurrence relation: 2a, 2b, 2c, (2f)
- Recurrence relation from tiling checkerboards: 5
- Lukas numbers: (9)
Lecture 20
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
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
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.
- 2018 forår
- 2017 forår
- 2016 forår
- Prøveopgaver 2015
- 2015
Eksamensopgaver med få eller ingen multiple choice (fra og med 2015 indgår der mange multiple choice opgaver, se ovenfor)
- Prøveopgaver
- 2011
- 2012
- 2013
- 2014
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.
København
Der afholdes spørgetime tirsdag d. 8. maj kl. 13:00-16:00. Dette finder sted i 3.160, FKJ10A.
Forud for reeksamen afholdes spørgetime mandag d. 13. august kl. 13:00–15:00 i lokale 2.0.028; ACM15, bygning A.