COSC 240 - Introduction to Algorithms (Fall 2018)

COSC 240 - Introduction to Algorithms

(Fall 2018)

Georgetown University

Prof. Calvin Newport

Monday and Wednesday, 12:30 - 1:45

St. Mary's Hall, Room 107

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 compexity theory. Time permitting additional advanced topics might be covered.

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 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 cn248@georgetown.edu. 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 some 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 often do not check 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.

Teaching Assistant

The teaching assistant for our class is Sam Balthazard (sjb265@georgetown.edu). He will primarily be responsible for helping with problem set grading. If there is enough demand from students, it is possible that he will also hold regular office hours to discuss the problem sets.

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:

  • You can work alone or with other people from the class on the problems. However: every student must hand in their own problem set solution written in their own words.
  • You are probably better off working alone, as this optimizes how well you learn the material, but I will not require this as it is too hard to enforce.
  • You may only discuss problems with me, your group members, or the course teaching assistant. 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.
  • 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 in advance for alternative submission procedures.
  • Problem sets not handed in by the beginning of lecture will be considered late, and 4 points will be deducted. Problem sets not handed until the day after the deadline will have 8 points 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 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 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 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 Wed 8/39 Introduction 1,2
  Mon 9/3 No class: Labor Day  
2 Wed 9/5 Tools: correctness proofs, step complexity and asymptotic analysis 2,3
3 Mon 9/10 Tools: Recurrences: recursion trees and master method 4
4 Wed 9/12 Tools: probabilistic analysis and randomized algorithms
  • Problem set 1 assigned (covers lectures 2 - 4; due Wed 9/19) [Download]
5,C
5 Mon 9/17 Divide and conquer: basic technique, mergesort, quicksort 2,7
6 Wed 9/19 Advanced sorting: randomized quicksort, linear-time sorting 7,8
7 Mon 9/24 Advanced sorting (cont.)
  • Problem set 2 assigned (covers lectures 5 - 7; due Mon 10/1)
7,8
Part 2: Advanced Data Structures and Design/Analysis Techniques
8 Wed 9/26 Search trees 12
9 Mon 10/1 Amortized analysis
  • Problem set 3 assigned (covers lectures 8 - 9; due Wed 10/10)
17
10 Wed 10/3 Dynamic programming (part 1) 15
  Mon 10/8 No class: mid-semester holiday  
11 Wed 10/10 Dynamic programming (part 2)
  • Problem set 4 assigned (covers lectures 10 - 13; due 10/22; note that this problem set covers last week and next week)
15
12 Mon 10/15 Greedy algorithms
  • Note: Due to professor travel, we will not meet in person for this lecture. Details on virtual lecture delivery method will be provided closer to this date.
16
13 Wed 10/17 Hashing
  • Note: Due to professor travel, we will not meet in person for this lecture. Details on virtual lecture delivery method will be provided closer to this date.
11
Part 3: Graph Algorithms
14 Mon 10/22 Greedy algorithms and hashing (cont.); Graph representation, graph search, topological sort 22
15 Wed 10/24 Graph representation, graph search, topological sort (cont.); start minimum spanning trees (if time)
  • Note: Extra office hours today from 2:00 to 4:00 for midterm related questions.
22
16 Mon 10/29 Midterm (covers parts 1 and 2)  
17 Wed 10/31 Minimum spanning trees 23
18 Mon 11/5 Minimum spanning trees (cont)
  • Note: Tomorrow is last day to withdraw
  • Problem set 5 assigned (covers lectures 14 - 18; due Mon 11/12)
24,25
19 Wed 11/7 Shortest paths 26
20 Mon 11/12 Flows and cuts 26
21 Wed 11/14 Flows and cuts (cont)
  • Problem set 6 assigned (covers lectures 20 - 21; due Mon 11/26)
34
Part 4: Computability and Complexity Theory
22 Mon 11/19 Decision problems and computability 34
23 Wed 11/21 Complexity theory basics  
24 Mon 11/26 NP completeness 34
25 Wed 11/28 NP completeness (cont)
  • Problem set 7 assigned (covers lectures 22 - 25; due Wed 12/5)
35
Part 5: Advanced Topics
26 Mon 12/3 Approximation algorithms  
27 Wed 12/5 Advanced topic (tbd.)  
28 Mon 12/10 Final exam review  
  12/13 to 12/21 Final Exam Period (date, time and room to be announced.)