[an error occurred while processing this directive]
TCSS 343A, Winter 2005
Mathematical Principles of Computing II

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

Office: Pinkerton 310
Office Hours: MW 2-3 PM, and by appointment
Telephone: (253) 692-4659

Meeting Times and Locations
Meets MW 4:15 PM -6:30 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. When studying algorithms, we will focus on how to design algorithms, and the basic 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:
Algorithm Design: Foundations, Analysis, and Internet Examples, by Michael T. Goodrich and Roberto Tamassia.
Note that corrections to the book can be found listed in the errata, found at this website: http://www.algorithmdesign.net/errata.html

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: 40%
  • Final: 30%

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. All late assignments may be turned in via e-submit into the " late assignments " folder. Participation in class will be judged upon effort put into group activities and problem solving done in class, as well as on participation in discussion and on asking questions.


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.