CS-340, Spring 2010: 60796 (section: 1)

Grades: PDF of final exam and class score

Grades: PDF of bar chart

Grades: PDF of all spreadsheet data

E-Mail: harry@cs.pdx.edu

Web Page: www.cs.pdx.edu/~harry

Short Bio: Click Here

Office space at PSU: Fourth Ave Bldg, room 115-06 (click here for map)

Office hours: Monday, Wednesday, 3:00-4:00 PM, and by appointment

Monday, Wednesday, Noon - 1:50 PM

Fourth Avenue Building, room 150

First Class: Monday, March 29, 2010

Holiday: Monday, May 31, 2010

Class: Monday, April 4, 2010 (Will be taught by Mark Jones)

Class: Wednesday, April 6, 2010 (Will be taught by Creighton Hogg)

Mid-Term Exam #1: Monday, April 19, 2010 (date is tentative)

Mid-Term Exam #2: Wednesday, May 12, 2010 (date is tentative)

Final Exam Time: Thursday, June 10, 2010, 12:30PM - 2:20PM

[photo from Amazon.com]

The textbook will be available through the PSU Bookstore. Amazon carries this book for $84.37 (new). (Amazon Page)

A one-term introduction to discrete structures with applications to computing problems. Topics include sets, relations, functions, counting, graphs, trees, recursion, propositional and predicate logic, proof techniques, Boolean algebra. The course may not be used as part of the degree requirements for the BS degree in Computer Science.

Upon the successful completion of this course students will be able to:

- Describe basic properties of sets, bags, tuples, relations, graphs, trees, and functions.
- Perform traversals of graphs and trees; construct simple functions by composition of known functions; determine whether simple functions are injective, surjective, or bijective.
- Describe the concepts of countable and uncountable sets, and apply the diagonalization method to construct elements that are not in certain countable sets.
- Construct inductive definitions for sets and construct recursive definitions for functions and procedures.
- Determine whether a binary relation is reflexive, symmetric, or transitive and construct closures with respect to these properties.
- Use elementary counting techniques to count simple finite structures that are either ordered or unordered and to count the worst case number of comparisons for simple decision trees.
- Find closed form solutions for simple recurrences using the techniques of substitution, cancellation, and generating functions.
- Demonstrate standard proof techniques and the technique of inductive proof by writing short informal proofs about simple properties of numbers, sets, and ordered structures.
- Apply the properties of propositional calculus to: determine whether a wff is a tautology, a contradiction, or a contingency; construct equivalence proofs; and transform truth functions and wffs into conjunctive normal form and disjunctive normal form.
- Write formal proofs in propositional calculus and first-order predicate calculus.
- Apply the properties of first-order predicate calculus to: determine whether a wff is valid, invalid, satisfiable, or unsatisfiable; construct equivalence proofs; and transform first-order wffs into prenex conjunctive or disjunctive normal form.
- Construct partial correctness proofs of simple imperative programs and construct termination proofs for simple loops.
- Apply algebraic properties of Boolean algebra to simplify Boolean expressions.

- Structures: sets and bags, ordered structures (tuples, lists, strings, products, relations), graphs and trees, functions (constructions, properties), countability.
- Recursion: inductively defined sets, recursively defined functions and procedures.
- Binary Relations: properties, equivalence, partial orders.
- Proof Techniques: direct and indirect proof, mathematical induction, well-founded induction.
- Analysis Techniques: closed forms, counting permutations and combinations, solving recurrences.
- Logic: propositional calculus, formal reasoning, first-order predicate calculus, equivalence, quantifier inference rules, program correctness.
- Boolean Algebra.

The official course prerequisites are:

CS 163: Data Structures Math 252: Calculus IIThis course assumes a basic understanding of the concepts of computer science and programming, although there will be no programming in this class. The concepts of calculus are somewhat tangential to the material in this class. A familiarity with mathematical thinking, terminology, and concepts is required, although this class will not use calculus directly.

