News

Next week there will be a regular class at X-hour, 9:05-9:55 on Thursday April 23. There will be no office hour after that class, and no class the following day (Friday April 24).

On the shelves outside our classroom (between Kemeny 007 and 008) the column closest to 007 is devoted to returning your graded homeworks. You can pick them up anytime, they're sorted into five alphabetic slots.

The classroom in which we will meet is Kemeny 007, sometimes called the "Bond room." The time slot is 9L, thus regular class meets MWF from 8:50 am to 9:55 am, with X-hour (which will be used occasionally for make-up or review) Thursday 9:05-9:55.

For those of you who are brushing up on probability using Grinstead and Snell, a set of answers that are "mostly correct" to the exercises therein was sent to me by Charles Grinstead and can be found here.

Abstract

Permutations are everywhere, it seems, in mathematics and computer science, and even in the social sciences. In many cases, for instance, when you are interested in sorting, it is natural to think of the set of permutations on a set of n elements as a probability space. Suppose you have information about some job candidates that suggests some are better than others, but nothing directly comparing x and y. What is the probability that x is better than y? Does it necessarily go up if you get a new letter saying x is better than z?

Suppose you wish to sort a set of data, but comparisons are expensive. Which pair of elements, if compared, would give you the most information?

This course will take you to the world of partial orders, linear extensions, permutahedra, permutation patterns, sorting algorithms, exact and approximate counting problems, random walk, and limit structures. You will need to have taken at least a basic course in probability (such as MATH 20) and seen enough mathematics or theoretical computer science to be comfortable with abstract concepts and logical reasoning.

There will be a homework assignment due at the beginning of each class, usually just one problem. You may consult with your colleagues or AI on homework provided they are suitably credited, but neither will be available during exams. You will not be required to write computer programs, but writing and running a program will sometimes provide an alternative way to do an assignment.

Here is a rough weekly syllabus:

1. The probability space of permutations: fixed points, cycles

2. Partial orders and linear extensions: permutahedron, convex subsets

3. Probability and sorting: correlation, XYZ inequality

4. The 1/3-2/3 conjecture and its successors

5. MCMC and approximate counting of linear extensions

6. #P hardness and exact counting of linear extensions

7. Sorting algoithms: quicksort, merging, filing

8. Stack-sorting, permutation patterns, Marcus-Tardos Theorem

9. Permutations generated by random walk

10. Limit structures, permutons

Classes

Room: TBA
Lectures: 9L slot: Monday, Wednesday and Friday 8:50 - 9:55.
Classroom: Kemeny Hall 007.
X-hour: Thursdays 9:05 - 9:55. Will be used only when so announced in class.

Staff

Instructor:

Prof. Pete Winkler -- Kemeny Hall 231
Office Hours: Tue 9-10, Thu 11-12. email: peter.winkler at dartmouth.edu

TA:

Andrew Zhao
email: Andrew.E.Zhao.28 at dartmouth.edu

Textbooks

There is no official textbook for the course.

If you need to brush up on elementary probability, we suggest Grinstead and Snell's Introduction to Probability, which is available online here at Dartmouth.

Grading

Your grade will be based on homework, class participation (attendance is expected!), midterms, and a final exam.

Exams

There will be in-class exams on Monday, April 13 and Monday, May 4. Let your instructor know in advance if you antipate a conflict. The final exam will be held on the assigned day and time for the course's time slot, namely, 3 pm on Monday, June 8.

Homework

Homework will be assigned at each class period, due on paper at the beginning of the next class. If you can't make it to class let the instructor know, and email a PDF of your homework to the instructor and the TA. Late homeworks will be checked off but not graded.

Assignments

Due Wednesday April 1: Let a permutation of {1,2,...,n} be chosen uniformly at random. For n large, what is the probability that it contains a cycle of length greater than n/2?

Due Friday April 3: Write up a little theorem and proof to justify the claim that, in the 100 prisoners problem, no matter how the warden chooses to distribute names in boxes, if the prisoners assign ownership of boxes uniformly at random, then the resulting permutation (mapping each prisoner to the name found inside the box he owns) is uniformly random.

