Discrete Structures

Spring 2014

Dr. Stephen Bloch

Post Hall 213,
phone 877-4483,
email `sbloch@adelphi.edu`

Web page `http://www.adelphi.edu/sbloch/`

Class Web page `http://www.adelphi.edu/sbloch/class/156/`

office hours MW 2:20-4:00, T 10:00-4:00

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
`http://www.adelphi.edu/sbloch/class/156/calendar.html`.
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!**

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.

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.

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:

- (Chap. 0) Yes, There Are Proofs!
- (Chap. 1) Logic
- (Chap. 2) Sets and Relations
- (Chap. 3) Functions
- (Chap. 5) Induction and Recursion
- (Chap. 6) Principles of Counting
- (Chap. 7) Permutations and Combinatorics
- (Chap. 9) Graphs
- (Chap. 10) Paths and Circuits
- (Chap. 12) Trees

Students completing this course should be able to...

- solve combinatorial counting problems.
- create and analyze mathematical models of real-world problems.
- use the laws of deductive logic and read and write Mathematical proofs.
- write mathematics following the conventions of the discipline.
- read and comment upon mathematics written by others.

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:

- 3 -- correct mathematics and well presented solution.
- 2 -- mostly correct, or correct mathematics but poorly presented.
- 1 -- needs substantially more work.
- 0 -- didn't do the problem or completely wrong.

**Late homework will not be accepted.**

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 | 95 | 90 | 88 | 82 | 80 | 78 | 72 | 70 | 60 |

your letter grade will be at least | A | A- | B+ | B | B- | C+ | C | C- | 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.

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
`http://academics.adelphi.edu/policies/ethics.php`.

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.