[ Announcements | Homeworks | Distributions | Slides ]

CSc 545 Design and Analysis of Algorithms
Review - on Tuesday 12/12 at GS906

Time and place MonWed 3:00-4:30, Gould-Simpson 906
Instructor Alon Efrat
alon@cs.arizona.edu
Gould-Simpson 720
(520) 621-8047
Office hours: TuesTh 3:00-4:00pm, or by an appointment.
Grader: Anurag Katiyar,
anuragk@email.arizona.edu
Description After a short illustration of algorithm design and analysis, the course begins with a brief review of basic analysis techniques (approximating functions asymptotically, bounding sums, and solving recurrences). Student are expected to have some familiarity with this material. After covering several topics related to data structures, we will study Amortized Analysis which is a common technique to bound the running time of algorithms which have the property that one of their operation might be computationally expensive, but their overall running time is still small. We will study several algorithms and data structures whose analysis require the use of this technique. We then study problems that are efficiently solvable, focusing on basic design techniques (divide-and-conquer, dynamic programming, and greedy). We present some graph algorithms (strongly-connected components, minimum spanning trees, shortest paths, and mainly maximum flow and its application). We will see how some of these, and similar algorithms can be used for the internet and other routing application We will survey some approximation algorithms, and branch-and-bound), as methods to handle intractability If time would permit, we will discuss other topics such as string matching and computational geometyr

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. The scope of the course will focus slightly more toward practical areas.

Hopmework Here.
Web resources Splay tree.
Notes Click Here
Newsgroup course.cs545
Required text Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, and Clifford Stein [CLR],
Introduction to Algorithms, second edition,
McGraw-Hill, Boston, 2001.
Optional text Dexter C. Kozen,
The Design and Analysis of Algorithms,
Springer-Verlag, New York, 1992.
Reserved books The optional text by Kozen will be put on reserve in the Main Library.
Syllabus The course is organized into several parts. After each topic below is the approximate number of lectures followed by chapter numbers from the text. Material not in the textbook [CLR] will be spread in the classroom.

I   Background

  • Introduction (2; 1, 2): illustration of algorithm design and analysis with the largest empty rectangle problem.
  • Analysis techniques (3; 3, 4, Appendix A): approximating functions asymptotically, bounding sums, solving recurrences.

II   Data structures

  • Augmenting data structures (1; 14) Maintaining order statistics synamicaly:
  • Hash Tables (1; 11) universal families of hash functions

III   Amortized Analysis and more data structures

  • Amortized analysis (1; 17): averaging, charging, and potential methods.
  • Splay trees (from a different text):
  • Fibonacci heaps (3; 20): maintaining a heap under merges and promotions of elements.
  • Disjoint sets (3; 21): maintaining a partition under unions.

IV   Design techniques

  • Divide and conquer (1; 9): finding the kth smallest.
  • Dynamic programming (2; 15): longest common subsequence, matrix-chain multiplication.
  • Greedy (3; 16): activity scheduling, Huffman coding.

V   Graph algorithms

  • Minimum spanning trees (2; 23): Prim's and Kruskal's algorithms.
  • Single-source shortest paths (1; 24): Dijkstra's and Bellman-Ford's algorithms.
  • All-pairs shortest paths (1; 25): Johnson's algorithm.
  • Maximum flow (2; 26): Goldberg and Tarjan's algorithm.
  • Routing and other applications to networks

    VI   Dealing with intractability

    • Reductions (1; 34): NP-completeness and polynomial-time reducibility.
    • Approximation algorithms, (2; 37): vertex cover, traveling salesman, set cover, and subset sum. Local ratio techniques.
    • Branch and bound (1): maximum cut.
    • Schedule There are two in-class exams.
    • Exam 1, Monday, November 6, during class time.
    • Exam 2, Wed Dec 13, 2:00-4:00.
    Grading 33%   Homeworks
    40%   Better Exam Grade
    27%   Lower Exam Grade

    Mapping numerical grading to a letter grade: Basically, 91-100 and up is mapped to 'A', 81-90 are mapped to 'B', 71-80 are mapped to 'C' etc. However, numerical grades which are close to the borderline (for example -89) might be mapped either way, based on parameters such as participation in discussions in class, originality in solving homework problems etc.
    Policies On homeworks 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. The online webpage of homeworks is here.

    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.

    Attendance would be checked during the first 2-3 weeks. Missing more than one class in this period might lead to an administrative drop from the class. After this period, attendance is not mandatory but recommended. However, it is your responsibility to know the material as it was taught in the class.

    [ Top | Department ]