Discrete Mathematics II

CSI35     D01 (45960)

Monday: 10:00 am - 11:50 am, NI 211A,
Wednesday, 10:00 am - 11:50 am, BL 104

 
Date Materials HW assignment
04/26 topic: Chapter 11
Section 11.4 Spanning Trees (DFS and BFS)

lecture slides: SpanningTrees - updated around 10:40pm on 04/26
practice: see lectures slides

A short (~2mins) but very nice video of depth first search algorithm application: https://www.youtube.com/watch?v=mE_PCK0oFyo
And Breadth-First Search from the same person and using the same graph:
https://www.youtube.com/watch?v=YYHeXhfwg3g

The next two videos are for the graph that is used in our lecture slides:
Depth-First-Search
Breadth-First Search
HW 19: due Wednesday, 05/03

pages 795-796 / 3, 11(c,d), 16(for #13 only)
04/24 topics: Chapter 11
Section 11.2 Applications of trees (Game trees)
Section 11.3 Tree Traversal

lecture slides: TreesTraversals
practice: Section11.3Practice

Hw 13 answers and solutions: CSI35_HW13_pages689-690.pdf, CSI35_HW13_pages703-704.pdf;
Hw 14 answers and solutions: CSI35_HW14_page706.pdf, CSI35_HW14_pages716-717.pdf;
Hw 15 answers and solutions: CSI35_HW14_page706.pdf.
HW 18: due Monday, 05/01

pages 783-784 / 8, 11, 14, 16, 18, 22, 24
04/20 topics: Chapter 11
Section 11.2 Applications of trees

lecture slides: TreesApplications
practice: see lecture slides
 
HW 17: due Wednesday, 04/26

pages 769-770 / 1, 3, 11, 19, 21, 23
04/19 topics: Chapter 11
Section 11.1 Introduction to trees

lecture slides: TreesIntro - updated on 04/19 at 6:30pm.
practice: see lecture slides
HW 16: due Monday, 04/24

pages 755-756 / 1, 3, 5, 7, 9(b), 11, 19, 20, 27, 29, 36

Suggested reading:
Examples 5, 6 on page 750;
Prove Theorem 4 on page 753;
exercise 23 on page 756.
04/03 topics: Chapter 10
Section 10.8 Graph Coloring

lecture slides: GraphColoring
practice: pages 732-733 / 4, 11, 18

Hw 13 answers and solutions: will be posted shortly

Programming projects for extra credit: CSI35programmingProjects.pdf

 
HW 15: due Wednesday, 04/19

page 733 / 3, 8, 9, 13, 15, 17
04/03 topics: Chapter 10
Section 10.5 Euler and Hamilton Paths
Section 10.6 Shortest-Paths Problems

lecture slides: HamiltonShortestPaths - updated on 04/19 at 6:30pm.
practice: page 705 / 34, pages 716-717 / 2, 26

Hw 12 answers and solutions: CSI35_HW12_pages 675-677.pdf
 
HW 14: due Wednesday, 04/05

pages 705 - 706 / 32, 33, 40, 47 (a,d),
pages 716-717 / 1, 3, 6, 25.

Don't forget to explain your answers!

Suggested reading:
Example 8 on page 702
03/29 topics: Chapter 10
Section 10.4 Connectivity (from page 687)
Section 10.5 Euler and Hamilton Paths

lecture slides: pathsIsomorphismEuler
practice: page 703 / 2, 22, 26

Hw 11 answers and solutions: CSI35_HW11_pages 665-666.pdf
HW 13: due Monday, 04/03

pages 689-691 / 1, 4, 11(a), 21, 23
pages 703 - 704 / 1, 7, 10, 13, 21, 27.

Don't forget to explain your answers!

Suggested reading:
Example 3 on page 680
03/27 topics: Chapter 10
Section 10.3 Representing Graphs and Graph Isomorphism
Section 10.4 Connectivity (only up to page 683, including)

lecture slides: GraphRepresentation_Connectivity
practice: page 676 / 25, 30, 45, 57 (c)

Hw 10 answers and solutions: CSI35_HW10_pages 650-651.pdf
 
HW 12: due Wednesday, 03/29

pages 675-677 / 1, 3, 7, 9(c), 11, 15, 17, 21, 35, 41, 57 (a,b)
Don't forget to explain your answers!

Suggested reading:
Example 3 on page 680
03/22 topic: Chapter 10
Section 10.2 Graph terminology and special types of graphs


lecture slides: GraphTerminology
practice: page 665 / 2, 6, 8, draw K4,5, and 22
HW 11: due Monday, 03/27

pages 665-666 / 3, 5, 9, 17, 20 (a,b,d,e,f), 21, 23, 27

Suggested reading:
Some Applications of Special Types of Graphs (pages 661-663 in the book).
03/20 topic: Chapter 10
Section 10.1 Graphs and graph models


lecture slides: GraphsAndGraphModels


HW 10: due Wednesday, 03/22

pages 650-651 / 3, 5, 7, 11, 13, 33

Suggested to look at:
Biological Neworks(page 648, Examples 11 and 12)
03/15 Midterm Exam

The Midterm Grade will be composed of:
Hws: 40%
Midterm Exam: 60%
 
03/13 Review
Review all nine homeworks!

Sample Midterm: CSI35-MidtermExamSample.pdf (updated on Monday, 03/13 around 9:50am)
Solutions/Answers: CSI35-MidtermExamSampleSolutions.pdf

Solutions to HW8:
page 597 / 21, 27, 31
pages 615-617 / 1, 3,9, 11, 21,23,41, 43, 1

Solutions to HW9:
pages 630-631: 1, 3, 5, 9, 15, 21, 33.
 
 
03/08 topic: Chapter 9
Section 9.5 Equivalence relations (finishing up, from slide 81)
Section 9.6 Partial orderings

lecture slides: Relations3 (will start at slide 81), Relations4
practice: Section 9.5

Solutions to HW7:
pages 589-590 / 1, 5, 7, 13, 17, 19
page 596: 1, 3, 13
HW9: due Monday, 03/13

pages 630-631 / 1 (a,c,e), 3 (c,d), 5 (a,b), 9, 15, 21, 33.

Suggested to look at:
Lexicographical order (pages 620-622)
 
03/06 topic: Chapter 9
Section 9.3 Representing relations (using digraphs)
Section 9.5 Equivalence relations

lecture slides: Relations3 (we stopped at slide 81)
practice: Section 9.3 (updated around 10:30 pm on 03/06), Section 9.5

Solutions to HW6: 1, 3, 7, 18, 27, 35
 
HW8: due Wednesday, 03/08

page 597 / 21 (do only for a from #4), 27, 31, (due 03/08)

pages 615 - 617 / 1(a,b,c), 3 (a,b,c), 9, 11, 21, 23, 41, 43 (a,b), 47 (c,d) (due 03/13)
03/01 topics: Chapter 9
Section 9.2 n-ary relations
Section 9.3 Representing relations (using matrices)

lecture slides: Relations (updated around 4 pm on 03/07, binary multiplication of matrices if fixed)

Solutions to HW5: 3, 7,11, 44
 
HW7: due Monday, 03/06

pages 589-590 /1, 5, 7, 13, 17, 19,

page 596 / 1 (a,c), 3(c), 13
02/27 topic: Chapter 9
Section 9.1 Relations and their properties

lecture slides: RelationsIntro (updated on 02/27 around 6 pm)

Solutions to HW4: 3,5,7, 13, 25, 27
HW6: due Wednesday, 03/01

pages 581-582 /1 (a-d), 3, 7 (a, e, f), 18, 27, 35 (a,c,e,g)

All the answers must be explained !
Answers without explanations get half credit.


Suggested to look at (not for grade):
Examples 5 and 6 on pages 363-364
02/22 topic: Chapter 5
Section 5.4 Recursive algorithms

lecture slides:Recursive algorithms
practice: recAlgsPractice

Solutions to HW3: 33, 49, 77, 3, 11
HW5: due Monday, 02/27

pages 370-371 / 3, 7, 11, 44

Suggested to look at (not for grade):
Examples 5 and 6 on pages 363-364
02/15
NI 211A
topic: Chapter 5
Section 5.3 Recursive definitions and structural induction

lecture slides:Recursive definitions and structural induction
practice: recDefsPractice

solutions to HW1: pages 1-5, page 6
solutions to HW2: 1 , 5, 11, 19, 23.

I found two examples for using math. induction as proof technique for summations. Check 2) and 3) under 02/01

