Computer Science 156
Discrete Structures
Spring 2014

Dr. Stephen Bloch
Post Hall 213, phone 877-4483, email
Web page
Class Web page
office hours MW 2:20-4:00, T 10:00-4:00

Time and space

This class meets in Hagedorn 217 every Monday, Wednesday, and Friday from 11:00-11:50 AM. I have office hours Mondays and Wednesdays from 2:20-4:00, and Tuesdays from 10:00-4:00, either in my office (Post 213) or in the Department computer lab (Post 103).

The schedule of topics, reading assignments, and homework assignments will be maintained on the Web at The dates are subject to change depending on how classroom discussions actually go. I expect you to have read the reading assignments before the lecture that deals with that topic; this way I can concentrate my time on answering questions and clarifying subtle or difficult points in the textbook, rather than on reading the textbook to you, which will bore both of us. Please read ahead!

Online support

Many course materials will be available on Moodle or the Web, but we'll also use another online discussion system called Piazza. The difference between the two is analogous to the difference between a Swiss-army knife (which does a little of everything) and a chef's knife (which does one thing very well): Piazza is really good for questions, answers, and discussion. Although you're always welcome to e-mail me, I encourage you to ask yourself “is there anybody else in the class who might be interested in this question too?” If so, I suggest posting your question on Piazza instead: somebody else in the class may answer your question before I've gotten around to checking my e-mail.

You should each receive an e-mail invitation to Piazza. If you haven't received one yet, check your spam-filters.

Official course description

Learn the concepts of Set Theory, Mathematical Logic, and Boolean Algebra, and their underlying similarities. Learn how to use quantifiers. Become fluent in the use of the Binary, Octal, and hexadecimal number systems. Learn how to use and apply Combinatorial Circuits and Finite State Machines and Automata.

What we'll really do

See "Textbook" below. I don't think we'll talk much about different number bases, nor finite-state machines/automata. We will do some proofs, providing a sort of warm-up for MTH 301 "Introduction to Proofs and Mathematical Reasoning". And we'll discuss a lot of concepts, techniques, and vocabulary that every working mathematician or computer scientist is expected to know.

This is basically a math course, but it's a completely different kind of math from precalculus or calculus; it feels like it uses a different part of your brain. One neat thing about discrete math is that many of the problems we solve are questions you could explain to a bright 13-year-old (although the answers may be much more difficult!) And these are exactly the sorts of problems that are most useful in computer science.


None. This course is required for the CS, CMIS, and Math majors, and is a prerequisite for many other CS and Math courses.


This course has one required textbook: Discrete Mathematics with Graph Theory by Goodaire and Parmenter, third edition. ISBN: 9780131679955. It should be in the Bookstore and on reserve in the Library.

Topics in the course will be selected from the following chapters:

Course Learning Goals

Students completing this course should be able to...

This course also satisfies the Quantitative Reasoning general-education learning goal.

Written Homework

Each week we'll post on Piazza two or three “written exercises”, whose solutions are due the following Wednesday. You may collaborate with other students on the homework, but (at least at the beginning of the semester) you must write up all solutions independently and on your own. Copying is not permitted and is a violation of the Honor Code (see below for more information); if you think your homework will look a lot like your collaborator's, mention your collaborator's name in the homework so we can tell that it's "working together" rather than "copying".

Homework will be graded on a scale of 0 to 3, and returned with comments. Think of this grade not as a percentage but, rather, as delivering a message:

If your homework grade was less than a 3, you're invited to rewrite your solution and re-submit it (with a copy of the original, or some other way of making clear what's changed) the following week. Both submissions will count towards your final grade.

Late homework will not be accepted.

Online Homework

Each week we'll also post on Piazza two or three "online exercises". These problems are similar to the written exercises, but we want the class as a whole to discuss these problems and jointly put together a clear, correct solution. Constructive participation in this process helps your semester grade; in addition, the whole class is graded uniformly on the quality of the solution produced. problems are to be completed by class time on Monday.


