Computing and Software Systems 343, Winter 2003
Mathematical Principles of Computing II

Syllabus

Instructor: Ed Hong
Office: PNK 310
Office Hours: W 3:30 - 5:30 PM and by appointment
Email: edhong@u.washington.edu
Telephone: (253) 692-4659

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 one midterm and one final. No late assignments will be accepted. This means you should turn in however much you have done on the due date. 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: 10%
• Assignments: 30%
• Midterm: 25%
• Final: 35%

FINAL: Thursday, March 20 , 4:15 PM – 6:30 PM

Other Items

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