It is the student's responsibility to ensure that he/she has the appropriate background before attempting this class.

## Week 1March 29 |
Proofs Reading: Section 1.1 Lecture notes Practice exercises: 1, 3ae, 4ac, 6a, 7a, 8a Sets Reading: Section 1.2 Lecture notes Practice exercises: 1ae, 2ac, 3aceg, 6ace, 7a, 8a, 10ac, 11ac, 16ac, 19ace, 23e, 28ac Ordered Structures Reading: Section 1.3 Lecture notes Practice exercises: 1, 2ace, 4ac, 5ac, 8ace, 9ace, 10ace, 11a, 12ac, 13ace, 14ac, 16a, 17c, 18c Graphs and Trees Reading: Section 1.4 Lecture notes Practice exercises: 2, 4ac, 5ab, 7ab, 8, 9, 11 Homework 1 |

## Week 2April 5 |
Functions: Definitions and Intro Reading: Section 2.1 Lecture notes (not online) Practice exercises: 1ac, 2ace, 3ac, 4ac, 5, 6ac, 7ac, 11ac, 12ac, 13ac, 14a, 15e, 18a, 19c Constructing Functions Reading: Section 2.2 Lecture notes (not online) Practice exercises: 1aceg, 2ac, 3ac, 4a, 6, 7a, 8a, 9ace, 11a Properties of Functions Reading: Section 2.3 Lecture notes (not online) Practice exercises: 1, 2ac, 3a, 4ace, 5ace, 6ac, 7ac, 8a, 9aceg, 10a, 11ac, 12ac, 13ac, 15ac Homework 2 |

## Week 3April 12 |
Countability Reading: Section 2.4 Lecture notes Practice exercises: 1ac, 2aceg, 3ac, 4ac Inductively Defined Sets Reading: Section 3.1 Lecture notes Practice exercises: 1a, 2ace, 3a, 4a, 6aceg, 7ac, 9a, 10ace, 11a, 13, 15, 16a, 17a, 18ac Recursive Functions and Procedures Reading: Section 3.2 Lecture notes Practice exercises: 1, 3, 4ace, 5ace, 6ac, 7ace, 10a, 14a, 15ac, 16a,18a, 19ac, 22, 24a Homework 3 |

## Week 4April 19 |
Properties of Binary Relations Reading: Section 4.1 Lecture notes Practice exercises: 1acegi, 2ace, 3a, 4ac, 5ac, 7a, 8a, 9ac, 12ac, 13ac, 15c, 16ab, 22c Homework 4 |

## Week 5April 26 |
Equivalence Relations Reading: Section 4.2 Lecture notes Practice exercises: 1ace, 2ace, 3aceg, 4a, 5a, 7a, 9 Order Relations Reading: Section 4.3 Lecture notes Practice exercises: 1ac, 2ace, 3abc, 5, 7ac, 9, 11, 14ac Inductive Proof Reading: Section 4.4 Lecture notes Practice exercises: 2acegi, 3a, 4a, 7, 10a, 11a, 13, 15, 20 Exam 1 Answer Key |

## Week 6May 3 |
Analyzing Algorithms Reading: Section 5.1 Lecture notes Practice exercises: 1, 2ac, 3 Summations and Closed Forms Reading: Section 5.2 Lecture notes (Read 5.2.1; Skip 5.2.2-5) Practice exercises: 1ac, 2ace, 3ac, 4aceg, 6a, 7a, 8a Permutations and Combinations Reading: Section 5.3 Lecture notes Practice exercises: 1ace, 2ace, 3ace, 4, 5ace, 7, 9 Discrete Probability Reading: Section 5.4 Lecture notes Practice exercises: 1ac, 2ac, 5, 6ac, 7ac, 8ac (Read 5.4.1-4; Skip 5.4.5; Read 5.4.6) Solving Recurrences Reading: Section 5.5 Lecture notes (Read 5.5.1; Skip 5.5.2-3) Comparing Rates of Growth (Not covered) Section 5.6 - Not assigned Lecture notes Homework 5 |

