Home Work Number 2 Fall 2014
This is Home Work Number 2 - Due on september 18
Please submit your answers in paper (typewritten will be preferred) with your name and section number. Questions on Chapter 1, Chapter 2 of Das Gupta (DG) et al's book and Cormen et al's book(CLRS) Chapter 4
Please submit only six (any six) problems.
- Question 1.16 (Das Gupta et al)
- Question 1.17 (Das Gupta et al)
- Question 1.20 (Das Gupta et al)
- Question 1.26 (Das Gupta et al)
- Question 1.27 (DG)
- Question 2.4 (DG)
- Question 2.5 a and b (DG)
- Question 2.12 (DG)
- 4.1 (CLRS) problem h T(n) = T(sqrt(n))+1 and 4.4 (CLRS) Problem d T(n) = T(n-1)+1/n
- One of the applications of Computing with numbers is in Hashing computation..
Please read Karp-Rabin String Search Algorithm which uses Hashing in a clever fasion.. Please write a pseudo code how rolling hashes are computed. In particular if a hash computation is
done for a substring s[i]...s[i+m-1] (m being the length of the pattern we
are trying to match) , how to compute the hash value for the substring
s[i+1]...s[i+m]. The lab home work for next week will be to implement
Karp - Rabin string search algorithm. You can use any hash function.
- (For fun problem - Please do not submit)Exercise 4.1.5 (CLRS) - read Section 4.1 of CLRS (third edition) - Wikipedia Article on Maximum subarray problem -
You need not submit the solution for this problem when you submit your
homework solution. Here is a nice write up by Bentley
Dr. Bentley