CS 206 - Introduction to Discrete Structures II

Spring 2014

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 lectures, and to notify the instructor if you will miss class. Required readings will be assigned from lecture notes on Sakai, and optional readings from the text (if you have it) will be noted when relevant.

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.

There will be two in-class midterms and one final exam. Tentative dates for the midterms are February 28 and April 4. The final exam will be scheduled by the university.

Final grades will be an average of homework grades (20%), midterm grades (45%), and final exam grades (35%). The lowest homework grade will be dropped from the average.


Homework assignments will be posted here and on Sakai.

Lecture Schedule

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