COURSE ASSIGNMENTS

Notes:

  1. All reading and homework assignments are from the texbook (Alsuwaiyel 2016) and CLRS (3rd ed) unless otherwise stated. An asterisk (*) indicates recommended supplementary material. You are expected to do the reading assignment and understand the related material before solving the homework problems.
  2. Homework assignments must be typed, saved as PDF, and electronically submitted by the deadline announced on the Blackboard.
  3. It is highly recommeneded to type the assignment in Latex. You may register with ShareLatex for an online account.
  4. Collaboration in homework is only allowed on Sharelatex. Every two students can work togather and submit one homework. See the guidelines for details.
  5. The homework PDF file must have a header on the first page (or cover page), and a header for each question. See HW format. You should follow this format when you submit your homework in order to be graded. See also a HW sample which can be used as a template for your homework.
  6. Late submission is subjected to a 50% penalty within the cut-off time (usually 48 hours after the announced deadline). No submission after the cut-off time and the removal of the homework submission link. No submission by email.
  7. Resubmission: If you submit a wrong file, or modify the solution after submission, you can resubmit within the deadline (at most twice). Only the latest submission will be graded and late penalty may apply if resubmitted after the deadline.

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.