This course is an introduction to formal structures and mathematial reasoning. Graphs, sets, logic, induction, structure of mathematical proof, counting, relations and algebraic structures are presented. Hands-on work is a central component of the course, embodied in homework assignments and lectures that include hands-on exercises.


Required Text:

Lehman, Eric, Leighton, F. Thomson, Meyer, Albert R., Mathematics for Computer Science,, Creative Commons Attribution - ShareAlike 3.0 License.

Class Web Site:

Goals: At the conclusion of this course, students should be familiar with the concepts and the language of logic, set theory, combinatorics, and other aspects of formal mathematics which arise in computer science. Skills in problem solving and analysis should be stronger, and students should feel more comfortable reading and writing mathematics.

Prerequisites: MATH 112 and one computer science course, or permission of the instructor.

Topics to be covered:

(A preliminary schedule can be found on the course web page.)

Logic and Proofs (Chapters 1, 2, 3)
Sets, Sequences, Functions, and Relations (Chapters 4 and 8)
Induction, Recursion, Recurrences (Chapters 5, 6, 7, 22)
Number Theory and Cryptography (Chapter 9)
Graph Theory (Chapters 10, 12, 13)
Counting and Probability (Chapters 14, 15, 17)

Grades will be based on:

Class Participation, In-class Exercises, Quizzes 15%
Homework 30%
Projects 15%
Two Exams and Final 40%

Attendance and Participation:

Regular attendance and fully engaged participation is expected of all students in this course. In the case of any absence, whether excused or not, you are responsible for all the material covered in class. We will have many in-class exercises. If you are not in class, you cannot get credit for these exercises. Active participation in the class means being on time, being prepared, listening to others, contributing ideas of your own, and asking questions as they come up.


Assignments, announcements, class notes, and other material will be made available on the course web site:
Students are responsible for checking this resource frequently.

Homework is an integral part of the course. Homework problems from the textbook, and possibly elsewhere, will be assigned each day, along with several pages of reading. You are expected to come to class having completed the reading. You should also bring questions you have from the reading and the exercises to class. There will always be at least one class day for questions and discussion between the assignment and its collection. Homework must be typed using LaTEX and should be submitted on Moodle by the beginning of class.

There will be several Projects assigned throughout the quarter. These will be opportunities to apply the language and concepts learned in class, and to explore other related concepts.

There will be three Exams in this class: an Exam at the end of third week, an Exam at the end of seventh week, and a Comprehensive Final Exam. The exams are meant to indicate how well you can apply what you have learned. They will encourage quick thinking and careful synthesis of ideas.

Collaboration and the Honor System

This course operates in accordance with the principles of the Kalamazoo College Honor System: responsibility for personal behavior, independent thought, respect for others, and environmental responsibility. In particular, academic integrity is a fundamental principle of scholarship. Representing someone else's work as your own, in any form, constitutes academic dishonesty. Unauthorized collaboration and receiving help from others outside the bounds permitted by the instructor are also violations of the College honor code. You are responsible for working within the permitted bounds, and acknowledging any help from others or contributions from other sources.

Homework questions: You should feel free to work with others on the homework questions. As you work with others, keep in mind that the goal is not just getting a solution to the problem, but learning how to solve the problem yourself. The write-ups of these problems should be your own work. You should also state at the top of the write-ups who you discussed these problems with. You should also feel free to take advantage of the Math Physics Center (MPC) and/or the CS Collaboration Center for help on the homework questions.

Projects: You may work in pairs or individually on any of the projects that are assigned. You may not work with the same partner more than once. When you work with a partner, you should only submit one copy of the project, with both names on it. I may also ask both partners to submit separate statements accounting for who did what on the project.

You may discuss the requirements and strategies of a programming project with others in the class, but you should not look at code belonging to anyone outside your team or make your code available to anyone other than your teammate. If you have code-specific questions you should address them to a TA or faculty member only. Computer Science TAs are available in the CS Collaboration Center, Sunday through Thursday. Check the door of OU 312 for a schedule. You should acknowledge in your program documentation any help you receive.

Exams should be entirely your own work.

Any student with a disability who needs an accommodation or other assistance in this course should make an appointment to speak with me as soon as possible.