Note: This is the web­page for the Fall 2024 of­fer­ing of COM­P2804, Sec­tions A and B.

In­struc­tor: Pat Morin, 5177 HP, morin@​scs.​carleton.​ca

Jump to Lec­ture Top­ics

Jump to Next Lec­ture Topic

News and An­nounce­ments

New (De­cem­ber 20): 435 stu­dents wrote the COMP 2804 final exam. Final exam grades and the class grade dis­tri­b­u­tions for all course­work are now vis­i­ble in Bright­space.

TAs con­tinue to mark As­sign­ment 4, but I went ahead and com­puted a ten­ta­tive grade dis­tri­b­u­tion by fill­ing in each stu­dent's miss­ing as­sign­ment grades with the av­er­age grade from their com­pleted as­sign­ments.  This is what the re­sult­ing grade dis­tri­b­u­tion looks like:

435 final grades
25th percentile: 63.1 (C)
Median grade: 70.6 (B-)
75th percentile: 79.1 (A-)
Average grade: 70.7 (B-)
F   15 ===============
D-  10 ==========
D   15 ===============
D+  21 =====================
C-  39 =======================================
C   43 ===========================================
C+  46 ==============================================
B-  47 ===============================================
B   51 ===================================================
B+  39 =======================================
A-  57 =========================================================
A   30 ==============================
A+  22 ======================

I don't ex­pect this dis­tri­b­u­tion to change much when the TAs are done with As­sign­ment 4.

Let­ter con­ver­sions are done using the most gen­er­ous in­ter­pre­ta­tion of Car­leton's per­cent­age to let­ter con­ver­sion scheme

Un­like many of your pro­fes­sors, I will post the com­plete data used to com­pute your let­ter grade on Bright­space once I have it all.  This means some of you will see that your per­cent­age grade was a very close to a higher let­ter grade.  For ex­am­ple, you may have got­ten 78.8% (a B+) and see that you were only 0.2% away from an A-.  I won't re­spond to re­quests ask­ing to round these up. As I said, I'm al­ready using the most gen­er­ous in­ter­pre­ta­tion of Car­leton's con­ver­sion scheme (which ac­tu­ally states that 80-84 is the range for A-). 

Happy Hol­i­days!

New (Sep 13): This course has course dis­cord to com­mu­ni­cate with other stu­dents.

Learn­ing Modal­ity

Classes will take place in a class­room some­where on cam­pus that I am not al­lowed to dis­close. Find the lo­ca­tion by log­ging into Car­leton Cen­tral. The mid-term exam will take place in class. The final exam is a for­mally sched­uled exam man­aged by exam ser­vices.

Below, you will find a class by class list of lec­ture top­ics along with videos of each topic recorded in Fall 2020. These can be a use­ful re­source if, for some rea­son, you miss some classes.

Course Ob­jec­tives

A sec­ond course that is de­signed to give stu­dents a basic un­der­stand­ing of Dis­crete Math­e­mat­ics and its role in Com­puter Sci­ence. Com­put­ers han­dle dis­crete data rather than con­tin­u­ous data. The course pre­sents an overview of some of the major the­o­ret­i­cal con­cepts needed to an­a­lyze this type of data.

Of­fice Hours Sched­ule

We have lots of of­fice hours dur­ing which TAs or my­self can help you with study­ing course ma­te­r­ial and offer you guid­ance for as­sign­ments.

Im­por­tant Dates

Due dates for as­sign­ments and the date of the midterm exam are in the Course Out­line

As­sign­ments

As­sign­ments will be posted here as they be­come avail­able. As­sign­ments are to be sub­mit­ted using Bright­space.

• As­sign­ment 4 is due on De­cem­ber 6, at 11:55pm. It should be sub­mit­ted on Bright­space as a sin­gle PDF file.

• As­sign­ment 3 is due on No­vem­ber 10th, at 11:55pm. It should be sub­mit­ted on Bright­space as a sin­gle PDF file. As­sign­ment 3 sam­ple so­lu­tions and grad­ing guide­lines.

• As­sign­ment 2 is due on Oc­to­ber 18th, at 11:55pm. It should be sub­mit­ted on Bright­space as a sin­gle PDF file. Here are As­sign­ment 2 sam­ple so­lu­tions and grad­ing guide­lines.

• As­sign­ment 1 is due Sun­day Sep­tem­ber 22nd, at 11:55pm. It should be sub­mit­ted on Bright­space as a sin­gle PDF file. Here are As­sign­ment 1 sam­ple so­lu­tions and grad­ing guide­lines.

If you would like to see some sam­ple so­lu­tions from a pre­vi­ous of­fer­ing of this course, you can find some here. If you are look­ing for an ex­am­ple of ex­cel­lent as­sign­ment so­lu­tions, here are the sam­ple so­lu­tions (pdf) (tex) for As­sign­ment 1 Fall 2019

Please note the fol­low­ing rules and re­quire­ments about as­sign­ments:

