PSU CS 250: Discrete Structures I

Winter 2016

Instructor: Bart Massey <bart@cs.pdx.edu>
Grader: Luke Kwak <lkwak@pdx.edu>
Time: Tuesday/Thursday 16:40-18:30 (4:40-6:30 PM)
Place: UTS 205
CRN: 45917
URL: http://moodle.svcs.cs.pdx.edu/cs250

As always, this is a tentative syllabus. Everything here is subject to vast change with little notice.

About This Course Offering

This section of this course is the first part of a special offering of CS 250 / CS 251! The course will be taught with a highly non-standard textbook and syllabus. If you complete this section of CS 250 , you must continue in Spring 2016 with the corresponding section of CS 251: otherwise, this course will not be usable toward your PSU CS degree.

About This Course

The catalog says "Introduces discrete structures and techniques for computing", and then goes on to give a long list of tools and methods.

CS 250 is a first course in "Discrete Structures". This is essentially mathematical modeling for computer science. The focus of the course is on learning notations and mathematical tools for describing and understanding algorithms and data.

This is not a software engineering course: there is little computational content. Instead, the course builds a vocabulary and set of tools for solving computational problems before or instead of writing programs.

Course Goals

The catalog says:

CS 250 is the first term of the two term sequence CS 250-251. The main goal of the sequence is that students obtain those skills in discrete mathematics and logic that are used in the study and practice of computer science.

The catalog's list of course goals is that students 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; and classify simple functions by rate of growth.

• 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, construct grammars for languages (sets of strings), 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.

• Construct a topological sort of a partially ordered set and determine whether a partially ordered set is well-founded.

• Use elementary counting techniques to count simple finite structures that are either ordered or unordered, to count the worst case number of comparisons and, with discrete probability, to count the average 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.

This is a lot to do in 10 weeks. We will cover whatever we can get to, plus some stuff normally taught in CS 251: please see the opening section of this syllabus for why this will work for us.

Approach: The Z Specification Notation

In this course, we will tackle the material in a unique way: by learning to use and apply the Z specification notation (pronounced "zed" because of its British ancestry). This notation, developed in the 1970s, is a particular syntax for first-order logic with finite and integral "sorts" (types).

The Z notation has a tiny bit of extra syntax and semantics that makes it easier to apply it to the specification of software. There are also a number of software tools for formatting, checking and proving Z specifications, some of which we will learn to use in this course.

Course Mechanics

This course is a high-effort essential part of the PSU undergraduate CS curriculum. There will be lectures, quizzes, examinations and homework. Anonymous peer review will be a part of the course activity.

Communication

The course website (see above) will be the focus of communication. Please use the website forum as a first resource for discussion and questions: your classmates are most likely the quickest source of best help. Students are encouraged to contact the instructor any time by email for an appointment if there are things that seem worth discussing. The instructor will run office hours as need warrants.

Lectures

The course lectures will cover a variety of topics. Please attend them all; they are required and should be useful.

Readings

The course textbook is

The Way Of Z
Jonathan Jacky, Cambridge Press 1997

This is not the textbook normally used for CS 250 / CS 251 at PSU: please make sure to have the correct textbook. It is not too expensive and will be used extensively: you need to own a copy.

Coursework

There will be many in-class assignments and weekly quizzes. You need to be in class every session. If you cannot make it to class, please contact me in advance of the class meeting. I will advise you on how to deal with the situation.

There will be a midterm examination and a final examination.

Grading

• Homework: 40%
• In-class quizzes: 20%
• Midterm : 20%
• Final: 20%

Due to the size of the course and the volume of material to be covered, late assignments will not be accepted. A grade of 0 may be given to any assignment not turned in on time; failing any one assignment is grounds for failure in the course.

Anonymous peer evaluation will be a component of assignment grading. A student will be graded both on the assignment itself and on the student's grading of the assignment of others.

Academic Honesty

If you do something that violates the University's or the Department's Student Conduct code, there will be the most severe penalties I can manage. In particular, if you plagiarize (use other people's ideas, text, or code without acknowledgment) I will do what I legally and ethically can to end your academic career. If you have questions, please contact me for clarification.