COSC 030 - Math Methods for Computer Science
(Fall 2014)
Georgetown University
Prof. Calvin Newport
Tuesday and Thursday, 3:30 - 4:45
Intercultural Center, Room 118
Course Overview
Description
This course covers the key mathematical concepts used in computer science, including: logic, proofs, basic counting and discrete probability, graph theory, and boolean algebra. Throughout the course, I will use algorithmic analysis to provide many of the motivating examples for these technqiues.
Textbook
The required textbook for this course is Discrete Mathematics and its Applications, 7th Edition by Kenneth H. Rosen. Most of the topics and examples covered in this course will be drawn from this text.
Grading
Grades in the course will be based on weekly problem sets and two exams (a midterm and a final). The problem set problems will be graded on the following scale: check plus (correct answer with at most minor issues), check (shows understanding but has at least one major issue), and zero (does not demonstrate any non-trivial understanding of problem). Each check plus earns you 2 points, each check 1 point, and each zero, of course, 0 points. At the end of the semester, I add up all the points you earned, and this is your raw problem set score. I will then translate that raw score into a letter grade.
As the semester continues, I can provide updates on how to approximately map your raw score into a letter grade. This mapping will evolve as I observe the relative difficulty of the problems assigned. Roughly speaking, however, if you want an A you should be aiming to get a check plus on most problems.
In determining your final grade, I will average your problem set grade with your midterm and final grades according to the below weights.
| Problem Sets | 50% |
| Midterm | 20% |
| Final | 30% |
Course Logistics
Teaching Assistants
This course has two teaching assistants who will hold regular office hours in Room 330 in Saint Mary's Hall:
- Tonghe Wang (tw473@georgetown.edu)
- Office hours: Monday from 3:00 to 4:30; Wednesday from 1:00 to 2:30.
- Jordan King (jwk67@georgetown.edu)
- Office hours: Tuesday from 11:30 to 1:30; Thursday from 12:00 to 1:30.
Office Hours
In addition to the teaching assistant office hours listed above, I will hold regular office hours from 1:00 to 2:30 pm on Thursdays, in my office at 334 Saint Mary's Hall.
E-mail Policy
If you have a question for me about the material or course logistics, my preference is that you ask me immediately before or after class, or during my office hours. If you instead e-mail me, I cannot guarantee a timely response. Therefore, if you have a last minute question about the problem set, you will likely be better served e-mailing one of the teaching assistants.
Problem Sets
The following rules describe my expectations and grading policies for problem sets:
- You must work alone on problem sets. You may only discuss problems with me or the teaching assistants. The only materials you can reference when working on these problems are your course notes and the assigned textbook. In particular, you may not reference online sources, solutions from previous classes, or talk to other students when working on problem set problems.
- I will post a problem set on the below schedule by the beginning of class every Tuesday. Each problem set covers the material to be taught that week and is due by the beginning of class the following Tuesday. There are some exceptions to the due dates because of holidays and travel. To keep things clear, I will mark the due date on the top of each problem set.
- Problem sets should be handed in at the beginning of class on the day they are due. That is, bring a physical copy of the problem set to class to give to me before the lecture begins.
- Problem sets not handed in by the beginning of lecture will be considered late, and 10% of the points deducted. Problem sets not handed until the day after the deadline will have an additional 10% deducted (slide late problem sets under my door if I am not in my office). Beyond this point, problem sets will not be accepted.
Exams
There will be two exams in the course: a midterm and a final. The final exam is cumulative; that is, it covers material from the full course.
Academic Integrity
I take academic integrity seriously. To repeat the problem set instructions from above: You must work alone on problem sets. You may only discuss problems with me. The only materials you can reference when working on these problems are your course notes and the assigned textbook. In particular, you may not reference online sources or talk to other students.
You may not bring any outside material into exams.
You may not reference any problem sets, exams, or solutions from prior teachings of this course.
When in doubt, ask me what is allowed.
Schedule
Below is the current schedule for the course. I will add more detail regarding the topics covered (and corresponding textbook sections) as the semester continues. I will adjust if needed if our pace proves too fast or slow.
Week 1 (8/28)
Introduction to the course and its topic; begin work on logic and proofs.
Problem Set 1 Assigned (Due on 9/9): [download]
Textbook Chapter(s): 1
Week 2 (9/2 and 9/4)
Logic and proofs continued.
Textbook Chapter(s): 1
Week 3 (9/9 and 9/11)
Sets, functions, and sums.
Problem Set 2 Assigned (Due on 9/16): [download]
Textbook Chapter(s): 2
Week 4 (9/16 and 9/18)
Algorithms: their specification, correctness, and complexity.
Problem Set 3 Assigned (Due on 9/23): [download]
Textbook Chapter(s): 3
Week 5 (9/23 and 9/25)
Induction.
Problem Set 4 Assigned (Due on 9/30): [download]
Textbook Chapter(s): 5
Week 6 (9/30 and 10/2)
Recursion.
Problem Set 5 Assigned (Due on 10/7): [download]
Textbook Chapter(s): 5
Week 7 (10/7 and 10/9)
Basic Counting
Problem Set 6 Assigned (Due on 10/14): [download]
Textbook Chapter(s): 6
Week 8 (10/14 to 10/16)
We will have no class this week as I will be traveling. I will schedule, however, extra office hours and perhaps an extra review session to prepare for the next week's midterm.
Textbook Chapter(s): N/A
Week 9 (10/21 and 10/23)
Your midterm is on 10/21. The second lecture of the week will begin our study of discrete probability.
Problem Set 7 Assigned (Due on 11/4): [download]
Textbook Chapter(s): 7
Week 10 (10/28 and 10/30)
Discrete probability continued.
Textbook Chapter(s): 7
Week 11 (11/4 and 11/6)
Advanced counting (recurrence relations, inclusion-exclusion, etc.).
Problem Set 8 Assigned (Due on 11/11): [download]
Textbook Chapter(s): 8
Week 12 (11/11 and 11/13)
Graphs and graph algorithms.
Problem Set 9 Assigned (Due on 11/18): [download]
Textbook Chapter(s): 10 and 11
Week 13 (11/18 and 11/20)
Graphs and graph algorithms continued.
Problem Set 10 Assigned (Due on 12/2): [download]
Textbook Chapter(s): 10 and 11
Week 14 (11/25 and 11/27)
Boolean algebra (notice: we only have one class this week due to the Thanksgiving holiday).
Textbook Chapter(s): 12
Week 15 (12/2 and 12/4)
Overflow material, wrap-up and exam review.
Textbook Chapter(s): N/A
Final Exam: Saturday, 12/13. (12:30 to 2:30 pm in ICC 103)