CS41: Algorithms — Fall 2017

Schedule | Grading | Course Policies | Resources

This is the syllabus for the 11:30 section with Bryce Wiedenbeck, and may differ slightly from that of the 10:30 section with Lila Fontes.

Announcements

  • Welcome to algorithms!

Course Information

Class: MWF 11:30–12:20am SCI 181
Lab C: Fri 2:15–3:45pm Clothier 016
Lab D: Fri 3:00–5:30pm Clothier 016

Office Hours: Mon 12:30–2:00, Wed 12:30–4:00 SCI 262
Piazza Forum: piazza.com/swarthmore/fall2017/cs412
Required Textbook: Algorithm Design, by Kleinberg and Tardos (K&T)
Supplemental: Introduction to Algorithms, by Cormen, Leiserson, Rivest, Stein (CLRS)

Please make a note of the office hour times and the Piazza link. Take advantage of them to ask a question if something I said in lecture didn't make sense, or you're stuck on homework, or for any other reason. If you want to talk in person but can't make it during office hours, you can send me an email to set up alternate time, or just drop by any time my door is open. I'm always happy to answer questions, but it's up to you to come and ask.


Course Overview

This class explores algorithmic design and analysis in a more formal approach than CS21 or CS35. Algorithmic problems arise in many diverse areas of computer science. Often, one must take open ended, abstract, real-world problems and extract a clean mathematical problem that can be approached algorithmically. Designing a solution requires knowing the rules and common techniques of the model of computation used. Multiple models represent various abstractions of real computer systems and may result in very different solutions. Regardless of the model however, good algorithmic design requires careful analysis of complexity and proofs of correctness. Topics covered include asymptotic notation, graph algorithms, greedy algorithms, divide and conquer, dynamic programming, NP-completeness, approximation algorithms, and randomized algorithms.

Goals for the course

By the end of this course, you will have developed the following knowledge and skills:

Schedule

WEEK DAY ANNOUNCEMENTS TOPIC & READING LABS     
1

Sep 04

  Course introduction
Stable matching
read: K&T chapter 1
set up github

Lab 1

Sep 06

 

Sep 08

 
2

Sep 11

  Analysis
read: K&T chapter 2.1-2.4
Lab 2

Sep 13

 

Sep 15

Drop/add ends

3

Sep 18

   

Sep 20

  Graph algorithms
read: K&T chapter 3

Sep 22

 
4

Sep 25

 

Sep 27

 

Sep 29

  Greedy algorithms
read: K&T chapter 4
5

Oct 02

 

Oct 04

 

Oct 06

  Divide and conquer
read: K&T chapter 5
6

Oct 09

 

Oct 11

 

Oct 13

 
 

Oct 16

Fall break

Oct 18

Oct 20

7

Oct 23

  Dynamic programming
read: K&T chapter 6

Oct 25

midterm 7-10pm (tentative)

Oct 27

 
8

Oct 30

  Intractability
read: K&T chapter 8.1-8.4; see also CLRS chapter 34

Nov 01

 

Nov 03

 
9

Nov 06

 

Nov 08

 

Nov 10

CR/NC/W Deadline

Network flow
read: K&T chapter 7.1-7.3; see also CLRS chapter 26
10

Nov 13

  Network flow (continued)
read: K&T chapter 7.5, 7.9
Linear programming & the simplex algorithm

Nov 15

 

Nov 17

 
11

Nov 20

  Approximation algorithms
read: K&T chapter 11.1-11.4, 11.6, 11.8; see also CLRS chapter 35

Nov 22

 

Nov 24

Thanksgiving break

12

Nov 27

  Approximation algorithms
read: K&T chapter 11.1-11.4, 11.6, 11.8; see also CLRS chapter 35 (continued)

Nov 29

  Local search
read: K&T chapter 12.1, 12.2, 12.4, 12.5

Dec 01

  Randomized algorithms
