| CSc 445 | Introduction to Algorithms |
| Announcements: |
Review for the exam - Monday May 07, 6:30 pm at GS 701. Leonard has supplemental office hours from 1:00-3:00 Monday (5/7) and Tuesday (5/8). Ask lingering questions, and also pick up your HW6. Optional HW8 is due by Monday, 4:45PM, in one of our (Leonard's, Andrew's, or Dr Efrat's) mailboxes in the CS mailroom (on the 7th floor). | |||||||||||||||||||||
| Time and place | Mon, Wed 3:00-4:15, Gould-Simpson 906
| |||||||||||||||||||||
| Instructor | Alon Efrat alon at cs.arizona.edu Gould-Simpson 742 (520) 626-8047 | |||||||||||||||||||||
| Assistants |
Andrew Predoehl
predoehl at cs.arizona.edu Gould-Simpson 710-A
Leonard D. Brown
| |||||||||||||||||||||
| 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. More details about the course are here. | |||||||||||||||||||||
| 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. Harry R. Lewis, Larry Denenberg Data Structures and Their Algorithms Addison Wesley 1991. | |||||||||||||||||||||
| Reserved books | Both texts will be put on reserve in the Main Library. | |||||||||||||||||||||
Other 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. 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 about seven homeworks. The lowest grade will be dropped. Homework
will be given roughly after the conclusion of each of the chapters.
The list of homeworks is here.
| 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 4
of the homeworks. The grade of the project will determine %25 of the final course grade, and also you can skip 3 of the homeworks.
More information is given in class.
| Distributions
|
| The scores can be found here. The summary of the scores can be found here. ListServ
|
csc445 at listserv.arizona.edu. The mailing list is used for class announcements from Instructor and TAs. For help in subscribing with the mailing list,
Click Here
| Newsgroup
|
cs.course445. The course newsgroup should be used for questions of general interest. For help in reading and posting news.
Click Here
|
Announcements:
|
|
|
| |