Diskret matematik

Plan

Lecture
New subjects

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

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

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

4
2.2: Set operations
2.3: Functions
2.4: Sequences and summation
Appendix 2: Exponential and logarithmic functions

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

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

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

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

9
3.2
3.3
Miniproject
10
5.2: Strong induction (Page 328-333)
5.3: Recursive definitions (Page 339-346)

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

12
(4.3: Extended Euclidean algorithm)
4.4: Chinese remainder theorem
(4.5: Applications of Congruences).
Miniproject
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)

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

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

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

17
11.2: Applications of trees
11.4: Spanning trees
Miniproject
18
6.4: Binomial coefficients and identities
8.1: Applications of recurrence relations
8.2: (Page 497 - 501line 8) Solving linear recurrence relations

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

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

21
4.6: Cryptography
8.3.Example 4: Karatsuba
Miniproject
22
9.5: Equivalence relations
9.6 (Page 597-598)

Exercises

Lecture
Exercises
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
2
From Rosen 1.3:
  • Use truth tables to verify logical equivalences and tautologies
    3, 5, 9
  • Verify tautologies without using truth tables
    7
From Rosen 1.2:
  • Translate English sentence
    3
  • Logic puzzle
    9
  • Logic circuit
    23
From Rosen 1.3:
  • Compound propositions in special form
    19, 20, 21, (22, 23)
  • Satisfiability
    37, (39)
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)
From 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)
From Rosen 1.6
  • What rule of inference is used
    1, 2, 5
  • Find the error(s) in an argument
    17, (16)
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
From Rosen 1.9
  • Proof by cases
    3
  • Triangle inequality
    (4)
  • Prove no integer solution to equation
    17
  • Tile a checkerboard
    21
From Rosen 2.1
  • Some small sets
    1, 4, 13
  • Power sets
    15, 17, (16)
  • Cartesian products
    22, (21)
  • Russell's Paradox
    29
5
From Rosen 2.2
  • Prove set identities
    5, (9)
  • Venn diagrams
    14
  • Union and intersection
    27
  • Inclusion-exclusion
    (26)
From Rosen 2.3
  • Is f a function
    3
  • One-to-one and onto functions
    14
  • Find values
    5a,c,g
From Appendix 2:
  • Exponential and logarithmic function
    1, 2, 3, (4, 5, 6)
From Rosen 2.4
  • Sequences
    7, 9a,b
  • Sums
    17, 19a,c,
  • Products
    29, (30)
6
From Rosen 3.2
  • Determine whether f(x) is O(g(x))
    1, (11, 17)
  • Prove that f(x) is O(g(x))
    3, 5, 9, (18)
  • Give good big-O estimates
    7, (15)
  • Big Θ  (Theta)
    25
  • f(x,y) is O(g(x,y))
    (39)
From 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
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)
From 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
8
From Rosen 4.2
  • Convert between decimal, binary and hexadecimal expansion
    1, 2, 6
  • Modular exponentiation
    15
From Rosen 4.3
  • Is this integer a prime?
    1
  • Prime factorization
    3, 4
  • Euler φ-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)
From Rosen 4.2
  • Two's complement (Read text after exercise 25):
    26, 27
    Suppose you let x=230 on a computer using a 32 bit two's complement representation of integers. What is the result if you compute 3*x on this computer. Try it on your own computer.
9
Miniproject 1
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 ℕ
    (31)
  • Greatest common divisor
    (28)
11
From Rosen 5.2:
  • Proof by strong induction
    3, 7, (10)
From 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
From Rosen 5.2:
  • Understanding proof by induction
    19, 21
12
Miniproject 2
13
From Rosen 5.3:
  • Recursive definition and structural induction
    18, 33, (27, 31)
From Rosen 5.4:
  • Trace algorithm
    1, 3
  • Merge sort
    29, (28)
  • Give a recursive algorithm
    5, 17, (27)
From Rosen Supplementary exercises, page 372:
  • Use mathematical induction
    24
14
From Rosen 5.5:
  • Loop invariant
    7
From Rosen 10.1:
  • Type of graph
    3, 4, 5
  • Intersection graph
    9
From Rosen 10.2:
  • Degree of vertex
    1, 3, 29, (14, 27)
From Rosen 10.3:
  • Representation of graph
    1, 3
From Rosen 10.4:
  • Paths and connectivity
    1, 2, 3, 50, (45)
From Rosen Supplementary exercises in Chapter 5, page 371:
  • Use mathematical induction
    3
15
From Rosen 10.6:
  • Shortest path problems
    1
  • Use Dijkstra's algorithm
    2, 3, 5
From 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
From Rosen 10.6:
  • Dijkstra's algorithm
    12, 13, 18
  • Floyd's algorithm
    (17)
16
From Rosen 11.1:
  • Trees
    1, 2
  • m-ary trees
    3, 13, 16, 17
  • Fibonacci trees
    (33, 34)
From Rosen 11.4:
  • Spanning trees
    1, 3
From Rosen 11.5:
  • Use Prim's algorithm / Kruskal's algorithm
    1, 2, 4
  • Maximum spanning tree
    7
  • Proofs
    13, (24)
17
Miniproject 3
18
From Rosen 6.1:
  • Counting
    1, 5
From Rosen 6.2:
  • Pigeon principle
    1, 3
  • An example relating to Theorem 3
    (17)
From Rosen 6.3:
  • Permutations
    1, 5
  • Combinations
    7
  • Permutations and combinations
    17, (21)
From Rosen 2.5:
  • Finite, countably infinite or uncountable
    1, 3
  • Application to computation
    (29, 30)
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)
From Rosen 8.1:
  • Towers of Hanoi
    1, (24)
  • Other applications of recurrence relations
    3, 9
From 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)
20
From Rosen 8.3:
  • Recurrens relations
    5, 8, 9
  • Divide-and-conquer
    13, 20, (22)
From Rosen 9.1:
  • Properties of relations
    2, 3, 38
  • Combining relations
    22, 23, 24, 25
  • Counting relations
    31
21
Miniproject 4
22
From Rosen 2.6:
  • Zero-one matrices
    27
From Rosen 9.3:
  • Matrix representation of relation
    1, 10, (8)
  • Graph representation of relation
    15, 16, 21
From Rosen 9.4:
  • Reflexive and symmetric closure
    5, 9
  • Transitive closure
    27,  (23)
From Rosen 9.5:
  • Is this an equivalence relation
    3, 11, 17-19, (13)
From Rosen 9.6:
  • Is this a partial ordering
    1, 6-7, (5)
From Exam "17. juni 2013":
  • Exercises
    1, 3, 4, 6, 13, 14

Miniprojekter

Miniprojekt 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.

Miniprojekt 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.

Miniprojekt 3: Træer med anvendelser

Miniprojekt 4: Hurtig multiplikation og RSA kryptering

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.

Eksamensopgaver med få eller ingen multiple choice (fra og med 2015 indgår der mange multiple choice opgaver, se ovenfor)