
CITIDEL >
Syllabus Collection >
Syllabus >
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
email 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 email 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 inclass 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) Midterm test  (total 100p). The test will be given TUESDAY, AUGUST 1. covers Hmks 12, 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. 131176).
Chapter 4
Loop invariants. Induction and recursion. Recursive definitions. Review and new problems. (pp. 187  213, 225246)
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
MIDTERM TEST
Covers homeworks 1 and 2 (with PHP). TUESDAY, AUGUST 1.
Chapter 11
Predicate Logic (pp.589599)
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 545579, 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, Inverseimage
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
20000711 
URI:  http://www.citidel.org/handle/10117/5454 
Appears in Collections:  Syllabus

Files in This Item:
File 
Size  Format 
95syllabus.html  17Kb  HTML  View/Open 

All items in DSpace are protected by copyright, with all rights reserved.
