**Professor Anita Wasilewska **

**Meets**- Tuesday, Thursday
6 pm 9:15 pm
**Place**- Old Eng. 145
**Professor Anita Wasilewska**-
e-mail adress: anita@cs.sunysb.edu, Office phone number: 632 8458, Office location: Computer Science Department building, office 1428.

**Office Hours**- will be held in Computer Science Department building, office 1428.
one hour before and half an hour after the class and by appointments.
Please e-mail or call Professor only in emergency cases.
**Recitations**- Monday or Wednesday - 6 - 9:15 pm, Place:
Earth and Space Sci. 079.
- time depends on
your recitation section.
**TA: Bin Tang**- bintang@cs.sunysb.edu
Office hours: - to be announced

**Textbook**-
DISCRETE MATHEMATICS
K.A. Ross, Ch.R.B. Wright

Prentice Hall, 1999 (Fourth Edition)

I will also put on the reserve shelf in the LIBRARY some lecture notes, sets of problems, and homeworks solutions.

**Grading**- The consistency of your efforts and work is the most important
for this course.
**None of the grades will be curved.**- There will be 4 homeworks and 4 QUIZZES (25pts each),
1 in-class test (100 pts)
and a final examination (200pts).
- During the semester you can earn 400pts or more (in the case
of extra points).
**Final grade computation**The grade will be determine in the folllowing way:

# of earned points divided by 4 = % grade.

The % grade which is translated into letter grade in a standard way i.e.

100 - 90 % is A range, 89 - 80 % is B range, 79 - 70 % is C range, 69 - 60 % is D range and F is below 60%.

**Homeworks**- There will be
FOUR (4) homework assignments. Look below for the homework schedule.
None of them will be collected or graded. You are responsable
for solving the problems and checking
if your solutions are correct by comparing them
with the posted solutions. The solutions
of homework problems will be discussed during the recitations and
posted in the CS library.
You homework knowledge will be tested by the quizzes.
**Quizzes**- There will be FOUR in class QUIZZES.
The quizzes will cover homework problems. Each quiz will
contain 2 or 3 problems. They will be a very slight alternation
of homework problems. The goal of these quizzes is to check
your undersdanding of homework solutions.
Ask TAs during ther recitations and their office hours if
you can't solve a problem or don't undersdand a solution.
**Test**- ONE (1) Mid-term test - (total 100p). The test will be given TUESDAY, AUGUST 1. covers Hmks 1-2, in class. It will take only HALF of the class time.
**Final**- Final examination - (total 200p). The final will be given the last day of classes ( August 17) and will last the whole period of 3 hours.

The course will follow the book very closely and in particular we will cover the following chapters and subjects.

**WEEK #1****Chapter 1**- Sets, sequences and functions. Image and Inverse Image.
Indexed Families of sets.
(pp. 1 - 57)

Some of it a review material, some new. **Chapter 2**- Propositional Logic - this is a review READING assignment.
(pp 69 -120). You can use any other book.
We will USE it, but I will not give a
homework on it.
(pp. 166- 176 ).
**Chapter 3**- PART ONE: Equivalence relation and partitions.
**WEEK #2****QUIZ 1**- Covers Homework #1
**Tuesday, July 18.** **Chapter 3**- PART TWO: Operations defined in a set. Congruences. Division algorithm.
Congruences modulo p.
*Z*(*p*). Addition and multiplication in finite sets - Arithmetic Modulo p. (pp. 131-176). **Chapter 4**- Loop invariants. Induction and recursion.
Recursive definitions.
Review and new problems.
(pp. 187 - 213, 225-246)
**Chapter 7**-
General Recursion. Recursive definition of a set.
(pp. 391- 403.)
**WEEK # 3****QUIZ 2**- Covers Homework #2 (without PHP)
**Tuesday, July 25.** **Chapter 5**- Counting finite sets.
Counting functions and sequences.
Pigeon Hole Principle.
(pp. 263- 274)
**Review**- TEST covers Hmks 1 and 2 (with PHP).
**WEEK #4****MID-TERM TEST**- Covers homeworks 1 and 2 (with PHP).
TUESDAY, AUGUST 1.
**Chapter 11**- Predicate Logic (pp.589-599)
**Extra Credit**- Logic homework.
Finite and infinite sets. (pp. 607 -617) Counable, uncountable. Cardinal numbers and Cantor Theoerm.

