Analysis of Algorithms - CSCI 570, Summer 2011, Session Two

Time	:	M/Tu/W/Th 10:00am - 11:40am
Location	:	ZHS 163
Instructor	:	Bill Cheng (for office hours, please see instructor's web page), E-mail: <bill.cheng@usc.edu>.   (Please do not send HTML-only e-mails. They will not be read.)
TA	:	(TBD)
Grader	:	(TBD)
Midterm Exam	:	during class time, Thu, 7/28/2011 (New Date)
Final Exam	:	10am-11:40am, Tue, 8/9/2011 (firm)

Description	:	textbooks, topics covered, grading policies, additional resources, etc.
Lectures	:	slides from lectures in HTML and PDF formats
Participation	:	rules about rowcalls.
Homeworks	:	homework assignments (please also see important information about programming assignments at the bottom of this page.)
Newsgroup	:	Google Group for discussing course materials and programming assignments. (This group is by invitation only.)

• 8/4/2011: The final exam will be closed book, closed notes, and closed everything (and no "cheat sheet"). Also, no calculators, cell phones, or any electronic gadgets are allowed. Please bring a photo ID. Your ID will be collected at the beginning of the exam and will be returned to you when you turn in your exam. There will be assigned seating.

  The final exam will cover everything from slide 18 of Lecture 14 on 7/25/2011 to the last slide of Lecture 20 on 8/4/2011.

  Here is a quick summary of the topics (not all topics covered are listed):

  • Divide and Conquer
    • merge sort
    • recurrence relations
    • counting inversions
    • closest pair of points
    • integer multiplication
    • matrix multiplication
    • convolution
    • FFT
  • Dynamic Programming
    • weighted interval scheduling
    • memoization vs. iteration over subproblems
    • segmented least squares
    • knapsack problem
    • RNA secondary structure
    • sequence alignment
    • sequence alignment in linear space
    • shortest paths
    • distance vector protocol
    • negative cycles in a graph
  • Network Flow
    • network flow basics
    • max-flow problem
    • Ford-Fulkerson algorithm
    • max-flows & min-cuts
    • choosing good augmenting paths
    • applications
      • bipartite matching
      • disjoint paths
      • circulation with demands
      • survey design
      • airline scheduling
  • HW3
    • maze generation
    • maze solutoin

• 7/25/2011: The midterm exam will be closed book, closed notes, and closed everything (and no "cheat sheet"). Also, no calculators, cell phones, or any electronic gadgets are allowed. Please bring a photo ID. Your ID will be collected at the beginning of the exam and will be returned to you when you turn in your exam. There will be assigned seating.

  The midterm exam will cover everything from the beginning of the semester till slide 5 of Lecture 14 on 7/25/2011.

  Here is a quick summary of the topics (not all topics covered are listed):

  • Some Representative Problems
    • stable matching and the propose-and-reject (Gale-Shapley) algorithm
      • correctness (termination, perfection, stability)
      • efficient implementation
      • man-optimality
      • woman-pessimality
      • weak Pareto optimality
      • deceit
    • give representative problems
      • interval scheduling
      • weighted interval scheduling
      • bipartite matching
      • independent set
      • competitive facility location
  • Basics of Algorithm Analysis
    • running time analysis
      • polynomial running time
      • worst-case running time
      • average-case running time
    • asymptotic order of growth
      • upper bounds
      • lower bounds
      • tight bounds
    • common running time
      • O(n)
      • O(n log n)
      • O(n²)
      • O(n³)
      • O(n^k)
      • exponential time
    • priority queues
      • tournament sort
      • heap sort
        • building a heap
        • output
      • maintaining a heap
        • insertion
        • deletion
      • implementing priority queues with heaps
  • Graphs
    • representation
    • paths, connectivity, trees
    • paths, connectivity, trees
    • connected components
    • testing bipartiteness
    • directed graphs
    • directed acyclic graphs
    • topological sort
  • Greedy Algorithms
    • interval scheduling
    • schedule all intervals
    • schedule to minimize lateness
    • optimal caching
    • finding shortest path
      • Dijkstra's algorithm
    • coin changing
    • selecting breakpoints
    • minimum spanning tree
      • cycles
      • cuts
      • cut sets
      • Kruskal algorithm
      • Prim's algorithm
      • clustering
  • HW1
    • doubly-linked circular list
    • display
  • HW2
    • binary search tree
      • insertion
      • deletion
    • AVL tree
      • global balance vs. local balance
      • insertion
      • deletion

• 6/30/2011: My office hours have been moved. After lectures, I will stay in ZHS 163 to hold office hours. I will set the time for the office hour to be from 11:40am to 12:30pm. As soon as no one is left to ask questions, I will leave ZHS 163 and head for my office (SAL 228). If you need to talk to me about something that you don't feel comfortable to discuss in front of others, you can talk to me when I walk back to my office or you can make an appointment.

• 6/25/2011:
  • Registering with the class mailinglist is required for this class. This is not the same as the class discussion Google Group. You will be receiving HW and exam scores through this list via individual e-mails. If you have not done so, please visit the mailinglist page after the semester starts. (You do not have to be registered for the course to register with the class mailinglist.) In the registration confirmation e-mail, you will also get your user ID and password for accessing protected area of this web site.

  • Watch this area for important announcements.

If a student signs up late for this class, he/she is still required to turn all projects and homeworks on time or he/she will receive a score of 0 for these assignments. No exceptions!