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 weeks | I/O, STL, java.util |
1 week | Brute force |
1 week | Dynamic programming and memoization |
Midterm 1 | |
2 weeks | Number theoretic algorithms |
3 weeks | Graph algorithms |
Midterm 2 | |
1 week | String parsing |
1 week | Computational 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.
|
|