**WEEK # 5****QUIZ 3**- Covers Homework #3
**Tuesday, August 8.** **Chapters 9, 10**-
Partially ordered sets,
Max, min elements. Chains, Trees, Binary trees, Lattices, Boolean Algebras
as Posets. Properties of General relations.
(pp 545-579, 499- 511)
**WEEK #6****QUIZ 4**- Covers Homework #4
**Tuesday, August 15.** **Review for FINAL****FINAL AUGUST 17**

**HOMEWORK #1, Q1**-
**Tuesday, July 18.** **1 - Sets**-
Page 28, Problems: 7, 9, 10.

Page 38, 6, 10, 12e,f. **2 - Sums**- Page 54. Problems: 7, 9b.
**3 - Functions**- Page 47, 3, 4, 7, 10, 13c, 15. Page 63: 1,2, 11, 12.
**4 - Family of sets**- Find
for

(i)

(ii)

(iii)

**5 - Image, Inverse-image**- 1. Let
be given by a formula:

FIND: and .

2. Let be given by a formula:

FIND: .

**Extra credit 1**- (5pts)
and
for all ,
.
Prove:

**6 - Equivalence, Partitions**-
Page 174: 3, 4, 7, 9, 10.
**7 - Equivalence**- Let
and
be a relation
defined
on the family
of all subsets of the set
*X*defined as follows. For anyiff ,

where denotes the number of lements of the set C, for every .

Find all equivalence classes of .

**8 - Equivalence**- Prove that in the set
there is no equivalence
relation having as its equivalence classes the sets:
,
,
.
**9 - Equivalence**- Let
*X*be a set at all sequences of the lenght 3 build up from elements 0 and 1. We define on*X*as follows:iff

*a*_{i}=*b*_{i}for an odd number of subscripts*i*= 1,2,3.Prove that is an equivalence relation and describe its equivalence classes.

**Extra credit 2**- (5pts) Let
be a fixed set and
let
be a fixed element of
*X*. We define a relation on the family as follows: for any

Prove that is an equivalence relation and describe its equivalence classes.

**HOMEWORK #2, Q2**-
**Oct. 12**

**1**- CONGRUENCES and Z(p): Page 183. 6, 8, 10a -c, 11, 12, 14.
**2**- LOOP INVARIANTS; Page 196. 7, 13, 22.
**3**- INDUCTION/RECURSION: Page 208. 2, 9, 10, 11, Page 232, 10, 11, 16.
Page 244. 2, 5 ,7. Page 250: 6, 8, 11.
**4**- GENERAL RECURSION: Page 400 . 3, 4, 5, 15, 17a.

**1**- COUNTING and PIGEON HOLE: page 316.
1, 2, 3, 4, 5, 6.

**HOMEWORK #3, Q3**-
**Nov. 23**

**1**- PREDICATE LOGIC: Page 596: 2, 3, 4, 5, 9, 10, 18. Page 604. 4, 6, 8, 9 PLUS HANDOUT homework.
**4**- INFINITE SETS: Page 683. 1, 2, 3, 6, 9, 11, 12, 13.

**HOMEWORK #4, Q4**-
**Dec. 7**

**1**- POSETS, LATTICES: Page 555. 1, 3, 4, 4, 10, 13, 16, 17, 18, 20.
**2**- CHAINS, SPECIAL ORDERS Page 565. 1, 3, 9.
**4**- Let
be a poset such that
and
is defined as follows: for any
iff m is DIVISIBLE by n.

(i) Draw a DIAGRAM of the poset .

(ii) List all Max, Min, Largest and Smallest elements in (if exist).

(iii) Find .

(iv) Determine whether is/is not a lattice, is/is not a distributive lattice.

**5**- Order the set
*N*of natural numbers (you can do it by drawing a diagram) in such a way that(i) has 2 Max and 3 Min elements.

(ii) has Max and Min elements.

(iii) has exactly ONE Max element but does not have a Largest element.

**6**- (EXTRA CREDIT 5 pts)
Give examples of Boolean Algebras with 4, 8,
,
and continuum elements.

**OLD Book pages****1**- POSETS, LATTICES: Page 539. 1, 3, 4, 10, 13, 17, 18, 20.
**2**- Page 550. 1, 3, 9.

**QUIZ 1**- Covers Homework #1
**Tuesday, July 18.** **QUIZ 2**- Covers Homework #2
**Tuesday, July 25.** **Midterm**- TUESDAY, AUGUST 1.
**QUIZ 3**- Covers Homework #3
**Tuesday, August 8.** **QUIZ 4**- Covers Homework #4
**Tuesday, August 15.** **FINAL**- THURSDAY August 17.