Roughly weekly, we'll hand out a sheet with some false mathematical statements. Students will work to produce counterexamples demonstrating that they're false, then present their counterexamples in class. Your "presentation" grade will be determined by the number of correct presentations you give in the semester.


Your final grade will be weighted as follows:

20% Written Homework
5% Online Homework Participation
5% Online Homework Class Correctness
10% Presentation
15% Midterm 1 Feb. 14, 2014
15% Midterm 2 Apr. 7, 2014
25% Final Exam probably May 16, 10:30 AM
5% Best Exam Score

Your letter grade for the course will be determined from your numeric grade (based upon the above weightings) as follows:

If your numeric grade is above 959088828078727060
your letter grade will be at least AA-B+BB-C+CC-D

The cut-off points for assigning letter grades will depend on the distribution of final numeric grades. Your final letter grade may be higher than the grade indicated above, but it will not be lower. (In past semesters, I've tended to give fairly low numeric grades, and some students have approached me in a panic, thinking they were failing the class, when they were actually heading for a B or B+.)


Calculators (or other electronic devices) are not allowed during examinations. Exams will be written so that they are not necessary.

Getting help

If you think any of your classmates might have the same question (or have an answer), post on Piazza or ask in class. If you have a more individual question (e.g. "am I going to fail this course?"), feel free to e-mail me or visit my office hours.

Office hours are not a “resource of last resort”. I consider them to be a part of the course like any other, and many of my best students have been 'regulars' in office hours. There is much that I can do for you in a one-to-one situation that I simply cannot do in a group setting. You should take advantage of the fact that I am easily available to help you outside of class.

The office hours listed above are times in which I am guaranteed to be in my office to work with you. I also maintain an open door policy. You're welcome to come by my office at any time to see if I'm in. As long as I don't have something pressing, I will be happy to talk with you, even if it's not office hours. If I do have something that can't wait, I will let you know what time I'll be free.

In addition to seeing me in-person in my office, I check e-mail fairly frequently (particularly during the day). I will always respond to math questions that you send me (though I may respond with a question of my own or an observation or request for clarification). If you e-mail me in the evening, I may not be able to reply that night but will almost always reply the following morning. I definitely want to hear from you, so don't hesitate to contact me!

Other students in your class can also be a source of help. Having a classmate with whom to work and talk regularly about classwork is a well-known factor in improving performance in calculus. You need not look for a student who "knows more" than you do; this arrangement works best for if the partners are well matched in ability and background.

In addition, the Mathematics department hires tutors who are able to help students in calculus (and other) courses. See this web page for tutoring schedules.


The Adelphi University Code of Ethics applies to this course; look it up on the Web at

Most assignments in this class are to be done individually or in teams of two. You may discuss general approaches to a problem with classmates, but you may not copy large pieces of homework solutions. If you do, all the students involved will be penalized (e.g. I'll grade the assignment once and divide the points equally among the several people who turned it in).

All work on an exam must be entirely the work of the one person whose name is at the top of the page. If I have evidence that one student copied from another on an exam, both students will be penalized; see above.

Academic Honor Principle:
On exams: No help is to be given or received.
On homework: Collaboration on homework is permitted and encouraged. It is a great idea to talk about the problems with each other and try to solve them together. However, for the online homework problems, you must input your own solutions and are responsible for knowing how you arrived at the answers you input.

Students' Religious Observances: Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with your instructor before the end of the second week of the term to discuss appropriate accommodations.

Disabilities: Students with disabilities are encouraged to speak with the professor about accommodations to produce an accessible learning environment.

Student Course Evaluations: During the last two weeks of the class, you will receive notification, via email and eCampus, that the course evaluation is available for your input electronically. Availability will end at the start of the final examination period. Your feedback is valuable and I encourage you to respond. Please be assured that your responses are anonymous and the results will not be available to the instructor until after the end of the semester and therefore after course grades have been submitted.