Discrete Mathematics II

CSI35     D01 (45670)

Monday, Wednesday: 10:00 am - 11:50 am, NI 203

 
-->
Date Materials HW assignment
12/19 FINAL EXAM       9:00 am - 11:50 am       at NI 203  
12/12 Sample Final Exam: finalExam_CSI35-Fall2018ZyBooks_Sample_.pdf  
12/10 Review - Chapter 14

Cheat sheet: ZyBooksFormulasSheet-Trees.pdf, source file: ZyBooksFormulasSheet-Trees.odg
CSI35ZyBooksChapter14Review.pdf

Answers/Solutions: CSI35ZyBooksChapter14Review_answers.pdf
no hw assignment
12/05 Review - Chapter 13

Cheat sheet: ZyBooksFormulasSheet-Graphs.pdf, source file: ZyBooksFormulasSheet-Graphs.odg
CSI35ZyBooksChapter13Review.pdf

Answers/Solutions: CSI35ZyBooksChapter13Review_answers.pdf
no hw assignment
12/03 no meeting, instead:
The Bronx Community College is hosting a visit by a team of scientists, post docs and graduate students from Princeton University.
LOCATION: NL 136
TIME: 10:20 11:30 AM

The scheduled discussion's goal is to facilitate collaboration between BCC and Princeton University students and scientists from the Cooperative Institute for Climate Science (CICS) and their partners Atmospheric and Oceanic Sciences Program and NOAA-Geophysical Fluid Dynamics Laboratory at Princeton University.

Here is the flyer: Students Invite_Dec 3.pdf
 
no hw assignment
11/28 Review - Chapter 12

Cheat sheet: Chapter12 Formulas Sheet, source file: Chapter12FormulasSheet.odg
Chapter12Review (no partitions, no restoration of equiv. relation from partitions, no SQL)

Some answers and solutions: CSI35ZyBooksChapter12Review_answers.pdf
 
no hw assignment
11/26 Review - Chapter 11

Cheat sheet: Chapter11Cheat Sheet source file (Libre Office): Chapter11_cheatSheet.odg
CSI35ZyBooksChapter11Review.pdf (no strong induction, no structural induction)

We worked on questions 1-7, 13, 19, and 20 in class.
Here are some answers/solutions to the reest of the questions: CSI35ZyBooksChapter11Review_q8.pdf, CSI35ZyBooksChapter11Review_q10.pdf, CSI35ZyBooksChapter11Review_someAnswers.pdf, CSI35ZyBooksChapter11Review_q9.pdf, CSI35ZyBooksChapter11Review_q17-1.pdf, CSI35ZyBooksChapter11Review_q17-2.pdf
 
no hw assignment
11/22-23 College is closed. Thanksgiving Break.

 
11/21 topic: Chapter 14
Section 14.6 Minimum Spanning Trees

lecture slides: ZyBooksCSI35_Ch14-Sect6.pdf

practice: ZyBooksCSI35_Ch14-Sect5Practice.pdf
HW 19: due Tuesday, 11/27 - last HW assignment

ZyBooks, HW18:
Chapter 14: Sections 14.6/ all participation and challenge activities as well as additional exercises

Extra practice (not graded, do not submit):
Rosen book:
page 796 / 23,
page 802 / 1, 3, 7, 9
Answers: CSI35_pages 796-802.pdf
11/19 topic: Chapter 14
Section 14.5 Spanning trees and graph traversals (DFS and BFS)

lecture slides: SpanningTrees
practice: ZyBooksCSI35_Ch14-Sect5Practice.pdf

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 18: due Saturday, 11/24, by 11:59pm

ZyBooks, HW18:
Chapter 14: Sections 14.5/ all participation and challenge activities as well as additional exercises

