This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Problems

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
102Final Exam0-32May 3
101Problems survey3May 3
100File fingerprinter5May 3
99String matching example3May 3
98Substring search algorithms2May 3
97Multiple choice test2May 3
96Fool the multiplication verification1May 3
95Cryptographic voting4May 3
94MIDN Burmeister Trident presentation3May 3
93Square root ORAM, more or less2April 26
92ORAM simulator webpage5April 26
91Garbled circuit simplification?2April 26
90Local vs remote storage sizes1April 26
89ORAM research paper2-3April 26
88Make a garbled circuit4April 19
87Run a garbled circuit using openssl2April 19
86Ungarble my circuit3April 19
85Garbled circuit over-simplification3April 19
8412-Week Exam0-20April 12
83Oblivious password authentication8April 26
82IND-CCA21April 12
811 out of n OT2April 12
80Speed comparison of cryptographic primitives2April 12
79Learn about a crypto hash1-2April 12
78Learn about a crypto PRNG1-2April 12
77Password validator6April 12
76Static Bloom filter?2March 29
75Bloom filter example2March 29
74Primality testing through perfect hashing5March 29
73Perfect hashing example3March 29
72Static hashing challenge1-4March 22
71Hash table to store a set #32March 29
70Hash table to store a set #22March 22
69Hash table to store a set #11March 22
682-choice hashing worst case2March 22
672-choice hashing example1March 22
66k-choice hashing simulation5March 22
65Multiple birthays problem3March 22
64Randomized search tree vs language built-in4March 8
63Video about shuffling2March 22
62Randomized dictionary comparison3March 8
61Treaps example2March 8
60Simpler Randomized BST, Part 22March 8
59Simpler randomized BST, Part 12March 8
58Search in a randomized BST1March 8
57Deletion from a randomized BST2March 8
56Zombie ambulance6-9March 1
55Limiting skip list height1March 1
546-Week Survey4March 1
536-Week Exam0-20February 23
51Randomized algorithms will find you true love2February 23
50Skip list PQ2February 23
49k-level skip list2March 1
48Complete my Skip List implementation5February 23
47Facebook degrees of separation3February 23
46Exam questions2May 3
45Find errors on my website1May 3
44Go to a math talk5February 23
43Skip list gallop search4February 23
42Skip list sort2February 23
412-level skip list3February 23
40Skip list level distribition test3February 23
39Make me a skip list2February 23
38Expected animal abuse1February 9
37Most likely running time2February 9
36Expected time to find a Delawarean3February 9
35From a PRNG to a hash function1February 9
34From a hash function to a PRNG1February 9
33Coin flipper comparison3February 9
32Seed one PRNG with another4February 9
31Create some random art4February 9
30Problem 17 actually2February 9
29What RNGs do Java and Python use?2February 2
28Combining two PRNGs3February 23
27Program to generate Lehmer LCG sequence2February 2
26Maximal-length mixed LCG sequence2February 9
25Longest-period Lehmer LCG with m=655372February 2
24Longest-period Lehmer LCG with m=111February 2
23Longest-period Lehmer LCG with m=61February 2
22Calculating entropy of network traffic2February 2
21Unweighting a die - BONUS2-4February 23
20Making a weighted coin2February 2
19Unweighting a die3-5January 26
18How many biased bits give an unbiased one?1January 26
17Dice rolling programs2January 26
16Demo Bull Mountain1February 2
15Read about Bull Mountain2January 26
14Summarize a research paper2January 26
13Summarize an article1January 26
12Mystery program3-4January 19
11A better system for who goes first3January 26
10Expected number of dice rolls2January 19
9Who goes first - more on dice sums2January 19
8Dice sum collisions1January 19
7Problem 2 with variables2January 26
6Give me code names!1January 19
5Powerball1January 19
4Your own scenario2January 19
3Lower bound for number of passengers2January 19
2How many passengers to screen?2January 19
1Fix Wikipedia1-10May 3