Course Syllabus

Math 118, Topics in combinatorics, Mathematical Analysis of Algorithms

“People who analyze algorithms have double happiness. First of all
they experience the sheer beauty of elegant mathematical patterns
that surround elegant computational procedures. Then they receive a
practical payoff when their theories make it possible to get other jobs
done more quickly and more economically.”
– Donald Ervin Knuth

Instructor: Nadia Lafrenière (nadia.lafreniere@dartmouth.edu)

Class schedule: MWF 10:20 - 11:25 AM, Zoom # 925 0515 7790, password: 818910
x-hour: Th 12:30-1:20 PM, will likely not be used

Office hours: Monday 1:30-3:30 on Zoom (same meeting as lectures), and by appointment.

 

Course Description

Analysis of algorithms is a field of research on the edge of computer science and mathematics.
The approach for this class is the one introduced in the 60’s by Donald Ervin Knuth. Namely, we look at best-case, worst-case and average-case performance analysis, with emphasis on the latter. This study needs an understanding of combinatorial structures and probabilistic arguments, which will be detailed in this course.

Part of our exploration will imply asymptotic methods. Most arguments in the analysis of algorithms assume that we repeat the procedure often enough, so it is worth analyzing its cost. Therefore, analysis of algorithms goes along with asymptotic combinatorics, as we count the cost of running an algorithm in relationship to the size
of its input.

In this class, we study algorithms independently of their implementation. This means that we look at theoretical limitations, regardless of the functionalities offered by any given programming language.

Teaching Methods

This class is remote with synchronous components. Class time will be devoted to live lectures on Zoom, and students are expected to work on problem sets outside of class. On some days, student presentations will replace the instructor’s lecture.

Despite the focus of the class being on algorithms, students are not expected to implement them. For students who want to code, there will be opportunities to replace a few homework problems over the term by implementation and bench marking of algorithms.

Attendance Policy and x-hour

Class attendance and participation are expected. If you know that you will not be able to deliver an evaluation on time for a serious reason, let me know as soon as possible.

The x-hour will not be used, except for one lecture that is moved to the x-hour due to Martin Luther King Jr. Day.

Content’s Schedule (tentative)

This schedule is tentative, and will be updated over the term. Homework assignments are due on Wednesdays.

Date	Content
January 8	Introduction to the analysis of algorithms
January 11	First example: merge sort, optimal sorting algorithms
January 13	Solving recurrences
January 15	Divide-and-conquer algorithms, part 1
January 18	No class, MLK day
January 20	Divide-and-conquer algorithms, part 2 (Master’s theorem, Strassen algorithm for matrix multiplication)
January 21 (x-hour)	The symbolic method, ordinary generating functions
January 22	Labeled classes and exponential generating functions
January 25	Lagrange inversion
January 27	Averages and moments
January 29	Asymptotic expansions, part 1
February 1	Asymptotic expansions, part 2
February 3	Compositions and partitions
February 5	Student presentations
February 8	Student presentations
February 10	Student presentations
February 12	Trees
February 15	Trees for searching
February 17	Q&A: The symbolic method
February 19	Permutation statistics: Ascents, descents, runs
February 22	Permutation statistics: Cycle lengths
February 24	Permutation statistics: Increasing sequences
February 26	Sorting: Bubble sort, Quicksort
March 1	Randomized algorithms, Quicksort
March 3	NP-completeness
March 5	Student presentations
March 8	Student presentations
March 10	Student presentations

 

Combinatorics seminar

Dartmouth hosts a combinatorics seminar every other Friday at 1:15. You are encouraged to attend it, and I will advertise it in class before each talk. More details can be found on this webpage: https://math.dartmouth.edu/~comb/.

Evaluation (tentative)

The homework assignments will be available on Fridays, and will be due each Wednesday. There might be one or two problems that you will not be able to solve on the first days the problem set is available, but these will be marked.2:45-3:45

Evaluation	Date	Value
Problem Sets	Weekly on Wednesdays	50 %
2 student presentations	Weeks of February 5 and March 5	40 %
Class participation	Throughout the term	10 %

Finding the right answer is not equivalent to solving a problem, and therefore your solution will be evaluated as a whole. Please, keep in mind while writing the assignments that I will not be with you when I will read it, so it must be complete.

The student presentations can be about the analysis of any standard algorithm, or about techniques for analyzing or creating algorithms. Early in the term, I will provide the class with a list of topics that can be explored, but students will be allowed to choose topics not listed there. Students must notify me when they choose a topic.

I encourage students to do their presentations in teams of two students. The goal is twofold: to invite students to collaborate and socialize, because most math is done in collaboration, and to allow for some harder or larger topics to be presented.

Textbook

