Computer Science Problem Solving: Course Outline

General Information

Class:T Th 12:30-14:00 @ SCRF1024
Coordinators: Ali Taleghani, Igor Naverniouk
e-mails: ali{at}math{dot}ubc{dot}ca, igor{at}lexansoft{dot}com
(optional) Text: Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms

About the Course

Objectives: After completing this course, you will have:
- Acquired an in-depth understanding of a variety of algorithms
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 datastructures. 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.

We will be using an automated judging software. The students will submit their problem solutions to the judge by e-mail and 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 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:20%
Two midterms:20%
Final exam:30%

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.

Late assignments will be accepted during a period of one week after the deadline with a penalty of 50%. Solutions that are mostly correct and on time will receive higher marks than late submissions.

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
Plagiarism: In accordance with the official department policy, plagiarism will not be tolerated. You are welcome to collaborate on the weekly assignments, provided you acknowledge your partners. For the quizzes, you will be allowed to use printed copies of your own code. Both midterms and the final exam will be closed-book.