MATH/CS 240 (Intro. Discrete Math.) SYLLABUS, Spring 2007Lecture: TR 1PM – 2:15 PM, BIRGE 145Prof. Jordan Ellenberg Text is:Office: 323 Van Vleck Hall Discrete Math. & its Applications6th ed., by K. RosenEmail: [email protected] http://www.math.wisc.edu/˜ellenberOffice Hours (JSE): Tues. (4:45-5:45 PM) (323 Van Vleck) Mon.(12-1 PM) (CRC dininghall)TA: Matt Davis, [email protected], 101 VV, http://www.math.wisc.edu/˜davis/240s07.htmOffice Hours (MD): Thurs. (12-1), Fri (11-12 and 1:20-2:20)Course ContentMathematics can be lo osely divided into two parts. The first is continuous mathematics;as the name suggests, this part of math treats phenomena that can be moved continuously,like functions, curves, and geometric spaces. Most of the math you’ve learned so far –geometry, trigonometry, calculus – is continuous in nature. The basic object of continuousmathematics is the real number line. Because the physical universe (at least to the nakedeye) is continuous, this is the part of mathematics most associated with physics. The secondpart is discrete mathematics, the subj ect of our course. Here we throw aside any notionof continuous variation. The basic objects of discrete mathematics are the set of integersand of logical values; there is no way to move continuously from 2 to 3, or from “true” to“false.” Because the states of a computer are discrete, this is the part of mathematics mostassociated with computer science.Math/CS 240 covers the fundamentals of discrete mathematics. It is a requirement forthe BS degree programs in Computer Engineering offered by the ECE Department and inComputer Science offered by the CS Department. It is now a prerequisite for (getting into)advanced computer science courses (CS 367, 520 and 577). The course is a foundationalmath course for this program and is meant to be taken early in the program; it is also agood foundation for higher mathematics courses. We will aim for breadth, not depth; youwill be introduced to many new concepts and topics, and we won’t spend a long time onany one of them. We hope that by the end of the course you’ll have developed a friendlyacquaintance with this important segment of mathematics, and have the expertise necessaryto develop a deeper relationship with whatever topics you will need in your future studies.The prerequisite for the course is Math 221 (Calculus I), and the course will be taughtroughly on the level of Math 222 (Calculus II.)Briefly, the topics covered in the course include: logic, set theory, functions and theirgrowth, Boolean functions, the integers, algorithms, relations and digraphs, inductive andrecursive definitions and arguments, divide and conquer relations, fundamentals of countingand discrete probability, variance and expected value, recurrence relations, relations includ-ing equivalence relations, some elementary graph theory including trees, tree-searching and1traversal, . . . This is a long list, but you’ll find that there are many connections between thetopics.How to do well in this course You should spend approximately 5–6 hours a weekon the course - studying your book and your lecture notes, thinking about the ideas andconcepts and how they relate to each other, talking with some of your classmates aboutthem (study groups are encouraged), and, most important, doing your homework. Not eventhe greatest genius can learn math by listening to it – you have to do it, and that’s what thehomework is for. If you are having trouble with a section of the course, the best remedy isto do even more problems than we assign – Matt and I will be happy to discuss these withyou.Not everything you need to know will be discussed in lecture, and not everything youneed to know is in the book. The lecture and the book will reinforce each other. We’ll covera pretty large chunk of the book, which is itself pretty large; lectures and exercises shouldgive you a goo d idea of what portions we mean to emphasize most, and what will be presenton exams. We will write exams assuming that you have completed the homework, and youshould expect to see some variations of questions from the homework appearing on exams.In addition to the lecture you have once-a-week discussion section with a Teaching Assis-tant (TA). In this discussion section you can get your questions answered, go over problems,review, etc. Homework will be turned in and exams passed back in these sections.Exercises Homework w ill be announced each Tuesday and due in discussion section thefollowing week. Each week, we will choose a subset of problems to be graded; your gradewill be a combination of your score on these selected problems, and the overall completenessof your homework. Homework is 25 percent of your grade, so be thorough! Late homeworkwill not be accepted unless your TA has agreed to an extension before the due date. You areencouraged to form study groups with your classmates; things not clear to you may becomeobvious when you try to explain them to others or when you hear other points of view.Sometimes just verbalizing your mathematical thoughts can deepen your understanding. Itis acceptable, indeed desirable, to work on homework collaboratively; however, write-ups mustbe your own work and may not be identical with those of any of your classmates.Exams There will be two in-class exams during the semester, each worth 20 percent ofyour grade, and a final exam, on May 13, from 2:45 - 4:45 pm, worth 35 percent of yourgrade. Depending on the pace we keep in lecture, we may also have some in-class quizzes.All quizzes will be announced.Grades will be distributed as follows: 25 percent homework, 40 percent midterm exams, 35percent final exam. We will grade on a curve. In the past, the cutoffs have been approxi-mately 93 for an A, 89 for an AB, 80 for a B, 70 for a C, 60 for a D.Calculator Policy It is acceptable to use calculators while doing your homework, but in thisgenre of math they are seldom helpful; computations are to be exact. So an answer whichhas√2 in it is to be presented as such, not as 1.414. Calculators will not be permitted in2exams, and we will not give questions which require (or would be made substantially easierby) the use of calculators.Attendance It is expected that each student will be present at all of the classes and dis-cussions and will be an attentive class participant.Office Hours Our office hours are listed on page 1. We encourage you to come, whetherto discuss homework problems, topics