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.

Problem 51

Randomized algorithms will find you true love

Due: February 23
Points: 2

Read this article from the Washington Post on a randomized algorithm for deciding when to settle down and get hitched.

I want you to write a very short (1 or 2 paragraphs) description of what the basic problem is. Then I also want you to choose 2 variants of the original problem and describe them too. You can get these variants from what the article itself discusses, or from some other related source you find, or from something you make up yourself.

For these three variants (the main problem the article talks about, plus your 2 variants), illustrate how the "optimal" algorithm works using some small examples, like with 10 or so potential mates and their relative rankings.

Be sure to include any additional citations to references you used.