Computing and Software Systems 343, Spring 2003
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. 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: 25%
• 2 Midterms: 30%
• Final: 35%

FINAL: Thursday June 12, 10:30 AM - 12:45 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 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