• Late as­sign­ments will not be ac­cepted.
• As­sign­ments emailed to me will not be ac­cepted.
• I will not re­spond to emails sent shortly be­fore or after as­sign­ment dead­lines ask­ing for ex­cep­tions to the pre­ced­ing two rules.
• You can type your so­lu­tions, or write them by hand and scan them (for ex­am­ple, using a scan app on your phone or using a real scan­ner).
• So­lu­tions writ­ten-up in LaTeX are pre­ferred, but not strictly re­quired. In case you want to learn LaTeX, here is a tu­to­r­ial. Learn­ing LaTeX is a use­ful ex­er­cise, since many pro­grams (in­clud­ing Mi­crosoft Word) now use LaTeX for type­set­ting for­mu­las.
• Each as­sign­ment must be sub­mit­ted as one sin­gle PDF file through Bright­space.

Exams

The midterm exam will take place in class. The final exam will be a for­mally sched­uled exam han­dled by ex­am­i­na­tion ser­vices.

Here are exams for pre­vi­ous of­fer­ings of this course (for study pur­poses).

Here you can use use pre­vi­ous exams as prac­tice exams.

Grad­ing Scheme

This course will use the fol­low­ing grad­ing scheme.

If you fail to sub­mit an as­sign­ment on time but are able to pro­vide me with a valid rea­son then I will shift the weight of the missed as­sign­ment onto the re­main­ing as­sign­ments. If you fail to sub­mit all of the as­sign­ments with a valid rea­son for each one them then I will shift their weight onto the final exam. If you fail to at­tend the midterm exam and pro­vide me with a valid rea­son then I will shift the weight of the midterm exam onto the final exam.

Text­books

We will be using the fol­low­ing free (libre and gratis) text­books. The first one is the pri­mary text­book for this course. The sec­ond con­tains sup­ple­men­tary and back­ground ma­te­r­ial:

• Michiel Smid. Dis­crete Struc­tures for Com­puter Sci­ence: Count­ing, Re­cur­sion, and Prob­a­bil­ity, 2019.
• Eric Lehman, F Thom­son Leighton, and Al­bert R Meyer. Math­e­mat­ics for Com­puter Sci­ence, 2018

Lec­ture Top­ics

You should al­ready be fa­mil­iar with the fol­low­ing top­ics from COMP 1805: basic log­i­cal rea­son­ing, sets and func­tions, proof strate­gies (di­rect proof, proof by con­tra­dic­tion, proof by in­duc­tion), Sigma-no­ta­tion for sum­ma­tions, basic graph the­ory, Big-Oh, Big-Omega, Big-Theta. You may take a look at Chap­ter 2 of the text­book and do some of the ex­er­cises at the end of that chap­ter. Re­view the rel­e­vant parts of Lehman et al if you are still strug­gling.

Note: Most of the videos below are from the Fall 2020 of­fer­ing of this course and are pro­vided as a tool for re­view­ing things that will be taught in class. The lec­ture-by-lec­ture sched­ule may be changed as the se­mes­ter pro­gresses and (late in the se­mes­ter) we may cover some top­ics not cov­ered in the videos below.

• Lec­ture 1: In­tro­duc­tion (in-class notes)
  • Course overview.
  • Chap­ter 1 in the text­book: Ram­sey The­ory, Quick-Sort, Sperner's The­o­rem.
    
• Lec­ture 2: Count­ing (1) (in-class notes)
  • Prod­uct Rule, Sec­tion 3.1
    
• Lec­ture 3: Count­ing (2) (in-class notes)
  • Bi­jec­tion Rule, Com­ple­ment Rule, Sum Rule, The Prin­ci­ple of In­clu­sion-Ex­clu­sion, Sec­tions 3.2, 3.3, 3.4, 3.5.
    
    
• Lec­ture 4: Count­ing (3) (in-class notes)
  • Bi­no­mial co­ef­fi­cients, New­ton's Bi­no­mial The­o­rem, com­bi­na­to­r­ial proofs, Van­der­monde's Iden­tity, Pas­cal's Tri­an­gle, Sec­tions 3.6, 3.7.
    
    
• Lec­ture 5: Count­ing (4) (in-class notes)
  • Sec­tions 3.7 and 3.8.
  • How many strings can be ob­tained from SUC­CESS? Sec­tion 3.9.1
  • Count­ing so­lu­tions of lin­ear (in)equal­i­ties, Sec­tion 3.9.2
    
    
• Lec­ture 6: Pi­geon­hole Prin­ci­ple (in-class notes)
  • Simon's Drink­ing Prob­lem, Sec­tion 3.10.1
  • Every $(n+1)$-el­e­ment sub­set of $\{1,\ldots,2n\}$ con­tains a di­vis­i­ble pair, Sec­tion 3.10.2
  • The Erdös-Szek­eres The­o­rem
  • In­fin­ity of primes, Sec­tion 3.10.4
    
