CS 350 Algorithms and Complexity

Term: Spring 2011
Credits: 4
CRN: 65214
Meeting Time: Mon, Wed 16:40-18:30
Meeting Location: The Broadway (BHB) 222

Instructor: Bart Massey (bart AT cs DOT pdx DOT edu)
Office Hours: By email appointment
Office Location: FAB 120-18

Prerequisites: CS 250, 251, 311


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


This course describes techniques for the design and analysis of algorithms. The course utilizes case studies of existing algorithms (sorting, searching, graph algorithms, dynamic programming, matrix multiplication, the Fast Fourier Transform). NP-completeness is discussed.

Goals, Topics and Objectives

This course will explore a group of useful algorithmic techniques which can be used to solve common problems. Students will master tools and principles for analyzing the time and space used by these algorithms. The course will include case studies of existing algorithms, such as sorting, searching, graph algorithms, greedy programming, string alignment and approximation algorithms. NP-complete sets and approximation algorithms for some languages in NP will be introduced. Upon the successful completion of this course students will be able to:


Introduction to the Design & Analysis of Algorithms, 2nd ed. Anany Levitin 2007, Pearson.

Course Communication

This course is being run using the Moodle open-source web Learning Management System software. Details of schedule, and news and announcements will be posted there, assignments will be distributed and collected there, etc. In addition, the course email list will be created from the information there.

It is thus vitally important that you register on this site at http://svcs.cs.pdx.edu/moodle promptly at the beginning of the quarter. Instructions will be given in class as to how to do this. Anyone who fails to register by the start of the second week of class will be summarily dropped from the course.

Course Work


This course requires weekly readings and both in-class and out-of-class homework. 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.

Test and Testing Policy

There will be in-class midterm and final examinations, as well as (potentially) in-class quizzes.


I will assign graded in-class homework during some meetings. I will also assign take-home homework many weeks, 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. You may submit as many times as you like, with the latest assignment received being the only one considered for a grade. Please submit something before the deadline, even if it is only your name—you can then continue to work on your assignment as desired.

Assignments will be graded only for having been turned in and having made a reasonable effort; the solutions will not be carefully checked. We will go through some of the problems during the class, as a part of the learning experience.


Your grade will be computed as follows:

   Homework     35%
   Midterm      25%
   Final        40%
A grade of zero on any one assignment or exam will result in a grade of zero for the entire course.


There will be no make-up exams 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 on homework or exams will result in a grade of zero on the affected material, and will be reported to appropriate authorities. 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.

Study Guide

(Thanks to Martin Cenek for these tips.)