Discrete Structures Schedule
CS 1800 Fall 2017

Last Updated:

THIS ISN'T THE CURRENT SEMESTER'S SCHEDULE. Click here for the spring 2018 schedule.

This is the schedule for the non-honors sections. The honors section can find its schedule here.

Lectures are at the following times and places:

• Aslam: 1:35 pm - 2:40 pm MWTh, Ell Hall Auditorium
• Gold: 10:30 - 11:35 am MWTh, Richards 300
• Pavlu (Honors): 9:50 am - 11:30 am TF, Churchill 101

Week Class Date Topics Reading Due
1 1 Sept 6
Overview and Course Organization
2
Sept 7
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
Lecture 2 Notes
Lecture 2 Video

2 3
Sept 11
Representing Negative Numbers
Two's Complement
1.4 Octal Representation
1.6 Representing Negative Numbers: Two's Complement
Lecture 3 Notes
Lecture 3 Video
4
Sept 13
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
Lecture 4 Notes
Lecture 4 Video
5
Sept 14
Logic and Logical Equivalence
Basic circuits
2.4 Binary Arithmetic: Ripple Carry Adders
3.3 Truth Tables
3.4 Logical Equivalence
3.5 Normal Forms
Lecture 5 Notes
Lecture 5 Video

Sept 16

OLHW1

3
6
Sept 18 Propositional and Predicate Logic Logic handout
Lecture 6 Notes
Lecture 6 Video
7
Sept 20
Module 2: Encryption
Caesar Shift
Simple Substitution Cipher
Ch. 5 Introduction
5.1 Simple Shift Ciphers
5.2 Encoding
5.3 The mod Function
5.4 Simple Substitution Ciphers
WHW1: Binary Arithmetic and Logic

Lecture 7 Notes
Lecture 7 Video
8
Sept 21
Proof Methods
Proofs handout Lecture 8 Notes
Lecture 8 Video

Sept 23

OLHW2

4
9
Sept 25
Modular Arithmetic
Division Algorithm
Powers Modulo n
5.5 Modular Arithmetic
5.6 Powers mod n
6.1 Divides
6.3 Division

Lecture 9 Notes
Lecture 9 Video
10
Sept 27
Prime Numbers
Prime Number Decomposition
6.2 Primes
Lecture 10 Notes
Lecture 10 Video
11
Sept 28
GCD, LCM
Euclid's Algorithm
6.4 Greatest Common Divisor and Least Common Multiple
6.5 Euclid's Algorithm

Lecture 11 Notes
Lecture 11 Video

Sept 30

OLHW3

5
12 Oct 2
Extended Euclid's Algorithm
Secret-sharing and public key cryptosystems
6.6 Extended Euclid's Algorithm
6.7 Inverses mod n

Lecture 12 Notes
Lecture 12 Video
13 Oct 4
RSA
Chapter 7 The RSA Cryptosystem
Lecture 13 Notes
Lecture 13 Video
14 Oct 5
Module 3: Counting
Set Builder Notation
Ch. 8 Sets
8.1 Set Definition and Examples
8.2 Set Basics
8.3 Set-Builder Notation
8.4 Venn Diagrams
Lecture 14 Notes
Lecture 14 Video

Oct 6

WHW2: Modular Arithmetic, Cryptography

Oct 7

OLHW4

6
Oct 9 Columbus Day – NO CLASS
15 Oct 11
Set Operations
Computer Representation of Sets
8.5 Set Operations
8.6 Computer Representation of Sets
Lecture 15 Notes
Lecture 15 Video
16 Oct 12
Simple Counting
Product and Sum Rules
Inclusion-Exclusion Principle
Pigeonhole Principle
Ch. 9 Introduction
9.1 Basic Rules
9.2 Inclusion-Exclusion Principle
9.3 Pigeonhole Principle
Lecture 16 Notes
Lecture 16 Video

Oct 14

OLHW5

7 17 Oct 16
Permutations and combinations
9.4 Permutations
9.5 Combinations
Lecture 17 Notes
Lecture 17 Video
18 Oct 18 Binomial Theorem
9.6 Binomial Theorem
Lecture 18 Notes
Lecture 18 Video
19 Oct 19 Balls in Bins
9.7 Balls in Bins
Lecture 19 Notes
Lecture 19 Video

