Computing and Software Systems 343, Spring 2004
Mathematical Principles of Computing II

Syllabus

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.

Course 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.

Topics Covered

1. Mathematical tools, including pseudo-code, asymptotic notation, proofs.
2. Basic data structures.
3. Sorting, searching, selection problems.
4. Design paradigms: Divide & Conquer, greedy, dynamic programming.
5. Graph Algorithms
6. Text processing algorithms
7. Introduction to NP-Completeness

Course Work and Evaulation

We will be covering a good portion of the topics in the book more or less in order presented. There will be weekly assignments. Some will be programming projects, others will be mathematical problem solving homework. There will be two midterms and one final. Assignments turned in after the beginning of class (4:15 PM) on the due date will be considered late. Late assignments turned in up to 48 hours after the deadline will be assessed a 20% penalty. No late assignments after the 48 hour grace period will be accepted. 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.

GRADING

• Participation: 5%
• Assignments: 20%
• 2 Midterms: 40%
• Final: 35%

FINAL: Wednesday June 9, 4:15 PM - 6:30 PM

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.

Other Items

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 Science Building, Suite 102. 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 you've conferred with the DSS Manager, and presented the required documentation of your disability to DSS.