Analysis of Algorithms - CSCI 570, Fall 2012, Section 30252D

Analysis of Algorithms - CSCI 570, Fall 2012, Section 30252D

General Information

Time	:	Tu/Th 12:30am - 1:50am
Location	:	THH 212
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	:	Yuan Yao, E-mail: <yuanyao@usc.edu>, Office Hours: Thu 3pm-5pm in SAL 211
Grader	:	Ningchong Chen, E-mail: <ningchoc@usc.edu>. (The grader will hold office hours the week after the announcement of each assignment's grades.)
Midterm Exam	:	during class time, Thu, 11/1/2012 (firm)
Final Exam	:	11:00am - 1:00pm, Tue, 12/18/2012 (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 (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)

12/6/2011: 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 2 of Lecture 16 on 10/18/2012 to the last slide of Lecture 27 on 12/6/2012.
Here is a quick summary of the topics (not all topics covered are listed):
- Divide and Conquer
  - 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
    - image segmentation
    - project selection
    - baseball elimination
- HW4
  - maze generation
  - maze solutoin
- HW5
  - sudoku puzzle solution
  - sudoku puzzle generation

11/18/2012: I have an appointment with my physical therapist this coming Tuesday afternoon (11/20/2012). I'm sorry that I have to cancel office hour this Tuesday on 11/20/2012. Sorry about the inconvenience.

11/1/2012: Instructor is ill. Office hour today (Thu, 11/1) is canceled. Sorry about the inconvenience.

10/29/2012: I have to cancel office hours today (Mon, 10/29) and this Wednesday (10/31) due to physical therapy appointments. Sorry about the inconvenience.

10/25/2012: I'm still ill. I have to cancel office hour today (Thu, 10/25). Sorry about the inconvenience. If you have questions about HW3 the midterm, please see thet TA!

10/23/2012: I'm ill. I have to cancel lecture and office hour today (Tuesday, 10/23) and office hour tomorrow (Wednesday, 10/24). Sorry about the inconvenience. If you have questions about HW3, please see thet TA!

10/22/2012: Office hour today (Monday, 10/22) is canceled. Sorry about the inconvenience.

10/18/2012: 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 1 of Lecture 16 on 10/18/2012.
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
  - five 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
  - long-hand multiplication
  - long-hand division
- HW2
  - doubly-linked circular list
  - display
- HW3
  - binary search tree
    - insertion
    - deletion
  - AVL tree
    - global balance vs. local balance
    - insertion
    - deletion

10/15/2012: Lloyd Shapley won the Nobel Prize!

9/24/2012: Office hour this Wednesday (9/26) is canceled. Sorry about the inconvenience.

9/13/2012: There will be no row sheet to sign for this semester. The midterm exam is now worth 30%.

8/30/2012: Tu/Th office hours moved to 2:10pm - 3:00pm for the rest of the semester. Sorry about the inconvenience.

8/26/2012: I'm sorry that I have to cancel the first office hour of the semester (on Monday, 8/27). Sorry about the inconvenience.

8/23/2012:
- 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

CS 102L (Data Structures) or graduate standing. It is assumed that you know how to write programs in C/C++, and how to debug them and make them work correctly under the UNIX development environment.

Important Information about Programming Assignments

All graded 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!