Oct 20

WHW3: Sets and Counting

Oct 21

OLHW6

8 20
Oct 23
Counting: Problem Solving Examples
Ch. 8, 9
Lecture 20 Notes
Lecture 20 Video
Midterm Review Sessions:
Sun 1pm - Pavlu, Behrakis 010
Sun 3pm - Pavlu, Behrakis 010
Mon 6pm - Gold, Behrakis 010
Tue 6pm - Aslam, ISEC 102
21 Oct 25
Probability Basics
Sum and Product Rules
Ch. 10 Introduction
10.1 Definitions and Basic Properties
10.2 (Probability) Examples
Lecture 21 Notes
Lecture 21 Video
Midterm Exam:
For Aslam and Gold: 6:00-8:00 pm
For Pavlu: 6:15-8:15 pm
For Aslam A-N: Richards 200
For Gold and Aslam O-Z: ISEC 102
For Pavlu: Snell Engineering 108
Practice Midterm 1 (Solutions)
Practice Midterm 2 (Solutions)
Practice Midterm 3 (Solutions)
Midterm Solutions
22 Oct 26
More Probability Examples 10.2 (Probability) Examples Lecture 22 Notes
Lecture 22 Video

Oct 28

OLHW7

9 23 Oct 30
Expectation and Variance
Lecture 23 Notes
Lecture 23 Video
24 Nov 1
Entropy
Lecture 24 Notes
Lecture 24 Video

25 Nov 2
Conditional Probability
Bayes Law
10.3 Conditional Probability and Bayes Theorem Lecture 25 Notes
Lecture 25 Video

Nov 4

OLHW8

10 26 Nov 6 Markov Chains and PageRank 10.4 Markov Chains
10.5 PageRank
Lecture 26 Notes
Lecture 26 Video
27 Nov 8
Module 4: Algorithms
Algorithms for Searching
11.1 Algorithms for Search
11.2 Analysis of Algorithms
Lecture 27 Notes
Lecture 27 Video
28 Nov 9 Algorithms for Sorting 11.3 Algorithms for Sorting Lecture 28 Notes
Lecture 28 Video
WHW4: Probability

Nov 11

11 29 Nov 13
Sequences
12.1 Sequences
Lecture 29 Notes
Lecture 29 Video
30
Nov 15
Sums 12.2 Series and Partial Sums Lecture 30 Notes
Lecture 30 Video
31 Nov 16
Proof by Induction
Ch. 13 Mathematical Induction
Lecture 31 Notes
Lecture 31 Video

Nov 18

OLHW10

12 32 Nov 20
Recurrences
14.1 Specifying Recurrences
14.2 Solving Recurrences
Lecture 32 Notes
Lecture 32 Video
Optional Recitation on Sun 11/19:
1:00pm or 3:00pm in Behrakis 010
Thanksgiving Break - No Class Wed-Fri

13 33 Nov 27
Recurrences and Induction
Ch. 13 Mathematical Induction
Ch. 14 Recurrences
Lecture 33 Notes
Lecture 33 Video
34 Nov 29
Growth of Functions
Ch. 15 Growth of Functions
Lecture 34 Notes
Lecture 34 Video
WHW5: Algorithms, Sums, and Induction

35

Nov 30
Module 5: Networks
Graph Data Structures
Graph Traversal
17.1 Simple Graphs
17.2 Weighted Graphs
17.3 Graph Data Structures
17.4.1 Graph Traversal
Lecture 35 Notes
Lecture 35 Video

Dec 2

OLHW11

14 36 Dec 4
More Graph Algorithms
17.4.2 Any Path
17.4.3 Shortest Path
17.4.4 Cheapest Path
Lecture 36 Notes
Lecture 36 Video
37 Dec 6 Review for Final Exam
Lecture 37 Notes
Lecture 37 Video
WHW6: Recurrences, Growth of Functions, and Graphs

Dec 9

OLHW12

Final Exam: Monday Dec 11 10:30am - 12:30pm
For Aslam: Ell Hall Auditorium
For Gold: Behrakis 010
For Pavlu: Cargill 097
Aslam's Review Session Notes
Practice Exam 1 (Solutions)
Practice Exam 2 (Solutions)
Practice Exam 3 (Solutions)
Final Exam Solutions