Extra practice (not graded, do not submit):
Rosen book:
pages 795-796 / 3, 11(c,d), 16(for #13 only), 17(b).
Answers: CSI35_pages 795-796.pdf
11/14 topics: Chapter 14
Section 14.2 Tree application examples (more examples)
Section 14.3 Properties of trees
Section 14.4 Tree traversals

lecture slides: TreesPropertiesAndTraversals
practice: see lecture slides + ZyBooksCSI35_Ch14-Sect4Practice.pdf
 
HW 17: due Tuesday, 11/20, by 11:59pm

ZyBooks, HW17:
Chapter 14: Sections 14.3, 14.4/ all participation and challenge activities as well as additional exercises

Extra practice (not graded, do not submit):
Rosen book:
pages 755-756 / 19, 20, 27, 29, 36
Answers: CSI35_pages 755-756.pdf
pages 783-784 / 8, 11, 14, 16, 18, 22, 24
Answers: CSI35_pages 783-784.pdf
11/12 topics: Chapter 14
Section 14.1 Introduction to trees
Section 14.2 Tree application examples

lecture slides: TreesIntro
practice: ZyBooksCSI35_Ch14-Sects1-2InClassPractice.pdf
HW 16: due Saturday, 11/17, by 11:59pm

ZyBooks, HW16:
Chapter 14: Sections 14.1, 14.2/ all participation and challenge activities as well as additional exercises

Extra practice (not graded, do not submit):
Rosen book:
pages 755-756 / 1, 3, 5, 7, 9(b), 11
Answers: CSI35_pages 755-756.pdf
pages 769-770 / 1, 3, 11, 19, 21, 23
Answers: CSI35_pages 769-770.pdf
11/07 topics: Chapter 13
Shortest Paths Problems

lecture slides: ShortestPathsProblems
practice: ZyBooksCSI35_Ch13-AdditionPractice.pdf
Chapter 13 overview (not finished): ZyBooksCSI35_Ch13-Overview.pdf

 
Extra practice (not graded, do not submit):
Rosen book:
page 716-717 / 1, 3, 6, 25
Answers: CSI35_pages716-717.pdf
11/05 topics: Chapter 13
Section 13.8 Planar graphs
Section 13.9 Graph coloring

lecture slides: PlanarGraphsColoring (updated on 11/06)
practice: ZyBooksCSI35_Ch13-Sects8-9Practice.pdf
HW 15: due Saturday, 11/10, by 11:59pm

ZyBooks, HW15:
Chapter 13: Sections 13.8, 13.9/ all participation and challenge activities as well as additional exercises

Extra practice (not graded, do not submit):
Rosen book:
pages 733 / 3, 8, 9, 13, 15, 17
Answers: CSI35_pages 733-734.pdf
10/31 topics: Chapter 13
Section 13.6 Euler circuits and trails
Section 13.7 Hamiltonian cycles and paths

lecture slides: EulerCircuitsTrailsAndHamiltonianCyclesPaths
EulerCircuitsAndPathsInDirectedGraphs

Mohammed's scimitars: Rosen_697.pdf
Grey Codes: Rosen_702-703.pdf

Terminology (ZyBooks -> Rosen):
walk -> path
circuit -> simple circuit
trail -> simple path
cycle -> N/A
path -> N/A

practice: ZyBooksCSI35_Ch13-Sects6-7Practice.pdf

HW 14: due Tuesday, 11/06, by 11:59pm

ZyBooks, HW14:
Chapter 13: Sections 13.6, 13.7/ all participation and challenge activities as well as additional exercises

Extra practice (not graded, do not submit):
Rosen book:
pages 703 - 704 / 1, 7, 10, 13, 21, 2,.
pages 705 - 706 / 32, 33, 34, 40, 47 (a,d),
Answers: CSI35_pages703-704.pdf, CSI35_page706.pdf
10/29 topics: Chapter 13
Section 13.4 Walks, trails, circuits, paths, and cycles
Section 13.5 Graph connectivity

lecture slides: Connectivity
practice: ZyBooksCSI35_Ch13-Sects4-5Practice.pdf

 
HW 13: due Saturday, 11/03, by 11:59pm

ZyBooks, HW13:
Chapter 13: Sections 13.4, 13.5/ all participation and challenge activities as well as additional exercises

Extra practice (not graded, do not submit):
Rosen book:
pages 689-691 / 1, 4, 11(a), 21, 23
Answers: CSI35_pages689-690.pdf

Suggested reading:
Example 3 on page 680
10/24 topic: Chapter 13
Section 13.2 Graph representations
Section 13.3 Graph isomorphism


lecture slides: ZyBooksCSI35_Ch13-Sects2_3.pdf
practice: see lecture slides
HW 12: due Tuesday, 10/30, by 11:59pm

ZyBooks, HW12:
Chapter 13: Sections 13.2-13.3/ all participation and challenge activities as well as additional exercises

Extra practice (not graded, do not submit):
Rosen book: pages 665-666 / 3, 5, 9, 17, 20 (a,b,d,e,f), 21, 23, 27
pages 675-677 / 1, 3, 7, 9(c), 11, 15, 17, 21, 35, 41, 57 (a,b)
Answers: CSI35_HW11_pages 665-666.pdf, CSI35_pages 675-677.pdf

Suggested reading:
Some Applications of Special Types of Graphs (pages 661-663 in the book).
10/22 topic: Chapter 13
Section 13.1 Graphs introduction

lecture slides: GraphsGraphModelsGraphTerminology

Formula/Cheat Sheet: ZyBooksFormulasSheet-Graphs.pdf

Practice: ZyBooksCSI35_Ch13-Sect1_Practice.pdf
HW 11: due Saturday, 10/27, by 11:59pm

ZyBooks, HW11:
Chapter 13: Section 13.1/ all participation and challenge activities as well as additional exercises

Extra practice (not graded, do not submit):
Rosen book: pages 650-651 / 3, 5, 7, 11, 13, 33
Solutions: CSI35_pages 650-651.pdf

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

The exam is closed book, closed notes, but you can use two pages of cheat sheets.

will be based on material from Chapters 11 and 12 (Rosen Book: Chapters 5 and 9)

The Midterm Grade will be composed of:
Hws: 40%
Midterm Exam: 60%

10/15 Preparation for Midterm Exam

Review questions are posted on the Midterm and Final Exam page.

You can also find more information about the Midterm Exam there.

10/10 topics: Chapter 12
Section 12.9 Equivalence relations
Section 12.10 N-ary relations and relational databases

Practice: ZyBooksCSI35_Ch12-Sect9_Practice.pdf

lecture slides: ZyBooksCSI35_Ch12-Sect9_10.pdf
HW10: due Monday, 10/15, by 11:59pm

ZyBooks, HW7:
Chapter 12: Sections 12.9-12.10/ all participation and challenge activities as well as exercises
10/08
Columbus Day
College is closed

10/03 topics: Chapter 12
Section 12.7 Partial orders
Section 12.8 Strict orders and directed acyclic graphs

lecture slides: PartialOrder-StrictOrder-DAGs
HW9: due Tuesday, 10/09, by 11:59pm

ZyBooks, HW7:
Chapter 12: Sections 12.7-12.8/ all participation and challenge activities as well as exercises
10/01 topic: Chapter 12
Section 12.5 Graph powers and the transitive closure,
Section 12.6 Matrix multiplication and graph powers

lecture slides: GraphPowersMatrices (corrected on 10/02 10:20 pm)

in-class practice: will be posted

HW8: due Saturday, 10/06, by 11:59pm

ZyBooks, HW6:
Chapter 12: Sections 12.5-12.6/ all participation and challenge activities as well as exercises
09/26 topics: Chapter 12
Section 12.3 Directed graphs, paths, and cycles
Section 12.4 Composition of relations

lecture slides: DirectedGraphs_Composition (corrected on 09/26 4:15 pm)
HW7: due Tuesday, 10/02, by 11:59pm

ZyBooks, HW7:
Chapter 12: Sections 12.3-12.4/ all participation and challenge activities as well as exercises
09/24 topic: Chapter 12
Section 12.1 Introduction to binary relations,
Section 12.2 Properties of binary relations

lecture slides: RelationsIntro
HW6: due Saturday, 09/29, by 11:59pm

ZyBooks, HW6:
Chapter 12: Sections 12.1-12.2/ all participation and challenge activities as well as exercises

Extra practice (not graded, do not submit):
Rosen book:
pages 581-582 /1 (a-d), 3, 7 (a, e, f), 18, 27, 35 (a,c,e,g)
Solutions: CSI35_HW06_page 581N1.pdf, CSI35_HW06_page 581N3.pdf CSI35_HW06_page 581N7.pdf, CSI35_HW06_page 582N18_27.pdf, CSI35_HW06_page 582N35.pdf
Suggested to look at: Examples 5 and 6 on pages 363-364
09/17 topic: Chapter 11
Section 11.10 Recursive algorithms
Section 11.11 Induction and recursive algorithms
the rest of the sections are optional

lecture slides:Recursive algorithms
practice: recAlgsPractice

No classes are scheduled on Tuesday and Wednesday, September 18-19th (Yom Kippur)
 
HW5: due Sunday, 09/23, by 11:59 pm

ZyBooks, HW5:
Chapter 11: Sections 11.10-11.11/ all participation and challenge activities as well as exercises

Extra practice (not graded, do not submit):
Rosen book:
pages 370-371 / 3, 7, 11, 44
Solutions: CSI35_HW05_page370N3.pdf, CSI35_HW05_page370N7_11.pdf CSI35_HW05_page371N44.pdf

Suggested to look at (not for grade):
Examples 5 and 6 on pages 363-364
09/12 topic: Chapter 11
Section 11.7 Loops invariants
Section 11.8 Recursive definitions
Section 11.9 Structural induction

lecture slides:Recursive definitions and structural induction
practice: recDefsPractice

Greek alphabet letters names: http://www.rapidtables.com/math/symbols/greek_alphabet.htm
HW4: due Wednesday, 09/19, by 11:59 pm

ZyBooks, HW4:
Chapter 11: Sections 11.7-11.9/ all participation and challenge activities as well as exercises

Extra practice (not graded, do not submit):
Rosen book:
pages 357-358 / 3 (c), 5(e), 7(c), 13, 25, 27
Solutions: CSI35_HW04_pages357_358N3_5_7.pdf, CSI35_HW04_page358N13.pdf, CSI35_HW04_page358N25.pdf, CSI35_HW04_page358N27.pdf

Suggested to look at (not for grade):
Ackermann's function: page 359 / 47, 48, 49, 51
09/10 no classes (Rosh Hashanah)
 
 
09/05
Wednesday runs on Monday schedule!

topics: Chapter 11
Section 11.5 Mathematical induction (finishing up)
Section 11.6 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

Recommended additional resources (proofs):
1) Cardinality of a finite powerset (video)
2) a proof that postage of 12 cents or more can be made with just 4c and 3c stamps (strong induction)
3) winning strategy for game NIM (~20 mins, for fun)
HW3: due Tuesday, 09/11, by 11:59 pm

