[ Announcements | Homeworks | Distributions ]



CSc 545 Design and Analysis of Algorithms

Time and place Fall 2012
Monday and Wednesday, 1:30-2:45pm
Gould-Simpson 906
Dates
August 20
September 3
November 12
December 5
  First class
  Labor Day holiday
  Veterans Day holiday
  Last class
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

  • Introduction (1; 1, 2): review of concepts of algorithm design and analysis.
  • Analysis techniques (3; 3, 4, Appendix A): approximating functions asymptotically, bounding sums, solving recurrences.

II   Design techniques

  • Divide and conquer (1; 9): finding the kth smallest.
  • Dynamic programming (2; 15): longest common subsequence, optimal static search-tree.
  • Greed (2; 16): activity scheduling, Huffman coding.

III   Amortized data structures

  • Amortized analysis (2; 17): averaging, charging, and potential methods.
  • Splay trees (optional) (1): maintaining a search tree without balance information.
  • Fibonacci heaps (2; 20): maintaining a heap under merges and promotions of elements.
  • Disjoint sets (optional) (1; 21): maintaining a partition under unions.

IV   Graph algorithms

  • Minimum spanning trees (2; 23): Prim's and Kruskal's algorithms.
  • Single-source shortest paths (2; 24): Dijkstra's and Bellman-Ford's algorithms.
  • All-pairs shortest paths (1; 25): Johnson's algorithm.
  • Maximum flow and minimum cut (3; 26): Goldberg and Tarjan's algorithm.
  • Maximum matchings (1): Fredman and Tarjan's algorithm for bipartite matchings.

V   String algorithms (optional)

  • Exact string matching (1; 32): Knuth-Morris-Pratt's algorithm.

VI   Linear programming (optional)

  • Simplex algorithm (1; 29): Solving linear programs by Dantzig's algorithm.

VII   Intractability

  • Approximation algorithms (2; 37): vertex cover, traveling salesman, set cover, and subset sum.
  • Branch and bound (optional) (1): maximum cut.
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.

Without the final          
25%   Homeworks
37%   Exam 1
38%   Exam 2
With the final
25%   Homeworks
20%   Exam 1
20%   Exam 2
35%   Final
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.



[ Top | Department ]

http://www.cs.arizona.edu/classes/cs545/fall12/
John Kececioglu (kece@cs.arizona.edu)
20 December 2012