## Computing and Information Technology Interactive Digital Educational Library

 Please use this identifier to cite or link to this item: http://hdl.handle.net/10117/5454

 Title: Fundations of Computer Science II Authors: Issue Date: Publisher: Citation: http://www.ug.cs.sunysb.edu/~cse213/syllabus.html Abstract: next up previous Next: About this document ... 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 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. 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) (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 ai =bi 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. * About this document ... next up previous Next: About this document ... bin tang 2000-07-11 URI: http://www.citidel.org/handle/10117/5454 Appears in Collections: Syllabus

Files in This Item:

File SizeFormat
95-syllabus.html17KbHTMLView/Open