CS 1800 Discrete Structures Schedule

Last Updated:

This is a detailed schedule for the Accelerated section. See CS1800-ACC Overview

--> -->

Date	Reading/Regular1800	Accelerated 1800	Optional	Assignments
Welcome	WELCOME Website / Canvas, Piazza , Staff Gradescope, Assignments, Exams, Grades	1800ACC-Gradescope ( code: RZNP5Y)	Live honors lectures from previous years (Chrome for 4k video), previous Notes, Team-streams, and other optional material.
Part 1: Logic, Proofs, Numbers, Binary
WEEK 1 Sep 4-11 Logic, Boolean variables Implication Logic Gates, Basic circuits Boolean Algebra Lecture 1 Notes	2.1 Transistors and Switches 2.2 Basic Logic Gates: AND, OR, NOT 2.4 Binary Arithmetic: Ripple Carry Adders 3.3 Truth Tables 3.4 Logical Equivalence BookNotes: simple circuits, boolean algebra BookNotes: circuits, logic rules Summary: Binary and Logic	Teaser: Konigsberg 7 bridges Teaser: Polygon triangulations Teaser: Sorting by digits (Radix Sort) (podcast)	(part 2, after min 42) Teams Stream	Recitation 1 (Logic) due Fri 9/8 HW 1 (Logic) due Tue 9/12 Project 1 : 2-CNF-SAT Due Sat 9/30
WEEK 2 Sep 11-18 Boolean Algebra, Predicates, Quantifiers Propositional and Predicate Logic Logic and Proofs Proofs 1 Negating Quantifiers Sets Intro Lecture 2 Notes	3.5 Normal Forms 8.1 Set Definition and Examples 8.2 Set Basics BookNotes: Predicate logic Quantifiers: Negation Rules	Proofs and quantifiers Logic basics Proof by Contradiction	Teams Stream	Recitation 2 (Boolean, Logic) due Fri 9/15 HW 2 (Logic, Proofs) due Tue 9/19
WEEK 3 Sep 18-25 Modulo Arithmetic Prime numbers, gcd Modulo Inverse Number Theory Notes Lecture 4 Notes	Chanpter 5 BookNotes: Modulo Arithmetic BookNotes: Modulo Properties BookNotes: GCD, Euclid	Proof: divisibility with 3		Recitation 3 (Modulo) due Fri 9/22 HW 3 (Modulo) due Tue 9/26
WEEK 4 Sep 25-Oct 2 Number Theory Modulo Inverse Number Theory Part 4 RSA Cryptography Lecture 5 Notes	BookNotes: Ext-Euclid, RSA			Recitation 4 (Number Theory) due Fri 9/29 Project 2 : Square Game Due 10/26
WEEK 5 Oct 2-9 Binary Representation Binary to/from Decimal Lecture 6 notes Lecture 6 notes	Ch. 1 Introduction 1.1 Binary Representation 1.2 Bytes 1.5 Converting Between Decimal and Binary BookNotes: binary representation	Binary card trick Card trick explained with decimal cards	Teams Stream	Recitation 5 (Binary) due Fri 10/6 HW 4 (Binary) due Thu 10/12
WEEK 6 Oct 9-16 Hexadecimal and Octal Negative Numbers, Two's Complement Bitwise Operations Radix Sort Sum Rule: Independent possibilities vs representation Notes OH Mon 10/9: Indigenous Peoples Day, no class	1.3 Hexadecimal Representation 1.4 Octal Representation 1.6 Representing Negative Numbers: Two's Complement Binary Search BookNotes: binary operations, hex, octal BookNotes: Two's complement Representation comparison Binary search optimality	Bitwise Operations ( code ) Proof basics addl notes on binary, two complement ( podcast )	Optional: Fast Inverse Square Root (pdf) (Newton) (code) (first part, up to minute 42)
Part 2: Sequences, Induction, Series, Recurrences
WEEK 6-7 Oct 9-18 Induction Sequences and Series Lecture 7 Notes Lecture 7 Notes	Ch12: Sequences, Series BookNotes: Sequences + Series Ch12: Sequences, Series Ch13: Induction BookNotes: Induction part 1	Geometric distribution Induction Handout Induction Proofs	Teams Stream	Recitation 6 (induction) due Fri 10/13 HW 5 induction due Wed 10/18
WEEK 7 Oct 16-23 Induction part 2 Inequalities Fibonacci Numbers Harmonic Series, e-limit Lecture 8 Notes	Book Notes: Induction Part 2	Harmonic Series Harmonic Approximation (Calculus)	Additional Induction Problems	Recitation 7 (induction) due Fri 10/20 HW 6 induction due Wed 10/25
WEEK 7 Oct 16-23 Asymptotic Run Time Solving Recurrences Recurrences and Induction Lecture 24 Notes	Book Notes: Recurrences	Function Growth Notation, Algorithms Slides: Searching And Sorting ( part 2) Slides : Recurrences Slides : Linear Recurrences
Part 3: Sets and Counting
WEEK 8 Oct 23-30 Set-Builder Notation Union, Intersection, Set Difference Set Size Power Set Product Rule Disjoint Sets: Sum/partition Rule Cartesian Product Inclusion-Exclusion Principle Pigeonhole Principle Lecture 9 Notes	Ch. 8 Sets 8.3 Set-Builder Notation 8.4 Venn Diagrams 8.5 Set Operations 8.6 Computer Representation of Sets 9.2 Inclusion-Exclusion Principle 9.3 Pigeonhole Principle BookNotes: Sets BookNotes: Set Counting BookNotes: Counting			Recitation 8 (sets, counting) due Fri 10/27 HW 7 (sets, counting) due Wed 11/1 Project 3 : Valid Dates Due 11/20
WEEK 9 Nov 1- 6 Product Rule, Permutations Combinations Balls Into Bins Sets vs Sequences Counting Problems Binomial Expansion, Theorem Pascal Triangle PIE general proof Lecture 10 Notes	Ch. 9 Introduction 9.1 Basic Rules 9.4 Permutations 9.5 Combinations 9.5 Balls in Bins BookNotes: Balls in Bins BookNotes: Binomial Coefficients Summary: Sets and Counting	Count Sets with one-to-one functions Countable Sets Infinite Enumerable Sets : N, Z, Q Inclusion-Exclusion Proof 9.6 Binomial Theorem, Pascal triangle Inclusion-Exclusion Proof	More on Inclusion-Exclusion Few Problems like the miderm (?) Optional: Counting, Pascal Triangle Formulas and a lot more Teams Stream Teams Stream
Midterm 11/3 Fri 3:20pm-7:20pm, WVH 212	Cheat Sheet allowed whole time: 4pages (2 sheets) Allowed first 60 min: notes/HWs/other written by you. Must be on paper, no electronic devices. Hand calculators: allowed
WEEK 10 Nov 6-13 Counting Problems Catalan Numbers Lecture 11 Notes	Catalan Numbers Balls into Bins with Capacity (2nd paper:Counting Multisets) Counting with Generative Functions Permutation Cycles	More on Generative Functions		Recitation 9 (counting) due Fri 11/10 HW 8 (adv counting) due Thu 11/16
Part 4: Probabilities, Random Variables, Expectation, Variance, Entropy
WEKK 11 Nov 13-20 Probabilities Spaces, Events Uniform Probabilities Non-Uniform Probabilites Random variables Joint and Conditional Probabilities Bayes Theorem Lecture 12 Notes	Ch. 10 Introduction 10.1 Definitions and Basic Properties 10.2 (Probability) Examples 10.3 Conditional Probability and Bayes Theorem BookNotes:Probability Basics Book : Intro to Probabilities	Probabilities (formal math) Monty Hall Problem (podcast) Zika Conditionals (podcast)		Recitation 10 (probabilities) due Fri 11/17 HW 9 (probabilities) due Thu 11/26
Week 12 Nov 20-27 Expectation Variance Entropy Binomial Distribution Markov Chain Lecture 13 Notes Lecture 14 Notes Thanksgiving Break: no class/OH Wed Nov 22- Sun Nov 26	BookNotes:Conditional Probability Conditional and Joint Examples 10.4 Markov Chains BookNotes: Markov Chain BookNotes: Expectation, Variance, Entropy Expectation Counting Summary: Probabilities, Expectation	Random variables, Expectation, Variance E[] VAr[] proofs Binomial Distribution Balls-Bins-Coupons podcast Optional: Law of Large Numbers		Recitation 11 (expectation, var) due Fri 12/1 HW 10 (expectation, entropy, graphs) due Thu 12/6
Skiplists BST Sampling	Skiplists Slides BST Slides	Skiplists Math Binary Search Trees (Cormen book) Sampling Code (Matlab)		Proj 4: Skiplists, BST due Tue 12/12
Part 5 : Graphs, Trees, Networks
Week 13 Nov 27- Dec 2 Graphs and Trees Binary Search Trees Skiplists Lecture 20 Notes Lecture 21 Notes	Book Notes: Graphs 1 Book Notes: Graphs 2	Graph Theory Notes Bipartite Graphs, 2-Coloring ( Wikipedia ) Graph Coloring
Week 14 Dec 2-9 Graph Traversal Algorithms: BFS, DFS Graph Min Spanning Trees (optional) Graph Shortest Path (Dijkstra) Lecture 22 Notes	Slides: Graphs,MST (without class annotations) Slides: Graphs Shortest Path
Part 6: Algorithms for Sorting (Optional)
Recap : Selection Sort, MergeSort Insertion Sort QuickSort Sorting1_Notes (CS5800) Sorting2_Notes (CS5800)	Book Notes: Algorithms Book Notes: Algorithms
Final Sat 12/9 1pm-5pm, SH 425	Cheat Sheet allowed whole time: 4pages (2 sheets) Allowed first 60 min: notes/HWs/other written by you. Must be on paper, no electronic devices. Hand calculators: allowed