Due Monday April 6: See if you can fix the insertion algorithm---keeping the spirit of the name---so that its worst-case running time is better than Θ(n²).

Due Wednesday April 8: A classic puzzle presents you with 12 coins, one of which is counterfeit and is either lighter or heaver than the others. The task is to determine which coin is the counterfeit and whether it is lighter or heavier, using just three weighings with a balance scale. Your mission, however, is to prove that it can't be done with 14 coins or (for your second point) even 13.

Due Friday April 10: Let x₀, x₁, x₂, x₃, x₄ be a sequence of integers with positive sum, with indices interpreted modulo 5. An "operation" consists of selecting a negative term, say x_k, replacing x_k by -x_k (a positive number), replacing x_k-1 by x_k-1 + x_k, and replacing x_k+1 by x_k+1 + x_k. Now, given any sequence x₀, x₁, x₂, x₃, x₄, you can create a doubly-infinite sequence ... s_-1 s₀ s₁ with the property that s_n+1 = s_n + x_{n mod 5}. The question is: what does an "operation" on x₀, x₁, x₂, x₃, x₄ do to its corresponding infinite sequence?

Due Wednesday April 15: Suppose you start with n items in a row. You choose one of the items uniformly at random and remove that item along with all the items to its left or all to its right, whichever is the smaller set. For example, if n = 10 and you choose item 8, items 8 through 10 are removed; but if you choose item 4, items 1 through 4 are removed. You now repeat this procedure on the remaining items, and repeat again, etc., until all the items are gone. How many "procedures" does this require, on average?

Due Friday April 17: Consider the following algorithm, which sorts "in place" but not by doing comparisons; instead, the items are numbered 1 through n and the spaces likewise. The algorithm finds (nondeterministically) an item which is not where it belongs, and shoves it in where it belongs---shifting the items in between up or down by one. For example, suppose item number 8 is found in space number 4. That item is moved into the 8th position, and the items previously in positions 5,6,7, and 8 are shifted down to positions 4,5,6, and 7 respectively. Note that this could dislodge some items that were previously in the right spot. Your question is: Does this algorithm even work? Clearly, if and when the algorithm terminates, the items will be correctly sorted. But maybe, if the algorithm makes sufficiently poor choices, it can run forever. Experiment with the algorithm and try to justify your answer.

Honor Code

Students are permitted to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a written homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of another person's solutions, in whole or in part, is a violation of the Honor Code.

If you employ generative AI, e.g. ChatGPT, say so, and say how you verified that what it told you is correct.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me, and I will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Notification to Student re Recording

(1) Consent to recording of course meetings and office hours that are open to multiple students. By enrolling in this course, a) I affirm my understanding that the instructor may record meetings of this course and any associated meetings open to multiple students and the instructor, including but not limited to scheduled and ad hoc office hours and other consultations, within any digital platform, including those used to offer remote instruction for this course. b) I further affirm that the instructor owns the copyright to their instructional materials, of which these recordings constitute a part, and my distribution of any of these recordings in whole or in part to any person or entity other than other members of the class without prior written consent of the instructor may be subject to discipline by Dartmouth up to and including separation from Dartmouth. (2) Requirement of consent to one-on-one recordings: By enrolling in this course, I hereby affirm that I will not make a recording in any medium of any one-on-one meeting with the instructor or another member of the class or group of members of the class without obtaining the prior written consent of all those participating, and I understand that if I violate this prohibition, I will be subject to discipline by Dartmouth up to and including separation from Dartmouth, as well as any other civil or criminal penalties under applicable law. I understand that an exception to this consent applies to accommodations approved by SAS for a student's disability, and that one or more students in a class may record class lectures, discussions, lab sessions, and review sessions and take pictures of essential information, and/or be provided class notes for personal study use only.

If you have questions, please contact the Office of the Dean of the Faculty of Arts and Sciences.

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations that might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Center is located at 318 Wilson Hall, ext. 6-9900, http://www.dartmouth.edu/~accessibility, if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.