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.
|
|
| Resources: |
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 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: | 20% |
| Quizzes: | 30% |
| Two midterms: | 20% |
| Final exam: | 30% |
|
| 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.
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.
|
| Schedule: |
| 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 |
|
| 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.
|
|