Syllabus
CS 350 Algorithms and Complexity
Term: Summer 2014
Credits: 4
CRN: 81514
Meeting Time: Tue, Thu 14:15-16:35
Meeting Location: Engineering Building (EB) 103
Instructor: Bart Massey (bart AT cs DOT pdx DOT edu)
Office Hours: Wed 11:00-12:00, 13:00-14:00
Office Location: FAB 120-18
Instructional Technology Assistant: Gabriel Stauth (gstauth@pdx.edu)
Office Hours: Tuesday, Thursday 13:00-14:00
Prerequisites: CS 250, 251, 311
Disclaimer
Everything about this syllabus is entirely tentative, and maybe be changed at the whim of the instructor without warning.
Description
This course describes techniques for the design and analysis of algorithms. The course utilizes case studies of existing algorithms (e.g. 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: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.
Textbook
Foundations of Algorithms (5th ed.), Richard E. Neapolitan. Jones & Bartlett Learning 2015.
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
Workload
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.
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.
Test and Testing Policy
There will be an in-class final examination, and may be an in-class midterm and/or quizzes.
Homework
I will assign graded in-class homework during some meetings. I will also assign take-home homework most 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 for having been turned in and having made a reasonable effort, as well as for a reasonable degree of correctness. We will go through some of the problems during the class, as a part of the learning experience.
Grading
Your grade will be computed as follows:
Final 35%
Homework 50%
Quizzes etc 15%
Make-ups
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.
—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.
Study Guide
(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