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
Grades: PDF of bar chart
Grades: PDF of all spreadsheet data


Instructor: Professor Harry Porter
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


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:

Textbook Photo [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
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 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
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 4

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

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

May 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 7

May 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 8

May 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 9

May 24

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

Week 10

May 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

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.

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.edu
For 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.)


Hints on how to study effectively:
Here is a document I wrote, which you may find useful or interesting:

Professor Porter's Study Tips

Problems / Comments on This Web Page