What is this course about? Until the 20th century, calculus reigned supreme amongst the mathematical disciplines. Calculus is the natural tool for analyzing a continuous world, a world in which space can be divided into smaller and smaller pieces ad infinitum, and in which time admits no jumps. Discrete Mathematics, on the other hand, is suitable for a universe in which there is no continuity. One such universe is the set of natural numbers 0, 1, 2, 3, etc., where the irrational number pi does not exist. The computer is another discrete model, a thinking machine which can process information enormously fast, but whose fundamental operations occur one at a time, and thus discontinuously. There have always been elements of mathematics, such as logic, proofs and number theory, which were discrete by nature: e.g., what continuous pathway can one make from truth to falsehood?
In the early 20th century mathematicians became introspective and began asking if they could automate their own job description and prove all theorems in a mechanical fashion. By the time the question was answered in the negative after the work of Gödel, Church, Turing and others, a foundation of Discrete Mathematics had been laid down which paved the way for the creation of computers and their analysis. As computers were developed and refined in the second half of the 20th century, further aspects of Discrete Mathematics evolved. In this course we don't aim to provide you with the historical context in which Discrete Mathematics was created (though the textbook's homepage provides a wealth of opportunities to explore these on your own). We do, however, cover the fundamental tools of discrete mathematics: logic, sets, proofs, number theory, recursion, induction, combinatorics, recurrence relations and graph theory. This course is a co-requesite for Data Structures (CS 3137 or 3139) and together, these two courses are pre-requisite for most of the junior and senior level course offered by the CS department. Thus CS 3203 is of fundamental importance.
Pre-requisites: A one semester programming course (COMS 1007 or 1009). Programming won't be part of any assignment, except possibly for extra credit. Understanding of basic programming constructs is assumed.
Course web site:
www.cs.columbia.edu/~zeph/3203/
Required Text: Kolman, Busby and Ross, Discrete Mathematical Structures, 5th Ed. Pearson (Prentice Hall), 2004, ISBN: 0-13-045797-3. Available at Labyrinth books (112th between Broadway and Amsterdam).
Recommended Reference: K.H. Rosen, Discrete Mathematics and its Applications, 4th Ed. McGraw-Hill, 1999, ISBN: 0-07233610-2. Available at Labyrinth books.
Other Requirements : You may need a non-programmable scientific calculator for exams. Programmable calculators, palm-pilots, cell-phone calculators etc. are not allowed.
Readings and Lectures: The syllabus/schedule (www.cs.columbia.edu/~zeph/3203/schedule.html) contains a list of readings for each lecture as well as lecture notes. You should complete the book readings before the lecture. Old electronic lecture notes will also be provided for another viewpoint, but you are responsible for the material taught in class, not the lecture notes.
Participation: Part of your grade will be based on participation. If you attend all the lectures and respond to questions you are guaranteed full participation credit.
Homeworks: There are 5 homeworks. The homework due-dates are given in the schedule. (www.cs.columbia.edu/~zeph/3203/schedule.html) for a precise list. All the homework problems are located at the homework page (www.cs.columbia.edu/~zeph/3203/hw/index.html). Homework solutions will be available online with a password, through the left frame of the homepage (www.cs.columbia.edu/~zeph/3203/) (CLICK ON "SOLUTIONS AND DOWNLOADS") which also gives more details about homework policy.
Homework lateness policy: The last homework is not accepted late, as it must be graded immediately. Other homeworks may be accepted up to 5 days late, and incur a 10% penalty for each day late. If you hand in homework after the beginning of class, the homework is considered slightly late and incurs a 5% penalty. If you want to hand the homework in late, it will be your responsibility to find the grading TA and hand the work to him/her at the TA's convenience.
Exams and Quizzes: There will be one in-class midterm, two in-class quizzes and a final exam. Not showing up for the final is an automatic course failure. No accomodations can be made for students who miss the midterm or show up late. If there is a reason you cannot come to the scheduled midterm or final please tell us as soon as possible. Quizzes are designed to test basic understanding of the homework, but the midterm and final are more difficult as typical exam question ask you to integrate several concepts.
Grading: There will be seperate curves on homeworks and exams. The percentage breakdown after the curve is:
Regrades: If you feel that a problem on a homework or on the midterm was graded incorrectly, we can give you a regrade. Be aware that the TA will regrade the whole assignment (except in cases such as incorrect recording of score) and that your score may go down if mistakes which were previously ignored are discovered. All regrades must be requested within 2 weeks of when the assignment or exam was returned. For homeworks, contact the TA who graded your assignment, but for exams contact the instructor. Grade changes are subject to instructor approval.
Honesty: Homework and exams should constitute your own work. You are encouraged to discuss homeworks with other students, but in such a case you should list all the people that you collaborated with on the top of the submitted work. You should not copy solutions from other students. Further information about our department's cheating policy can be found at www.cs.columbia.edu/home/academics/cheating.html.
Here are typical examples of what does and does not constitute cheating:Uncollected work: A designated TA or the instructor will hold on to any homework or midterm that you didn't pick up.
Special circumstances: If there are reasons beyond your control which make it impossible to follow one of the above policies, you should inform us as soon as possible. You will need to properly document your special situation.