Analysis of Algorithms - CSCI 570, Spring 2013, Section 30097D

Time	:	TuTh 12:30am - 1:50am
Location	:	GFS 101
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	:	Kai Song, E-mail: <kaisong@usc.edu>, Office Hours: Mon 12pm-2pm in SAL 235
Grader	:	(none)
Midterm #1	:	during class time, Thu, 2/28/2013 (firm)
Midterm #2	:	during class time, Thu, 4/11/2013 (firm)
Final Exam	:	2:00pm - 4:00pm, Wed, 5/15/2013 (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
Newsgroup	:	Google Group for discussing course materials and programming assignments. (This group is by invitation only.)

• 4/30/2013: [BC: updated 5/13/2013] The final exam will be closed book, closed notes, and closed everything, except for a single "crib sheet / cheat sheet". You can write or print whatever you want on it on one side of an 8.5in by 11in paper. Magnifying glasses are not allowed, so don't print too small! You will be required to turn in the cheat sheet together with the exam paper.

  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 36 of Lecture 17 on 3/14/2013 to the last slide of Lecture 26 on 4/25/2013. (Chapter 8 of K&T is outside of the scope of the final exam.) Please also be familiar with the notes on exams, covered in slides 45 through 55 of Lecture 11 on 2/19/2013.

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

  • Dynamic Programming (K&T Ch 6)
    • 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 (K&T Ch 7)
    • 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
      • image segmentation
      • project selection
      • baseball elimination

• 4/29/2013: The statistics for Midterm #2 are:

       Count = 17
         Avg = 62.88
      StdDev = 13.59
         Max = 88.00
         Min = 44.00
  
     1 87+ X
     0 84+ 
     1 81+ X
     2 78+ XX
     1 75+ X
     0 72+ 
     1 69+ X
     1 66+ X
     1 63+ X
     1 60+ X
     1 57+ X
     0 54+ 
     4 51+ XXXX
     1 48+ X
     1 45+ X
     1 42+ X

  Since the maximum possible score is 90, to get your normalized score (i.e., normalized to 100 points), you need to divide your score by 90 and then multiply by 100. (The same goes with the class average. Therefore, the normalized class average is 62.88/0.9=69.87.)

• 3/25/2013: The 2nd 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 2nd midterm exam will cover everything from slide 19 of Lecture 9 on 2/12/2013 to slide 35 of Lecture 17 on 3/14/2013. Please also be familiar with the notes on exams, covered in slides 45 through 55 of Lecture 11 on 2/19/2013.

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

  • Greedy Algorithms (K&T Ch 4)
    • 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
    • huffman codes and data compression
  • Divide and Conquer (K&T Ch 5)
    • merge sort
    • recurrence relations
    • counting inversions
    • closest pair of points
    • integer multiplication
    • matrix multiplication
    • convolution
    • FFT

• 3/6/2013: The statistics for Midterm #1 are:

       Count = 17
         Avg = 58.82
      StdDev = 12.61
         Max = 81.00
         Min = 39.00
  
     1 81+ X
     3 78+ XXX
     0 75+ 
     0 72+ 
     0 69+ 
     0 66+ 
     1 63+ X
     1 60+ X
     1 57+ X
     5 54+ XXXXX
     1 51+ X
     0 48+ 
     2 45+ XX
     1 42+ X
     1 39+ X

  Since the maximum possible score is 84, to get your normalized score (i.e., normalized to 100 points), you need to divide your score by 84 and then multiply by 100. (The same goes with the class average. Therefore, the normalized class average is 58.82/0.84=70.02.)

• 2/21/2013: The first 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 first midterm exam will cover everything from the beginning of the semester till slide 18 of Lecture 9 on 2/12/2013. Please also be familiar with the notes on exams, covered at the end of Lecture 11 on 2/19/2013.

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

  • Some Representative Problems (K&T Ch 1)
    • stable matching and the propose-and-reject (Gale-Shapley) algorithm
      • correctness (termination, perfection, stability)
      • efficient implementation
      • man-optimality
      • woman-pessimality
      • weak Pareto optimality
      • deceit
    • five representative problems
      • interval scheduling
      • weighted interval scheduling
      • bipartite matching
      • independent set
      • competitive facility location
  • Basics of Algorithm Analysis (K&T Ch 2)
    • 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 (K&T Ch 3)
    • graph representations
    • paths, connectivity, trees
    • graph traversal, breadth first search
    • connected components
    • testing bipartiteness
    • directed graphs
    • directed acyclic graphs
    • topological sort

• 2/14/2013: Office hour today is canceled. Sorry about the inconvenience.

• 1/24/2013: Office hour today is cut short (from 2pm to 2:15pm). Sorry about the inconvenience.

• 1/10/2013:
  • To get your user ID and password for accessing protected area of this web site, please visit the request access page after the semester starts and submit the requested information. (You do not have to be registered for the course to get the password.)

  • Watch this area for important announcements.