Final Exam Time: Dec 10, 2020 (Thursday) 8:00am-10:00am
Topics covered
● Proof techniques (~30 points)
1. direct proof
2. proof by contrapositive
3. proof by contradiction
4. Inductive proof
● Algorithms (~30 points)
1. Algorithms using pseudo-codes
2. Non-recursive algorithms and recursive algorithms
3. Binary search, merge sort
4. Analysis of algorithms
▪ Big-O notation
▪ Basic complexity classes: O(1), O(log n), O(n), O(nlog n), O(n
2
), O(n
3
), …, O(2
n
),
O(3
n
), …, O(n!)
▪ Analysis of non-recursive algorithms
▪ Analysis of recursive algorithm
▪ recursively defined functions
▪ State the recurrence relation and solve it using Master Theorem
● Division Algorithm and Modular Arithmetic (~10 points)
● Graphs (~30 points)
1. Graph representation (set representation, adjacency matrix and adjacency list)
2. Basic terminology: vertex, edge, neighbor, degree, simple graph, multi-graph
3. Common graphs: Kn
, Qn
, Cn
, Kn, m
4. Graph isomorphism
5. Walk, trail, circuit, cycle, path
6. Connected component, vertex connectivity, edge connectivity
7. Euler Circuit and Trail, Hamiltonian Cycle and Path
0 comments