Cake Cutting Algorithms [CSE 544T (Fall 2012)]

Course Information

Overview

Cake-cutting algorithms consider the division of resources among a set of participants such that the recipients believe they have been treated fairly. In some cases, a given resource can be divided without loss of value, while in other cases, dividing a resource may lessen its value, perhaps significantly. Notions of fairness include proportionality, envy-freeness, and equitability. This course is organized around a rich set of fair-division problems, studying the correctness, complexity, and applicability of algorithms for solving such problems. The problems and algorithms studied span millennia and include recent technical literature.

Students taking this course should be familiar with topics in a standard computer science course covering discrete math and logic (including proofs), and asymptotic analysis.

Instructor

Ron K. Cytron

office:	525 Bryan Hall
email:	cytron@wustl.edu
office hours:	M 11:30 AM-12:30 PM; W 11:30-Noon; F 9-10 AM

Teaching Assistants

• Marc Schlosberg

Grading

What	When	Weight for final grade
Exams	Two exams will be given in class (not take-home): one at midterm and one at the end. The end exam may or may not be cummulative, depending on how people do on the midterm exam.	Each is worth 25%
Homework	No homework will be graded, but questions will be posed throughout the semester.	0%
Project	You must find some fair division problem to which you will apply a technique we study this semester. The problem can come from your life, from campus life, from greek life, from the region, the state, the nation, or the world. You will be required to propose your project in the few weeks of the semester, and reports on your progress may be required periodically during the course.	This is worth 30%
Participation	Presentations in class (but not project presentations). Maybe you will present a paper or address an open issue. Scribing a lecture, which works as follow: If you tell me before class that you will not be present, then you have an excused absence from class. You may have at most two excused absences in the semester unless we have some other arrangement. A name will be randomly chosen from the class roster, and that person must be present or have an excused absence. If your name is called and you do not have an excused absence, then your participation score for the semester is 0. The person whose name is randomly chosen is a scribe for the lecture. If you have previously scribed, you can ask that I pass the scribe token to another student, whose name would be randomly chosen using the same process described above. The duties of the scribe are as follows: You must take notes and send those to me in PDF by the next day. No other format is acceptable, so scan or convert what you have to PDF. I will post those notes and credit you for the participation. These rules may seem Draconian, but I am not interested in teaching this course to students who are not present. If you plan on missing many classes, the best grade you can earn is 80%. Please be aware of these policies and act accordingly.	This is worth 20%

Academic Integrity

Anyone found cheating will on any graded assignment will receive an F for this course; other action may also be taken.