Home Assignments (Fall 2011/2012)
Number Last updated Due Problem set
1 Nov 2 Nov 9 PDF (see code for Q4 below)
2 Nov 14 Nov 22 PDF
3 Nov 30 Dec 8 PDF (see constants for Q1 below)
4 Dec 19 Jan 1 PDF (see code for Q2, Q4 below)
5 Jan 4 Jan 16 PDF ZIP (faxes)ZIP (proteomes) (see code for Q3 below)
6 Jan 17 Jan 31
Feb 2
PDF ZIP (shreds)ZIP (nin)



Code Excerpts

Assignment #1

Assignment #3

# Constants for Q1
a = 282505608130256018180884312838134978798922148782577
b = 78726769113808772903613726574521358167226725481

Assignment #4

Assignment #5

Assignment #6


Assignment 1, question 2

The operator ** denotes exponentiation in Python; that is, to compute $c = a^b$ write

c = a**b

Assignment 2, question 2

As some on you noticed, a $b$-bit number $n$ actually satisfies $2^{b-1} \le n < 2^b$ instead of $2^b \le n < 2^{b+1}$.
Nevertheless, it makes little difference in the context of our question, as $P(100) \approx P(101)$.

Assignment 4, question 4

Make the hash tables for all three hash methods be of size $5N$ slots. For the cuckoo hashing, use half of this ($2.5N$ slots) for $h1$, and the second half (another $2.5N$ slots) for $h2$ (these two memory allocations should be disjoint).

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License