

Analysis of Algorithms 
CSCI 570, Fall 2013, Both Sections


General Information


Instructor 
Bill Cheng
(click to see office hours)
Email:
<bill.cheng@usc.edu>. (Please do not send HTMLonly emails. 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 ChienChun Hung,
Email:
<chienchun.hung@usc.edu>
Office Hours: Tu/Th 4pm  5pm in SAL 211

Hao Feng,
Email:
<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 
11am1pm, Thu, 12/12/2013 (firm).
 11am1pm, Tue, 12/17/2013 (firm)
in SLH 200.
SLH is located in section 6C of the
campus map.



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



News

(in reversed chronological order)
 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
 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
 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
 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 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
 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.


Prerequisites

Graduate standing.


