COSC 030 - Math Methods for Computer Science
(Fall 2019)
Georgetown University
Prof. Calvin Newport
Tuesday and Thursday, 11:00 - 12:15
Healy Hall, Room 105
Course Overview
Description
This course covers key mathematical concepts used in computer science, including: logic, proofs, counting, discrete probability, graph theory, and boolean algebra. These topics all fall within the general category of discrete mathematics as oppose to continuous mathematics (see here for more on this distinction.) Throughout the course, I will use algorithmic analysis to provide motivating examples, so you will also learn algorithm basics.
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 adapted 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 a reasonable understanding of the problem).
On the problem sets, each check plus earns you 4 points, each check 2 point, and each zero, of course, 0 points. There will be approximately 200 total possible points you can earn on the problem sets during the semester. The midterm and the final will each be made up of approximately 100 total points. Accordingly, the impact of the problem sets and exams on your grade works out to roughly the following:
| Problem Sets | 50% |
| Midterm | 25% |
| Final | 25% |
At the end of the semester, I will convert your raw numerical score into a letter grade. To help you keep track of how you're doing, each problem set and exam sample solution will include a scale so you can covert your numerical score into an approximate letter grade. I am also happy to give you an update on your current grade at any point during the semester, just ask me if you're curious.
Course Logistics
Teaching Assistants
This course has two teaching assistants who will hold regular office hours in the student lounge (near the bathrooms) on the third floor of Saint Mary's Hall. Their contact information and office hour times are below.
- Tiffany Lam (tcl49@georgetown.edu)
- Office hours: Wednesday, 3:45 to 5:45
- Elena Mehiel (ekm64@georgetown.edu)
- Office hours: Monday, 6:20 to 8:20 pm
Professor Office Hours
In addition to the teaching assistant office hours listed above, I will hold regular office hours from 12:30 to 2:00 on Tuesdays, in my office at 356 Saint Mary's Hall.
If these office hours conflict with your class schedule just let me know, we can find alternative times to meet as needed. I am also always happy to chat right after class if you have quick questions, or over email.
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 each problem set on the below schedule by the beginning of class on the day it is assigned. For the most part, each problem set covers the material taught in class the week it is assigned as is due on the first class of the next week. There are some exceptions to this timing due to holidays and travel. Please check the assignment and due dates carefully for 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.
- You should expect to get your problem sets back within nine days. That is, problem sets handed in on Tuesday will come back Thursday of the next week, if not earlier. I will let you know if more time is needed for a grading a given problem set.
Exams
There will be two exams in the course: a midterm and a final. The final exam is not cumulative; that is, it covers material from the second half of the course starting with discrete probability and ending with boolean algebra.
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 this schedule if needed if our pace proves too fast or slow.
Week 1 (8/29)
Introduction to the course and its topics; begin work on logic and proofs.
Problem Set 1 Assigned (Due on Tue, 9/10): [Download]
Textbook Chapter(s): 1
Week 2 (9/3 and 9/5)
Logic and proofs continued.
Textbook Chapter(s): 1
Week 3 (9/10 and 9/13)
Sets, functions, and sums.
Problem Set 2 Assigned (Due on Thur, 9/19): [Download]
Textbook Chapter(s): 2
Week 4 (9/17 and 9/19)
No Class on Tuesday, 9/17
Algorithms: their specification, correctness, and complexity.
Problem Set 3 Assigned (Due on Thur, 9/26): [Download]
Textbook Chapter(s): 3
Week 5 (9/24 and 9/26)
Finish algorithms.
No Class on Thursday, 9/16
Textbook Chapter(s):3,5
Week 6 (10/1 and 10/3)
Induction.
Problem Set 4 Assigned (Due on Tue, 10/8): [Download]
Textbook Chapter(s): 5
Week 7 (10/8 and 10/10)
Recursion and basic counting.
Problem Set 5 Assigned (Due on Tue, 10/17): [Download]
Textbook Chapter(s): 6
Week 8 (10/15 to 10/17)
Finish basic counting and begin discrete probability.
Textbook Chapter(s): 6, 7
Week 9 (10/22 and 10/24)
Your midterm is on Tuesday, 10/22. We will then continue with discrete probability on Thursday.
Problem Set 6 Assigned (Due on Tue, 11/5): [Download]
Textbook Chapter(s): 7
Week 10 (10/29 and 10/31)
Finish discrete probability; randomized algorithms.
Textbook Chapter(s): 7
Week 11 (11/5 and 11/7)
Solving recurrences. Begin graph theory.
Problem Set 7 Assigned (Due on Tue, 11/19): [Download]
Textbook Chapter(s): 8, 10 and 11
Week 12 (11/12 and 11/14)
Graph theory continued.
Textbook Chapter(s): 10 and 11
Week 13 (11/19 and 11/21)
Graph theory concluded. If time: start circuits and boolean algebra.
Problem Set 8 Assigned (Due on Tue, 12/3): [Download]
Textbook Chapter(s): 10 and 11
Week 14 (11/26)
Circuits and boolean algebra.
Textbook Chapter(s): 12
Week 15 (12/3 and 12/5)
Finish circuits and boolean algebra; advanced topics; and final exam review.
Final Exam: Monday, December 16, 4:00 - 6:00pm, in Healy 103 (note: not our normal classroom.)