| CSc 445 | Introduction to Algorithms |
| Time and place | Tue Thu 2:00-3:15pm, ARCHITECTURE
103 | ||||||||||||||||||||||||||||||||||||||||||||
| Review Session (before the final exam)
| Tues May 5/10/2005
5:30-7:30, at BIO W Room: 208
| Discussion session
| Mon 7:30-8:50pm,
FCS 101
| Instructor
| Alon Efrat | alon@cs.arizona.edu Gould-Simpson 747 (520) 626-8047 Assistants
| Pooja Vaswani | pooja@cs.arizona.edu Gould-Simpson 721 Office hours
|
|
Description |
After a short illustration of algorithm design and
analysis, the course begins by reviewing 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, greed, and amortization),
graph algorithms (minimum spanning trees, shortest paths, maximum flow and stable marriage),
string algorithms (on- and off-line string matching), and
geometric algorithms (convex hull, line sweep and closest point-pair). We
conclude with techniques for dealing with approximation algorithms
and branch-and-bound algorithms.
| The emphasis is on learning algorithm design (the ability to synthesize correct and efficient procedures for new combinatorial problems), acquiring an algorithm repertoire (a toolbox of classic algorithms for well-solved problems), and applying algorithm reduction (the ability to reduce new problems to known problems from your repertoire). These skills are developed through written assignments containing challenging exercises. Prerequisites |
CSc 342, and CSc 344. |
Required text |
Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, and
Clifford Stein, | Introduction to Algorithms, second edition, McGraw-Hill, Boston, 2001. Optional text
| Steven S. Skiena, | The Algorithm Design Manual, Springer-Verlag, New York, 1998. Reserved books
| Both texts will be put on reserve
in the Main Library.
| Other resources |
| Syllabus
| Click
Here
| Schedule
| There are two in-class exams.
|
Grading
|
|
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. The attendance policy is that you are allowed one unexcused absence in the first week, two unexcused absences in the first four weeks, and four unexcused absences in the first eight weeks. On exceeding these limits, you may be dropped from class. Roll is taken at the start of class with a sign-in sheet; if your signature is not on the roll sheet, it counts as an absence. Homeworks
| There are seven homeworks, the last of which is optional,
which occur roughly after the conclusion of each of the chapters.
| Honor projects
|
Any students (including non-honors) can commit to be involved in a research project.
The grade of the project would substitute 20% of the final grade, and the student can skip 2 of the homeworks.
More information is given in class.
| Distributions
|
| Grade distributions are available here. Newsgroup
|
cs.course445 For help in registering with the group,
Click Here
|
Announcements:
|
Dear Ms. Ezell:
|