Discrete Structures II (COMP 2804)
Winter 2019
Instructor:
Michiel Smid
Office: Herzberg Building 5125C
E-mail: michiel(@scs.carleton.ca)
Lectures: Wednesday/Friday 1:05-2:25 pm,
Minto Centre 2000
Office hours: Wednesday 9-11
Teaching assistants:
- TA's office hours will be held in Herzberg Building 5336
- Alexa de Grandmont
Office hours: Friday 9:30 - 11:30
- Justin Lo
Office hours: Thursday 1:30 - 3:30
- Luke Connolly
Office hours: Wednesday 10:30 - 12:30
- Mohamed Kazma
Office hours: Monday 3-5
- Zoltan Kalnay
Office hours: Thursday 10 - noon
- Yingjie Song
Office hours: Tuesday 12:30 - 2:30
- Tyler Tuttle
Office hours: Monday 1:30 - 3:30
- Vincent Wang
Office hours: Tuesday 10:30 - 12:30
- Yuan Wu
Office hours: Thursday 10 - noon
Course objectives:
A second course that is designed to give students a basic understanding
of Discrete Mathematics and its role in Computer Science. Computers handle
discrete data rather than continuous data. The course presents an
overview of some of the major theoretical concepts needed to analyze
this type of data.
Topics covered include:
Counting, recursion, discrete probability, random variables,
randomized algorithms. Material is illustrated
through examples from computing.
Textbook:
- The following free textbook will be used:
Discrete Structures for Computer Science: Counting, Recursion, and
Probability.
- Additional material:
Discrete Mathematics and its Applications, by Rosen. This book
contains a large number of exercises, as well as solutions.
Do not buy this book, because it is too expensive. We used
to use this book for COMP 1805, so you may still have an old
copy, or you may borrow a copy from a friend.
Important dates:
- Assignment 1: posted January 17, due January 31
- Assignment 2: posted January 31, due February 14
- Midterm: Wednesday February 27 (in class)
- Assignment 3: posted March 7, due March 21
- Assignment 4: posted March 21, due April 4
- Final exam: Sunday April 14, 7-9 pm, Field House, rows 1-15
Grading scheme:
- Assignments: 25%
- Midterm: 25%
- Final exam: 50%
Assignments:
- Late assignments will not be accepted.
- Real computer scientists use
LaTeX to type
their solutions. In case you want to learn LaTeX,
here is a tutorial.
- Each assignment must be submitted as one single PDF file through
cuLearn.
- You can type your solutions, or write them by hand and scan them
(for example, using a scan app on your phone or using a real
scanner).
- Instructions on how to submit your assignment can be found
here.
- Assignment 1 is due Thursday January 31, before 11:55 pm.
- Here is Assignment 1 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
- Here are the solutions
as a LaTeX file, and
here and
here are the figures.
- I used the freely available
Ipe
drawing editor to make the figures.
- Assignment 2 is due Thursday February 14, before 11:55 pm.
- Here is Assignment 2 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
- Here are the solutions
as a LaTeX file, and
here and
here are the figures.
- Assignment 3 is due Thursday March 21, before 11:55 pm.
- Here is Assignment 3 as a
pdf file.
- Here is the LaTeX file and
here is the figure.
- Here are the solutions.
- Here are the solutions
as a LaTeX file.
- Assignment 4 is due Thursday April 4, before 11:55 pm.
- Here is Assignment 4 as a
pdf file.
- Here is the LaTeX file.
- Here are the solutions.
- Here are the solutions
as a LaTeX file.
Practice problems:
- Here you
find assignments from previous terms.
- Here you
find midterms from previous terms.
- Here you
find final exams from previous terms.
Midterm:
- For the midterm, you have to know everything we did in class up to
and including the February 15 lecture, as well as the first two
assignments.
- Calculators are allowed.
- Bring pencils (the scantron machine prefers pencils).
Final exam:
- Final exam: Sunday April 14, 7-9 pm
- Calculators are allowed.
- Bring pencils (the scantron machine prefers pencils).
- The exam will be multiple-choice, 25 questions. It covers everything
we have done in class, assignments, and midterm.
What was done in class:
- January 9:
- Course overview. Chapter 1 in the textbook:
Ramsey Theory,
Sperner's Theorem,
Quick-Sort.
- You are supposed to be familiar with the following topics
from COMP 1805: basic logical reasoning, sets and functions,
proof strategies (direct proof, proof by contradiction, proof
by induction), Sigma-notation for summations, basic graph
theory, Big-Oh, Big-Omega, Big-Theta.
You may take a look at Chapter 2 of the textbook and do some
of the exercises at the end of that chapter.
- January 11:
- January 16:
- January 18:
- January 23:
- January 25:
- January 30:
-
Recursion: Recursive functions, Section 4.1.
- Recursion:
Fibonacci numbers,
Section 4.2.
- Recursion: Counting 00-free bitstrings,
Section 4.2.1.
- Recursion: Exercise 4.38.
- February 1:
- February 6:
- Recursion:
MergeSort,
Section 4.6.
- Recursion: I am skipping this this term, because we are
behind schedule; you should read this by yourself:
Exercise 4.69, my notes are
here.
- February 8:
- February 13: Snow day. Class cancelled.
- February 15:
- Uniform probability spaces, Section 5.4.
- Exercise 5.11 (same as Q4 of A3 of Fall 2017), which is
known as the
Newton Pepys problem.
- February 18-22: Winter break.
- February 27: Midterm
- March 1:
- March 6:
- March 8:
- March 13:
- Section 5.12, in particular, the probability of a circuit
failing, Section 5.12.3.
- Choosing a random element in a linked list, Section 5.13.
- March 15:
- Infinite probability spaces, Section 5.15, Exercises 5.85 and
5.91.
- March 20:
- March 22:
- March 27:
- March 29:
- Indicator random variables, finish Exercise 6.58.
- Largest elements in prefixes of random permutations,
Section 6.8.2.
- Estimating the
harmonic number, Section 6.8.3.
- I am skipping this this term, because we are behind schedule:
Expected running time of
Insertion-Sort, Section 6.9.
- Introduction to
Quick-Sort,
Section 6.10.
- April 3:
- April 5:
- April 10:
Tentative schedule (based on last term)