CS222 Syllabus, Fall 2007 Course title: Discrete Structures for Computing Professor Lewis Barnett Office Jepson Hall 212A (804) 289-8091 [email protected] Office hours: MW 2:00pm – 3:00pm; TR 10:00am – 11:00am; or by appointment. (please don’t be bashful!) Prerequisites: CS 221 is a corequisite for this course Course Description This course covers topics in discrete mathematics that are needed in the study of computer science, including sets, functions, logic, methods of proof, mathematical induction, counting methods, discrete probability, graphs and trees. An algorithmic framework for these topics will be emphasized. Readings Susanna S. Epp, Discrete Mathematics with Applications 3e, Thompson Learning - Brooks/Cole, 2004. ISBN: 0-534-35945-0. You may also find the Student Solution Manual and Study Guide by the same author helpful. Grading Policy Homework 15% Programming assignments 15% Tests 45% Final exam 25% (Cumulative, see below for date) Makeup tests will not be given; in the event that a test is missed, the final exam grade will be substituted for the missed test in calculating the final grade for the course. Missed assignments will receive a grade of 0. Assignments There will be two types of outside-of-class work in this course. • Homework problem sets - exercises from the textbooks or other sources which will be graded and returned for discussion.• Programming projects - programs which you will design, implement, test, and document based on a general description of a problem to be solved. You will typically be expected to turn in both a working program and a writeup describing your approach to the problem. Procedures for turning in programs will be discussed when the first programming assignment is given. Late assignments will not be accepted. Collaboration As noted above, there will be two types of outside work assigned: problem sets and programming assignments. It is appropriate and helpful to work on the problem sets together or in small groups, but you are expected to write up your answers in your own words. The web site for your textbook supplies answers for odd-numbered exercises. If I assign an odd-numbered problem or one that is answered in the student solution manual for homework, it means that I expect you to complete the assignment without consulting the provided answer for that problem. It is never appropriate to consult instructor’s manuals or other similar types of solution sets in preparing your homework assignments. Unless otherwise stated in the assignments, the programming projects must be your own work and will be pledged under the Honor Code. Programming projects may be discussed with others subject to the “empty hands” policy – you may freely discuss ideas and approaches with other students subject to the restriction that each student must leave the discussion without any written or otherwise recorded material. In your project write-up, you must also document any person or source that you consulted for that project. Failure to comply with this policy will be treated as an Honor Code violation. It is never appropriate for code written by another student to appear in your program. If you experience problems in completing a programming assignment, please see me for help during office hours, or make an appointment to see me at another time if you are unable to come during office hours. You may also ask me questions by email. Please begin work early on programming assignments! I may not always be reachable in the final hours before a deadline. Collaboration is not allowed on quizzes or tests. Attendance Policy All students are expected to attend each class meeting. Each unexcused absence will result in a reduction by 1 point of your final average. I reserve the right to assign the V grade (Failure due to excessive absences) to any student who misses more than six class without excuse. Course Outline An outline of topics to be covered follows. This list does not necessarily reflect the order in which we will cover the topics -- they will quite likely be interwoven with each other. Please note the date for the final exam: THIS DATE WILL NOT CHANGE. Please make your travel plans accordingly. First order predicate logic Propositional logic Methods of proof Direct proof Contradition/contraposition Mathematical inductionBasic set theory Counting Elementary probability Trees, graphs, and algorithms that operate on them Test schedule There will be three tests tenatively scheduled for the following dates: • Wednesday, Sept. 19 • Wednesday, Oct. 24 • Wednesday, Nov. 14 Final exam: Tuesday, Dec. 11, 2:00 – 5:00