Discrete Mathematics in Computer Science

This course integrates discrete mathematics with algorithms and data structures, using computer science
applications to motivate the mathematics.

The course introduces counting techniques and number theory, with an emphasis on the application to RSA public
key cryptography. It covers logic and proofs, including mathematical induction. Relationships among recursive
algorithms, recurrence relations, and mathematical induction are discussed with particular attention to trees as a
recursive data structure. Issues of expected running time for algorithms and the technique of hashing data files
for quick recovery of information guides the discussion of probability through independent trials experiments and
expected values. The course also covers matrix algebra, motivated by how linear transformations are used in
computer graphics and (time permitting) in error correction codes.

The teaching method for the course is based on student group discussion of problems in class for about half of each
class period. These group discussions are followed by whole-class discussions which explain the ideas behind the
problems and amplify on them. There is a good bit of research that shows students retain more information when
they "construct" their own understanding of it in some way; the teaching method is designed to foster such
constructions while covering the material in discrete mathematics that computer science students need to know.

Although the reasons for group work are based on research in learning, it is worth mentioning that people
responsible for hiring in business usually put very high priority on a recruit's ability to function as part of a team. Thus
outstanding teamwork will be recognized in grading the course as described below to allow a potential employer to
learn about it.

I hope the following quote will inspire you to participate in this course.

"Mathematics is not for spectators; in order to gain in understanding, confidence, and enthusiasm one has to participate." M.A. Armstrong

CS 5 or equivalent
CS 15 or 18 (corequisite)

Required

• Discrete Math in Computer Science by Ken Bogart and Cliff Stein

• MWF 10:00-11:15, Bradley 102
• (xhour) Thursday, 12-12:50 Bradley 102

Note: X-hours will be used frequently when the class needs additional time working together, for review and for other purposes. However the use of an X-period will be announced in advance. Since the advance notice may be short, students are expected to keep the X-period open.

Tutorial sessions will be held Tuesday, Thursday, and Sunday evenings from 7:00 PM to 9:00 PM.
TAs will aso be available for office hours.  The room for the tutorials is Gerry 103

• Written homework will be assigned daily and will be collected two lectures later (for example homework assigned on Monday will be collected on Friday) at the beginning of class.

• All homework assignments will be posted on the course assignment's web page.
• Late homework will not be accepted under any circumstance. Since this seems harsh, I will allow you to drop 2 homeworks with lowest scores.
• Late and missing papers count zero.
• Homework is to be written neatly using both sides of 8 1/2 x 11 inch paper. Do not use paper from a spiral notebook unless you can tear off the ragged edge. All papers are to be stapled.
• Use English. If you can't read your solutions aloud as fluently as if you were reading a textbook, try using nouns and verbs in your write ups!

The course grade will be based upon the scores on the homework, two exams, participation (this means attending class and office hours as well as asking and responding to questions), and the final exam.

Exams (2)	20% (each)
Homework	20%
Participation	10%
Final Exam	30%

On Exams: No help given or received from anyone. You may not use books or notes during in-class exams. For take-home exams you can use your class notes only.

On Homework: Collaboration is permitted and encouraged, but NO COPYING . In other words, you should feel free to talk to other students while you are in the process of thinking about a problem. However, when it comes time to write up your solutions, you should do this by yourself without outside assistance.

Any student with a documented disability needing academic adjustments or accommodations is requested to speak with the instructor by January 20. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability. Students who think they may have a disability but are not sure are encouraged to consult with the Academic Skills Center in Collis Center to register for support services.

Back to math 19 webpage