Computer Science Problem Solving: Course Outline
General Information
Class:  T Th 12:3014:00 @ SCRF1024 
Coordinators: 
Ali Taleghani, Igor Naverniouk 

emails: 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 indepth 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, numbertheoretic
algorithms, computational geometry, graph algorithms, and string
parsing. Time permitting, we will look at NPcomplete and NPhard
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 email 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 online 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(*)  NPcomplete and NPhard 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 closedbook.