• Lec­ture 7: Re­cur­sion (1) (in-class notes)
  • Re­cur­sive func­tions, Sec­tion 4.1.
  • Fi­bonacci num­bers, Sec­tion 4.2.
  • Proof that $f_n = (\varphi^n - \psi^n)/\sqrt{5}$
  • Count­ing 00-free bit­strings
  • Count­ing $aa$-free strings over $\{a,b,c\}$
  • Count­ing $ab$-free strings over $\{a,b,c\}$
    
• Lec­ture 8: Re­cur­sion (2) (in-class notes)
  • Ex­er­cise 4.38
  • Eu­clid's al­go­rithm, Sec­tion 4.5. (gcd.​py)
    

• Lec­ture 9: Re­cur­sion (3) (in-class notes)

  • Merge­Sort, Sec­tion 4.6. (merge_­sort.py)
    

• Lec­ture 10: Ran­dom­iza­tion and prob­a­bil­ity (in-class notes)

  • Anony­mous broad­cast­ing: Din­ing Cryp­tog­ra­phers, Sec­tion 5.1.
  • Prob­a­bil­ity The­ory: Prob­a­bil­ity spaces, sam­ple spaces, prob­a­bil­ity func­tions, Sec­tion 5.2.
  • Basic rules of prob­a­bil­ity, Sec­tion 5.3.
    
    
• Lec­ture 11: Two sur­pris­ing ex­am­ples (in-class notes)
  • The Birth­day Para­dox (sec­tion 5.5)
  • Find the big box (sec­tion 5.6)
    
    

• Lec­ture 12:

  • Find Patti: The O'Reil­ley Triplets Prob­lem, Sec­tion 5.7.
  • Con­di­tional prob­a­bil­ity, Sec­tion 5.8.
  • Anil's kids, Ex­er­cise 5.40, the re­mark­able set B.
    

• Midterm Exam Prepa­ra­tion (sam­ple midterm)

• Midterm Exam

• Lec­ture 13: In­de­pen­dent events (in-class notes)

  • In­de­pen­dent events, Sec­tion 5.11.
  • Ex­er­cise 5.81: Annie, Boris, and Char­lie write an exam.
    
    

• Lec­ture 14: (in-class notes)

  • Sec­tion 5.12, in par­tic­u­lar, the prob­a­bil­ity of a cir­cuit fail­ing, Sec­tion 5.12.3.
  • Choos­ing a ran­dom line in a file, Sec­tion 5.13.
    

• Lec­ture 15: (in-class notes)

  • In­fi­nite prob­a­bil­ity spaces, Sec­tion 5.15, Ex­er­cises 5.85 and 5.91.
  • The law of total prob­a­bil­ity
    

• Lec­ture 16: (in-class notes)

  • Ran­dom vari­ables, Sec­tion 6.1.
  • In­de­pen­dent ran­dom vari­ables, Sec­tion 6.2.
  • Ex­pected value, Sec­tion 6.4.
  • Lin­ear­ity of ex­pec­ta­tion, Sec­tion 6.5.
    

• Lec­ture 17: (in-class notes)

  • In­di­ca­tor ran­dom vari­ables, Sec­tion 6.8, Ex­er­cise 6.57.
  • Ex­pected run­ning time of In­ser­tion-Sort, Sec­tion 6.9
  • Largest el­e­ments in pre­fixes of ran­dom per­mu­ta­tions, Sec­tion 6.8.2.
  • Es­ti­mat­ing the har­monic num­ber, Sec­tion 6.8.3.
    
    

• Lec­ture 18: (in-class notes)

  • Quick-Sort and ran­dom bi­nary search trees, Sec­tion 6.10 and Sec­tion 7.1 of ODS.
    

• Lec­ture 19: (in-class notes)

  • Geo­met­ric dis­tri­b­u­tion and its ex­pected value, Sec­tion 6.6, Ex­er­cise 6.35.
  • Ex­er­cise 6.59 (the Coupon Col­lec­tor's Prob­lem)
  • Bi­no­mial dis­tri­b­u­tion and its ex­pected value, Sec­tion 6.7.
    

• Lec­ture 20: The Prob­a­bilis­tic Method (in-class notes)
  • Find­ing large bi­par­tite sub­graphs, Sec­tion 7.1
  • Graphs with no large clique or in­de­pen­dent set, Sec­tion 7.2
  • Jac­card dis­tance sat­is­fies tri­an­gle in­equal­ity, Sec­tion 7.4
    

• Lec­ture 21: Pla­nar graphs and the Cross­ing Lemma (in-class notes)
  • Proof that the Ram­sey Num­ber $R(k,k)\le 2\cdot 4^k$
  • Pla­nar graphs, Sec­tion 7.5.1
  • The cross­ing lemma, Sec­tion 7.5.2
    

• Final-exam re­view
  • Solv­ing the Win­ter 2019 Final Exam
    
  • Solv­ing ques­tions 19-25 on the Win­ter 2019 Final Exam