CPSC490 - Problem Solving in Computer Science

Course Outline

General Information

Class:T Th 12:30-14:00 @ Dempster 301
Coordinator: Frank Chu, Igor Naverniouk
e-mails: fpmchu{at}gmail{dot}com, igor{at}cs{dot}ubc{dot}ca
Supervisor: Prof. George Tsiknis
Text (optional): Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms
Website: http://www.ugrad.cs.ubc.ca/~cs490/

About the Course

Objectives: After completing this course, you will have:
- Acquired an in-depth understanding of a variety of algorithms
Focus will be on theoretical basis and efficient implementation.
- Mastered practical programming skills
- Developed a useful personal code library
We will be implementing a large number of algorithms common to many programming projects.
Contents: We will begin with a practical overview of input/output methods in C++ and Java. The C++ Standard Template Library is then reviewed with focus on streams and useful data structures. To motivate our discussion of more efficient algorithms, we will take a brief look at brute force solutions to some common problems. We follow with a discussion of dynamic programming, memoization, number-theoretic algorithms, computational geometry, graph algorithms, and string parsing. Time permitting, we will look at NP-complete and NP-hard problems and efficient ways of using brute force methods to solve these problems.
Resources:

We will be using an automated judging software. Students will submit their problem solutions to the judge and automatically receive feedback as to the correctness and efficiency of their source code. After the submission deadline, we will collect the submissions from the automated judge for marking.

A similar automated judge, along with a large problem archive of over 1000 problems, is available on the University of Valladolid (Spain) website at http://acm.uva.es/p. This on-line judge can be used as an additional testing tool for the students' submissions.

The textbook is available in the bookstore and is the course textbook used in CPSC320 and CPSC420. Either of the two editions will be sufficient.

Assessment: The final grades will be determined from the following components:
Weekly problem sets:40%
Two midterms:20%
Final exam:40%
Homework:

There will be a problem set assigned every week. Students will have one week to submit their solutions to the automated judge. Solutions producing the correct output for the test data are deemed correct, but extremely inefficient solutions will not be accepted. Incorrect solutions will be judged manually for part marks.

The main focus of the homework problems is to test students' understanding of the algorithms involved and their ability to implement the algorithms correctly and efficiently. Marking will be based on accuracy, conciseness and elegance. Commenting your code is not required.

You will receive a 30% deduction on your grade for each subsequent day that you have submitted an assignment late, up to two (2) days. No assignments will be accepted afterwards.

Schedule: Except for the midterms, the schedule is tentative. Students will have a chance to alter the direction of the course if they would like a specific topic covered over another.
2 weeksI/O, STL, java.util
1 weekBrute force
1 weekDynamic programming and memoization
Midterm 1
2 weeksNumber theoretic algorithms
3 weeksGraph algorithms
Midterm 2
1 weekString parsing
1 weekComputational geometry
1 week(*)NP-complete and NP-hard problems
Academic Conduct: In accordance with the official department policy, plagiarism will not be tolerated. You may discuss the approach you used to solve a problem with your fellow students. However, this discussion must not involve any coding details, only the approach used. The code you submit must be written by you entirely, with the possible exception of code provided by the instructor, or short snippets from language reference sites, such as the SGI C++ reference. Both midterms and the final exam will be closed-book.