Discrete mathematics

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

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.

Exam problems with few or none multiple choice (from 2015, more multiple choice problems will be included in the exam, see above)