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
03/22 topic: Chapter 10
Section 10.2 Graph terminology and special types of graphs


lecture slides: GraphTerminology
practice: will be given on the board

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