## Week 7May 10 |
Elementary Logic Reading: Section 6.1 Lecture notes Propositional Calculus Reading: Section 6.2 Lecture notes Practice exercises: 1ac, 2a, 3, 5, 7ace, 8aceg, 9ace, 10aceg, 11ace, 12aceg, 13a, 14ace, 15ace Formal Reasoning Reading: Section 6.3 Lecture notes Practice exercises: 1a, 2, 3a, 4, 5acegi, 6aceg, 7acegik, 8a, 9a |

## Week 8May 17 |
First-Order Predicate Logic Reading: Section 7.1 Lecture notes Practice exercises: 1a, 2ace, 3a, 4, 5ac, 6, 7a, 8a, 9a, 10a, 11ace, 12aceg, 13a, 14ac, 16aceg, 17ac Equivalent Formulas Reading: Section 7.2 Lecture notes Practice exercises: 1ace, 2ac, 3ac, 4ace, 5ace, 6a, 7ace, 8aceg, 9a, 10aceg Homework 6 |

## Week 9May 24 |
Formal Proofs in Predicate Calculus Reading: Section 7.3 Lecture notes Practice exercises: 1ace, 2, 3a, 5, 6aceg, 7ace, 8ace |

## Week 10May 31 |
Program Correctness Reading: Section 8.2 Lecture notes Practice exercises: 7, 8a, 9, 13ac, 14ac, 15ac, 16ac, 17ac, 18a Homework 7 |

## Finals Week |
Final Exam --- Thursday, June 10, 2010 --- 12:30PM-2:20PM
Study-Guide-for-Final |

Attendance in class is mandatory. Successful students will arrive on-time, relaxed and full of curiosity.

Attendance will be checked regularly and will count for part of your grade.

Please bring your homework submissions to class; they are due at the beginning of class. I will collect submissions before lecture.

I will not accept submissions after I begin class and late homeworks will not be accepted without prior approval. The reason I am such a stickler about this is that I do not want students to miss lectures because they are trying to finish up a homework. Plan ahead; all due times are "hard."

I will make extensions to deadlines in the case of medical emergencies and business travel if you contact me ahead of time.

I encourage students to freely discuss the material in this class. You may also use the class mailing list to post questions, comments, etc. You should not post solutions to homework problems.

However, you must compose and write all homework and exam material individually. You may not copy or plagiarize.

The exams may test on material covered only in class and/or on material covered only in the reading assignments.

Your grade will be based approximately, as follows. These percentages are tentative and subject to change.

10% - Homeworks 12% - In-class quizzes, class participation 50% - Midterm Exams 30% - Final ExamIncompletes will not be given.

A "MailMan" e-mailing list will be maintained for this class. From time to time I may post notices about the class and hints/comments about assignments. Students are encouraged to send mail to the list, too.

All students should subscribe to this list. Go to the following web page and enter your email address and a password and click "subscribe".

https://mailhost.cecs.pdx.edu/mailman/listinfo/porterclasslist2/The MailMan program will email you a confirmation message. You must reply, but you can simply hit your email "reply" button. After being adding to the mailing list you will get a "welcome" message from me.

To post a message to all the list members, send email to:

PorterClassList2@mailhost.cecs.pdx.eduFor additional documentation, see

staff.imsa.edu/~ckolar/mailman/mailman-userguide-0.1.pdf (pdf, 159 kb)(By the way, if Internet Explorer does not work with MailMan on the Mac, use the "Safari" web browser instead.)

Here is a document I wrote, which you may find useful or interesting:

Professor Porter's Study Tips

- Send email to: harry@cs.pdx.edu
- Harry Porter's Web Page: www.cs.pdx.edu/~harry