read: K&T chapter 13.1-13.5
13

Dec 04

 

Dec 06

 

Dec 08

  Miscellaneous fun topics: the master theorem, Arrow's impossibility theorem, hat puzzles, etc.
14

Dec 11

Last day of classes (Dec 12)

Course review
 

Dec 23

Final Exam (time not yet announced)
registrar schedule



Grading

Grades will be weighted as follows:
45%Homework Assignments
25%Midterm Exam
25%Final Exam
5%Class and Lab Participation


Course Policies

Homework Assignments

Most lab assignments will consist of in-class exercises and will not be graded. Expect roughly ten homework assignments during the semester. You'll be able to work with a partner on several but not all of them; each homework assignment will specify if working with a partner is allowed.

Written homework will typically go out Friday afternoon and be due the next Thursday. We should have around 10 homework assignments. The initial couple of homeworks will be individual assignments; after the first few weeks, you'll be able to work with a partner. You must write your solutions in LaTeX and submit .tex files using git. Resources for LaTex are here.

Extra Credit Policy. In many of the homework assignments, there will be one or two extra credit problems. These problems are completely optional -- do not feel obligated in any way to complete these problems. Extra credit will not be directly applied to your overall grade; at best, they will be used to make up some credit lost by not handing in assignments on time. Please contact me if you have questions about the extra credit policy.

Late Policy. Each student will be given 3 late days for the semester. This will encompass any reason---illness, interviews, paper deadlines, hackathons, etc. For partnered assignments, both students need to have late days to use them. If only one partner has late days remaining, you cannot use late days for the assignment. Once you use up your late days, further late assignments will not be accepted except in very unusual extreme circumstances. Even if you do not fully complete a lab assignment you should submit what you have to receive partial credit.

You do not need to notify my ahead of time to use late day(s). Instead, email me when you have pushed your completed solution.

Student Responsibilities

CS41 covers material that is similar to what you saw in CS35 or CS21. However, the perspective is much different, and what you will be learning is different too. This course is much more about learning how to solve computational problems and analyze your solution(s), and less about implementing algorithms that we've gone over in class. To succeed in this course, you should consistently do the following:

Academic Integrity

Note: in the following paragraphs, "code" refers to all homework solutions, including written programs but also proofs, analysis, written reports, etc.

Academic honesty is required in all your work. Under no circumstances may you hand in work done with (or by) someone else under your own name. Your code should never be shared with anyone; you may not examine or use code belonging to someone else, nor may you let anyone else look at or make a copy of your code. This includes, but is not limited to, obtaining solutions from students who previously took the course or code that can be found online. You may not share solutions after the due date of the assignment.

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else's code or let anyone else read your code. All code you submit must be your own with the following permissible exceptions: code distributed in class, code found in the course text book, and code worked on with an assigned partner. In these cases, you should always include detailed comments that indicates on which parts of the assignment you received help, and what your sources were.

Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook: "Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."

Please contact me if you have any questions about what is permissible in this course.


Academic Accommodations

If you believe that you need accommodations for a disability, please contact Leslie Hempling in the Office of Student Disability Services (Parrish 113) or email lhempli1@swarthmore.edu to arrange an appointment to discuss your needs. As appropriate, she will issue students with documented disabilities a formal Accommodations Letter. Since accommodations require early planning and are not retroactive, please contact her as soon as possible. For details about the accommodations process visit Student Disability Services. You are also welcome to contact me privately to discuss your academic needs. However, all disability-related accommodations must be arranged through the Office of Student Disability Services.


LaTeX Resources

Writing homework solutions in LaTeX is required for this course. It is also a good skill to learn. If you plan on going to graduate school and/or publishing papers in the future, you will end up writing in latex.

For most latex files, you should be able to compile a latex file using e.g. 'pdflatex foo.tex'. As with other compilable programs like C++, you might get some compilation errors.

The following links have good latex resources and tutorials.