CSE 213 Fundations of Computer Science II

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 6 - 9:15 pm, Place: Earth and Space Sci. 079. There is no recitation on Wedn. !!

TA: Bin Tang

bintang@cs.sunysb.edu

Office hours: - 5:00-6:00 pm Monday and Wednesday, CS building 1206

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.

Course Contents and Schedule

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

CSE 213 HOMEWORKS

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) $A_n = \{ x \in R: \ (1+1/n)^n \leq x \leq 3 \}$

(iii) $A_n = \{ x \in R: \ (1+1/n)^n \leq x \leq 3 \}$

5 - Image, Inverse-image

1. Let $f: N \longrightarrow N$ be given by a formula:

FIND: $f(\{3,4,5 \})$ and $f^{-1}(\{ 0, 1,3, 5,6\})$.

2. Let be given by a formula: $f(n) = \{ m \in N: \ \ m < n \}.$

FIND: .

Extra credit 1

(5pts) $f: X \longrightarrow Y$ and for all $t \in T$, $A_t \subset X$. Prove:

6 - Equivalence, Partitions

Page 174: 3, 4, 7, 9, 10.

7 - Equivalence

Let and $\approx$ be a relation defined on the family ${\cal P}(X)$ of all subsets of the set X defined as follows. For any $A,B \in {\cal P}(X)$

$A \approx B$ iff $\char93 A = \char93 B$,

where $\char93 C$ denotes the number of lements of the set C, for every $C \in {\cal P}(X)$.

Find all equivalence classes of $\approx$.

8 - Equivalence

Prove that in the set there is no equivalence relation having as its equivalence classes the sets: , $\{ x \in R: \ 1 \leq x < 3/2 \}$, $\{ x \in R: \ 1 \leq x \leq 2 \}$.

9 - Equivalence

Let X be a set at all sequences of the lenght 3 build up from elements 0 and 1. We define $\equiv$ on X as follows:

$a_1, a_2, a_3 \ \approx \ b_1, b_2, b_3$ iff a_i =b_i for an odd number of subscripts i = 1,2,3.

Prove that $\approx$ is an equivalence relation and describe its equivalence classes.

Extra credit 2

(5pts) Let $X \not= \emptyset$ be a fixed set and let $a \in X$ be a fixed element of X. We define a relation $\approx$ on the family ${\cal P}(X)$ as follows: for any $A,B \in {\cal P}(X)$

Prove that $\approx$ 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 $\leq$ is defined as follows: for any $m,n \in A,$

$n \leq n$ 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 $glb\{3,9\}, \ \ lub\{ 10, 20\}$.

(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) $(N, \leq)$ has 2 Max and 3 Min elements.

(ii) $(N, \leq)$ has $\aleph _0$ Max and $\aleph _0$ Min elements.

(iii) $(N, \leq)$ 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, $\aleph _0$, 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.

Quizzes and Tests Schedule

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.