Analysis of Algorithms - CSCI 570, Fall 2013, Both Sections

Instructor	Bill Cheng (click to see office hours) E-mail: <bill.cheng@usc.edu>.  (Please do not send HTML-only e-mails. They will not be read.)
	AM Section	PM Section
Time	TuTh 9:30am - 10:50am	TuTh 12:30pm - 1:50pm
Location	SLH 102	ZHS 352
TA	Michael Chien-Chun Hung, E-mail: <chienchun.hung@usc.edu> Office Hours: Tu/Th 4pm - 5pm in SAL 211	Hao Feng, E-mail: <haofeng@usc.edu> Office Hours: Fri 3pm - 5pm in SAL 219
Midterm #1	during class time, Thu, 10/10/2013 (firm).	during class time in MHP 106, Thu, 10/10/2013 (firm),  MHP is located in section 6B of the campus map.
Midterm #2	during class time, Thu, 11/14/2013 (firm).	during class time in MHP 101, Thu, 11/14/2013 (firm),  MHP is located in section 6B of the campus map.
Final Exam	11am-1pm, Thu, 12/12/2013 (firm).	11am-1pm, Tue, 12/17/2013 (firm) in SLH 200.   SLH is located in section 6C of the campus map.

Description	:	textbooks, topics covered, grading policies, additional resources, etc.
Lectures	:	slides from lectures in HTML and PDF formats
Participation	:	rules about rowcalls.
Homeworks	:	written homework assignments (please note that there is no programming assignments in this class)
Newsgroup	:	Google Group for discussing course materials. You are required to be a member of this group. (This group is by invitation only.) Please note that this Google Group currently does not exist. It will be created after the first lecture.

• 12/5/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 an 8.5in by 11in paper. (You can use both sides if you want but it must be a single sheet of 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.

  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 1 of Lecture 19 on 10/31/2013 to the last slide of Lecture 27 on 12/5/2013. Please also be familiar with the notes on exams, covered in slides 1 through 13 of Lecture 11 on 10/1/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

• 12/5/2013: The statistics for Midterm #2 (AM section) are:

       Count = 72
         Avg = 43.77
      StdDev = 12.27
         Max = 67.00
         Min = 9.50
  
     2 66+ XX
     1 63+ X
     6 60+ XXXXXX
     3 57+ XXX
     5 54+ XXXXX
     2 51+ XX
     8 48+ XXXXXXXX
     9 45+ XXXXXXXXX
     8 42+ XXXXXXXX
     5 39+ XXXXX
     8 36+ XXXXXXXX
     1 33+ X
     3 30+ XXX
     5 27+ XXXXX
     3 24+ XXX
     0 21+ 
     1 18+ X
     1 15+ X
     0 12+ 
     1  9+ X

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

• 12/5/2013: The statistics for Midterm #2 (PM section) are:

       Count = 72
         Avg = 46.19
      StdDev = 8.64
         Max = 65.00
         Min = 30.50
  
     3 63+ XXX
     3 60+ XXX
     2 57+ XX
     8 54+ XXXXXXXX
     7 51+ XXXXXXX
     7 48+ XXXXXXX
     9 45+ XXXXXXXXX
    11 42+ XXXXXXXXXXX
     4 39+ XXXX
    10 36+ XXXXXXXXXX
     4 33+ XXXX
     4 30+ XXXX

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

• 11/25/2013: Office hour today will end at 2:45pm. Sorry about the inconvenience.

• 10/31/2013: The 2nd midterm exam will be closed book, closed notes, and closed everything (and no "cheat sheet"). You will not be permitted to use your own paper when working on exam problems. 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 14 of Lecture 11 on 10/1/2013 till the last slide of Lecture 18 on 10/29/2013. Please also be familiar with the notes on exams, covered in slides 1 through 13 of Lecture 11 on 10/1/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
    • shortest path algorithms
      • 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

• 10/24/2013: The statistics for Midterm #1 (AM section) are:

       Count = 72
         Avg = 35.73
      StdDev = 10.33
         Max = 59.00
         Min = 13.00
  
     2 57+ XX
     1 54+ X
     3 51+ XXX
     6 48+ XXXXXX
     3 45+ XXX
     7 42+ XXXXXXX
     3 39+ XXX
    10 36+ XXXXXXXXXX
    11 33+ XXXXXXXXXXX
     6 30+ XXXXXX
     5 27+ XXXXX
     5 24+ XXXXX
     6 21+ XXXXXX
     2 18+ XX
     0 15+ 
     2 12+ XX

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

• 10/24/2013: The statistics for Midterm #1 (PM section) are:

       Count = 72
         Avg = 41.28
      StdDev = 11.25
         Max = 60.00
         Min = 15.00
  
     2 60+ XX
     3 57+ XXX
     7 54+ XXXXXXX
     5 51+ XXXXX
     8 48+ XXXXXXXX
     4 45+ XXXX
     7 42+ XXXXXXX
     6 39+ XXXXXX
    10 36+ XXXXXXXXXX
     3 33+ XXX
     6 30+ XXXXXX
     5 27+ XXXXX
     1 24+ X
     0 21+ 
     2 18+ XX
     3 15+ XXX

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

• 10/8/2013: Office hour this Thursday (10/10/2013) is canceled. Sorry about the inconvenience.

• 10/1/2013: The first midterm exam will be closed book, closed notes, and closed everything (and no "cheat sheet"). You will not be permitted to use your own paper when working on exam problems. 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 the last slide of Lecture 10 on 9/26/2013. Please also be familiar with the notes on exams, covered at the end of Lecture 11 on 10/1/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

• 8/25/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.