1. Before solving the homework problems, you are expected to study and understand the related material.
2. Homework assignments must be typed, saved as PDF, and electronically submitted on the Blackboard.
3. It is highly recommeneded to do the homeowk in Latex. Please register with ShareLatex for an online account. Collaboration is only allowed in ShareLatex (must be shared with instructor before start).
4. The homework PDF file must have a header on the first 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.
5. Assignments deadlines are announced on the Blackboard.
6. Late submission is subjected to a 50% penalty if it is submitted by the cut-off time (usually 48 hours after the announced deadline).
7. You may find your CSN here.

Homework problems are taken from the textbook, Alsuwaiyel (2016) by default unless otherwise stated

Homework 1:
Chapter 1, Exer: 1(a,b), 6, 8, 13, 14, 16(c,d), 17(d,e), 18, 20, 27.
Total: 10 exercises.

Homework 2:
Chapter 1, Exer: 29, 33(a,b,d), 36, 45(a,b), 47(b), 56.
Chapter 3, Exer: 5, 7, 13, 14, 24, 26.
Extra Problem:
EP#1. Using the master theorem, find the complexity of each of the following functions:
(a) T(n) = 8T(n/2) + n^3
(b) T(n) = 4T(n/3) + n log n
EP#2. Given an array A[1..n] of positive integers less than some constant k.
(a) Design an optimal algorithm to sort the array if k is a small constant, like k = 100.
(b) What is the time and space complexities of your algorithm in (a)?
(c) Estimate the time and space complexities of your algorithm if k is arbitrarily large using big-O notation in terms of n and k.
Total: 14 exercises.

Homework 3:
Chapter 4, Exer: 4, 10(c), 13, 14(b), 16(a: for x = 2), 17(a), 18(b,c), 20, 21, 22, 23, 32.
Total: 12 exercises.

Homework 4: Chapter 5, Exer: 2, 13, 15(b,c), 18, 19(b, show steps), 28, 35, 36, 37(c, show steps), 44, 45.
Total: 11 exercises.

Homework 5:
Chapter 6, Exer: 2, 6, 8, 10, 11, 12, 15(a), 17(explain), 18, 21(show V-table), 24, 29(a,b), 32.
Total: 13 exercises.

Homework 6:
Chapter 7, Exer: 1, 4, 5, 6, 10, 11, 17, 21, 22, 23, 25, 27.
Total: 12 exercises.

Homework 7:
Chapter 9, Exer: 10, 11, 12, 13, 14, 17, 18, 25.
Chapter 11, Exer: 2, 6, 12.
Extra Problem:
EP#1. Give an example of a boolean formula in CNF on three variables, f(x,y,z), such that each clause consists of at least two literals and f is not satisfiable. Then:
(a) Reduce f to an instance of clique (G,k) and verfiy that G has no clique of size k.
(b) Reduce f to an instance of Vertex Cover (G,k) and verfiy that G has no vertex cover of size k.
Total: 12 exercises.