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:
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:
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:
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:
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
|