TCSS 343, Spring2007
Algorithms

Instructor: Ed Hong
Email: edhong@u.washington.edu

Office: Pinkerton 310

Office Hours: MW 4 PM-5PM and by appointment


Telephone: (253) 692-4659

Meeting Times and Locations
Meets MW 7 PM -9:15 PM in Pinkerton 104

Course description
This class is about algorithms, both design and analysis. We will study algorithms for many standard problems, such as sorting, searching, and graph algorithms. Our algorithm study will focus on how to design algorithms, and on learning the "bag-of-tricks" of the various different design techniques. These include design paradigms such as divide-and-conquer, greedy, and dynamic programming. We will also analyze algorithms, using mathematical tools to determine the run-time efficiency of various algorithms, and to prove that particular algorithms do in fact correctly solve the problem. We also introduce complexity classes as a way of classifying problems.

Objectives

After taking this class, students should be able to:

  1. Determine the efficiency of basic algorithms.
  2. Identify the design paradigm used in an algorithm
  3. Prove the correctness of simple algorithms (including simple induction proofs for recursive algorithms).
  4. Write code that implements a wide variety of algorithms for standard problems, such as sorting, minimum spanning tree, depth first search, traveling salesman, etc.


Coursework and Evaluation
We will use the following book:
Introduction to the Design and Analysis of Algorithms., by Anany Levitin.

We will cover selections of the material in the book portion mostly in the order presented in the book. There will be weekly assignments; assignments will include both written problem solving and programming projects. There will be two midterms and one final. See the schedule for more details.

GRADING

  • Participation: 5%
  • Assignments: 25%
  • 2 Midterms: 35%
  • Final: 35%

Assignments turned in after the beginning of class on the due date will be considered late. Late assignments turned in up to 24 hours after the deadline will be assessed a 20% penalty. No late assignments after the 24 hour grace period will be accepted. Programming assignments must be turned in electronically using e-submit turn-in process. Written assignments should be turned-in during class; however, they may also be turned-in electronically if you obtain prior approval. 

Participation in class will be judged mostly upon the participation problems, assigned at least two days (48 hours) before class starts. It will also be judged secondarily on effort put into group activities, problem solving, and discussion done in class. The participation problem will be one simple problem based on the reading for the day and should be handed in before class starts. There will typically be one participation problem per week, on days that homework is not due. Participation problem solutions will not be graded; your grade depends on whether or not you have a reasonable attempt at the problem.


Code of Conduct

All work turned in is expected to be your own. Unacknowledged copying is plagiarism and is not acceptable!

Although students are encouraged to study together to understand the course content, each student is expected to produce his or her own solution to the homework problems, unless explicitly allowed otherwise. This means that mentors and fellow students may not write any part of any program or homework solution for you.

If you are not clear on whether some form of cooperation is allowed by these rules, don't guess ask the instructor first. Violations of these rules will be referred to the appropriate University authorities for disciplinary action.


Student Support Services

In addition to the traditional email and office hours, there are also many other ways to get help for this course; here are some of them.

CSS Mentors: The CSS mentors staff the labs throughout the week. They can provide help with specific questions about specific classes. Please note, however, that they will not do your homework for you. Instead, they will help you when you get stuck (either in programming or in homework) and help you develop the reasoning skills you need to solve future problems. See the CSS Mentors website for information about when the mentors are in the labs and other information. See css.tacoma.washington.edu/~lab/Mentors

If you would like to request academic accommodations due to a temporary or permanent disability, contact Lisa Tice, Manager for Disability Support Services (DSS) in the Mattress Factory Bldg, Suite 206. An appointment can be made through the front desk of Student Affairs (692-4400), through Student Services (692-4501), by phoning Lisa directly at 692-4493 (voice) or 692-4413 (TTY), or by e-mail ltice@u.washington.edu. Appropriate accommodations are arranged after you've conferred with the DSS Manager and presented the required documentation of your disability to DSS.