COSC 240 - Introduction to Algorithms

(Spring 2020)

Georgetown University

Prof. Calvin Newport

Tuesday and Thursday, 12:30 - 1:45

Healy Hall, Room 103

NEW: Information on Shift to Online Instruction

Lectures

The current plan for online instruction is to hold our lectures during their normally scheduled times using Zoom video conferencing software. I will use the shared whiteboard feature in conjunction with a writing tablet to simulate the blackboard. I'll also make available video recordings of all lectures.

We will use the same recurring meeting for all lectures. The link was sent to you via email. Let me know if you need it.

Midterm/Final

Based on the recommendation of the Dean's office to delay formal assessments until after the move out period, the midterm has been shifted to April 2nd. It still, however, only covers Parts 1 and 2. The midterm will be take home but timed, taking place during the normal lecture period. I will be available via Zoom for questions. Additional time periods can be arranged for students who need accomodations due to issues such as time zone conflicts. More details will be shared as we get closer to the exam date.

I will wait until after our midterm to decide on the details for how I will administer the final exam (I want to learn from the midterm experience.)

Problem Sets

The only change to the problem set process is that you'll now submit them electronically by 12:30 on their due date using a Canvas site for this course. (Instrutions for this electronic submission procedure are pending.)

Office Hours

Professor and TA office hours will nowplace using Zoom during their nnormally scheduled times. The relevant links are below:

Communication

Outside of the Zoom lectures and office hours, I'll continue to send any relevant updates or notes to the class email list. I will also monitor my email carefully, including during scheduled zoom conferences (in case of technical difficulties).

Course Overview

Description

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 complexity theory.

Supported by funding from the Mozilla Foundation, and working in conjunction with Georgetown's Ethics Lab, we will also be experimenting this semester with integrating into the curriculum content on ethics and social responsibility in computer science. Your participation and feedback regarding these modules will be much appreciated, as it will help shape the evolution of this innovative endeavor.

Textbook

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.

Grading

This course focuses on the theoretical aspects of designing and analyzing correct and efficient algorithms. Accordingly, there are no programming projects. 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, a midterm, and a non-cumulative 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 we could not follow your 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. The midterm will be returned to you with sample solutions, grading notes, and a guide to mapping your numerical score to a letter grade.

In determining your final grade, I will add up the total points you earned on problem sets, the total points you earned on your midterm, and the total points you earned on your final. I will then map your point sum to a final letter grade.

To do so, I add to our class grading spreadsheet invented A, B, C, and D students. For each assignment and exam I give the A student the score that corresponds to the middle of the A range, the B student the score that corresponds to the middle of the B range, and so on. At the end of the class, I sum up the scores in these rows to establish a basic point range for A, B, C, and D grades. I use these to help inform the final mapping of your numerical score to a letter grade.

Notice, the total points available for the problem sets will add up to be roughly 50% of the total possible points, with the total points available on the midterms and final each adding up to roughly 25% of the available points.

If you have any questions about your current course performance please do not hesitate to talk to me. I do not want your final grade to be a surprise.

Course Logistics and Policies

Professor Office Hours

I hold regular office hours from 2:00 to 3:00 on Tuesday and Thursdays in my office at 356 Saint Mary's Hall. I'm also available for quick questions before and after class and via email at cn248@georgetown.edu. If you need a longer meeting and cannot make my regular office hours times, we can always find another meeting time that works.

Teaching Assistants

This course has two graduate student teaching assistants who will hold their own regular office hours in the student lounge (STM 328) near the bathrooms on the third floor of Saint Mary's Hall. They can also answer questions via email. Their contact information and office hours times are as follows:

Problem Sets

The course schedule below describes when each problem set is assigned, when it is due, and what lectures it covers. I will post a link for downloading each problem set on the course schedule on the day the problem set is assigned. Keep in mind that the problem set schedule on the course schedule is preliminary and might shift as the semester progresses.

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

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.

Academic Integrity

I take academic integrity seriously. To repeat the problem set instructions from above: You can work in groups of at most three people 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 assistant. The only materials you can reference when working on these problems are course notes from the current semester and the assigned textbook. In particular, you may not reference online sources or solutions from previous semesters.

You may not bring any outside material into exams.

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

When in doubt, ask me what is allowed.

Schedule

Below is the current schedule for the course. I might adjust this schedule as the semester progresses so please keep checking back for the latest version.

 


Class NumberDateDescription CLRS Chapters
Part 1: Algorithm Basics
1 Thur 1/9 Introduction 1,2
2 Tue 1/14 Tools: correctness proofs, step complexity; ethics discussion: "What makes a good algorithm?" 2,3
3 Thur 1/16 Tools: asymptotic analysis; recursion trees 4
4 Tue 1/21 Tools: recursion trees (cont); the master method 5,C
5 Thur 1/23 Tools: probabilistic analysis basics (expectation, random variables)
  • Problem set 1 assigned [Download] (covers lectures 2 - 6; due Tue 2/4)
  • Ethics reading assigned (read before next class; PDF will be emailed to students)
5,C
6 Tue 1/28 Tools: average case complexity and randomized algorithms; ethics discussion: "Reducing people to data points." 5, C
7 Thur 1/30 Divide and conquer: basic technique; mergesort 2,7
8 Tue 2/4 Advanced sorting: quicksort, randomized quicksort
  • Problem set 2 assigned [Download] (covers lectures 7 - 9; due Thur 2/13)
2, 7
9 Thur 2/6 Advanced sorting: randomized quicksort (cont), sorting lower bounds, linear time sorting.. 7, 8
Part 2: Advanced Data Structures and Design/Analysis Techniques
10 Tue 2/11 Amortized analysis 17
11 Thur 2/13 Amortized analysis (cont.); dynamic programming (part 1)
  • Problem set 3 assigned [Download] (covers lectures 10 - 13; due Thur 2/27)
15
  Tue 2/18 No Class: President's Day
12 Thur 2/20 Dynamic programming (part 1) 15
13 Tue 2/25 No lecture
14 Thur 2/27 Dynamic programming (part 2) 15
15 Tue 3/3 Dynamic programming (part 3); greedy algorithms 15, 16, 22
16 Thur 3/5 Hashing; midterm review (if time) 11
  Tue 3/10 No Class: Spring Break
  Thur 3/12 No Class: Spring Break
17 Tue 3/17 Online Instruction Review/Midterm Review [Zoom Conference Link]
Part 3: Graph Algorithms
23
18 Thur 3/19 Graph algorithm basics; BFS 24,25
19 Tue 3/24 Minimum spanning trees 24,25
20 Thur 3/26 Minimum spanning trees (cont.)
  • Problem set 4 assigned [Download] (covers lectures 18 - 23; due Thur 4/16 (Notice new deadline))
24, 25
21 Tue 3/31 Shortest paths 26
22 Thur 4/2 Flows and cuts 26
23 Tue 4/7 Flows and cuts (cont) 26
  Thur 4/9 No Class: Easter Break
  Tue 4/14 Midterm (covers only parts 1 and 2)
  • Midterm will be take home but timed during the normal class period. I will be online via Zoom to answer questions. An alternative timed period can be arranged for students who need accomodations. We will discuss more details as we get closer to this date.
 
Part 4: Computability and Complexity Theory
24 Thur 4/16 Decision problems and computability
  • Problem set 6 assigned (covers lectures 23 - 26; due Tue 4/28)
34
25 Tue 4/21 Complexity theory basics 34, 35
26 Thur 4/23 NP completeness 35
27 Tue 4/28 NP-completeness (cont); approximation algorithms (if time) 35