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.
Analyze the running time and space complexity of algorithms.
Use the big Oh notation. (e.g., O(n lg n).)
Describe how to prove the correctness of an algorithm.
Use mathematical techniques, for example limits and sums of series, in complexity analysis.
Perform inductive proofs.
Solve recurrences using direct methods and using the Master Theorem.
Describe the notions of P, NP, NP-hard and NP-complete.
Compare the rates of growth of functions.
Apply algorithmic complexity principles in the design of programs.
Design algorithms using standard techniques such as divide-and-conquer and dynamic programming.
Introduction to the Design & Analysis of Algorithms, 2nd ed. Anany Levitin 2007, Pearson.
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.
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.
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%
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.
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.
—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.
(Thanks to Martin Cenek for these tips.)
Study a little every day, you cannot learn the material in a day...
Learn language - syntax, semantics, glossary of symbols and definitions.
Do lots of problems, and then some.
Do additional problems - ones that were not assigned.
Make study groups.
Make up your own problems and try to solve them.
Start early on the assignments and the lab experiments.
Review the topics frequently - not just the increments, review entire topics.
Read the assigned chapters and lab manual before each lecture.
Don't expect immediate success. Anything worthwhile takes time and effort