Analysis of Algorithms - CSCI 570, Fall 2010, TuTh Section

General Information
Time   :   TuTh 12:30pm - 1:50pm
Location : THH 208
Instructor   :   Bill Cheng (for office hours, please see instructor's web page), E-mail: <>.   (Please do not send HTML-only e-mails. They will not be read.)
TA   :   Yuan Yao, E-mail: <>, Office Hours: WF 4pm - 5pm in SAL 229
Grader   :   Xinxin Wu, E-mail: <>(The grader will hold office hours the week after the announcement of each assignment's grades.)
Midterm Exam   :   during class time in MHP 101, Thu, 10/21/2010 (firm),  MHP is located in section 7D of the campus map.
Final Exam   :   11am-1pm, Tue, 12/14/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.)
(in reversed chronological order)
  • 12/4/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 1 of Lecture 17 on 10/26/2010 to the last slide of Lecture 27 on 12/2/2010.

    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
    • HW3
      • maze generation
      • maze solutoin
    • HW4
      • sudoku puzzle solution
      • sudoku puzzle generation

  • 10/28/2010: The statistics for Midterm Exam are:
             Count = 52
               Avg = 50.18
            StdDev = 11.50
               Max = 70.00
               Min = 15.00
           2 69+ XX
           1 66+ X
           2 63+ XX
           4 60+ XXXX
          10 57+ XXXXXXXXXX
           3 54+ XXX
           6 51+ XXXXXX
           5 48+ XXXXX
           4 45+ XXXX
           5 42+ XXXXX
           3 39+ XXX
           2 36+ XX
           0 33+ 
           1 30+ X
           1 27+ X
           2 24+ XX
           0 21+ 
           0 18+ 
           1 15+ X

    Please read the following carefully!

    The TA (Yuan Yao, <>) graded your exam. The exam will not be returned back to you. If you would like to discuss your exam, please make an appointment with the TA for a 15-minute timeslot for the following four days:

             Friday, 10/29/2010: 3:00pm-5:00pm, SAL 229
          Wednesday, 11/03/2010: 3:00pm-5:00pm, SAL 229
             Friday, 11/05/2010: 3:00pm-5:00pm, SAL 229
          Wednesday, 11/10/2010: 3:00pm-5:00pm, SAL 229

    If you are not available during the above time frame, please make an appointment. The deadline for discussing about your exam will be 11/23/2010 (right before Thanksgiving holiday).

    Please remember that the coverage between the midterm and final exams will not overlap. So, if the only reason you want to discuss your midterm exam is because you are concerned that the same problem will be asked in final exam, then you really don't need to discuss your midterm exam!

    Here are some important rules:

    1. You must have an exam appointment in order for you to see and discuss your exam. This applies even during the TA's office hours.

    2. Also, if you make an appointment and do not show up, and do not cancel 30 minutes before your appointment, the TA will not give you another appointment to discuss your exam. I'm sorry to have to be so strict with this. But we've been stood up by students too many times!

    3. When you make an appointment, please e-mail at least two time slots for the TA to choose from. Once the TA and you have agreed on a time slot, you must either come to the appointment or cancel it 30 minutes before the appointment in order to reschedule.

    4. Finally, if you need to go beyond your scheduled timeslot to finish looking at your exam, you must make another appointment. And to be fair to everyone, the maximum number of appointment you may have to discuss your exam is two.

    The TA has applied one standard to all exams. If he has made a mistake, he will change your score. But if he did not make a mistake, there is no point arguing that you should have gotten 1.5 points here instead of 0.5 point. Everyone got the same number of points for answering the same way. And please remember, better answers may receive more points. And please always be courteous and professional.

    I always get question regarding class letter grade at this time. At the end of the semester, after all the scores are in, I will plug in all your scores in the equation given on the course description web page and computer your overall score and plot everyone on the same curve. Around the class average is a grade of B+. Please do not expect an A just because you do very well in the programming assignments.

    Please also refer to the last two slides of the exams lecture notes regarding regrades.

  • 10/19/2010: There will be no need to sign rowsheet today.

  • 10/17/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 the last slide of Lecture 16 on 10/14/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(n2)
        • O(n3)
        • O(nk)
        • 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 (not covered by this exam)
      • 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

  • 8/29/2010: Office hour on Monday, 8/30/2010, has been canceled. Sorry abou the inconvenience.

  • 7/30/2010:
    • Registering with the class mailinglist is required for this class. This is not the same as the class discussion Google Group. You will be receiving HW and exam scores through this list via individual e-mails. If you have not done so, please visit the mailinglist page after the semester starts. (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.

    • Watch this area for important announcements.
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 (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!


[Last updated Sat Sep 19 2020]    [Please see copyright regarding copying.]