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 combine your scores approximately as follows:
Problem Sets | 40% |
Midterm | 30% |
Final | 30% |
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.
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 cn248@georgetown.edu. A few notes about email communication:
Roughly speaking, I will assign one problem for each (full) week of class -- though this varies some due to holidays and the distribution of material. A tentative schedule for problem set assignments is included in the syllabus below. I will likely adjust these assignment dates as the semester progresses to better reflect our actual pace through the material.
Each problem set covers all lectures since the last problem set assignment (if any) including the lecture on the day it is assigned. For example, if problem set 1 is assigned on Wed 9/13, it covers all lectures up to and including 9/13. If problem set 2 is then assigned on Wed 9/20, then it covers Mon 9/18 and Wed 9/20.
Unless otherwise noted, each problem set is due one week from the day it's assigned. For example, if a problem set is assigned on a Wednesday, it is due the next Wednesday.
The following rules describe my expectations and grading policies for problem sets:
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.
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 Number | Date | Description | 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: correctness proofs, step complexity and asymptotic analysis | 2,3 |
3 | Mon 9/11 | Tools: Recurrences: recursion trees and master method | 4 |
4 | Wed 9/13 |
Tools: probabilistic analysis and randomized algorithms
|
5,C |
5 | Mon 9/18 | Divide and conquer: basic technique, mergesort, quicksort | 2,7 |
6 | Wed 9/20 |
Advanced sorting: randomized quicksort, linear-time sorting
|
7,8 |
Part 2: Advanced Data Structures and Design/Analysis Techniques | |||
7 | Mon 9/25 | Search trees: tree analysis, red-black trees | 12,13 |
8 | Wed 9/27 |
Amortized analysis
|
17 |
9 | Mon 10/2 |
Hashing
|
11 |
10 | Wed 10/4 | Hashing (cont.) | 21 |
Mon 10/9 | No class: columbus day | 15 | |
11 | Wed 10/11 | Dynamic programming (part 1) | 15 |
12 | Mon 10/16 |
Dynamic programming (part 2)
|
15 |
13 | Wed 10/18 | Greedy algorithms | 16 |
Midterm | |||
14 | Mon 10/23 | Lecture overflow and midterm review | |
15 | Wed 10/25 | Midterm | |
Part 4: Graph Algorithms | |||
16 | Mon 10/30 | Graph representation, graph search, topological sort | 22 |
17 | Wed 11/1 | Minimum spanning trees | 23 |
18 | Mon 11/6 |
Minimum spanning trees (cont)
|
24,25 |
19 | Wed 11/8 | Shortest paths | 26 |
20 | Mon 11/13 | Flows and cuts | 26 |
Part 5: Complexity Theory | |||
21 | Wed 11/15 |
Flows and cuts (cont)
|
34 |
22 | Mon 11/20 | Decision problems and computability | 34 |
23 | Wed 11/22 |
Complexity theory basics
|
|
24 | Mon 11/27 | NP completeness | 34 |
Part 6: Advanced Topics | |||
25 | Wed 11/29 |
NP completeness (cont)
|
35 |
26 | Mon 12/4 | Approximation algorithms | |
Final Exam | |||
27 | Wed 12/6 | Lecture overflow and final exam review | |
Tue 12/12 | Final Exam from 12:30 to 2:30 (Room tbd.) |