Notes:
Reading Assignment [Week 1]: General
review.
Alsuwaiyel (Chapters 1-9)*: General review on sorting and searching
algorithms, Complexity notations and classes, Heaps, Divide and conquer, Dynamic programming, and NP-Complete problems.
Reading Assignment [Weeks 2-3]: NP-completeness, Recurrence relations and the master theorem.
Alsuwaiyel (Chapter 9): Decision vs optimization, Reduction, Complexity classes: P, NP, co-NP, NP-Complete.
Alsuwaiyel (Sections 6.6* and 1.15): Dynamic programming*, Recurrence relations.
CLRS (Section 4.5): Divide and Conquer, the master theorem.
CLRS (Chapter 34*): NP-Completeness, Reduction of NP-C problems.
Homework Assignment HW1.
Part A: (Q1-Q6)
Alsuwaiyel (2016), Chapter 9, Exer: 4, 8, 13, 14, 18, and 28.
Part B: Extra Problems (Q7-Q10)
EP#1. Find the complexity of each of the following function:
(a) T(n) = n^(1/10) + (log n)^10
(b) T(n) = 8T(n/2) + n^3
(c) T(n) = 4T(n/3) + n log n
EP#2. Find the time-complexity of the algorithm using Theta-notation.
Algorithm A
s = 0
for i = 1 to [log n]
| for j = 1 to i^2
| | s = s + i
| endfor
endfor
EP#3. According to our understanding of the complexity classes, decide whether each of the following statement is True, False or Unknown (i.e. it depends on whether P = NP or not). Briefly justify your answer.
(a) The decision problem Is_Sorted is an NP problem because its solution is verifiable in polynomial time.
(b) If P = NP, then every problem in Class co-NP is also in Class P.
(c) UNSATISFIABLILITY is in Class co-NP.
EP#4. Prove that the 0-1 knapsack problem is NP-Complete.
Total: 10 exercises.
Reading Assignment [Weeks 4-5]:Lower Bounds
Alsuwaiyel (Chapter 11): Lower bounds, Decision tree models, Algebraic
decision tree, Linear time redection.
Homework Assignment HW2:
Alsuwaiyel: Chapter 11. Exer: 3, 6, 7, 10, 11, 12, 14, 15.
Total: 8 exercises.
Reading Assignment [Weeks 6-8]: Computational Complexity, Backtracking.
Alsuwaiyel (Sections 10.1-5, 10.6*): Turing machines, Time and space classes, Compression and linear speed-up, Complexity hierarchy.
Alsuwaiyel (Sections 10.7-8*): Reduction, Completeness*
Alsuwaiyel (Chapter 12): Backtracking, Branch and bound.
Homework Assignment HW3:
Alsuwaiyel: Chapter 10. Exer: 1, 3, 10.
Alsuwaiyel: Chapter 12. Exer: 1, 8, 10, 12, 17.
Extra Problems:
EP#1. Add each of the following time functions to its proper class (and name its place within the class) in the time-complxity hierarchy (Table 1). Breifly justify your decision.
(a) T(n) = 2^√(n log(n))
(b) T(n) = √(2^n)
(c) T(n) = n^n
EP#2. Using tape compression arguments,
(a) Prove Theorem 10.1.
(b) Suppose L is accepted by a (3n) space-bounded off-line Turing Machine (M1)that uses 2 tape symbols (i.e. Gama={0,1)). Based on Theorem 10.1, we can build another machine (M2) bounded by (n) space using tape compression. How many tape-symbols do we need for M2?
Total: 10 exercises.
Reading Assignment [Weeks 9-10]: Randomized algorithms.
Alsuwaiyel (Sections 13.1-5, 13.9, 13.11-13): Randomized algorithms, LV and MC, Quicksort, Selection, String equality, Pattern matching,
Primality test, Random sampling, Discrete probability, Birthday problem.
Alsuwaiyel (Sections 4.2, 5.5, 5.6, 13.6, Appendix B)*: Majority element, Selection, The balls and bins model, Birthday paradox, Discrete probability.
Rosen (Sections 7.1-2)*: Discrete probability, The birthday problem.
LNDP (Sections 1-2)*: Discrete probability.
Homework Assignment HW4:
Alsuwaiyel: Chapter 13. Exer: 2, 3, 7, 8, 10, 20, 24.
Extra Problems:
EP#1. Give an example of an integer n such that:
(a) n is pseudoprime to the base-2, but not to the base-5.
(b) n is a Carmichael number divisible by 3 and 11.
(c) n statisfies both (a) and (b) if possible, or explain otherwise.
EP#2. Using Fermat's theorem, guess whether the following integers are probably prime or not (wiht probabilty > 90%). It is enough to try small basis like 2 and 3. Show work for credit:
(a) n = 1387
(b) n = 1729
Total: 9 exercises.
Reading Assignment [Week 11}: Review for the midterm exam.
Reading Assignment [Weeks 12-13]: Approximation Algorithms, Network Flow.
Alsuwaiyel (Chapter 14): Approximation algorithms, Difference bounds, Approximation ratio, Bin packing, ETSP, TSP, VC, Knapsack, Subset-sum, PAS, FPAS.
Alsuwaiyel (Chapter 15): Network flow, Max-flow, Ford-Fulkerson, MCA, MPLA, Dinic and MPM algorithms.
Alsuwaiyel (Sections 7.2, 8.2, 8.4)*: Dijkstra, DFS, BFS
Homework Assignment HW5:
Alsuwaiyel: Chapter 14. Exer: 1, 3, 11.
Alsuwaiyel: Chapter 15. Exer: 3, 6, 8, 9, 15.
Extra Problems:
EP#1. Given an instance I of a subset-sum problem of size n,
(a) Compute the performmance ratio of the approximation algorithm, Ae, where the error e = 1/n.
(b) Estimate the running time in terms of n of the algorithm Ae in (a)
EP#2. Let (G=(V,E), s, t, c) be a network where
V={s,a,b,t}, E={(s,a), (s,b), (a,b), (b,a), (a,t), (b,t)}
and c(s,a) = 10, c(s,b) = 6,
c(a,b) = 7, c(b,a) = 4,
c(a,t) = 6, c(b,t) = 12.
(a) Apply Ford-Fulkerson method to find the maximum flow. Use Edmonds-Karp bottleneck heuristic to select the augmenting paths. Show the augmenting path and the flow
amount, |f|, for each iteration.
(b) Draw the residual graph after the last iteration.
(c) Compare the time complexities of this method with and without using the bottleneck heuristic, and explain in which scenarios one will outperform the other.
Total: 10 exercises.
Reading Assignment [Weeks 14-15]: Matching, Geometric Sweeping, Voronoi Diagrams.
Alsuwaiyel (Sections 16.1-4): Matching, Max matching for bipartite graphs, Network flow and Hungarian tree methods.
Alsuwaiyel (Sections 17.1-3, 17.5): Geometric seeping, Maximal points, Polygon types and signed area, Convex hull problem.
Alsuwaiyel (Sections 18.1-2): Nearest-point Voronoi diagram, Delaunay triangulation.
Alsuwaiyel (Sections 16.5-6, 17.6, 18.3)*.
Homework Assignment HW6:
Alsuwaiyel: Chapter 16. Exer: 8, 9, 18, 19.
Alsuwaiyel: Chapter 17. Exer: 2, 12, 13, 17.
Alsuwaiyel: Chapter 18. Exer: 5, 8.
Total: 10 exercises.