Discrete Structures Schedule
CS 1800 Spring 2014

College of Computer and Information Science
Northeastern University

Last Updated: 

Week Class Date Topics Reading Due
1 1 Mon, Jan 6th Overview and Course Organization Get an online homework Account
2 Wed, Jan 8th Module 1: Computers and Computing
Binary Representation of Numbers
Converting Between Binary and Decimal
Ch. 1 Introduction
1.1 Binary Representation
1.2 Bytes
1.5 Converting Between Decimal and Binary
3 Thur, Jan 9th Hexadecimal and Octal Representation
Representing Negative Numbers
Two's Complement
1.3 Hexadecimal Representation
1.4 Octal Representation
1.6 Representing Negative Numbers: Two's Complement
Fri, Jan 10th OLHW1: Binary, Octal, Hex
2 4 Mon, Jan 13th Review of Two's Complement
Wrap up of Binary Arithmetic Operations
Basic Logic and Logic Gates
Chs. 2, 3 Introductions
2.1 Transistors and Switches
2.2 Basic Logic Gates: AND, OR, NOT
5 Wed, Jan 15th Logic Gates and Logic, contd. 2.3 More Logic Gates: NAND, NOR, XOR, XNOR
3.1 Truth Values
3.2 Truth Tables
6 Thur, Jan 16th Logic and Logical Equivalence
Basic circuits
3.3 Logical Equivalence
2.4 Binary Arithmetic: Ripple Carry Adders
Fri, Jan 17th OLHW2: Logic, Logic Gates
3 Mon, Jan 20th MLK Day, NO CLASS
7 Wed, Jan 22nd Gem 1: Design of a CPU Lecture notes
Lecture slides
8 Thurs, Jan 23rd Module 2: Encryption
Caesar Shift
Simple Substitution Cipher

Ch. 4 Introduction
4.1 Simple Shift Ciphers
4.2 Encoding
4.3 The mod Function
4.4 Simple Substitution Ciphers
Fri, Jan 24th
4 9 Mon Jan 27th Modular Arithmetic
Division Algorithm
Powers Modulo n
4.5 Modular Arithmetic
4.6 Powers mod n
5.1 Divides
5.3 Division
10 Wed, Jan 29th Prime Numbers
Prime Number Decomposition
5.2 Primes WHW1: Binary Arithmetic and Logic
11 Thurs, Jan 30th GCD, LCM
Euclid's Algorithm
5.5 Euclid's Algorithm
5.4 Greatest Common Divisor and Least Common Multiple
Fri, Jan 31st OLHW3: Modular Arithmetic, Linear Encryption
5 12 Mon, Feb 3rd Extended Euclid's Algorithm
Secret-sharing and public key cryptosystems

5.6 Extended Euclid's Algorithm
13 Wed, Feb 5th Gem 2: RSA Lecture notes
The Mathematical Guts of RSA Encryption
RSA article
14 Thurs, Feb 6th Module 3: Counting
Password Spaces, Sets
Set Builder Notation
Ch. 6 Introduction
6.1 Set Basics
6.2 Set-Builder Notation
6.3 Venn Diagrams
Fri, Feb 7th OLHW4: Prime Decomposition, GCD, LCM
6 15 Mon, Feb 10th Set Operations
Computer Representation of Sets
6.4.1-6.4.4 Set Operations
6.4.5 Power Set
6.4.6 Cartesian Product
6.5 Computer Representation of Sets
16 Wed, Feb 12th Simple Counting
Product and Sum Rules
Inclusion-Exclusion Principle
Pigeonhole Principle
Ch. 7 Introduction
7.1 Basic Rules
7.2 Inclusion-Exclusion Principle
7.3 Pigeonhole Principle
WHW2: Modular Arithmetic, Cryptography
17 Thurs, Feb 13th Review for Midterm 1 Chapters 1 through 5, and handouts

Fri, Feb 14th OLHW5: Sets, Set Operations, Power Set, Cartesian Product
7 Mon Feb 17th President Day, NO CLASS
18 Wed, Feb 19th Midterm Exam 1
19 Thurs, Feb 20th Permutations and combinations
7.4 Permutations
7.5 Combinations
Fri, Feb 21st OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle
8 20 Mon, Feb 24th More permutations and combinations
Pascal's Triangle
21 Wed, Feb 26th Binomial Theorem 7.6 Binomial Theorem
22 Thurs, Feb 27th Balls in Bins 7.7 Balls in Bins
Fri, Feb 28th OLHW7: Permutations and Combinations
Wed, Mar 5th
Thurs, Mar 6th
9 23 Mon, Mar 10th Counting: Problem Solving Examples Ch. 6, 7
24 Wed, Mar 12th Probability Basics
Expectation and independence
Ch. 8 Introduction
8.1 Definitions and Basic Properties
8.2 (Probability) Examples
25 Thurs, Mar 13th More Probability Examples
Fri, Mar 14th
10 26 Mon, Mar 17th Conditional Probability
Bayes Law
8.3 Conditional Probability and Bayes Theorem
27 Wed, Mar 19th Review for Midterm 2 Chapters 6 through 8
OLHW8: Probability
28 Thurs, Mar 20th Midterm Exam 2
Fri, Mar 21st
11 29 Mon, Mar 24th Module 4: Algorithms
Algorithms for Searching
9.1 Algorithms for Search
9.2 Analysis of Algorithms
30 Wed, Mar 26th Algorithms for Sorting
9.3 Algorithms for Sorting
31 Thurs, Mar 27th Sequences 10.1 Sequences

Fri, March 28th OLHW9: Conditional Probability and Markov Chains
12 32 Mon, Mar 31st Sums
Proof by Induction
11.1 Specifying Recurrences
33 Wed, Apr 2nd Simple Recurrences
11.2 Solving Recurrences
WHW3: Probability, Counting and Algorithms
34 Thurs, Apr 3rd Growth of Functions
Ch. 12 Growth of Functions
Fri, Apr 4th OLHW10: Sorting and Searching
13 35 Mon, Apr 7th Module 5: Networks
Graph Data Structures
13.3 Graph Data Structures
13.4 Graph Problems
36 Wed, Apr 9th More Graphs
Graph traversals
13.4 Graph Problems
13.5 Graph Theory
37 Thurs, Apr 10th Graphs Continued
Fri, Apr 11th
14 38 Mon, Apr 14th Wrap up and Review Ch. 1 to 14 WHW4: Graphs and Algorithms
OLHW11: Graphs