ZyBooks, HW3:
Chapter 11: Sections 11.5 and 11.6/ all participation and challenge activities as well as exercises

Extra practice (not graded, do not submit):
Rosen book:
pages 329-330 / exercises 33, 49, 77,
pages 341-342 / exercises 3, 11
Solutions: CSI35_HW03_page330N33.pdf, CSI35_HW03_page331N49-page333N77.pdf, CSI35_HW03_page341N3.pdf, CSI35_HW03_page342N11.pdf
09/03 College is closed. Labor Day!
 
08/29
topics: Chapter 11
Section 11.4 Mathematical induction


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

Recommended additional resources (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 Tuesday, 09/04, by 11:59 pm

ZyBooks, HW2:
Chapter 11: Section 11.4 / all participation and challenge activities as well as exercises

Extra practice (not graded, do not submit):
Rosen book: pages 329-330 / exercises 1, 5, 11, 19, 23
Solutions: CSI35_HW02_page326N1.pdf, CSI35_HW02_page329N5.pdf, CSI35_HW02_page330N11.pdf, CSI35_HW02_page330N19.pdf, CSI35_HW02_page330N23.pdf
08/27
Welcome to CSI35!

topics: Chapter 11
11.1 Sequences
11.2 Recurrence relations
11.3 Summations


lecture slides: Sequences and Summations
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) The main book for our class is ZyBooks Discrete Mathematics (online book). The HW assignment will be given in this book. The price is $37.
Here are the details on how to subscribe to it:
    1. Sign in or create an account at learn.zybooks.com
    2. Enter zyBook code: CUNYCSI35NovakFall2018
    3. Subscribe
(Subscriptions will last until Jan 12, 2019)

You can also get the Discrete Mathematics and its Applications, Seventh Edition, by Kenneth H. Rosen, McGraw Hill, 2012 and use is as a suplementary textbook.
First chapter of this book is available through e-reserves:
http://bcc-libweb.bcc.cuny.edu/electronic-course-reserves/
    choose CSI35 from the drop-down menu

2) Math and CS club

meets on Thursdays, 12-1:50pm at CP 308 or ME 328
HW1: due Sunday, 09/02, by 11:59 pm

ZyBooks, HW1:
Chapter 11: Sections 11.1 - 11.3 / all participation and challenge activities as well as exercises

Extra practice (not graded, do not submit):
page1, page2, page3 (pdf files)
Solutions: CSI35_HW01_pages1-5.pdf, CSI35_HW01_page6.pdf

Suggested guided exercises for practice
(not graded, 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