| CSc 545 | Design and Analysis of Algorithms |
| Time and place | MW 1:30-2:45pm, Gould-Simpson 701 |
| Instructor |
Alon Efrat alon@cs.arizona.edu Gould-Simpson 720 (520) 621-8047 |
| Office hours | MoWe 3:00-3:50pm, and by appointment. |
| Grader TBA | |
| Description |
After a short illustration of algorithm design and analysis,
the course begins with a brief review of basic
analysis techniques
(approximating functions asymptotically, bounding sums,
and solving recurrences).
We then study problems that are efficiently solvable, focusing on
basic design techniques
(divide-and-conquer, dynamic programming, and greed),
advanced data structures
(amortized analysis, Fibonacci heaps, and disjoint sets),
and basic graph algorithms
(strongly-connected components, minimum spanning trees, shortest paths,
and maximum flow).
We conclude with techniques for dealing with intractability
(reductions, approximation algorithms, and branch-and-bound).
The emphasis throughout is on algorithm design: the ability to synthesize correct and efficient procedures for new combinatorial problems. This skill is developed through written assignments containing challenging exercises. The scope of the course will focus slightly more toward practical areas. |
| Hopmework |
Homework #1 (+ solution) Homework #2 (+ solution) Homework #3 (+ solution) Homework #4 (+ solution) Homework #5 (+ solutions) Homework #6 Homework #7 (optional) |
| Web resources | Splay tree: Java Applet, and another one. Also, some Notes by Roger Whitney. Stable Marrige Demo . |
| Notes | Click Here |
| Newsgroup | course.cs545 |
| Prerequisites | CSc 445, CSc 473, and Math 362. |
| Required text |
Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, and Clifford Stein [CLR], Introduction to Algorithms, second edition, McGraw-Hill, Boston, 2001. |
| Optional text |
Dexter C. Kozen, The Design and Analysis of Algorithms, Springer-Verlag, New York, 1992. |
| Reserved books | The optional text by Kozen will be put on reserve in the Main Library. |
| Syllabus |
The course is organized into several parts.
After each topic below is the approximate number of lectures
followed by chapter numbers from the text.
Material not in the textbook [CLR] will be spread in the classroom.
I Background
II Design techniques
III Amortized data structures
IV Graph algorithms
V Dealing with intractability
|
| Schedule |
There are two in-class exams.
|
| Grading |
33% Homeworks 40% Better Exam Grade 27% Lower Exam Grade Mapping numerical grading to a letter grade: Basically, 91-100 and up is mapped to 'A', 81-90 are mapped to 'B', 71-80 are mapped to 'C' etc. However, numerical grades which are close to the borderline (for example -89) might be mapped either way, based on parameters such as participation in discussions in class, originality in solving homework problems etc. |
| Policies |
On homework, you may discuss general ideas with friends, but your
solutions must be written up separately and represent individual work.
Use of solutions from previous offerings of the course is not
permitted.
Homework is due at the start of class; homework turned in once
class begins is not accepted.
When you turn in solutions to homeworks and exams, write only
on one side of the paper, and staple your pages together.
Neatness, and especially conciseness, is required
to earn the highest marks.
If you cannot solve a problem,
state this in your write-up,
and write down only what you know to be correct;
rambling at length about ideas that don't quite work
may cause additional points to be deducted. Attendance would be checked during the first 2-3 weeks. Missing more than one class in this period might lead to an administrative drop from the class. After this period, attendance is not mandatory but recommended. However, it is your responsibility to know the material as it was taught in the class.
|