Welcome to the Winter 2019/20 Term 2 edition of CPSC 320.
In this class you'll learn about useful problem-solving techniques, such as greedy algorithms, divide-and-conquer algorithms, and dynamic programming. You'll gain experience in judging how to apply these techniques to solve computational problems efficiently. You'll also learn about NP-complete problems, for which no efficient algorithms are known.
At the end of the course, you will be able to:
- Recognize which algorithm design technique, such as divide and conquer, greedy strategies, or dynamic programming is used in a given algorithm.
- For a given problem, evaluate which design technique and/or data structures can be used to solve the problem efficiently.
- Implement a solution to a problem using a specified algorithm design technique.
- Select and apply mathematical techniques, such as asymptotic notation or recurrence relations, to obtain good upper and lower bounds on the running time of algorithms.
- Recognize similarities between a new problem and problems that you have already encountered, and judge whether or not these similarities can be leveraged to design an algorithm for the new problem.
- Apply the theory of NP-completeness to provide evidence that certain problems may not have algorithms that are efficient on all inputs.
Following are the key resources you need for the course. Click on the People link above to learn more about your instructors and TAs. Click on the Course Work link to learn what work you will do in this course and how your learning will be evaluated.
Lectures
- Section 201:
- Lecture Time: Monday, Wednesday, Friday 10-11am
- Lecture Room: Woodward IRC 6
- Section 202:
- Lecture Time: Monday, Wednesday, Friday 4-5pm
- Lecture Room: LSK 200
Textbook
The required textbook is Algorithm Design by Jon Kleinberg and Éva Tardos (2005).
Online Tools
CS Ugrad account: If you do not already have an account, it should be set up soon after you register for the class. Associated with this account is your CSID. See here for more information. Make sure to activate your account right away, or you won't be able to submit homeworks on Gradescope. Don't wait until the homework deadline to discover this!
Gradescope:
Assignments will be collected on Gradescope.
Please check the e-mail associated with your CSID for a
Gradescope course invitation. Until the withdrawal deadline,
instructors will be running daily enrollment updates to Gradescope
using your CSID.
When using Gradescope, make sure to use your CS Ugrad email address.
Please note that this course uses Gradescope to facilitate the grading of exams and assignments.
Your @ugrad.cs.ubc.ca email alias (as listed
in https://www.cs.ubc.ca/getacct) is used to identify you on
Gradescope. As Gradescope is hosted outside Canada, we want to remind
you to keep your @ugrad alias private, just as you would any other
account information. If you choose not to keep your @ugrad alias
confidential, please note that UBC will proceed on the assumption that
you do not object to Gradescope potentially identifying you
personally, and that you are consenting to the storage of personal
information on Gradescope servers outside Canada.
Canvas: Review quizzes and grades are hosted here. You should able to access Canvas within 36 hours of registering for the class. Assignments and midterm exam marks can be found on GradeScope.
Piazza: Please register yourself. You will need an access code which will be announced in initial classes and can also be found on the Canvas home page. Use Piazza for communication with peers and course staff about class work, exams, etc. However, please exercise discretion that you do not directly discuss solutions to homeworks that are yet to be submitted. If you have any matter requiring private discussion, you can post privately on Piazza or e-mail the instructor.
Other Materials
-
Mathematics for Computer Science
by Eric Lehman, Tom Leighton and Albert Meyer. Free PDF.
This has great background material on proofs, induction, graphs, etc. - Kevin Wayne's slides based on the Kleinberg-Tardos book.
- Algorithms, etc. by Jeff Erickson. Free PDF.
- Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., and Stein, Clifford, Introduction to Algorithms, 3rd edition, 2009, ISBN 0-262-03384-4.
- Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, Algorithms, McGraw Hill Book Company, 2008, ISBN 0-07-352340-2.
- Michael Garey and David Johnson, Computers and Intractability: a Guide to the theory of NP-Completeness, W.H. Freeman & Company, 1979, ISBN 0-7167-1044-5.
The CS Reading Room has most of our references on reserve so that you can browse them in the room (but not checkout). You can find the Reading Room on the second floor of the older wing of ICCS, next to its central atrium.
Resources
-
Equity, Inclusion & Wellness. We hope that all students
will find this classroom to be a supportive environment, and the
course staff are here to help you do your best. Resources are available to help you in
times of illness or distress, please check them out and talk with
your instructors if we can be helpful.
- University Policy on Academic Integrity. All UBC students are expected to behave as honest and responsible members of an academic community. Make sure you understand UBC's academic integrity principles! Breach of UBC's policies with respect to academic honesty can result in serious disciplinary action.