CSC 1300: Discrete Structures

Spring 2017

Dr. MaryAngela Papalaskari  Office Hours MSC 162C T: 2:30pm-4:00pm; Wednesdays: 10:30am-12:00pm; and by appointment
Teaching assistants: Andrew Keenan, Office Hours Mendel 292: Mondays, noon-3pm
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.

 Chapter 

Date

Topic
Reading and Exercises
Chapter

1
Tuesday
1/17

Course introduction
Counting, sets, sum & product principles
slides - 4up
Be sure to do all the "Check yourself" exercises  as part of the reading.

Reading: 1.1-1.5
Exercises: Section 1.2
Thursday
1/19
Counting and proofs
Counting subsets; the pigeonhole principle; introduction to mathematical proofs
Exercises 1.7: 1, 2, 3, 11, 12, 16, 17, 19, 20, 21
Problem set 1 - due Thursday 1/26
Quiz 0 (practice - does not count for grade)
Chapter

2

Tuesday
1/24

Sets
Notation, basic definitions, proofs about sets
slides - 4up
Reading: 2.1 & 2.2
Exercises 2.4: 1, 3, 5, 7, 8
Exercises 2.9: 1, 4, 6, 8, 14
Quiz 1 (available now - 8am 1/26/17)
Thursday
1/26
Logic
Notation, basic definitions, logical connectives, quantifiers, types of proofs

Reading: 2.3 & 2.5
Exercises 2.4: 2, 4, 6, 9
Exercises 2.9: 5, 17, 19, 20, 23
Problem set 2 - due Thursday 2/2
Quiz 2 (available 2:30pm 1/26/17 -  8am 1/31/17)
Chapter

2

Tuesday
1/31
Graphs and Functions
Functions: one-to-one, onto, bijections, domain, co-domain
Graphs: vertices, edges, paths, cycles, handshaking lemma

slides - 4up
Reading: 3.1, 3.2, 3.4, 3.5
Excercises: 3.3.1(all), 3.3.2(all)
Quiz 3 (available 2:30pm 1/31/17 -  8am 2/2/17)
Thursday
2/2
Graph and Functions (continued)
Special graphs, subgraphs, complements, bipartite graphs, graph isomorphism
See also - graph isomorphism in the news
Reading: 3.6, 3.7
Exercises 3.8
Exercises 3.13: 1, 3, 5, 6, 8, 10, 13, 14, 20, 24
See also - graph isomorphism resource
Chapter

4

Tuesday
2/7
Exam 1 (chapters 1, 2, 3)






Thursday
2/9
University closed - class is canceled - see note on Piazza
Study CS written on snow
Reading: 4.1, 4.2
Quiz 4a (available until 12pm 2/14/17)
Chapter

4

Tuesday
2/14
Induction
Proof techniques, summation formulas, mathematical induction
slides - 4up
mathematical induction proof template
Reading:  4.4, 4.5
Exercises 4.3: 1, 2, 5
Quiz 4b (available until 12pm 2/16/17)
Thursday
2/16
(induction continued)

Exercises 4.6: 1, 2, 3
Exercises 4.11:  2, 3, 4, 5, 8, 12
Problem set 3- due Thursday 2/23

Chapter

5

Tuesday
2/21
Modular arithmetic and equivalence relations
modular arithmetic, congruences, equivalence relations, equivalence classes, partitions.
slides - 4up

Reading:  5.3
(5.1, 5.2 review algorithms)
Exercises 5.5:  1, 2
Quiz 5a (available until 12pm 2/23/17)
Thursday
2/23
Applications of modular arithmetic to cryptography
shift ciphers, one-time pads, public key cryptography, RSA algorithm, digital signatures
See Piazza for additional links and resources, including spreadsheets and code to experiment with modular arithmetic.
Reading:  5.4 (focus on shift ciphers and supplement with material from slides)
Exercises 5.9: 2, 4, 9, 18, 23
Problem set 4- due Thursday 3/2/17 
Chapter

6

Tuesday
2/28
 Binomial coefficients and Pascal's triangle
Combinations, permutations, Pascal's triangle, combinatorial proofs, binomial theorem
slides - 4up



Reading:  6.1-6.7
Exercises 6.3: 1-4
Exercises 6.6: 1, 2
Quiz 6a (available until 12pm 3/2/17)

Thursday
3/2
(continued - focus on binomial theorem & combinatorial proofs)

Reading:  6.8
Exercises 6.3: 5, 6
Exercises 6.6: 3-6
Exercises 6.9: all
Exercises 6.13: 10, 15, 16, 21
Spring Break
Chapter