There is no required textbook for the class. Instead, course notes will be shared with students, and references will be indicated on them. A list of references that I am using to design the course material follows in this syllabus. All books listed here are either freely available online (at least partially) or are available (in both paper and electronic format) through the Dartmouth library. The main reference for the course will be [AofA]. Depending on students’ interests, a list of papers will be added to this list of books.

References

• [AC] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. Freely available online at https://ac.cs.princeton.edu/home/.
• [Algo] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. Available online through Dartmouth  Libraries.
• [AoCP] D. E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley, 1968. Available online through Dartmouth Libraries.
• [AofA] R. Sedgewick and P. Flajolet. An introduction to the analysis of algorithms. Addison-Wesley-Longman, 1996. Available online through Dartmouth Libraries.
• [EC1] R. P. Stanley. Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2012. Freely available online at http://www-math.mit.edu/~rstan/ec/ec1.pdf.
• [EC2] R. P. Stanley. Enumerative combinatorics. Volume 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. Available online through Dartmouth Libraries.
• [Wilf] H. S. Wilf. generatingfunctionology. Academic Press, Inc., Boston, MA, second edition, 1994. Freely available at https://www.math.upenn.edu/~wilf/gfologyLinked2.pdf. Only the first edition is physically available at the library.

Consent to Record

(1) Consent to recording of course and group office hours
a) I affirm my understanding that this course and any associated group meetings involving students and the instructor, including but not limited to scheduled and ad hoc office hours and other consultations, may be recorded within any digital platform 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 distribution of any of these recordings in whole or in part without prior written consent of the instructor may be subject to discipline by Dartmouth up to and including expulsion;

(2) Requirement of consent to one-on-one recordings
By enrolling in this course, I hereby affirm that I will not under any circumstance make a recording in any medium of any one-on-one meeting with the instructor 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 expulsion, as well as any other civil or criminal penalties under applicable law.

Honor Principle

Assignments and examinations serve both the purpose of fixing your ideas on a given subject and, for the evaluator, to assess the comprehension you have of the class and how the class material has been understood. None of these goals can be achieved if you hand out a solution that is taken from someone else or from a publicly available source.

Nevertheless, students are allowed to work together on problems to explore their solutions. The homework you submit must reflect your own understanding, and you thus need to write your own copy of the solution, in your own words.

More information on the Academic Honor Principle can be found on Dartmouth’s website: https://students.dartmouth.edu/judicial-affairs/policy/academic-honor-principle

 

Student Accessibility and Accommodations

Students with disabilities who may need disability-related academic adjustments and services for this course are encouraged to see me privately as early in the term as possible. Students requiring disability-related academic adjustments and services must consult the Student Accessibility Services office by phone: 646-9900 or email: Stu-
dent.Accessibility.Services@Dartmouth.edu.

Once SAS has authorized services, students must show the originally signed SAS Services and Consent Form and/or a letter on SAS letterhead to me. As a first step, if you have questions about whether you qualify to receive academic adjustments and services, you should contact the SAS office. All inquiries and discussions will remain
confidential.

Mental Health

The academic environment at Dartmouth is challenging, our terms are intensive, and classes are not the only demanding part of your life. There are a number of resources available to you on campus to support your wellness, including your undergraduate dean (http://www.dartmouth.edu/~upperde/), Counseling and Human Development
(http://www.dartmouth.edu/~chd/), and the Student Wellness Center (http://www.dartmouth.edu/~healthed/). Remember, mental and physical health should be your number one priority!

Religious Observances

Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me as soon as possible, preferably before the end of the second week of the term to discuss appropriate accommodations.

Financial Needs

All material for this class is aimed to be freely available, either at the library or online. If you encounter financial challenges related to this class (because of the workload for example), please let me know.

 

Title IX

At Dartmouth, we value integrity, responsibility, and respect for the rights and interests of others, all central to our Principles of Community. We are dedicated to establishing and maintaining a safe and inclusive campus where all have equal access to the educational and employment opportunities Dartmouth offers. We strive to promote an environment of sexual respect, safety, and well-being. In its policies and standards, Dartmouth demonstrates unequivocally that sexual assault, gender-based harassment, domestic violence, dating violence, and stalking are not tolerated in our community.

The Sexual Respect Website (https://sexual-respect.dartmouth.edu) at Dartmouth provides a wealth of information on your rights with regard to sexual respect and resources that are available to all in our community.

Please note that, as a faculty member, I am obligated to share disclosures regarding conduct under Title IX with Dartmouth’s Title IX Coordinator. Confidential resources are also available, and include licensed medical or counseling professionals (e.g., a licensed psychologist), staff members of organizations recognized as rape crisis centers under state law (such as WISE), and ordained clergy (see https://dartgo.org/titleix_resources).

Should you have any questions, please feel free to contact Dartmouth’s Title IX Coordinator or the Deputy Title IX Coordinator for the Guarini School. Their contact information can be found on the sexual respect website at: https://sexual-respect.dartmouth.edu.