﻿ CS 1800 Discrete Structures

## CS 1800 Discrete Structures: Spring 2013 Schedule

#### College of Computer and Information Science, Northeastern University

Mon Jan 7
Overview and Course Organization
Wed Jan 9
Module 1: Computers and Computing
Binary Representation of Numbers
Converting Between Binary and Decimal
Ch. 1 Introduction
1.1 Binary Representation
1.5 Converting Between Decimal and Binary
Book: Chapter 1 Exercises

OLHW1: Binary, Octal, Hex
Thu Jan 10
Representing Negative Numbers
Two's Complement
1.2 Bytes
1.4 Octal Representation
1.6 Representing Negative Numbers: Two's Complement

Mon Jan 14
Wrap-up of Number Representations
Logic Gates and Circuits
Ch. 2 Introduction
2.2 Basic Logic Gates: AND, OR, NOT
2.3 More Logic Gates: NAND, NOR, XOR, XNOR
Book: Chapter 2 Exercises
Book: Chapter 3 Exercises

OLHW2: Logic, Logic Gates
Wed Jan 16
Logical Completeness
Logic Gates and Circuits, contd.
2.4 Binary Arithmetic: Ripple Carry Adders
Thu Jan 17
Logic and Logical Equivalence
Ch. 3 Introduction
3.1 Truth Values
3.2 Truth Tables
3.3 Logical Equivalence

Mon Jan 21
Martin Luther King Jr.'s Birthday observed, no classes
Wed Jan 23
Laws of Logical Equivalence
Logic Wrap-up
Module 2: Cryptography
Shift Ciphers
Ch. 4 Introduction
4.1 Simple Shift Ciphers
4.2 Encoding
4.3 The mod Function
Book: Chapter 4 Exercises

OLHW3: Modular Arithmetic, Linear Encryption
Thu Jan 24
Simple Substitution Ciphers
Modular Arithmetic
4.4 Simple Substitution Ciphers
4.5 Modular Arithmetic

Mon Jan 28
Powers Modulo n
Prime Numbers
Prime Number Decomposition
4.6 Powers mod n
5.1 Divides
5.2 Primes
5.3 Division
Book: Chapter 5 Exercises

OLHW4: Prime Decomposition, GCD, LCM
Wed Jan 30
GCD, LCM
Euclidean Algorithm
Extended Euclidean Algorithm
5.4 Greatest Common Divisor and Least Common Multiple
5.5 Euclidean Algorithm
5.6 Extended Euclidean Algorithm
Thu Jan 31
Multiplicative Inverse
Linear Ciphers
Public-Key Cryptography

Mon Feb 4
Review for Test 1
Chapters 1 to 5
Wed Feb 6
Test 1
Thu Feb 7
Module 3: Combinatorics
Sets
Ch. 6 Introduction
6.1 Set Basics
6.2 Set-Builder Notation
6.3 Venn Diagrams
6.4.1-6.4.5 Set Operations

Mon Feb 11
Sets (Continued)
6.4.6 Power Set
6.4.7 Cartesian Product
6.5 Computer Representation of Sets
Book: Chapter 6 Exercises

OLHW5: Sets, Set Operations, Power Set, Cartesian Product
Wed Feb 13
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
Thu Feb 14
Permutations
Combinations
7.4 Permutations
7.5 Combinations

Mon Feb 18
Presidents' Day, no classes
Wed Feb 20
Pascal's Triangle
Binomial Theorem
Balls in Bins
7.6 Binomial Theorem
7.7 Balls in Bins
Book: Chapter 7 Exercises

OLHW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle

OLHW7: Permutations and Combinations
Thu Feb 21
Probability Basics
Division of Stakes
Ch. 8 Introduction
8.1 Definitions and Basic Properties
8.2 (Probability) Examples

Mon Feb 25
More Probability Basics
Conditional Probability
8.3 Conditional Probability and Bayes Theorem
Book: Chapter 8 Exercises

OLHW8: Probability

OLHW9: Conditional Probability
Wed Feb 27
Bayes Theorem
Monty Hall Problem
Thu Feb 28
Pancakes Problem
Puppies Problem ("Two Boys")

Mon Mar 4
Spring Break – NO CLASS
Wed Mar 6
Spring Break – NO CLASS
Thu Mar 7
Spring Break – NO CLASS

Mon Mar 11
Expectation
Wed Mar 13
Review for Test 2
Chapters 6 to 8
Thu Mar 14
Test 2

Mon Mar 18
Module 4: Algorithmic Analysis
Searching and Analysis
9.1 Algorithms for Search
9.2 Analysis of Algorithms
Book: Chapter 9 Exercises

OLHW10: Sorting and Searching
Wed Mar 20
Sorting
9.3 Algorithms for Sorting
Thu Mar 21
Sequences
10.1 Sequences

Mon Mar 25
Sums
10.2 Series and Partial Sums
Book: Chapter 10 Exercises
Book: Chapter 11 Exercises

OLHW11: Sequences and Summations
Wed Mar 27
Recurrences
Proof by Induction
11.1 Specifying Recurrences
11.2 Solving Recurrences
Thu Mar 28
Sorting Analysis
Growth of Functions
Ch. 12 Growth of Functions

Mon Apr 1
Module 5: Networks
Graphs
Ch. 13 Introduction
13.1 Simple Graphs
13.3 Graph Data Structures
Book: Chapter 13 Exercises

OLHW12: Graphs
Wed Apr 3
Graph Problems
13.4 Graph Problems
Thu Apr 4
More Graphs
13.4 Graph Problems
13.5 Graph Theory

Mon Apr 8
Module 6: Relations
Relations
Ch. 14 Introduction
14.1 Examples
14.2 Properties of Relations
14.3 Equivalence Relations
Wed Apr 10
Review for Test 3
Chapters 9 to 14
Thu Apr 11
Test 3

Mon Apr 15
Patriots' Day, no exams or classes
Wed Apr 17
Wrap-up and review
Chapters 1 to 14
OLHW13: Review

Tue Apr 23
FINAL EXAM
﻿﻿﻿﻿