1 CMSC 175 A Discrete Mathematics Spring Semester, 2012 Instructor: Lydia Sinapova Office: Carver Science 235 Phone: 961-1841 (office), 962-1574 (home) Catalog Description This course covers selected topics in discrete mathematics that are essential to the study of computer science. Topics include logic and proofs, sets and Boolean algebra, relations and functions, algorithms and counting of operations, recursion and recurrence relations, graphs and trees. The course has a programming component to illustrate the discussed topics. Four credits. Prerequisite: One of Math 130/130T, Math ACT of 24 or higher, or Math SAT of 570 or higher. Co-requisite: CMSC 150 or permission of instructor. Course Objectives Upon successful completion of this course students should be able to: - Understand basic properties and operations of sets and relations - Use predicate logic and recursion to describe sets and relations - Understand and properly use proof methods to prove properties of sets and relations - Understand and properly use methods of counting permutations and combinations of set elements - Understand basic properties of graphs and trees. Required Text The lecture notes provided on the class web page are based on Richard Johnsonbaugh's Discrete Mathematics, 6th edition, Prentice Hall, 2005, ISBN: 0-13-117686-2. The textbook however is not required. On the class web page you will find links to several web-based learning resources. Topics 1. Propositional and Predicate Logic 2. Proofs 3. Sets and Boolean Algebra 4. Relations and Functions 5. Sequences, Recursion and Mathematical Induction 6. Counting 7. Graphs and Trees Coursework, Assignments and Tests - Preparation for class You will have to read in advance the scheduled sections, and solve (or at least attempt to solve) assigned problems for those sections. You will have to send me the problems that you have solved before the class meeting. These problems will be part of your homework assignments. - Homework assignments Homework assignments are based on the problems solved in class and provided on the class web page. All homework assignments have due dates. They have to be uploaded in Scholar. All files and folders have to start with your first name and to indicate the assignment, e.g. John_HW01.doc. You are encouraged to send your homework earlier (at least 48 hours before the due time) for feedback. This will not affect your grade.2 Policy on late assignments The penalty for being late is 10% reduction of the grade for each day after the due date. You will have the option to turn in late (but not later than 24 hours after the due time) two assignments without penalty. Use this option in case of unexpected circumstances. - Quizzes A 10-minute quiz will be given weekly on Fridays. At the end of the semester your lowest quiz grade will not be considered. - Unit tests You will have three unit tests, as specified in the schedule. The midterm grades to be reported to the Registrar Office will be determined as 40% of Test 1, 40% of the homework assignments and 20% of the quizzes completed by the Midterm date. - Final exam The final exam will be comprehensive - the problems will cover everything studied in class. Class notes posted on the web contain exam-like questions and problems. I strongly recommend that you work on the exam-like questions and problems during the semester. You may send your answers for comments and corrections. Grading Policies The final grade will be based on the homework assignments, quizzes, and the final exam, determined in the following way: Homework assignments 30% Quizzes 10% Tests 30% Final exam 30% Grades follow a normal distribution as shown in the following table where the percentage is the lowest percentage allowed to obtain that grade. B + 87.0% C + 77.0% D + 67.0% A 93.0% B 83.0% C 73.0% D 63.0% A - 90.0% B - 80.0% C - 70.0% D - 60.0% Study Time This is a four credit course that meets 3 days per week for 50 minutesл It is designed to have learning opportunities and activities totaling approximately 160 hours over the 15 weeks of the course (including finals week). The designed activities may take each student a different amount of time to finish, however the average will be 160 hours. You have to plan for an average of 8 hours per week out-of-class study time. Further estimates include: In-class activities 39 hours Required reading and studying (12 weeks x 4 hours each) 48 hours Homework assignments (12 x 4 hours each) 48 hours Preparation for exams 25 hours Total 160 hours3 How to Succeed - Read the lecture notes before and after each class session. Send (by e-mail) questions on specific paragraphs that are difficult for you to understand. - Start to work early on your homework. In case of difficulties, send me your questions. - Attend classes and participate in class discussions. Take notes. Spending 15 minutes to read your notes immediately after class is very much worth the effort. - Make a weekly schedule of the time you are going to spend studying for this class. Generally you will need 8 hours per week spent in studying, including work on homework assignments. Instructional Help I will be available for any type of questions and consultations during and outside my office hours. In order to avoid conflicts with other scheduled appointments, please let me know in advance (by e-mail or by phone) that you want to see me. You are encouraged also to send questions by e-mail. Attendance Class attendance is extremely important. The concepts and the notation to be studied will in most cases be completely unfamiliar to you, and it would be difficult for you to understand the material without the class experience. In class we will solve various problems to illustrate the new concepts (you will get similar problems on the exams). Academic Integrity In all endeavors, Simpson College expects its students to adhere to the strictest standards of honesty and integrity. In keeping with the College’s mission to develop the student’s critical intellectual skills, while fostering personal integrity and moral responsibility, each student is expected to abide by the Simpson College rules for academic integrity. Academic dishonesty includes (but is not limited to) any form of cheating, plagiarism, unauthorized