CS 860: Patterns in Strings: Existence, Avoidability, Enumeration

University of Waterloo: Fall 2008

Time: 11:30 AM - 12:20 PM MWF MC 2036A

Instructor: Jeffrey Shallit, DC 3134, x 34804, e-mail: `shallit` at cs

My office hours will be 10:00 AM - 11:00 AM on Tuesdays and Thursday in DC 3134. You can also make an appointment, or just stop by. I am available whenever my office door is open; if it is closed, please don't knock, as I am either not there or having a nap.

The course description and other information about the course can be found here.

Problem Set 1 (distributed October 3, due October 17).

Solutions to Problem Set 1 (password needed)

Problem Set 2 (distributed October 22, due November 5).

Solutions to Problem Set 2 (password needed)

Problem Set 3 (distributed November 10, due November 24). (Revised 9:15 AM, Monday, November 10; if you downloaded it before then, please reload.)

Solutions to Problem Set 3 (password needed)

Here are descriptions of each lecture (updated daily).

Here are the open problems discussed in the course.

Here is the current schedule for the class presentations.

Here are the course project ground rules and a first draft of the course project ideas (updated September 11).

Here is a tentative outline of what we will cover:

Week 1: Introduction, basic definitions and results
Week 2: No class, instructor at a conference
Week 3: Overlap-free words and the Restivo-Salemi factorization theorem. Lexicographically least overlap-free words. Student presentations begin on Friday, September 26
Week 4: De Bruijn words
Week 5: Decision procedures for squarefree, overlap-free, etc. words defined by automata
Weeks 6 and 7: The Lovász local lemma
Weeks 8 and 9: Abelian powers, including enumeration results
Week 10: Dejean's conjecture
Weeks 11-12: Algorithmics of patterns; perhaps some more enumeration
Week 13: Biology
If there is time: Generalization to larger ordinals, enumeration, other results, applications to biology, music, etc.

Here are the course notes. You will need a username and a password -- see instructor for details.

University-Required Text

Academic Integrity:

In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research. The Office of Academic Integrity's website www.uwaterloo.ca/academicintegrity) contains detailed information on UW policy for students and faculty. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in -- and out -- of the classroom.

Grievance:

A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 - Student Petitions and Grievances, Section 4, http://www.adm.uwaterloo.ca/infosec/Policies/policy70.htm .

Discipline:

A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about "rules" for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71 - Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71 - Student Discipline, http://www.adm.uwaterloo.ca/infosec/Policies/policy71.htm.

Avoiding Academic Offenses:

Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy, http://www.math.uwaterloo.ca/navigation/Current/cheating_policy.shtml .

Appeals:

A student may appeal the finding and/or penalty in a decision made under Policy 70 - Student Petitions and Grievances (other than regarding a petition) or Policy 71 - Student Discipline if a ground for an appeal can be established. Read Policy 72 - Student Appeals, http://www.adm.uwaterloo.ca/infosec/Policies/policy72.htm .