COSC 240 - Introduction to Algorithms (Fall 2017)

COSC 240 - Introduction to Algorithms

(Fall 2017)

Georgetown University

Prof. Calvin Newport

Monday and Wednesday, 12:30 - 1:45

ICC, Room 106

Course Overview


This course explores various techniques used in the design and analysis of computer algorithms. Topics covered include sorting, search trees, hashing, dynamic programming, greedy algorithms, amortized analysis, graph algorithms and basic compexity theory. Time permitting additional topics connected to more cutting edge research might also be covered.


The required textbook for this course is Introduction to Algorithms (Third Edition) by Cormen, Leiserson, Rivest and Stein. Most of the topics and examples covered in this course will be adapted from this text.


This course focuses on the theoretical aspects of designing and analyzing correct and efficient algorithms. Accordingly, there are no programming assignments. Problem set assignments and exams will instead require pencil and paper analysis.

In more detail, grades in this course will be based on problem sets and two non-cumulative 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, or could not read the writing and/or follow the solution). Each check plus earns you 4 points, each check 2 points, and each zero, of course, 0 points. At the end of the semester, I add up all the points you earned, and this number is your problem set score.

Each problem set will be returned to you along with sample solutions, grading notes, and a guide to mapping your point score to a letter grade scale. Though this mapping will vary from problem set to problem set, depending on length and difficulty, in most cases, to earn an A on a problem set you should be aiming to get a check plus on most problems.

The midterm will be taken in class and will cover material from the first half of the class. The final exam will be taken during the final exam period and will cover material from the second half of the class. That is, the final exam is not cumulative.

In determining your final grade, I will add your numerical problem score with the numerical scores you earned on your midterm and final. This produces a final numerical score for the class. I will then map these scores to letter grades to determine your final grades. I will provide feedback along the way about how your current numerical scores map to letter grades.

In general, the different scores you earn should contribute roughly the following percentages to your final grade (if needed, I will weight these three scores to better match the below allocation):

Problem Sets50%

Course Logistics and Policies

Professor Office Hours

I will hold regular office hours from 2:00 to 3:30 pm on Monday, in my office at 334 Saint Mary's Hall. I'm also always available for quick questions immediately following class.

Professor Communication

For quick questions, I prefer talking in person immediately following class or in office hours. For complicated technical questions, asking me in person during office hours is also usually best.

If neither option works, you can email me at A few notes about email communication:

  • If possible, put "COSC 240:" in your subject line. This will help ensure your message does not get buried or lost amid less urgent communication.
  • On many days, I only check email once or twice, so I cannot guarantee a quick response, but can guarantee that with few exceptions if you email me on a weekday I'll get back to you either that day or the next weekday. (I don't email during weekends.)
  • With this in mind, I recommend starting your problem sets soon after they are assigned so you can bring questions to me in advance when there is plenty of time for us to discuss.

Problem Sets

The following rules describe my expectations and grading policies for problem sets:

  • You can work alone on the problem sets or in groups of size at most three.
  • If you work in a group, you must write the names of your group members on the top of your problem set.
  • Whether or not you work in a group, every student must hand in their own problem set solutions written in their own words.
  • You many only discuss problems with me, your group members, or 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 or solutions from previous/other classes.
  • I will post each problem set on this web page in the schedule section below, on the day that it is assigned.
  • 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. If you cannot make class, please make arrangements with me for alternative submission procedures before the due date.
  • 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 20% deducted (slide late problem sets under my door if I am not in my office). Beyond this point, problem sets will not be accepted.


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.

Academic Integrity

I take academic integrity seriously. To repeat the problem set instructions from above: You can work in groups of at most three pepope on the problem sets. All students must write up their own answers and record on the top of the problem set any group members they worked with.

You many only discuss problems with me, your group members, and 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.

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.

Violating these rules will lead to a zero on the assignment and potental reporting to the academic honor council.

When in doubt, ask me what is allowed.


Below is the current schedule for the course. I will likely 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.


Class NumberDateDescription CLRS Chapters
Part 1: Algorithm Basics
1 Wed 8/30 Introduction 1,2
  Mon 9/4 No class: labor day  
2 Wed 9/6 Tools: asymptotic analysis; recurrences
  • Problem set 1 assigned
    Covers classes 2 and 3
    Due: Mon 9/18
3 Mon 9/11 Tools: probabilistic analysis and randomized algorithms 5,C
4 Wed 9/13 Sorting (part 1): heap sort; quicksort; randomized quicksort 6,7
5 Mon 9/18 Sorting (part 2): sorting lower bound; linear time sorting
  • Problem set 2 assigned
    Covers classes 4 - 6
    Due: Wed 9/27
6 Wed 9/20 Fast selection and statistics 9
Part 2: Data Structures
7 Mon 9/25 Search trees (part 1) 12,13
8 Wed 9/27 Search trees (part 2)
  • Problem set 3 assigned
    Covers classes 7 - 9
    Due: Wed 10/4
9 Mon 10/2 Hashing 11
Part 3: Advanced Design and Analysis Techniques
10 Wed 10/4 Dynamic programming (part 1)
  • Problem set 4 assigned
    Covers classes 10 - 13
    Due: Mon 10/23
  Mon 10/9 No class: columbus day 15
11 Wed 10/11 Dynamic programming (part 2) 15
12 Mon 10/16 Greedy algorithms 16
13 Wed 10/18 Amortized analysis 16
14 Mon 10/23 Lecture overflow and midterm review  
15 Wed 10/25 Midterm  
Part 4: Graph Algorithms
16 Mon 10/30 BFS, DFS, topological sort, and components
  • Problem set 5 assigned
    Covers classes 16 - 18
    Due: Wed 11/8
17 Wed 11/1 Minimum spanning trees 23
18 Mon 11/6 Shortest paths
  • Last day for undergraduates to withdraw
19 Wed 11/8 Flows and cuts (part 1)
  • Problem set 6 assigned
    Covers classes 19 - 20
    Due: Mon 11/20
20 Mon 11/13 Flows and cuts (part 2) 26
Part 5: Complexity Theory
21 Wed 11/15 NP completeness (part 1) 34
22 Mon 11/20 NP completeness (part 2)
  • Problem set 7 assigned
    Covers classes 21 - 24
    Due: Mon 12/4
23 Wed 11/22 Tbd.  
24 Mon 11/27 Approximation algorithms 35
Part 6: Advanced Topics
25 Wed 11/29 Advanced topic: distributed algorithms  
26 Mon 12/4 Advanced topic: online/streaming algorithms  
Final Exam
27 Wed 12/6 Lecture overflow and final exam review  
    Final exam period covers 12/12 to 12/20. The time and date of our final exam will be posted once available.