Instructor: James R. Glenn, Ph.D.
Office: AKW 013
Office Phone: TBD
Office Hours: Tue 4-6pm and Thu noon-2pm, or by appointment, or drop by and see if I'm in
e-mail: [first name][dot][last name]@yale.edu

TF and ULA Hours: See Piazza

• TBD

Course Home Page:
Piazza Page: https://piazza.com/yale/spring2018/cpsc365/home

Class Meeting: Lecture Tue, Thu 2:30 – 3:45pm in DL 220

Prerequisites: CPSC 202 and CPSC 223 or equivalent

Required Textbook:

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

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 Undergraduate Regulations and Definitions of Plagiarism, Cheating, and Documentation of Sources.

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 web sites other that the required textbook and the course website then you must cite those sources as well.

• Exams: each student must work individually.

Grading:

• Homework Assignments: 75%
• In-Class Exams: 25% (Thu Mar 1 and Thu Apr 26 during regular class period, both in Davies Auditorium)

Schedule (approximate and subject to change):

---