Problems

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Problems will be listed here as they are assigned, along with their due dates and point values.

# Extended problems (last chance!)

NumberTitlePointsDue

# Upcoming problems

NumberTitlePointsDue

# Past-due problems

NumberTitlePointsDue
97Randomized complexity classes3April 29
96Family reunion tester4April 29
95Is problem 94 good?2April 29
94Primality testing through perfect hashing6April 29
93String matching example4April 29
92File fingerprinter6April 29
91Load balancing in a network3April 29
90Multiple substring search5April 26
89Substring search algorithms2April 26
88Prisoners regroup5April 26
87Prisoners hardness3April 26
86Multiple choice test2April 19
85Fool the multiplication verification1April 19
84Progress in randomized algorithms4April 26
83Perfect hashing example3April 19
82Static Bloom filter?3April 19
81Static hashing challenge2-6April 19
80Analysis of prisoners algorithm4April 19
79Hashing with a guarantee4April 12
78Make up a problem1-2April 29
76Max bucket size in a hash table5April 12
75Bloom filter example4April 12
74Hash table to store a set #33April 5
73Hash table to store a set #22April 5
72Hash table to store a set #12April 5
712-choice hashing worst case4April 5
702-choice hashing example2April 5
69Grouping prisoners6April 12
68Another hash table simulation7April 5
67Why the max?2April 5
66Multiple birthays problem4April 5
65History of MST5April 12
64Hash table simulation5April 5
63Problem 621March 29
62Birthday Problem2March 29
61Randomized MST example4March 29
60Worst case of randomized MST3April 5
59Subgraph selection with different probability3March 29
58Boruvka examples5March 22
57Beyond win-loss game trees4March 29
56Game tree evaluation with arbitrary branching factor4March 29
55Game tree evaluation with branching factor 33March 22
54Count to 56March 1
53The opposite of a treap3March 8
52Randomized dictionary comparison5March 8
51Treaps example4March 1
50Simpler Randomized BST, Part 24March 1
49Simpler randomized BST, Part 13March 1
48Search in a randomized BST1March 1
47Deletion from a randomized BST3March 1
46Zombie ambulance8-12February 22
45Complete my Skip List implementation6February 15
44Limiting skip list height1February 15
43Expected animal abuse1February 15
42Expected value vs probability3February 15
41Expected time to find a Delawarean4February 22
406-Week Survey10February 15
39Skip list gallop search4February 22
38Skip list sort2February 8
37Skip list PQ3February 8
36k-level skip list2February 15
352-level skip list3February 8
34Skip list level distribition test3February 8
33Make me a skip list2February 8
32Problem 16 redux2February 15
31Cryptographic vs algorithmic randomness1February 8
30Universal PRNG2 FOR ALLFebruary 22
29Use Mersenne twister to shuffle a deck of cards6February 8
28From a PRNG to a hash function1February 1
27From a hash function to a PRNG1February 1
26Combining two PRNGs3February 1
25Coin flipper comparison3February 8
24Seed one PRNG with another4February 1
23Create some random art8February 15
22Dice roller4February 8
21Maximal-length mixed LCG sequence2February 1
20Program to generate Lehmer LCG sequence2February 1
19Longest-period Lehmer LCG with m=655373January 25
18Longest-period Lehmer LCG with m=111January 25
17Longest-period Lehmer LCG with m=61January 25
16Random using dev random4February 1
15Calculating entropy of network traffic3February 1
14Entropy in CS and Physics2January 25
13Which is the randomest of them all?1January 18
12Making a weighted coin3January 25
11Unweighting a die5-7January 18
10How many biased bits give an unbiased one?3January 18
9Give me code names!1January 18
8Problem 4 with variables3January 25
7Fix Wikipedia1-10April 29