CS 584/684 Algorithm Design & Analysis

Term: Spring 2014
Credits: 3
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)

Disclaimer

Everything about this syllabus is entirely tentative, and might be changed at the whim of the instructor without warning.

Description

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.

Prerequisites

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.

Philosophy

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:

1. Analyze most algorithms encountered in practice (at least roughly).
2. Find a good algorithm to solve a problem.
3. Use and understand asymptotic notation.
4. Follow a correctness proof for an algorithm.
5. Understand divide and conquer methods and dynamic programming.
6. Understand the concept of amortized analysis.
7. Describe the major sorting and searching algorithms and know their time complexity.
8. Describe the meaning of NP-completeness.
9. Know the process of proving a problem is NP-complete.
10. Understand the idea of NP-approximation.
11. Read papers describing algorithms in the computing literature.
12. Write a paper clearly explaining a complex algorithm, using proper style and citations.

Textbook

Cormen, Leiserson, Rivest and Stein
Introduction to Algorithms (3rd ed.)
McGraw Hill 2009
ISBN 978-0-262-03384-8

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.

Course Communication

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.

Course Work

Workload

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.

Collaboration

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.

Attendance

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.

Exams

There will be a midterm exam, a final exam, and in-class quizzes.

Homework

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.

Grading

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.

Make-ups

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.

Academic Honesty

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.
—www.dictionary.com

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.

Schedule

The current course schedule is always on the Moodle.