Computer Science 463/810 (Detailed Information)

Introduction

This course shares lectures between Cmpt463, a senior undergraduate course, and Cmpt810, an introductory graduate course. Students taking the course un- der either number will need to complete several assignments, write examinations, and complete one larger project.

Staff

Instructor: Chris Dutchyn
email mailto:dutchyn@cs.usask.ca
web http://www.cs.usask.ca/faculty/cjd032
office Thorvaldson 286.10

Marker: Banani Roy
email mailto:bar156@mail.usask.ca

Meetings

We will be meeting in room Thorvaldson 205A, on Mondays, Wednesdays, and Fridays from 1:30 pm to 2:20 pm.

First instructional day is January 5, 2011. Last instructional day is April 8, 2011. Excepting mid-term break, holidays will not disrupt classes: no lectures will be held from February 21 to 27, 2011

The midterm examination will occur on February 18, during class time.

The final exam date will be scheduled by central timetabling, but will occur during the April 11 to April 30, 2011 window.

Instructor office hours are still undecided, but will be announced in class and on the course website. If the times announced do not suit, please contact the instructor to schedule a specific appointment. The TA will offer tutorial assistance in the Spinks help centre, according to their schedule.

Grading

Intangibles may count in the determination of your grade. Regular attendance and productive classroom participation may slightly ameliorate some weaknesses elsewhere; the converse is also true.

ItemDescriptionWeighting
Assignments(four@10%)40%
Project(one)15%
Midterm ExaminationFebruary 1815%
Final ExaminationApril 11–3030%
Total100%
Project

The project is essentially a larger assignment, planned to be either a game- search implementation (or other system as determined with the consultation and approval of the instructor). The final details will be discussed in class, during the latter part of the term.

Sitting In

Students can unofficially audit (sit-in on) the course. But they will be expected to attend regularly and actively participate in classroom discussion, They may also be asked to look up a topic and make a short presentation to the class, upon request of the instructor. Otherwise, they will be asked to absent themselves from the course.

Late Homework

If you turn in an assignment late, you must get the instructor’s permission to do this before the assignment deadline. When we do accept a late submission, we will use this formula to compute your net grade:

netGrade -- compute final grade based on unpenalized grade and lateness
fun netGrade rawScore lateDays = netGrade * (0.9 ^ lateDays)

Textbooks

Recommended
  • Algorithm Design, Jon Kleinberg and Eva Tard ́s, Addison-Wesley, 2005.
Supplemental
  • Problems on Algorithms 2ed., Ian Parberry and William Gasarch, avail- able online at http://www.eng.unt.edu/ian/books/free/poa.pdf.
  • Purely Functional Data Structures, Chris Okasaki, Cambridge University Press, 1999.

Software

I will primarily use a pseudocode which closely resembles functional program- ming languages like Haskell and SML/NJ, because it provides unmatched clarity and economy of expression. Students are recommended to do the same.

Topics

The order and depth with which the following topics are covered may still be altered.

  1. heaps and finger trees,
  2. recurrences
  3. efficiency (Banker’s and Physicist’s methods)
  4. linear programming
  5. network flows
  6. computational geometry
  7. parallel (and quantum, if time available) algorithms
  8. probabalistic/random algorithms
  9. security
  10. single and multiple agent search