Greek alphabet letters names: http://www.rapidtables.com/math/symbols/greek_alphabet.htm

There will be no classes on Monday, Februrary 20th (President's Day)
HW4: due Wednesday, 02/22

pages 357-358 / 3 (c), 5(e), 7(c), 13, 25, 27

Suggested to look at (not for grade):
Ackermann's function: page 359 / 47, 48, 49, 51
02/13 no classes (Lincoln's birthday)

Look through the:
    1) practice,
    2) suggested video proof 1), and
    3) suggested example
from our 02/08 meeting
 
 
02/08
NI 211A
topics: Chapter 5
Section 5.1 Mathematical induction (finishing up)
Section 5.2 Strong induction and well-ordering (most likely won't cover in class)


lecture slides:Mathematical induction and Strong Induction
practice: 3-cent and 10-cent stamps

Warning: in homework submissions all work must be shown (otherwise no credit given) and no copying (both parties will get a grade of F without opportunity to re-do the homework, upon the first occurence; and if it happens one more time, then the person who copied will be reported to the chairperson)

There will be no classes on Monday, Februrary 13th (Lincoln's Birthday),
and Wednesday 02/15 will run on Monday's schedule.
HW3: due Wednesday, 02/08

pages 329-330 / exercises 33, 49, 77,
pages 341-342 / exercises 3, 11

Suggested video proofs for extra practice
(not for grade, not for submission):
1) a proof that postage of 12 cents or more can be made with just 4c and 3c stamps (strong induction)
2) winning strategy for game NIM (~20 mins, for fun)

