CS 584/684 Algorithm Design & Analysis
Term: Spring 2014
CRN: 60936 (584), 60942 (684)
Meeting Time: Tue, Thu 12:00-13:15
Meeting Location: Neuberger (NH) 237
Instructor: Bart Massey (bart AT cs DOT pdx DOT edu)
Office Hours: By appointment
Office Location: FAB 120-18
TA: Simon Niklaus (simon DOT niklaus AT pdx DOT edu)
Prerequisites: CS 350 and its prerequisites CS 250, CS 251, CS 311 (or equivalents)
Everything about this syllabus is entirely tentative, and might be changed at the whim of the instructor without warning.
From the Course Catalog: An advanced in-depth study of the design and analysis of algorithms. Topics include models of computation, sorting, data structures, graph algorithms, matrix multiplication, fast Fourier transform, polynomial arithmetic, pattern matching, and NP-complete problems.
Note that this is not just an "in-depth" study or an "advanced" study, it is an "advanced in-depth" study. The successful student will be able to make contributions to computer science by understanding, analyzing, designing and communicating advanced algorithms.
In addition to the material contained in the course prerequisites mentioned above, you will need:
- Fluent technical English reading and authoring skills.
- Fluent pseudocode reading and authoring skills.
- Familiarity with mathematics at the college level, including trigonometry, geometry and calculus.
The only way to get good at analyzing and designing algorithms is to analyze and design good algorithms. In this course, in-class time will be split between traditional lecture and interactive activities. Keeping up with the required reading and working outside the classroom will be essential. The course will move quickly, and getting behind will be a disaster. Come prepared to work at learning.
Goals, Topics and Objectives
Upon the successful completion of this course students will be able to:
- Analyze most algorithms encountered in practice (at least roughly).
- Find a good algorithm to solve a problem.
- Use and understand asymptotic notation.
- Follow a correctness proof for an algorithm.
- Understand divide and conquer methods and dynamic programming.
- Understand the concept of amortized analysis.
- Describe the major sorting and searching algorithms and know their time complexity.
- Describe the meaning of NP-completeness.
- Know the process of proving a problem is NP-complete.
- Understand the idea of NP-approximation.
- Read papers describing algorithms in the computing literature.
- Write a paper clearly explaining a complex algorithm, using proper style and citations.
Cormen, Leiserson, Rivest and Stein
Introduction to Algorithms (3rd ed.)
McGraw Hill 2009
This is an expensive textbook, but I would encourage you to purchase it and keep it after the course ends. It is one of the standard references of our field, and something you will use regularly throughout your computing career.
This course is being run using the Moodle LMS. The course Moodle is at http://moodle.svcs.cs.pdx.edu/cs684. Please do not try to register for the Moodle until instructed.
To be enrolled in this course, you must have a valid, working @cs.pdx.edu or @pdx.edu email address. If you do not have one, get it promptly. If you need help forwarding your email from that address to someplace you read more frequently, contact the CAT.
Each student will be assigned an anonymized "'nym" on the first day of class. Students are asked to retain their 'nym and keep it private.
This course has weekly readings and weekly homework. Students will anonymously grade each other's work. In addition, each student will prepare a scholarly paper for submission. It is reasonable to expect 6-8 hours of effort outside of class each week.
All coursework must be completed individually unless otherwise explicitly specified. I do encourage group collaboration on individual assignments: creating study groups or online chat-rooms to discuss the approach and understand the problem is an acceptable and encouraged methodology. The write-up, programming, and actual solutions must be your individual work. If you represent someone else's work as your own, you are committing plagiarism.
Class attendance is required. There will routinely be in-class assignments; these will not be accepted late without advance notice or extraordinary circumstances. If you think you might miss more than a couple of class meetings of this course, I would encourage you to avoid this class for now.
There will be a midterm exam, a final exam, and in-class quizzes.
I will assign graded in-class homework during some meetings. I will also assign take-home homework almost every week, both as a study guide and as a part of your grade. Late homeworks will be accepted, if at all, only for good reasons and at a substantial penalty. Take-home assignments will be collected using the course website.
Assignments will primarily be anonymously peer-graded. Each week, each student will be assigned peer assignments for grading from the previous week. The instructor will serve as the ultimate reviewer and authority in all grading issues.
The current plan is to compute grades as follows:
Homework 50% Peer Grading 15% Midterm 10% Final 10% Paper 15%
However, this plan is tentative, and may change at any time.
There will be no make-up exams or homeworks except in a case of medical or family emergency. (The instructor reserves the right to request documentation in this case.) It is your responsibility to contact the instructor and arrange for special accommodations.
Cheating will result in a grade of zero on the affected material, and will be reported to appropriate authorities. A grade of zero on any assignment will result in a grade of F for the course. Plagiarism is a form of cheating. Please do not let me catch you plagiarizing.
Plagiarism: n 1: a piece of writing/work that has been copied from someone else and is presented as being your own work 2: the act of plagiarizing; taking someone's words or ideas as if they were your own.
If you use code, ideas, or text authored by someone else, cite them. It is OK to get help from external sources of knowledge, but citation is mandatory.
The current course schedule is always on the Moodle.