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.