Suggested examples from the book
(not for grade, not for submission):
1) Example 2 (page 336)
02/06 class is cancelled  
02/01
BL 104
topics: Chapter 5
Section 5.1 Mathematical induction


lecture slides:Mathematical induction, Part 1 (updated on 02/02)
practice: Practice (Mathematical induction, Part 1)
cheat sheet for Chapter 5 (to be completed later): Chapter5 Cheat Sheet (updated on 02/02)

Video/non-video links:
1) proof of summation 1+2+3+...+n = n(n+1)/2 (video)
2) proof of summation Σni=1 (3i-2)= n(3n-1)/2
3) proof of summation Σni=1 1/(2i-1)(2i+1)= n/(2n+1)
4) justification of geometric sequence partial sum formula (not using induction, worth checking out!)
HW2: due Monday, 02/06

pages 329-330 / exercises 1, 5, 11, 19, 23

01/30
NI 211A
Welcome to CSI35!

topics: Chapter 5
Sequences and Summations


lecture slides: Sequences and Summations (updated on 01/30 at 8pm)
practice: Practice


Video resources from Khan Academy:
1) Sequences (a bunch of short videos and guided practices)
note that you don't need to go over all videos, becuase they cover more than we did in class
2) Sigma notation and summations (a bunch of short videos and guided practices) note that it covers more than we did in class
3) geometric sequence sigma notation
4) Partial sums (consider only first two videos and a guided practice that follows them)

Announcements:
1) First chapter of the book is available through e-reserves:
http://bcc-libweb.bcc.cuny.edu/electronic-course-reserves/
Choose CSI35 from the drop-down menu

2) annual CUNY MATH CONTEST

The contest begins on-line at 9:00 A.M. on Monday, February 15, 2016
more info:
http://math.cisdd.org/
HW1: due Wednesday, 02/01

page1, page2, page3 (pdf files)

Suggested guided exercises for practice
(not for grade, not for submission):
1) arithmetic sequences
2) arithmetic sequences 2
3) geometric sequences
4) geometric sequences 2
5) geometric sequences 3
6) sigma notation
7) summation (arithmetic series)
8) summation (geometric sequence)
9) general summation