Analysis of Algorithms - CSCI 570, Spring 2010, MW Section

Analysis of Algorithms - CSCI 570, Spring 2010, MW Section

General Information

Time	:	MW 10:30am - 11:50am (although on the schedule of classes, it says that this class starts at 10:00am). Starting on Wednesday, 1/20/2010, class time will be 10:30am - 11:50am as indicated.
Location	:	THH 210
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: Tu 9am - 11am in SAL 235
Grader	:	Jun Hao, E-mail: <haojun@usc.edu>. (The grader will hold office hours the week after the announcement of each homework assignment's grades.)
Midterm Exam	:	during class, Wed, 3/10/2010 (firm) in ZHS 159 (ZHS/SCI is located in section 6D of the campus map)
Final Exam	:	8am-10am, Mon, 5/10/2010 (firm) in MHP 101 (MHP is located in section 7D 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	:	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.)

News

(in reversed chronological order)

5/3/2010: The TA's final office hour for this semester will be from 1:30pm to 3:30pm in SAL 235 on 5/4/2010.

4/28/2010: 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 16 of Lecture 14 on 2/25/2010 to the last slide of Lecture 26 on 4/28/2010.
Here is a quick summary of the topics (not all topics covered are listed):
- Divide and Conquor
  - 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
    - project selection
    - baseball elimination
- HW3
  - maze generation
  - maze solutoin
- HW4
  - sudoku puzzle solution
  - sudoku puzzle generation

4/19/2010: A review session for the final exam has been scheduled for 2-3pm on Monday, 5/3/2010 in GFS 116. (GFS is located in section 5C of the campus map) You are not required to come to the review session. I'm hoping that this may be helpful in preparing for the final exam.

4/4/2010: Office hour tomorrow (Monday, 4/5/2010) has been canceled. Sorry abou the inconvenience.

3/3/2010: 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 15 of Lecture 14 on 3/3/2010.
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

1/19/2010: Starting tomorrow, our class will meet between 10:30am and 11:50am.
1/19/2010: If you do not know the user ID and password for accessing protected part of the class web site, please registering with the class mailinglist. In the registration e-mail, you will get the user ID and password that you are looking for.

1/7/2010: [ This item is obsoleted. Please see note above for 1/19/2010. ]
On the schedule of classes, it says that this class starts at 10:00am and ends at 11:50am. In actuality, the lecture time for this class is 80 minutes per class meeting. Therefore, lectures will end at 11:20am.

1/7/2010: Registering with the class mailinglist is required for this class. If you have not done so, please visit the mailinglist page. (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.

1/7/2010: Watch this area for important announcements.

Prerequisites

CS 102L (Data Structures) or graduate standing. It is assumed that you know how to write programs, and how to debug them and make them work correctly.

Important Information about Programming Assignments

All homework assignments are programming assignments to be done in C/C++. No other programming language will be accepted and your program must compile and run with a Makefile on nunki.usc.edu. (Sorry, no Java.) You must be familiar with the UNIX development environment (vi/pico/emacs, cc/gcc or g++/CC, make, etc.)

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!