Instructor: James R. Glenn, Ph.D.
Office: office?
Office Phone: TBD
Office Hours: TBD
e-mail: [first name][dot][last name]@yale.edu

TF and ULAs: (see Ed Discussion for hours)

• John Lazarsfeld (TF)
• SK Bong
• Ryan Cain
• Peter Prastakos
• Vincent Schaffer
• Jeffrey Zhou

Course Webpage:
Ed Discussion: https://us.edstem.org/courses/3191/discussion/ (sign up through Canvas)

Class Meeting: Lecture Tue, Thu 2:30pm – 3:45pm on Zoom

Prerequisites: CPSC 202 and CPSC 223 or equivalent

Required Textbook:

• Algorithm Design by Jon Kleinberg and Éva Tardos ISBN 978-0321295354 (retail price $173.32)

Other Resources:

Catalog Description:
Paradigms for algorithmic problem solving: greedy algorithms, divide and conquer, dynamic programming, and network flow. NP completeness and approximation algorithms for NP-complete problems. Algorithms for problems from economics, scheduling, network design and navigation, geometry, biology, and optimization. Provides algorithmic background essential to further study of computer science.

Course Outcomes: Students will be able to

• use and adapt standard algorithms and data structures to design efficient solutions to problems
• reason about the correctness of algorithms
• explain the significance of the complexity classes $P$, $NP$, and $NP$-complete and determine to which a given problem belongs

Academic Dishonesty: Please see Yale College's general Undergraduate Regulations and regulations regarding Academic Integrity.

The implications for this course:

• Homework Assignments (from Dan Spielman's Spring 2017 version of CPSC365): You should strive to solve these problems on your own. But sometimes even understanding the problems poses a challenge. You are welcome to discuss the problems with your classmates to achieve understanding of the problems and to consider small examples. After you understand the problems, you should try to solve them on your own. If you need help, you can discuss the problems with the course staff. You may also ask others to find mistakes in your attempted solutions, and you may help find mistakes in your classmates' solutions. If you are truly stuck, you may discuss the problems with a few other students. If you do this, you must follow Stan Eisenstat's "Gilligan's Island Rule":

  When discussing an assignment with other students, you may write on a board or a piece of paper, but you may not take that or any other written or electronic record away from the discussion. Moreover, you must engage in a full hour of mind- numbing activity (e.g., watching back-to-back episodes of Gilligan's Island) before you work on the assignment again. This will ensure that you can reconstruct what you learned from the discussion, by yourself, using your own brain.

  You must write your solutions independently and report your collaborators for every problem set. Failure to list people with whom you have discussed a problem set is considered a violation of academic honesty.

  Similarly, if your solution draws on books or websites other than the required textbook and the course website then you must cite those sources as well. But it is a violation to access books or websites that offer complete solutions to the homework problems whether you cite those sources or not.

• Exams: each student must work individually.

Grading:

• Homework Assignments: 36%
• Exams: 64%

Schedule (subject to change):

Week of	Topics	Reading	Events
			Mon	Tue	Wed	Thu	Fri