CS 584/684 Algorithm Design & Analysis

Term: Spring 2013
Credits: 3
CRN: 65317 (584), 65462 (684)
Meeting Time: Tue, Thu 12:00-13:15
Meeting Location: UTS 208

Instructor: Bart Massey (bart AT cs DOT pdx DOT edu)
Office Hours: Wed 14:30-17:30
Office Location: FAB 120-18

Prerequisites: CS 350 and its prerequisites CS 250, CS 251, CS 311, or equivalents

(Schedule)

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 a "wiki" and an email list. You will be registered manually for these with a password to be given to you later. The wiki is at <http://wiki.cs.pdx.edu/cs684> and the email list settings can be changed via <http://wiki.cs.pdx.edu/mailman/listinfo/cs684-spring2013>.

To be enrolled in the 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, as well as an initial password for the wiki and email list. 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 and a final exam, although the later may be waived in favor of an in-class paper presentation. There may also be 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

Your grade will be computed as follows:


   Homework      50%
   Peer Grading  15%
   Midterm       10%
   Final         10%
   Paper         15%

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

Ch 3
WDateTopicReadingHW DueGrading Due
12 AprilCourse Intro and Setup; Entrance EvalsCh 1, 2
14 AprilReading and Writing Algorithms
29 AprilAnalyzing Algorithms
211 AprilProving Algorithms Correcthw1
316 AprilAlgorithm Design Patterns
318 AprilAlgorithm Complexity and Performancehw2
423 AprilMark Jones: Trees and Balancing (PDF)hw1, hw2
425 AprilMidterm
530 AprilMemoization and Dynamic Programmingch. 15
52 MayString Matchingch. 32
67 MayAmortized Analysisch. 17
69 MayMatrix Operationsch. 28hw3
714 MayLinear Sorting and Order Statsch. 8,9
716 MayGraph Representations and Algs.ch. 22hw4hw3
821 MayGraph ColoringA. Kozowski and K. Manuszewski, Classical Coloring of Graphs, ch. 1 of Graph Coloring, ed. M. Kubale, AMS 2004
823 MayGraph Coloring (cont.)hw4
928 MayMaximum Flowch. 26
930 MayRandomizationch. 5.3, Fast Perfect Weighted Resamplinghw5
104 JuneState Space SearchEssentials of Artificial Intelligence, chs. 2-3, M. Ginsberg, MKP 1993
106 JuneQuickfire Design Competitionhw5