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!)

Number	Title	Points	Due

Upcoming problems

Number	Title	Points	Due

Past-due problems

Number	Title	Points	Due
97	Randomized complexity classes	3	April 29
96	Family reunion tester	4	April 29
95	Is problem 94 good?	2	April 29
94	Primality testing through perfect hashing	6	April 29
93	String matching example	4	April 29
92	File fingerprinter	6	April 29
91	Load balancing in a network	3	April 29
90	Multiple substring search	5	April 26
89	Substring search algorithms	2	April 26
88	Prisoners regroup	5	April 26
87	Prisoners hardness	3	April 26
86	Multiple choice test	2	April 19
85	Fool the multiplication verification	1	April 19
84	Progress in randomized algorithms	4	April 26
83	Perfect hashing example	3	April 19
82	Static Bloom filter?	3	April 19
81	Static hashing challenge	2-6	April 19
80	Analysis of prisoners algorithm	4	April 19
79	Hashing with a guarantee	4	April 12
78	Make up a problem	1-2	April 29
77	Password validator	8	April 19
76	Max bucket size in a hash table	5	April 12
75	Bloom filter example	4	April 12
74	Hash table to store a set #3	3	April 5
73	Hash table to store a set #2	2	April 5
72	Hash table to store a set #1	2	April 5
71	2-choice hashing worst case	4	April 5
70	2-choice hashing example	2	April 5
69	Grouping prisoners	6	April 12
68	Another hash table simulation	7	April 5
67	Why the max?	2	April 5
66	Multiple birthays problem	4	April 5
65	History of MST	5	April 12
64	Hash table simulation	5	April 5
63	Problem 62	1	March 29
62	Birthday Problem	2	March 29
61	Randomized MST example	4	March 29
60	Worst case of randomized MST	3	April 5
59	Subgraph selection with different probability	3	March 29
58	Boruvka examples	5	March 22
57	Beyond win-loss game trees	4	March 29
56	Game tree evaluation with arbitrary branching factor	4	March 29
55	Game tree evaluation with branching factor 3	3	March 22
54	Count to 5	6	March 1
53	The opposite of a treap	3	March 8
52	Randomized dictionary comparison	5	March 8
51	Treaps example	4	March 1
50	Simpler Randomized BST, Part 2	4	March 1
49	Simpler randomized BST, Part 1	3	March 1
48	Search in a randomized BST	1	March 1
47	Deletion from a randomized BST	3	March 1
46	Zombie ambulance	8-12	February 22
45	Complete my Skip List implementation	6	February 15
44	Limiting skip list height	1	February 15
43	Expected animal abuse	1	February 15
42	Expected value vs probability	3	February 15
41	Expected time to find a Delawarean	4	February 22
40	6-Week Survey	10	February 15
39	Skip list gallop search	4	February 22
38	Skip list sort	2	February 8
37	Skip list PQ	3	February 8
36	k-level skip list	2	February 15
35	2-level skip list	3	February 8
34	Skip list level distribition test	3	February 8
33	Make me a skip list	2	February 8
32	Problem 16 redux	2	February 15
31	Cryptographic vs algorithmic randomness	1	February 8
30	Universal PRNG	2 FOR ALL	February 22
29	Use Mersenne twister to shuffle a deck of cards	6	February 8
28	From a PRNG to a hash function	1	February 1
27	From a hash function to a PRNG	1	February 1
26	Combining two PRNGs	3	February 1
25	Coin flipper comparison	3	February 8
24	Seed one PRNG with another	4	February 1
23	Create some random art	8	February 15
22	Dice roller	4	February 8
21	Maximal-length mixed LCG sequence	2	February 1
20	Program to generate Lehmer LCG sequence	2	February 1
19	Longest-period Lehmer LCG with m=65537	3	January 25
18	Longest-period Lehmer LCG with m=11	1	January 25
17	Longest-period Lehmer LCG with m=6	1	January 25
16	Random using dev random	4	February 1
15	Calculating entropy of network traffic	3	February 1
14	Entropy in CS and Physics	2	January 25
13	Which is the randomest of them all?	1	January 18
12	Making a weighted coin	3	January 25
11	Unweighting a die	5-7	January 18
10	How many biased bits give an unbiased one?	3	January 18
9	Give me code names!	1	January 18
8	Problem 4 with variables	3	January 25
7	Fix Wikipedia	1-10	April 29
6	Your own scenario	3	January 25
5	Lower bound for number of passengers	2	January 11
4	How many passengers to screen?	2	January 11
3	Summarize an article	3	January 11
2	Summarize an article	3	January 11
1	Summarize an article	3	January 11