nb-algs-winter2018/ syllabus

NB Foundations: Algorithms

Term: Winter 2018
Credits: 6
Course Number: CS 299
Section: 4
CRN: 44956
Meeting Time: Mon, Wed 10:15-13:50
Meeting Location: Fourth Avenue Building (FAB) 88-10

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

Teaching Assistant: Sascha Strand (sastrand AT pdx DOT edu)
TA Office Hours: Here
Office Hours Location: CS Department Fishbowl

Disclaimer

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

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 informally how to prove the correctness of an algorithm.
  • Use mathematical techniques, for example limits and sums of series, in complexity analysis.
  • Solve recurrences 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

Algorithm Design Manual (2nd ed)
Stephen S. Skiena Springer 2008

The course textbook has some strong points and weak points which will be discussed in class. A supplementary text which may be useful is

Algorithms (1st ed)
Sanjoy Dasgupta, Christos Papdimitriou, Umesh Vazirani
McGraw-Hill 2008

While there are free online PDFs of this text to be found, I cannot verify that these are legal, authorized publications.

Course Communication

Communications for this course will primarily be through the Slack workspace psu-nb-algs-winter2018.slack.com. An invite to this workspace has been emailed to you. Everyone is strongly encouraged to participate in the channel.

Course Work

Course Format

This is a "laboratory" course. A typical session will involve two hours of lecture and two hours of directed in-class study and exploration.

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 be weekly in-class assignments; these will not be accepted late without advance notice or extraordinary circumstances.

Examinations

There may be one or more in-class midterm examinations: there will be a final examination.

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.

Homework

Submit your homework to the TA as an emailed PDF (no other format will be accepted).

I will assign graded in-class homework each meeting. 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.

You may submit a homework 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 up until they are graded.

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:

    Out-of-class Homework             35%
    In-class Homework                 35%
    Exams                             30%

A grade of zero on any one assignment or exam will result in a grade of zero for the entire course.

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.