Notes:
- Before solving the homework problems, you are expected to do the weekly reading assignments and understand the related material. An asterisk (*) indicates supplementary reading material.
- Homework assignments are announced on Blackboard or Gradescope, and must be submitted as PDF on Gradescope. Assignments submitted by emails and other means are NOT graded.
- The homework file must have a header on the first page, showing your name and SID. Each question should have header, showing the question number, source, chapter/section, and the exercise number, for example: Q1. Alsuwaiyel 1.16 Exer 8.
- Late submission is subjected to late penalty if it is submitted during the grace period (usually 7 hours after the announced deadline).
- Resubmission: If you submit a wrong file, or modify the solution after submission, you can resubmit within the deadline. Only the latest submission will be saved on Gradescope and late penalty may apply if resubmitted after the deadline.
Reading Assignment [Weeks 1-2]: Basic concepts, Searching and Sorting, Complexity notations
Alsuwaiyel: Sections 1.3 - 1.12 (skip 1.5)
Reading Assignment [Weeks 3-5]: Input size analysis, Recurrences, Mater Theorem, Divide and Conqure, Quicksort
Alsuwaiyel: Sections 1.14, 1.15*, 4.5, 5.1-5.4, 5.6
CLRS: Sections 3.1*, 4.3, 4.5
Reading Assignment [Weeks 6-7]: Graphs and Trees, NP-Completeness, Reductions
Rosen (10.1-3*, 10.7-8): Graphs, Isomorphism, Hamiltonian cycle, Planner graphs, Coloring.
Rosen (11.1*, 11.4-5)*: Trees, Rooted trees, Minimum Spanning Tree.
Alsuwaiyel (Chapter 9): Decision vs optimization, Reduction, Complexity classes: P, NP, co-NP, NP-Complete.
CLRS (Chapter 34*): NP-Completeness, Reduction of NP-C problems.
Reading Assignment [Week 8]: Preparation for Midterm Exam
Reading Assignment [Weeks 9-10]: Dynamic Programing, Gready Algoritms, Knapsack, MST, Approximation Algorithms
Alsuwaiyel (Sections 6.1*,6.6, 7.1*, 7.3, 7.4): Knapsak, Gready algorithms, MST, Kruskal's and Prim's algorithms.
Alsuwaiyel (Chapter 14): Approximation algorithms, Difference bounds, Approximation ratio, Bin packing, ETSP, VC, Knapsack, PAS, FPAS.
CLRS (Chapter 35*): Approximation Algorithms.
Reading Assignment [Weeks 11-12]: Randomized algorithms
Alsuwaiyel (Sections 13.1-4, 13.9, 13.11,13) Randomized algorithms, LV and MC, Randomized Quicksort, Random sampling, String Equality, Primality test, FTL, Pseudoprimes.
Rosen (Section 4-3-4.4*): GCD, FLT, Pseudoprimes.