CSc 545 | Design and Analysis of Algorithms
| ||
Time and place | Fall 2012 Monday and Wednesday, 1:30-2:45pm Gould-Simpson 906 | ||
Dates |
| ||
Instructor |
John Kececioglu kece@cs.arizona.edu Gould-Simpson 739 (520) 621-4526 | ||
Grader |
Mark Tokutomi tokutomi@email.arizona.edu | ||
Office hours | Mondays 3:00-4:00pm Tuesdays 3:30-4:45pm and by appointment | ||
Description |
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),
basic graph algorithms
(minimum spanning trees, shortest paths, maximum flow, maximum matchings),
and basic string algorithms
(exact string matching).
We conclude with techniques for dealing with intractability
(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. | ||
Prerequisites | CSc 445 and CSc 473 | ||
Required text |
Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, and Clifford Stein, Introduction to Algorithms, third edition, McGraw-Hill, Boston, 2009. | ||
Optional text |
Jon Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley, Boston, 2006. | ||
Reserved books | The optional text by Kleinberg and Tardos will be put on reserve in the Main Library. | ||
Syllabus |
The course is organized into seven parts.
After each topic below is the approximate number of lectures
followed by chapter numbers from the text.
I Background
II Design techniques
III Amortized data structures
IV Graph algorithms
V String algorithms (optional)
VI Linear programming (optional)
VII Intractability
| ||
Exams | There are two exams and an optional final. The final is comprehensive and optional. Students attending the final must take it. | ||
Homeworks |
There are five homeworks, the last of which is optional.
| ||
Grading |
Grades are determined from a weighted average of the percentage of points earned on homeworks and exams. The weights depend on whether the final is taken. Attaining a weighted score of at least 90% guarantees an A in the course, at least 80% guarantees a B, at least 70% guarantees a C, and at least 60% guarantees a D. These thresholds may be lowered, but will not be raised. The awarding of points on homework and exam questions is roughly according to the following scheme. Having the right solution idea and the right technical execution of this idea earns at least 90%. (Only a perfect write-up that cannot be improved earns 100%.) Having the right idea but with errors in its execution is at least 80%. Having the wrong idea and errors in its execution, but demonstrating comprehension of the material, is at least 70%. Having the wrong idea, errors in execution, and deficiencies in comprehension, is roughly 60%. Work that shows no understanding is roughly 50%. On homework and exam questions, writing an answer that relates to the question guarantees at least 50% of the points for the question (which is a failing percentage). No points are awarded for writing nothing. Homeworks may contain bonus problems. Points earned on bonus questions are not added to points for required questions. Bonus points are tallied separately at the end of the semester, and considered subjectively as a measure of effort when deciding whether to move up a student who is near a letter-grade boundary. | ||
Policies |
For the overall course grade, the instructor reserves the right to give a grade of D or E to a student whose weighted average on the exams is a D or an E. On homework, only very-high-level ideas can be discussed with others; any details relevant to the solution cannot be discussed among a group. Your submitted solutions must represent your individual work alone. Use of solutions from previous offerings of this course or other courses is not permitted. Any material from the Internet that is used in a solution must be cited by its URL; to not cite it is plagiarism, which is considered cheating. (For more information, see the Department of Computer Science Course Policy on Collaboration and the University Code of Academic Integrity.) When turning in solutions to homeworks, write only on one side of the paper, start each problem on a separate page, put the problems in the correct order, and staple the pages together. Neatness, and especially conciseness, is required to earn the highest marks. If a problem eludes solution, state this up front and write down only what you know to be correct. Rambling at length about attempts that didn't succeed may result in more points being deducted. Homework that is late (submitted after the due date and time) is not accepted. The grade on the last optional homework may be used to replace the lowest prior homework grade. Requests for regrading homeworks or exams must be submitted within one week of receiving the graded homework or exam. The exams during the semester are in-class. The final at the end of the semester is in-class, comprehensive, and optional. There are no makeup exams. On missing an exam, the final may be used to replace one missed exam; grades will then be computed as if taking two exams and no final. 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. | ||
Distributions | Grade distributions are available here. | ||
Grades | Scores in the course, posted by student CSID, are available here. | ||
Announcements |
The current course grades are posted above. The distributions of grades for Homework 4, Homework 5, the Final Exam, and the Overall Course Score, are posted above. If you'd like to learn about algorithms applied to bioinformatics problems in computational biology, you might consider attending the department's Bioinformatics Seminar. |