

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


General Information


Time 
: 
TuTh 12:30am  1:50am 
Location 
: 
GFS 101 
Instructor 
: 
Bill Cheng
(for office hours, please see
instructor's web page),
Email:
<bill.cheng@usc.edu>.
(Please do not send HTMLonly emails. They will not be read.)

TA 
: 
Kai Song,
Email:
<kaisong@usc.edu>,
Office Hours: Mon 12pm2pm 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)



Class Resources


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.)



News

(in reversed chronological order)
 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
 maxflow problem
 FordFulkerson algorithm
 maxflows & mincuts
 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
 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 proposeandreject (GaleShapley) algorithm
 correctness (termination, perfection, stability)
 efficient implementation
 manoptimality
 womanpessimality
 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
 worstcase running time
 averagecase running time
 asymptotic order of growth
 upper bounds
 lower bounds
 tight bounds
 common running time
 O(n)
 O(n log n)
 O(n^{2})
 O(n^{3})
 O(n^{k})
 exponential time
 priority queues
 tournament sort
 heap sort
 maintaining a heap
 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.


Prerequisites

Graduate standing.


