# 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, 11Find formula and prove by induction. 9Other 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.

## Vidcasts

Klik nedenfor for at downloade vidcasts (video-podcasts) med korte forelæsninger om selvindeholdte emner:

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

• Prøveopgaver 2015
• 2015