2013 March 31,

Math of Computer Science

CS 202-00, Carleton College, Winter 2013

Prof. Joshua R. Davis, , Goodsell 204, x4473

Introduction

When you first study computer science, you focus on creating algorithms and getting the computer to execute them (CS 111). As you continue studying CS, you might practice creating algorithms more (CS 201), or you might delve into how the computer hardware executes those algorithms (CS 208). If you've worked hard, you emerge from this study with a deep understanding of how to solve problems through programming. That's great, but you probably still can't solve these common computing problems:

• Most e-mail is junk mail. So how do you write a spam filter?
• Data is subject to errors when stored (e.g. scratches on a DVD) or transmitted (e.g. noise on communication lines). How do you handle these errors, to maintain data integrity?
• When you purchase goods over the web, your credit card information is encrypted, so that it can't be stolen. How does that work?
• You've perhaps learned that merge sort is a really fast sorting algorithm — O(n log n) on a list of length n. Why, exactly?

Good solutions to these problems require more than just algorithmic thinking and programming knowledge. They require math. In this course, we learn a variety of neat mathematical concepts and facts, that computer scientists use routinely. More importantly, we learn how to prove new facts, so that we are not merely users of math, but creators of math. That's a key step in becoming a computer scientist. The official prerequisites for this course are CS 111 and Math 111 (Calculus I), but you will find that this course is extremely different both of those courses.

Our class meets in CMC 319 during period 5A (MW 1:50-3:00, F 2:20-3:20). My office hours are MWF 6A and Thu 2:20-3:20. You can also schedule an appointment with me. The course materials are as follows.

• Textbook: Prof. Musicant and I are trying an experiment this term. We have collected material from two books — Kenneth H. Rosen's Discrete Mathematics and its Applications (7th ed.), and our own Prof. Liben-Nowell's forthcoming book — into a custom textbook in three parts. The textbook is significantly cheaper than a conventional textbook for this course.
• Algebra, Trigonometry, Vectors, Limits, Derivatives, Integrals are one-page reviews of basic mathematics, that I wrote many years ago. We don't need most of it, but the algebra review might help if you're really rusty.
• Here are some short tutorials on how to write math. I originally designed them for calculus students. But they could easily help students in this course.
  1. An Equation Is A Statement
  2. A String Of Equations Is A String Of Statements
  3. The Arrow "=>" Indicates That One Equation Implies Another
  4. Make Your Solutions Self-Explanatory
  5. Writing Sample (understandable, even though you don't have the intended textbook!)
• Recursion Problems, in case you need some practice.
• Fall 2008 Exam 1 and Answers (Percentiles: 75th = 66/100, 50th = 52/100, 25th = 43/100).
• Fall 2008 Final Exam (Percentiles: 75th = 73/100, 50th = 65/100, 25th = 48/100).
• Quiz, Answers to check how you're doing in the third week.
• Exam A, Answers (Percentiles: 75th = 38.5/50, 50th = 34/50, 25th = 29/50).
• Exam B, Answers (Percentiles: 75th = 38/52, 50th = 36/52, 25th = 27.5/52).
• Final Exam (Percentiles: 75th = 57/77, 50th = 50/77, 25th = 41.5/77).

Responsibilities

Final grades (A, B, C, etc.) are assigned according to an approximate curving process. By this I mean that there are no predetermined percentages (90%, 80%, 70%, etc.) required for specific grades. The following elements contribute to the final grade.

• Participation: You are expected to attend every class meeting promptly, and to participate in the discussion and group work. You are also required to visit me in my office (Goodsell 204) at least once by January 18, even if just to say "hi". You can make up for a deficiency in class participation by talking with me in office hours or generally demonstrating exceptional effort and interest. Participation is used to make small adjustments to the class grades.
• Assignments: Assignments are where you learn the material. I regard them as the core of the course. They count for 25% of your grade.
• Exam A: The first midterm exam is given in class on Friday 2013 February 1. (This is the day before midterm break. Your attendance is required, unless it is impossible due to another Carleton course.) It counts for 25% of your grade.
• Exam B: The second midterm exam is given near the end of the term. It counts for 25% of your grade.
• Final Exam: The final exam is cumulative. It is scheduled for Saturday 2013 March 16, 8:30AM-11:00PM. It counts for 25% of your grade. Self-scheduled final exams are not allowed.

You are expected to spend at least 10 hours per week on this course outside class. Some students need to spend more than 10 hours. If you find yourself spending more than, say, 15 hours, then talk to me.

Standards for Work

You are encouraged to work with others on all assignments. Work together to figure out the proofs/problems/programs, but write/type them up separately, in your own words. You may not copy someone else's work or allow them to copy yours. Presenting someone else's work as your own is an act of Academic Dishonesty. If Carleton College finds you to not to have upheld its Academic Honesty standards in this course, then you will receive an F for this course.

Writing is not just for English and history majors. Written and oral communication skills are essential to every academic discipline, and are highly prized by employers. In this course, your written work is evaluated both for correctness and for presentation. I do not require you to learn the typesetting system LaTeX, but you may find that it speeds up your homework writing. Talk to me if you're interested.

How much work should you show? The answer is simple: Compose your solutions as if the intended audience is your fellow students. By doing so, you show enough detail that your grader can ascertain whether you yourself understand the material. Your solutions should also be self-explanatory. If a classmate were to read one of your solutions, then she or he should be able to understand what the problem was and how you solved it.

When handing in multiple pages of paper, staple them into a single packet, in the correct order. Packets that are not stapled are unacceptable. I will not accept packets that are not stapled. Is there a stapler in the classroom? Often not, so staple ahead of time. Is a paper clip okay? No.

Computer files should be submitted in plain text (.txt), PDF (.pdf), or Python (.py) formats only, unless otherwise specified. In particular, Microsoft Word documents are unacceptable. Fortunately, you can "print" any document to PDF easily.

Depending on time constraints in any given week, perhaps not all of your homework is graded; in order to ensure full credit, do all of the assigned problems.

Special Accommodations

During the term, you have one free pass to hand in an assignment late. Instead of handing in the assignment, send me e-mail, by the due date, declaring that you are using your late pass. You assignment is now due when the next assignment is due. When you submit your late work, mark it "Late Pass Used" prominently at the top. Once you have used your late pass, no late assignments are accepted, except in extreme circumstances that are truly beyond your control.

If some medical condition affects your participation in class or your taking of exams, let me know in the first week of class. You may need to make official arrangements with the Office of Disability Services.

Schedule

Because of our textbook situation and my desire to customize our schedule to the students, this schedule has been filled in as we've gone along. Readings marked "DLN" are from David Liben-Nowell's book, while those marked "KHR" are from Kenneth H. Rosen's book.