| CSc 445 | Introduction to Algorithms |
| Homeworks: |
HW1
|
HW2
| HW3 | HW4 | HW5 | HW6 |
| Time and place |
TueThu 12:30-1:45, KOFFL 216
| |||||||||||||
| Instructor |
Alon Efrat
alon@cs.arizona.edu Gould-Simpson 742 (520) 626-8047 Office hours Mon 1:40-2:55. Wed 1:00-2:15. | |||||||||||||
| Assistant |
Nitin Shinde
nitinshinde@email.arizona.edu Gould-Simpson 721 Office hours Tuesday: 10:30 AM - 12:00 PM Thursday: 11:00 AM - 12:00 PM | |||||||||||||
| This course vs. CSc345 | Here is a list of relevant items from CSc345. Some topics you are expected to know in general. other are stricktly needed for this course and you are expected to validy that you master them. Finally, other topics are going to be (re)-discussed in this course. link. | |||||||||||||
| 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, greedy, and others), graph algorithms (minimum spanning
trees, shortest paths, maximum flow and stable marriage), and geometric algorithms
(convex hull, line sweep and closest point-pair) and other cool applications. 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. | |||||||||||||
| 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. | |||||||||||||
Resources
|
| Schedule
| There are two 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. Homeworks
| There are about seven homeworks, which occur roughly after the conclusion of each of the chapters. The homework with the lowest score will be ignored.
| 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 at least 2 of the homeworks.
More information is given in class.
|
Announcements:
|
Announcements are published on the D2L link
|
|