# CS-340: Discrete Structures for Engineers

## Syllabus - Spring 2010

Course Reference Number:
CS-340, Spring 2010: 60796 (section: 1)
Grades: PDF of final exam and class score

Instructor: Professor Harry Porter
E-Mail: harry@cs.pdx.edu
Web Page: www.cs.pdx.edu/~harry
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

When and Where:
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

Required Textbook:

[photo from Amazon.com]

Discrete Structures, Logic, and Computability (third edition), James L. Hein, Jones and Bartlett, 2009, ISBN-10: 0-7637-7206-2, ISBN-13: 978-0-7637-7206-2.

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

Catalog Description:
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.
Major topics:
• 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.

Prerequisites:
The official course prerequisites are:
```   CS 163: Data Structures
Math 252: Calculus II
```
This 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.

Course Outline:

#### Week 1

March 29

Proofs
Practice exercises: 1, 3ae, 4ac, 6a, 7a, 8a
Sets
Practice exercises: 1ae, 2ac, 3aceg, 6ace, 7a, 8a, 10ac, 11ac, 16ac, 19ace, 23e, 28ac
Ordered Structures
Practice exercises: 1, 2ace, 4ac, 5ac, 8ace, 9ace, 10ace, 11a, 12ac, 13ace, 14ac, 16a, 17c, 18c
Graphs and Trees
Practice exercises: 2, 4ac, 5ab, 7ab, 8, 9, 11
Homework 1

#### Week 2

April 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 3

April 12

Countability
Practice exercises: 1ac, 2aceg, 3ac, 4ac
Inductively Defined Sets
Practice exercises: 1a, 2ace, 3a, 4a, 6aceg, 7ac, 9a, 10ace, 11a, 13, 15, 16a, 17a, 18ac
Recursive Functions and Procedures
Practice exercises: 1, 3, 4ace, 5ace, 6ac, 7ace, 10a, 14a, 15ac, 16a,18a, 19ac, 22, 24a
Homework 3

#### Week 4

April 19

Properties of Binary Relations
Practice exercises: 1acegi, 2ace, 3a, 4ac, 5ac, 7a, 8a, 9ac, 12ac, 13ac, 15c, 16ab, 22c
Homework 4

#### Week 5

April 26

Equivalence Relations
Practice exercises: 1ace, 2ace, 3aceg, 4a, 5a, 7a, 9
Order Relations
Practice exercises: 1ac, 2ace, 3abc, 5, 7ac, 9, 11, 14ac
Inductive Proof
Practice exercises: 2acegi, 3a, 4a, 7, 10a, 11a, 13, 15, 20

#### Week 6

May 3

Analyzing Algorithms
Practice exercises: 1, 2ac, 3
Summations and Closed Forms
Practice exercises: 1ac, 2ace, 3ac, 4aceg, 6a, 7a, 8a
Permutations and Combinations
Practice exercises: 1ace, 2ace, 3ace, 4, 5ace, 7, 9
Discrete Probability
Practice exercises: 1ac, 2ac, 5, 6ac, 7ac, 8ac
Solving Recurrences
Comparing Rates of Growth (Not covered)
Section 5.6 - Not assigned Lecture notes
Homework 5

#### Week 7

May 10

Elementary Logic
Propositional Calculus
Practice exercises: 1ac, 2a, 3, 5, 7ace, 8aceg, 9ace, 10aceg, 11ace, 12aceg, 13a, 14ace, 15ace
Formal Reasoning
Practice exercises: 1a, 2, 3a, 4, 5acegi, 6aceg, 7acegik, 8a, 9a

#### Week 8

May 17

First-Order Predicate Logic
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 9

May 24

Formal Proofs in Predicate Calculus
Practice exercises: 1ace, 2, 3a, 5, 6aceg, 7ace, 8ace

#### Week 10

May 31

Program Correctness
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

Policies:
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 Exam
```
Incompletes will not be given.

Snow Closure: For inclement weather information, call the University switchboard, 725-3000, for a recorded message about university-wide class cancellation. Snow closure info is also available at: www.flashnews.net/pdx.html (click on "View Current Info").

Other Cancellations: If I should need to cancel class for any reason, I will email the class mailing list.

MailMan Mailing List: PorterClassList2
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.

```
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.edu
```
```    staff.imsa.edu/~ckolar/mailman/mailman-userguide-0.1.pdf (pdf, 159 kb)