BRONX COMMUNITY COLLEGE
Of the City University of New York
DEPARTMENT
OF
MATHEMATICS
AND COMPUTER SCIENCE
SYLLABUS: CSI
35 DISCRETE MATHEMATICS II
3 credits 4 hours
SYLLABUS: CSI 35 Discrete Mathematics II
PREREQUISITE: CSI 30 & MTH 31, and
ENG 02 and RDL 02, if required.
TEXT: Discrete Mathematics and its Applications Seventh Edition, by
Kenneth H. Rosen,
McGraw Hill, 2012
Objectives: A successful student in
this course
will learn to
1. classify
basic
discrete structures,
2. use graphs and trees as models and tools for studying computational complexity,
3. analyze
finite and infinite structures using
mathematical reasoning and tools of
first order logic,
4. design and analyze algorithms, in particular those based
on recursion and iteration,
5. prove formal statements using
mathematical induction,
6. use
mathematical induction in
verification of
program correctness.
Suggested in-class
examples
Suggested
Homework
Chapter 5: Induction and Recursion (4
weeks)
5.1 Mathematical Induction Examples 1-6,
8, 10, 13-15
p. 329 1,
3, 4, 5, 7, 8, 9, 10,
18, 49, 56
5.2 Strong Induction and Well- Ordering
Examples 1-4 p. 341 1, 3, 4, 12,
5.3 Recursive definitions and
structural induction
Examples 1-10,
12
p. 308 1-9
odd, 18, 23, 25, 34-
36, 44, 47, 48
5.4 Recursive Algorithms Examples 1, 2,
|
Computer projects
|
p. 382
|
1, 4, 5, 8, 9, 11, 12, 13,
|
|
|
|
15
|
|
Computations and explorations
|
p. 383
|
1, 2, 3, 4, 7
|
|
|
3, 5-10
p. 370 1,
2, 3, 7, 21, 44, 45
9.1 Relations and their properties
Chapter 9 Relations (3 weeks)
Examples 1-22 p. 581 1, 3, 5, 10, 27, 33, 35,
42, 43,
44
9.2 n-ary
relations and their
applications
Examples 1-11 p. 589 1-9 odd, 19
9.3 Representing relations All p.
596 1, 3, 13, 18, 20,
31, 32
9.5 Equivalence relations All p.
615 1, 3, 9, 11-16,
21-24,
43, 46, 47
9.6 Partial orderings Examples 1-20 p.
630 1, 3, 4, 5, 9, 11,
13, 15,
19-21, 32, 36
|
Computer projects
|
p. 638
|
1, 2,
3, 4
|
|
Computations and explorations
|
p. 638
|
1, 2, 3, 6, 7
|
Chapter 10 Graphs (3 weeks)
10.l Graphs and graph models All p.
649 1, 3-12 all
10.2 Graph terminology Examples 1-13 p.
665 1, 2, 3, 5, 7, 8, 9,
18-26 all
10.3 Representing Graphs and
Graph Isomorphism
Examples 1-11 p. 675 1-15 odd, 35-43 , odd,
57
10.4 Connectivity Examples 1, 2,
3,
5, 6,7, 13,14
p. 689 1-6,
20, 21
10.5 Euler and
Hamilton paths All p.
703 1-15 odd, 19-23 odd,
31, 33, 35
10.6 Shortest path problems All p.
707 1-13 all
10.8 Graph Coloring Examples 1-4 p.
732 1-11 all, 13,
15
|
Computer projects
|
p. 742
|
1, 2,
3, 4, 5, 17
|
|
Computations and explorations
|
p. 743
|
1, 2, 3, 4, 8, 9, 10, 11
|
Chapter 11
Trees (4 weeks)
|
11.1
|
Introduction to Trees
|
All
|
p. 755
|
1-11
odd, 21, 23
|
|
11.2
|
Applications of
Trees
|
All
|
p. 769
|
1, 3, 5, 19, 21, 23, 25,
|
|
|
|
|
|
37, 40, 42
|
|
11.3
|
Tree Traversal
|
All
|
p. 783
|
1-5, 7-15 all
|
|
11.4
|
Spanning Trees
|
All
|
p. 795
|
1-9 all, 13, 15, 23
|
|
11.5
|
Minimum spanning Trees
|
All
|
p. 802
|
1-9 all
|
Computer projects, computations and
explorations for
chapter 11: there are many relevant projects listed
on page 808; choose those that correspond
to
the material covered
and emphasized in
class.
RK/2003; revised Nov
2003/AW; revised Jan
2007/NEA Updated Jan 2013/AT