CSC 1300: Discrete Structures

Spring 2018

Dr. MaryAngela Papalaskari  Office Hours MSC 162C T: 2:30pm-4:00pm; Wednesdays: 10:30am-12:00pm; and by appointment
Teaching assistants: Kathleen Antaki, Office Hours Mondays 12-3pm; and by appointment
syllabus                blackboard                  piazza             resources       CSC Peer Tutors        exam archive        

Schedule is tentative and materials will be updated frequently. Please bookmark this page and check often.

 Week   
Topic

Date

Reading and Exercises






1
Course introduction, Logic
Notation, basic definitions, logical connectives, tautologies and contradictions
slides - 4up
Tuesday
1/16

Reading: Chapter 0 & Chapter 1, sections 1.1-1.3
Exercises:
1.1: 3, 4, 5
1.2: 1, 2, 4, 8, 9, 15
1.3: 1-6, 8, 23, 25
(these are practice exercises, some answers in back of textbook)
Thursday
1/18
Reading: 1.4-1.5
Exercises:
1.4: 2, 3, 7
1.5: 5, 6, 7, 11
Quiz 1 due Tuesday 1/23 - 12 noon.
Problem Set 1 - due Thursday 1/25 - Solution


2

Sets
Notation, operations on sets, cartesian products, partitions
slides - 4up
Tuesday
1/23

Reading: 2.1, 2.2
Exercises:
2.1: 1, 3, 5,  7, 8, 9, 10,  11, 13, 15,  21, 25
2.2: 1, 6, 9, 11, 12, 13, 15, 16, 18
Quiz 2a due Thursday 1/25 - 12 noon.
Thursday
1/25
Reading: 2.3, 2.4
Exercises:
2.3: 1, 3, 5,  7, 10, 12, 13, 14
2.4: 1, 5, 6, 9, 10
Quiz 2b due Tuesday 1/30 - 12 noon.
Problem Set 2 - due Thursday 2/1 -
Solution


3

Proofs
Quantifiers, types of proofs, 
slides - 4up

mathematical induction
slides - 4up

mathematical induction proof template

Tuesday
1/30
Reading: 3.1, 3.2, 3.3
Exercises:
3.1: 1, 4, 5, 8, 11
3.2: 1, 5, 7, 8, 13, 18
3.3: 2, 4, 11
Quiz 3a due Thursday  2/1 - 12 noon.
Thursday
2/1
Reading: 4.1, 4.2
Exercises:
4.1: 1, 4, 5, 7, 10, 11
4.2: 1, 3, 5, 7, 8, 17
Quiz 3b due Tuesday 2/6 - 12 noon.


4

Proofs (continued)

Tuesday
2/6
Reading: 4.3
Exercises:
4.3: 2, 4  6  9 13 17 21
Thursday
2/8

Exam 1 (chapters 1 - 4)
Quiz 4 due Tuesday 2/13 - 12 noon.
Problem Set 3 - due Thursday 2/15



5

Relations and Functions
Relations, relation representation, properties of relations, equivalence relations
slides - 4up

Functions, one-to-one and onto functions, bijections, compositions of functions, inverse of functions
slides - 4up
Tuesday
2/13
Reading: 5.1, 5.2
Exercises:
5.1: 3, 5, 6, 9, 11
5.2: 1, 3, 5
Quiz 5a due Thursday 2/15 - 12 noon.
Thursday
2/15
Reading: 5.3, 5.4
Exercises:
5.3: 2, 3, 5, 10, 18, 29
5.4: 1, 6, 8, 9, 11, 22, 23, 31, 36
Quiz 5b due Tuesday 2/20 - 12 noon.
Problem Set 4 - due Thursday 2/22



6

Integers modular arithmetic and cryptography
Integer representation, divisibility, modular arithmetic, congruences
slides - 4up

Private key and public key encryption
RSA algorithm
slides - 4up

Khan Academy videos:
modular arithmetic   ---  cryptography
Tuesday
2/20
Reading: 7.1-7.4 & 7.7
Exercises:
7.4: 1,2,6,9,13
7.7: 1,2,5,6,12
Quiz 6a due Thursday 2/22 - 12 noon.
Thursday
2/22
Reading: 7.5 & extra notes
Exercises:
7.5: 1, 2, 3, 4, 5
Quiz 6b due Tuesday 2/27 - 12 noon.
Problem Set 5 - due Thursday 3/1



7

Counting
Sum and product principles; principle of inclusion-exclusion, pigeonhole principle;
Tuesday
2/27
Reading: 8.1, 8.2
Exercises:
8.1: 1,3,4, 7,10, 22, 23
8.2: 1,6, 9, 10, 11, 12
Thursday
3/1
Reading: 8.3
Exercises:
8.3: 3, 7, 9, 12, 19, 20, 21
Spring Break


8

Combinatorics
permutations and combinations; binomial coefficients; Pascal's triangle; combinations and permutations with repetitions.
Tuesday
3/13


Thursday
3/15
Exam 2 (chapters 5, 7, 8)


9

Combinatorics (continued)

Tuesday
3/ 20

Thursday
3/22



10
Graphs
Graphs: vertices, edges, paths, cycles, connected graphs, handshaking lemma;
Eulerian and Hamiltonian graphs

Tuesday
3/27

Thursday
3/29
Easter Recess


11

Graphs (continued)
Tuesday
4/3

Thursday
4/5
  


12

Trees
properties of trees: rooted and spanning trees


Tuesday
4/10

Thursday
4/12
Exam 3 (chapters 9 & 12)


13

Trees (continued)

Graph Planarity


Tuesday
4/17


Thursday
4/19



14

Graph Colorability & applications
Tuesday
4/24

Thursday
4/26


15

Wrap up and review
Tuesday
5/1
No class - (Friday schedule)
Thursday
5/3



Final Exam - Friday, May 11, 11:30am-2:00pm, room TBA

Spring 2015