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                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
slides - 4up

Pigeonhole principle
slides - 4up
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
Quiz 7a due Thursday 3/1 - 12 noon.
Thursday
3/1
Reading: 8.3
Exercises:
8.3: 3, 7, 9, 12, 19, 20, 21
Spring Break


8

Combinatorics
permutations and combinations

slides - 4up
Tuesday
3/13
Reading: 8.4
Exercises:
8.4:  1, 4, 7, 11, 21, 32, 34
Thursday
3/15
Exam 2 (chapters 5, 7, 8)


9

Combinatorics
Binomial coefficients; Pascal's triangle
slides - 4up
Tuesday
3/ 20
Reading: 9.1
Exercises:
9.1: 6, 12, 14, 24, 27
Quiz 7b due Tuesday 3/27 - 12 noon.

Problem set 6: Exercises  8.4, 9.1 from last week and
this week due Tuesday 3/27 (Note: problem sets will
be collected at BEGINNING of class from now on)

Thursday
3/22
University closed, classes canceled


10
Combinatorics
Combinations and permutations with repetitions, anagrams
slides - 4up
(continued from last week)
Tuesday
3/27
Reading: 9.2
Exercises:
9.2: 2, 10, 16, 20, 24, 25
Quiz 7c due Thursday 4/5 - 12 noon.
Note: deadline extended

Problem set 7: Exercises 9.2 due Friday 4/6 noon.
Note: deadline extended - hand in at my office Mendel 162C.

Thursday
3/29
Easter Recess


11

Graphs
Graphs: vertices, edges, graph isomorphism, graph representation, subgraphs, paths, cycles, connected graphs, bipartite graphs
slides - 4up

GO Cats!!!!
Tuesday
4/3

No classes this week. Exam 3 rescheduled. Please see note on Piazza
Reading:
12.1, 12.2
Exercises:
12.1: 2, 3, 12, 14, 16, 34, 38
12.2: 2, 3, 4, 12, 21, 26

Problem set 8: Exercises 12.1 and 12.2 due Tuesday 4/10
(Reminder: collected at beginning of class.)

Quiz 8a due Tuesday 4/10 - 12 noon. 
Thursday
4/5


12

Eulerian and Hamiltonian graphs
necessary & sufficient conditions for Euler circuits/trails;
Hamilton cycles;
slides - 4up

Trees
properties of trees: rooted and spanning trees

slides - 4up
Tuesday
4/10
Reading: 12.3, 12.4
Exercises:
12.3: 2, 4, 8, 9, 14, 16, 22
12.4: 2, 4, 6, 16
Problem set 9: Exercises 12.3, 12.4 due Tuesday 4/17
(Reminder: collected at beginning of class.)

Quiz 8b due Thursday 4/12 - 12 noon.
Thursday
4/12
Reading: 13.1, 13.2
Exercises:
13.1: 2, 4, 8, 9, 14, 16, 20
13.2: 2, 4, 6, 16
Quiz 8c due Tuesday 4/17 - 12 noon.


13

Trees (continued)
binary search trees, depth-first/breadth-first trees, minimum spanning trees

slides - 4up
Tuesday
4/17
Reading: 13.3
Exercises:
13.3: 2, 6 & supplementary exercises p522 19, 20
Quiz 9a due Tuesday 4/24 - 12 noon
Problem set 10: Exercises 13.1, 13.2, 13.3 due Tuesday 4/24
(Reminder: collected at beginning of class.)

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


14

Graph Planarity
Planar and non-planar graphs; planar graph regions and Euler's identity; non-planarity results
slides - 4up

Graph Colorability
chromatic number, 4-color theorem, graph coloring (greedy algorithm), applications

slides - 4up
Tuesday
4/24
Reading: 14.1
Exercises 14.1: 1, 4, 6, 10, 12, 14
Quiz 9b due Thurday 4/26 - 12 noon.

Thursday
4/26
Reading: 14.2
Exercises 14.2: : 8, 12, 16, 18
Problem set 11: Exercises 14.1, 14.2 due Thursday 5/3
(Reminder: collected at beginning of class.)

15

End of semester and Exam week:

Office hours:
Tuesday, April 24: Regular Tuesday hours
Wednesday, April 25:  regular  hours canceled
Friday, April 27:  9:30am-11:30am
Monday, April 30:  10:30am-12:30pm
Tuesday, May 1: 1:00-4:00 pm
Wednesday May 2: 12:00-2:00pm
Friday, May 4: 9:00-11:00 am
Tuesday, May 8: 12:00 pm - 2:00 pm
Thursday, May 10: 10:00 am-12:00pm

Tuesday
5/1
No class - (Friday schedule)
Thursday
5/3

Wrap up and review

Dr. Beck's Discrete Structures Summary




Final Exam - Friday, May 11, 11:30am-2:00pm, Mendel 102


Spring 2015