CS1800 Discrete Structures: Fall 2012 Schedule

College of Computer and Information Science, Northeastern University

Instructors: Harriet Fell(HF) and Ravi Sundaram(RS)

Last Modified 08/04/2012 18:29:13

Week

Class

Date

Instructor

Topics

Reading

Due

1

1

Sep 05

HF & RS

Overview and Course Organization

Get online homework(OL-HW) account

2

Sep 06

HF

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

 

Sep 07

 

Recitation 1. Number Representations

 

 

 

 

2

3

Sep 10

HF

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

 

Sep 11

 

Recitation 1. Number Representations

 

 

4

Sep 12

HF

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

OL-HW1: Binary, Octal, Hex

5

Sep 13

HF

Logic Gates and Logic, contd.

2.3 More Logic Gates: NAND, NOR, XOR, XNOR

3.1 Truth Values

3.2 Truth Tables

Sep 14

 

Recitation 2. Logic and Logic Gates

 

 

 

3

6

Sep 17

HF

Logic and Logical Equivalence

Basic circuits

3.3 Logical Equivalence

2.4 Binary Arithmetic: Ripple Carry Adders

 

Sep 18

 

Recitation 2. Logic and Logic Gates

 

 

7

Sep 19

HF

Gem 1: Design of a CPU

OL-HW2: Logic, Logic Gates

8

Sep 20

RS

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

Sep 21

 

No Recitation

 

 

 

4

9

Sep 24

RS

Modular Arithmetic

Division Algorithm

Powers Modulo n

4.5 Modular Arithmetic

4.6 Powers mod n

5.1 Divides

5.3 Division

W-HW1: Binary Arithmetic and Logic

 

Sep 25

 

Recitation 3. Modular Arithmetic

 

 

10

Sep 26

RS

Collisions in ciphers and hash functions

Prime Numbers

Prime Number Decomposition

5.2 Primes

 

11

Sep 27

RS

GCD, LCM

Euclid's Algorithm

5.5 Euclid's Algorithm

5.4 Greatest Common Divisor and Least Common Multiple

Sep 28

 

Recitation 3. Modular Arithmetic

OL-HW3: Modular Arithmetic, Linear Encryption

 

 

5

12

Oct 01

RS

Extended Euclid's Algorithm

Secret-sharing and public key cryptosystems

5.6 Extended Euclid's Algorithm

 

Oct 02

 

Recitation 4. Euclid’s Algorithm & PKC

 

OL-HW4: Prime Decomposition, GCD, LCM

13

Oct 03

RS

Gem 2: RSA

14

Oct 04

RS

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

Oct 05

 

Recitation 4. Euclid’s Algorithm & PKC

W-HW2: Modular Arithmetic, Cryptography

 

 

6

Oct 08

 

Columbus Day – NO CLASS

 

Oct 09

 

No Recitation.

Midterm Exam 1: 7:00-8:00 PM in 200 Richards

Chapters 1 through 5, and handouts

Practice Problems for Midterm (with solutions)

 

15

Oct 10

RS

Set Operations

Computer Representation of Sets

 

 

16

Oct 11

RS

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

Oct 12

 

Recitation 5. Sets and Set Operations

 

 

 

7

17

Oct 15

RS

Permutations and combinations

Combinations

7.4 Permutations

7.5 Combinations

Oct 16

 

Recitation 5. Sets and Set Operations

OL-HW5: Sets, Set Operations, Power Set, Cartesian Product

18

Oct 17

RS

More permutations and combinations

Pascal's Triangle

19

Oct 18

RS

Binomial Theorem

7.6 Binomial Theorem

Oct 19

 

Recitation 6. Inclusion-Exclusion & Pigeonhole

 

 

 

8

20

Oct 22

RS

Counting: Problem solving Examples

7.7 Balls in Bins

 

Oct 23

 

Recitation 6. Inclusion-Exclusion & Pigeonhole

 

OL-HW6: Simple Counting, Inclusion-Exclusion, Pigeonhole Principle

21

Oct 24

RS

Counting: More Problem Solving Examples

Ch. 6, 7

22

Oct 25

RS

Gem 3: Polymerase Chain Reaction

Lecture notes

Oct 26

 

Recitation 7. Permutation, Combination

 

 

 

9

23

Oct 29

HF

No Class

Hurricane Sandy

 

Oct 30

 

Recitation 7. Permutation, Combination

 

OL-HW7: Permutations and Combinations

24

Oct 31

HF

Probability Basics

Expectation and independence

Ch. 8 Introduction

8.1 Definitions and Basic Properties

8.2 (Probability) Examples

25

Nov 01

HF

More Probability Examples

Conditional Probability

Chapter 8

Lecture notes

Nov 02

 

Recitation 8. Conditional Probability

 

 

 

10

26

Nov 05

HF

More Conditional Probability

Bayes Law

 

OL-HW8: Probability

 

Nov 06

 

Markov Chains

Matrices

Introduction to Graphs

Ch. 13 Introduction

13.1 Simple Graphs

Lecture notes

 

27

Nov 07

HF

Recitation 8. Conditional Probability

OL-HW9: Conditional Probability and Markov Chains

28

Nov 08

HF

Module 4: Algorithms

Sorting and Searching

9.1 Algorithms for Search

9.2 Analysis of Algorithms

9.3 Algorithms for Sorting

 

Nov 09

 

No Recitation

W-HW3: Probability and Counting

 

 

 

 

Nov 12

 

Veteran’s Day – NO CLASS

 

 

Nov 13

 

No Recitation.

Midterm Exam 2: 7:00-8:30 PM in 200 Richards

Chapters 6 through 8

Practice Problems for Midterm

 

11

29

Nov 14

HF

Sequences and Sums

10.1 Sequences

10.2 Series and Partial Sums

 

30

Nov 15

HF

Proof by Induction

11.1 Specifying Recurrences (Extra Credit)

11.2 Solving Recurrences (Extra Credit)

 

Nov 16

HF

Recitation 9. Induction

 

OL-HW10: Sorting and Searching

 

 

12

31

Nov 19

HF

More Proofs by Induction

Nov 20

 

Recitation 9. Induction

 

Nov 21

 

Thanksgiving Break – NO CLASS

Nov 22

 

Thanksgiving Break – NO CLASS

 

 

Nov 23

 

Thanksgiving Break – NO CLASS

 

 

13

32

Nov 26

HF

Growth of Functions

Ch. 12 Growth of Functions

 

Nov 27

 

No Recitation.

 

 

33

Nov 28

RS

Module 5: Networks

Graph Data Structures and Trees

13.3 Graph Data Structures

13.4 Graph Problems

34

Nov 29

RS

Graph Traversals

13.4 Graph Problems

13.5 Graph Theory

 

Nov 30

 

Recitation 10. Graphs

 

 

14

35

Dec 03

RS

Course recap and MidTerms review

WHW4: Induction and Recurrences

 

Dec 04

 

Recitation 10. Graphs

 

OL-HW11: Graphs

36

Dec 05

RS

Course recap and MidTerms review