Discrete Structures Schedule - Honors Section
CS 1800 Fall 2020


Khoury College of Computer and Information Science
Northeastern University

Last Updated: 

This is a detailed schedule for the honors section. See CS1800 Honors Overview
Geneal CS1800 Topics Description/Syllabus, Policies, Instructors, TAs, hours are on NEU Canvas.

SquareGame.jar --> --> --> --> --> --> --> --> --> --> -->
Date Reading/Regular1800 Honors Optional Assignments
Part 1: Numbers, Binary, Logic
Tue Sep 9
Welcome
WELCOME
Website / Canvas
Piazza (https://piazza.com/class/keofe4ymq3h20l )
Staff
Gradescope
Assignments, Exams, Grades
This column includes live honors
lectures from previous years. Use the Chrome Browser for 4k quality.
Honors Problem 1: squares game
Due Fri 10/2 on

Honors-1800-Gradescope (Enroll Entry code: 5VXVKW)

Thu Sep 10 Office Hours (Teams)
Binary Representation
Binary to/from Decimal

Notes 1
Teams Stream
Canvas Module 1
Ch. 1 Introduction
1.1 Binary Representation
1.2 Bytes
1.5 Converting Between Decimal and Binary
BookNotes: binary representation




Teaser: Konigsberg 7 bridges
Teaser: Polygon triangulations
Homework 0 (no credit) PDF
Supplemental Doc
Due Sun 9/20
Mon Sep 14 Office Hours (Teams)
Hexadecimal and Octal
Negative Numbers

Sum Rule: Independent possibilities vs representation
Notes 2
1.3 Hexadecimal Representation
1.4 Octal Representation
1.6 Representing Negative Numbers: Two's Complement

BookNotes: binary operations, hex, octal

addl notes on binary, two complement ( podcast )


Optional: Fast Inverse Square Root
(pdf) (Newton) (code)
Tue Sep 15
Recitation week 2 (WVH102)
Week 1 Recitation Material

Week 1 Recitation Answers
Print this at home, cut the 6 rectangle cards, bring them to class

Binary card trick

Card trick explained with decimal cards
Optional: Other cardtricks

recitation paper due on Gradescope Fri 9/25s 8pm
Thu Sep 17 Office Hours (Teams)
Two's Complement
Binary Search

Bitwise Operations

Notes 3
BookNotes: Two's complement

Representation comparison
Binary search opitmality

Bitwise Operations ( code )

(first part, up to minute 42)

Optional: Fast Inverse Square Root
(pdf) (Newton) (code)
Homework 1
Due Sun 9/27
Mon Sep 21 Office Hours (Teams)
Radix Sort
Bitwise Operations
Logic Gates, Basic circuits
Boolean Algebra
Notes 4
Teams Stream
Canvas Module 2
Chs. 2, 3 Introductions
2.1 Transistors and Switches
2.2 Basic Logic Gates: AND, OR, NOT
BookNotes: simple circuits, boolean algebra
Summary: Binary and Logic
Proof basics

Proof: divisibility with 3


(part 2, after min 42)

Sorting by digits (Radix Sort) (podcast)

Square Game Hint

Tue
Recitation week 2 (WVH102)
Week 2 Recitation Material

Week 2 Recitation Answers
recitation paper due on Gradescope Fri 9/18 8pm
Thu Sep 24 Office Hours (Teams)
Boolean Algebra
Propositional and Predicate Logic
Logic and Proofs
Notes 5a
Notes 5b
Teams Stream
2.4 Binary Arithmetic: Ripple Carry Adders
3.3 Truth Tables
3.4 Logical Equivalence
3.5 Normal Forms
BookNotes: circuits, logic rules

BookNotes: predicate logic

Quantifiers: Negation Rules

Logic basics

Sequence Limit

Homework 2
Due Sun 10/4
Part 2: Sets and Counting
Mon Sep 28 Office Hours (Teams)

Negating Quantifiers
Sets Builder Notation
Union, Intersection, Set Difference
Set Size
Power Set
Notes 6
Canvas Module 3
Ch. 8 Sets
8.1 Set Definition and Examples
8.2 Set Basics
8.3 Set-Builder Notation
8.4 Venn Diagrams
8.5 Set Operations
8.6 Computer Representation of Sets
BookNotes: Sets
Infinite Enumerable Sets : N, Z, Q
Tue Sep 29
Recitation week 3 (WVH102)
Week 3 Recitation Material

Week 3 Recitation Answers
Gabe's java code plays the Sq. Game ( screenshot )
recitation paper due on Gradescope Fri 10/2 8pm
Thu Oct 1 Office Hours (Teams)

Cartesian Product
Product Rule
Union of Disjoint Sets: Sum Rule
Notes 7
Ch. 9 Introduction
9.1 Basic Rules
Count Sets with one-to-one functions

Countable Sets

Homework 3
Due Sun 10/11

Sat Oct 3 Office Hours (Teams) 3pm

HW2
Honors Problem 2
Due Fri 10/23
Mon Oct 5 Office Hours (Teams)
Honors PB2 Union Size: Sum Rule
Inclusion-Exclusion Principle
Pigeon Principle

Notes 8
Teams Stream
Canvas Module 4
9.2 Inclusion-Exclusion Principle
9.3 Pigeonhole Principle
BookNotes: Set Counting
Inclusion-Exclusion Proof
(first part 30 min)

Optional: More on Inclusion-Exclusion
Tue Oct 6
Recitation week 4 (WVH102)
Week 4 Recitation Material

Week 4 Recitation Answers
recitation paper due on Gradescope Fri 9/18 8pm
Honors: Modulo Arithmetic I
Thu Oct 8 Office Hours(Teams)
Number Theory part I
Proofs by contradiction
Inclusion-Exclusion
Honors PB 2

Notes 9
Teams Stream
Chanpter 5
BookNotes: Modulo Arithmetic
BookNotes: Modulo Properties

BookNotes: GCD, Euclid

Proof by Contradiction

Number Theory Part 1 (sections 1-3 or pages 1-10)


Honors Problem 3
Due Fri 11/20
Sat Oct 10 Office Hours (Teams) 3pm

HW3
Homework 4
Due Sun 10/18

Part 3: Counting: Permutations and Combinations, Probabilities
Mon Oct 12 Office Hours (Teams)
Sets vs Sequences
Combinations and Permutations
Pascal Triangle
Counting Problems
Inclusion-Exclusion Theorem
Hon PB2 notes
Canvas Module 5
9.4 Permutations
9.5 Combinations
BookNotes: Counting

Inclusion-Exclusion Proof

Tue Oct 13
Recitation week 5 (WVH102)
Week 5 Recitation Material

Week 5 Recitation Answers
recitation paper due on Gradescope 8pm
Thu Oct 15 Office Hours (Teams)
Balls Into Bins
Binomial Expansion, Theorem
Notes 11
Teams Stream
9.4 Permutations and combinations

9.5 Balls in Bins
BookNotes: Balls in Bins

Summary: Sets and Counting
9.6 Binomial Theorem, Pascal triangle
BookNotes: Binomial Coefficients

Catalan Numbers


Optional: Counting with Generative Functions

Optional: Counting, Pascal Triangle Formulas and a lot more
Homework 5
Due Sun 10/25
Sat Oct 17 Office Hours (Teams) 3pm

HW4
Mon Oct 19 Office Hours (Teams)
Probabilities Spaces, Events
Uniform Probabilities
Non-Uniform Probabilites
Joint anf Conditional Probabilities
Bayes Theorem
Hon-PB2-hint

Teams Stream : HonPb2, Conditional Probabilities

Ch. 10 Introduction
10.1 Definitions and Basic Properties
10.2 (Probability) Examples
10.3 Conditional Probability and Bayes Theorem
BookNotes:Probability Basics
BookNotes:Conditional Probability

Conditional and Joint Examples

Summary: Probabilities
Probababilities (formal math)

Tue Oct 20
Recitation week 6 (WVH102)
Week 6 Recitation :Probabilities

Week 6 Recitation Answers
recitation paper due on Gradescope Fri 8pm
Thu Oct 22 Office Hours (Teams)
Random variables
Expectaion
Variance
Sampling
Notes 12

Teams Stream : HonPb2, Expecataion, HW5

BookNotes: Expectation, Variance, Entropy
Expectation over sum and product
Variance over Sum
Random variables, Expectation, Variance
10.4 Markov Chains
BookNotes: Markov Chain

E[] VAr[] proofs

Optional: Markov Chains (formal)

Optional: Law of Large Numbers

Optional: Binomial Distribution
Homework 6
Due Sun 11/1
Sat Oct 24 Office Hours (Teams) 3pm

HW5
Part 4A: Sequences, Series
Mon Oct 26 Office Hours (Teams)
Random Variables
Expected value

Sampling Code (Matlab)
Tue Oct 27
Recitation week (WVH102)
Week 7 Recitation : Probabilities, Sequeces and Series

Week 7 Recitation Answers
recitation paper due on Gradescope Fri 8pm
Thu Oct 29 Office Hours (Teams)
Sequences and Series
Notes 13
Teams Stream
Canvas Module 7
Ch12: Sequences, Series
BookNotes: Sequences + Series


Harmonic Series
Harmonic Approximation (Calculus)
Homework 7
Due Sun 11/8
Sat Oct 31 Office Hours (Teams) 3pm

HW6
Honors Problem 3
Due Fri 11/20
Midterm Prep,Exam - No HW
Mon Nov 2 Office Hours (Teams)
Advanced Counting
Advanced Probabilities
Notes 14
Teams Stream

BookNotes: Counting Problems

Monty Hall Problem
(podcast)
HW6-PB6-iii solution
Tue Nov 3
Recitation week (WVH102)
Week 8 Recitation : Advanced Counting, Probabilities
Presidential Election Probabilities
U.S. Senate Expectation

Geometric distribution

Inclusion-Exclusion Proof
time=1:26

Balls into Bins - Statistics
(podcast)
Thu Nov 5 Office Hours (Teams)
Notes
Double Counting Mistake
(podcast)

Zika Conditionals (podcast)
Sat Nov7 Office Hours (Teams) 3pm

HW7
Mon Nov 9 Office Hours (Teams)
Midterm Problems
Canvas Module Midterm
Fall 2019 Midterm
15 Problems harder than the miderm

Tue Nov 10
Recitation week 9 (WVH102)
Week 9 : Midterm Recap

Week Recitation Answers
Thu Nov 12 Office Hours (piazza)
Midterm Clarifications Only

Thu Nov 12
MIDTERM EXAM




Part 4B: Induction
Mon 11/16 Office Hours (Teams)
Notes 15
Teams Stream

Canvas Module 7
Ch12: Sequences, Series
Ch13: Induction
BookNotes: Induction part 1
Induction Handout


Homework 8
Due 11/23
Tue 11/17
Recitation week 10 (WVH102)
Week 10 Recitation Material

Week Recitation Answers
recitation paper due on Gradescope 8pm
Thu 11/19 Office Hours (Teams)
Notes-Hon-PB3
Teams Stream
Book Notes: Induction Part 2
Induction Proofs

Sat 11/21 Office Hours (Teams) 3pm

HW8
Tue 11/24
(optional)
Notes-Catalan.pdf
Teams Stream

WVH102 + Teams
11:45AM - 1:25PM
Catalan Numbers
Convex Functions/Applications
(not related to any grade/assignment/exam in CS1800)

FINAL PHASE 1

Due 12/4



Tue 11/24 Office Hours 3PM (Teams)
Additional Induction Problems
Wed-Sun 11/25-29 ThanksGiving Holiday
Part 5: Algorithms, Recurrences, Growth
Mon 11/30 Office Hours (Teams)
Canvas Module 8
11.1 Algorithms for Search
11.2 Analysis of Algorithms

15 Growth of Functions
Intro to Algorithms (prof Gold)
Sorting: Insertion, Bubble, Selection, Merge
Slides: Searching And Sorting

Sorting Animations

Function Growth Notation, Algorithms

Binary Search Trees (Cormen book)

Tue 12/1
Recitation week (WVH102)
Week 9 Recitation Material

Week Recitation Answers
recitation paper due on Gradescope 8pm
Thu 12/3 Office Hours (Teams)
Notes
Solving Recurrences
Recurrences and Induction
Book Notes: Recurrences
Slides : Recurrences


FINAL PHASE 2

Due 12/14



Sat 12/5 Office Hours (Teams) 3pm



Honors Problem 4
Due Thu 12/17 on Honors-1800 Gradescope
Mon 12/7 Office Hours (Teams)
Tue 12/8
(optional)
Sorting, Searching
Teams Stream

WVH102 + Teams
11:45AM - 1:25PM
QuickSort, BucketSort, MergeSort
Binary Search/Sort Trees
(not related to any grade/assignment/exam in CS1800)
Thu 12/10 Office Hours (Teams)
Notes
Part 6: Graphs and Networks
Mon 12/14 Office Hours 6PM(Teams)
Optional : Slides: Graphs Intro, MST
Tue 12/8
(optional)
Thu 12/17 Office Hours 6PM (Teams)
Notes
OPtional
Bipartite Graphs, 2-Coloring ( Wikipedia )

Optional: Graph Coloring