CS 206 - Introduction to Discrete Structures II

Spring 2017

Course Overview

This course is an introduction to probability theory and combinatorics, including their basic mathematical foundations as well as several applications of each to computer science, and to life. Your work will involve solving problems through rigorous mathematical reasoning, often constructing proofs, and the course is designed to teach how to do this.

By studying probability theory you will learn to think about randomness in a rigorous and sensical way. This is harder (and more fun) than it sounds as first: One's intuition is easily misled when it comes to probability, and we will discover surprisingly complex behavior in the world around us by examining simple processes carefully.

Combinatorics is about counting the number of objects fitting a given description. It is intimately related to probability theory: Knowing the number of possibilities for a random outcome often goes a long way to understanding that random process. But its relevance goes well beyond probability and thus we will look at several other applications as well.

Course Topics

The course covers the following list of topics, which are broken into three parts. Lecture summaries will be posted at the bottom of this page. You can also find previous semesters' class web pages linked from my homepage.

General Information

Expectations, Assignments and Grading

You are expected to attend every lectures. Required readings will be assigned from lecture notes occasionally posted on Sakai, and the text.

Semester grades will be a weighted average of the following:


Homeworks will be assigned every week. You are allowed to collaborate on homeworks, but you must write up your own submission. Copying someone else's work is considered a violation of the Honor Code and will be addressed accordingly. Homework is worth a significant part of your grade, but not as much as exams. I recommend viewing them as a chance practice thinking about problems before exam time -- If you find solutions via collaboration you will not likely get much out of them, only making things more difficult later.

Important notes regarding homework:


There will be X (where X is TBD) in-class quizzes. These will be scheduled in advance.

Midterms and Final

There will be two midterms and one final exam. The midterms will given in lecture. Practice material to prepare for the midterms and final will be provided. You may bring single-sided, handwritten (not copied) cheat sheet to the exams. A formula sheet will be provided on all exams. No books, notes, calculators, phones, laptops, or any other resource will be allowed during exams. The midterms will be on TBD and TBD. The final exam will be scheduled by the university.

Homework Assignments

Homework assignments will be posted on Sakai.

Lecture Schedule

A brief summary of each lecture and the associated reading will be posted here.