Tapasya Patki
tpatki@email.arizona.edu
Gould-Simpson 710C
(520) 621-4089

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.

I   Background

• Introduction (3; 1, 2): illustration of algorithm design and analysis with the maximum-sum subarray problem.
• Analysis techniques (4; 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, matrix-chain multiplication.
• Greed (2; 16): activity scheduling, Huffman coding.
• Amortization (2; 17): potential functions, splay trees.

III   Graph algorithms

• Fundamental algorithms (2; 22): depth- and breadth-first search, topological sorting, strongly-connected components.
• 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 (3; 26): Goldberg and Tarjan's algorithm.

IV   String algorithms

• On-line string matching (2; 32): Knuth-Morris-Pratt's algorithm.
• Off-line string matching (2; outside material): suffix trees.

V   Geometric algorithms

• Fundamental algorithms (4; 33): Line-segment intersection, convex hull, closest point-pair.

VI   Intractability

• Approximation algorithms (4; 37): vertex cover, traveling salesman, set cover.
• Branch and bound (3; outside material): traveling salesman, maximum cut.

VII   Linear programming (optional)

• Modeling and solution (4; 29): applications, duality, simplex algorithm.

• Exam 1: March 5 (solutions).
• Exam 2: April 23.
• Final (optional): May 12, 11:00am-1:00pm.

• Homework 1, due January 29 (solutions).
  
• Homework 2, due February 12 (solutions).
  
• Homework 3, due February 23 (solutions).
  
• Homework 4, due March 26 (solutions).
  
• Homework 5, due April 9 (solutions).
  
• Homework 6, due April 16 (solutions).
  
• Homework 7 (optional), due May 5.
  

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

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.

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, very-high-level ideas can be discussed with friends, but solutions must represent individual work and must be written up separately. Use of solutions from previous offerings of the course 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.

Grade distributions are available here.

Student scores, listed by CS ID number, are available here.

The scores for students in the course are now available above.