Discrete Structures Schedule - Accelerated Section
CS 1800 ACC Fall 2024


Khoury College of Computer and Information Science
Northeastern University

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: VDGJWR) 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 5-17
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/13

HW 1 (Logic) due Mon 9/16

Project 1 : 2-CNF-SAT Due 9/27

WEEK 2 Sep 17-24
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/20

HW 2 (Logic, Proofs) due Mon 9/23

WEEK 3 Sep 24- Oct 1
Modulo Arithmetic
Prime numbers, gcd
Modulo Inverse
Number Theory Notes
Lecture 4 Notes
Lecture 4 Extended Euclid
Chanpter 5
BookNotes: Modulo Arithmetic
BookNotes: Modulo Properties

BookNotes: GCD, Euclid



Proof: divisibility with 3



Recitation 3 (Modulo) due Fri

HW 3 (Modulo) due Tue 9/30

WEEK 4 Oct 1-8
Number Theory
Modulo Inverse
Number Theory Part 4
RSA Cryptography
Lecture 5 Notes
BookNotes: Ext-Euclid, RSA

Recitation 4 (Number Theory) due Fri

Project 2 : Square Game
Due 10 / 29

WEEK 5 Oct 8-15
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
Geometric Progression, binary base

Binary card trick

Card trick explained with decimal cards
Teams Stream Recitation 5 (Binary) due Fri

HW 4 (Binary) due Mon 10/14

WEEK 5-6 Oct 8-15
Hexadecimal and Octal
Negative Numbers, Two's Complement

Bitwise Operations
Radix Sort
Sum Rule: Independent possibilities vs representation
Notes OH

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 Oct 8-15
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
Induction Handout




Teams Stream
Recitation 6 (induction) due Fri

HW 5 induction due Mon 10/21

WEEK 7 Oct 22-29

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

HW 6 induction due Mon 10/28

WEEK 7-8 Oct 22-29
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 29- Nov 5
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

HW 7 (sets, counting) due Mon 11/4

Project 3 : Valid Dates
Due
Midterm Fri 11/1, 4 hours in class. time: 3:30-7:30, room:RY 159
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 9 Nov 5- 12

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 midterm (?)






Optional: Counting, Pascal Triangle Formulas and a lot more
Teams Stream
Teams Stream
WEEK 10 Nov 12-19
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

HW 8 (adv counting) due Mon 11/18

Part 4: Probabilities, Random Variables, Expectation, Variance, Entropy
WEKK 11 Nov 19-26
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

HW 9 (probabilities) due Mon 11/26

Week 12 Nov 26- Dec 3
Expectation
Variance
Entropy
Binomial Distribution
Markov Chain
Lecture 13 Notes

Lecture 14 Notes
Thanksgiving Break: no class/OH
Wed - Sun
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

Geometric distribution

Balls-Bins-Coupons podcast

Optional: Law of Large Numbers

Recitation 11 (expectation, var) due Fri

HW 10 (expectation, entropy, graphs) due


Skiplists
BST
Sampling
Skiplists Slides

BST Slides


Skiplists Math

Binary Search Trees (Cormen book)

Sampling Code (Matlab)


Proj 4: Skiplists, BST due

Part 5 : Graphs, Trees, Networks
Week 13-14 Dec 3 - 10
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 13-14 Dec 3-10

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/7 4 hours, in class
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