7

Tuesday
3/14
University closed - class is canceled - Exam postponed until Thursday 3/16 - see note on Piazza
Study CS written on snow



Thursday
3/16
Exam 2 (chapters 4, 5, 6)
Similar in structure to Exam 1. Although this exam will focus on material from chapters 4-6, it may use concepts from earlier chapters and will include a repeat question from Exam 1.


Chapter

7

Tuesday
3/ 21
Combinatorics I
Counting - review, principle of inclusion-exclusion
slides - 4up

Reading: 7.1, 7.2, 7.5
Quiz 7a (available until 12pm 3/23/17)
Thursday
3/23
Combinatorics II
Counting - permutations and combinations with repetition; stars and bars argument
slides - 4up
Reading:  7.4, 7.6
Exercises 7.6: 1, 2, 3, 5, 6, 7, 8
Exercises 7.9:  1, 2, 3, 5, 6, 7,  9, 11, 13, 14, 16, 17, 22
(also good problems for review: *7.4 check yourself)
Problem set 5- due Tuesday 3/28/17 
Quiz 7b(available until 12pm 3/28/17)
Chapter

8
Tuesday
3/28
Recurrences
Arithmetic and geometric sequences, techniques for finding closed forms of recurrence relations
slides - 4up
Reading:  8.1, 8.2, 8.3, 8.5, 8.6
Quiz 8a(available until 12pm 3/30/17)
Thursday
3/30
Recurrences
continued
slides - 4up
recursive google recursion easter egg
Reading:  8.8
(But this week you only need to do the check yourself exercises listed below)

Check yourself exercises:
Exercises 8.2:  1, 2
Exercises 8.3:  1, 2, 4
Exercises 8.5:  1, 2, 3 (find formula, proof is optional)
Exercises 8.6:  (none, just skim the section)
Exercises 8.8:  1, 2, 4

Exercises 8.9:   1, 7
Exercises 8.12:   1, 3, 7, 8, 9, 14, 17, 18, 19, 25
Problem set 6- due Thursday 4/6/17 
Quiz 8b (available until 12pm 4/4/17)
Chapter

10

Tuesday
4/4
Graph theory - Trees
definitions, examples, spanning trees, minimum weight spanning trees, Prim's and Kruskal's algorithms
slides - 4up
Reading:  10.1-10.4

graph activity - London Tube
Quiz 10A (available until 12pm 4/6/17)
Thursday
4/6
Graph theory - Trees
binary search trees, matchings, backtracking


Reading:  10.5 - 10.8

Check yourself exercises:
Exercises 10.2:  all
Exercises 10.3:  1, 2, 7
Exercises 10.4:  all
Exercises 10.5:  all
Exercises 10.6:  3, 4, 6, 7
Exercises 10.7:  1, 2
Exercises 10.8:  1, 2

Exercises 10.11:   1, 2, 4, 7, 8, 17, 19
Chapter

10

Tuesday
4/11

Exam 3 (chapters 7, 8, 10)
Similar in structure to Exams 1 and 2. Although this exam will focus on material from chapters 7, 8 &10, it may use concepts from earlier chapters (almost surely chapters 3, 4 & 6).

Thursday
4/13
Easter Recess
Chapter

11, 12

Tuesday
4/18
Graph planarity
Planar graphs and faces of the plane, Euler's formula, special non-planar graphs
Planarity game

slides - 4up
Reading:  11.4-11.6
Exercises 11.11:  3, 4, 5, 6, 7, 13

Quiz 11 (available until 12pm 4/20/17)

Thursday
4/20
Graph traversals
Euler circuits/paths; Hamilton circuits/paths
slides - 4up
Reading: 12.1-12.4
Exercises 12.10:  1, 4, 5, 7, 15, (24)
Quiz 12 (available until 12pm 4/25/17)

Problem set 7- due Tuesday 4/25/17 
Chapter

13

Tuesday
4/25
Graph coloring
Vertex coloring; coloring planar graphs; the four color map theorem; applications
slides - 4up
Reading:  13.1-13.5
Exercises 13.8:  3, 8, 9, 14, 15, 16, 19, 22, 23
Quiz 13A (available until 12pm 4/27/17)
Thursday
4/27
Graph coloring
Edge coloring; vertex coloring algorithms revisited
slides - 4up

Quiz 13B (available until 12pm 5/4/17)
*

Tuesday
5/2
No class - (Friday schedule)
Thursday
5/4
Review



Final Exam - Saturday, May 6, 4:15-6:45pm Room TBA

Spring 2015