Course Description - CSCI 570, Spring 2013, Section 30097D

Links to sections on this page:
  • Focus
  • Note From A Doctor
  • Student Responsibilities
  • Textbooks
  • Regrading Policy
  • Fairness
  • Syllabus / Topics Covered
  • Using Public Code
  • Auditing
  • Homework Assignments
  • Office Hours
  • E-mail
  • Exams
  • Extra Credits
  • Academic Integrity Policy
  • Grading
  • Class Newsgroup
  • Academic Calendar
  • Late Policy
  • Implicit Student Agreement
  • Additional Resources
    The course is intended as a first graduate course in the design and analysis of algorithms. The course will give an overview of common techniques, and applications of these techniques in different settings.
    Required: Optional:
    Syllabus / Topics Covered
    The following schedule and topics are tentative and are subject to change without notice.
    • Introduction and representative problems
    • Basic algorithm analysis
    • Graph algorithms
    • Greedy algorithms
    • Divide and conquer
    • Dynamic programming
    • Network flow
    • NP & Computational intractability
    • PSPACE
    Homework Assignments
    There will be no programming assignments. Written homework assignments will not be collected or graded.
    A midterm and a final examination will be given. The coverages of the two exams will not overlap. The dates for these exams are posted near the top of the class home page. Any scheduling conflicts regarding the midterm exam date must be resolved with the instructor at least one week before the exam date. The date of the final examination is firm and cannot be changed.

    The exams are usually closed book, closed notes, and closed everything (and no "cheat sheet"). Also, no calculators, cell phones, or any electronic gadgets are allowed. There will be assigned seating.

    The grading breakdown is as follows:
    Participation:   3%  
    Midterm #1:   30%  
    Midterm #2:   32%  
    Final Exam:   35%  

    Pleaes also note the following:

    • The above percentages will be used to calculate your total score. Final grades (A,B,C,D,or F) will be determined using a modified curve (i.e., we won't necessarily assign an equal number of failing grades as passing grades) based on this total score. No other methods will be considered. (So, please do not ask the instructor to take how much you have improved since the beginning of the semester into account. You are expected to try your best from the beginning!)

    • We will assign grades of C and below to individuals who do not perform satisfactorily in the above areas. (i.e., you should not assume a B- or even C if you perform unsatisfactorily.) However, we hope that everyone will perform well.

    • Your assignments are your own work! No group assignments are allowed or will be tolerated. You are free to talk to other students about assignments but no actual material (files, photocopies, code fragments, etc.) should be shared. We will act harshly at any sign of copying.

    • We will not assign incompletes unless it is for a documented medical reason (in accordance with USC policy).
    Late Policy
    All homeworks must be turned in on time. Late submissions will receive severe penalties. Due to clock skews, electronic submissions of homework assignments will be accepted within 15 minutes after the specified deadlines without penalties. If you submit within the next 24 hours, you will receive 80% of your grade. Although right after midnight, you will lose 1% every 5 minutes. When the penalty reaches the day limit, it flattens out. For example, if your submission has a timestamp that is 32 minutes after the grace period, 7% will be deducted from your assignment after grading; if your submission has a timestamp that is 1 day, 6 hours, and 41 minutes after the grace period, you will receive a score of zero (and your assignment will not be graded). The figure below summarize the deductions.

    If you are unable to complete a homework assignment due to illness or family emergency, please see the instructor as soon as possible to get an extension. A doctor's note is required as proof of illness or emergency. In general, when you get sick, it's best to see a doctor and get a note just in case you may need it later.

    Note From A Doctor
    Recently, there has been a change in the policy at the Student Health Center regarding giving a "note from the doctor" to you to bring to a faculty member so that you can be execused from deadlines. Basically, they will not give you such a note any more. What they would give you is an Authorization for Disclosure of Medical Information form. With this form, you give them permissions to discuss your illness with me.

    So, if you visit a doctor at the Student Health Center, please make sure you fill out one of these forms, check the "limited discussion with faculty" checkbox, get it stamped, signed, and dated by someone there (a clerk/receptionist would sign at the "witness" line), and bring it back to me. This would satisfy the "note from a doctor" requirement so that you can get an extension.

    If you visit a doctor somewhere else, please either bring a "note from the doctor" or a similar authrozation letter so I can contact them.

    Regrading Policy
    All requests to change grading of homework or exams must be submitted in writing within one week of the time the initial grade was given. Requests must be specific and explain why you feel your answer deserves additional credit. A request to re-grade an assignment can result in the entire assignment being re-evaluated and as a result the score of any part of the assignment be increased or lowered as appropriate.
    Using Publically Available Code in Programming Assignments
    For some programming assignments, you are permitted to use any publically avaialble code you can download from the Internet as long as you give proper credit. When you use such code, you must (1) follow the copyright instructions of the code you use, and (2) cite your source properly. Citing your source properly means the following:
    1. If you copy a whole file and don't change the file, all you have to do is to add the folowing comment to the top of the file to give proper credit:
           * This file is downloaded from the following location:
           *     [ give the URL ]
           * The source code has not been modified.
           * The file has the following copyright from the original author:
           *     [ give the copyright as required by your source ]
    2. If you copy some code from a web site and put it in a file where you wrote other code in the file and did not change the downloaded code, you must add the following comment for each class declaration and each function to give proper credit:
           * This class definition (or function) is downloaded from
           * the following location:
           *     [ give the URL ]
           * The source code has not been modified.
           * The file has the following copyright from the original author:
           *     [ give the copyright as required by your source ]
    3. If you copy some code from a web site and have modified the code, you must add the following comment for each class declaration and each function to give proper credit:
           * This class definition (or function) is derived
           * from the code available at the following location:
           *     [ give the URL ]
           * The file has the following copyright from the original author:
           *     [ give the copyright as required by your source ]
    If you use public code and does not follow the instruction above and MOSS matched your code with someone else's code, you will lose 25 points (in a 100-point scale).

    If you use public code and does not follow the instruction above and MOSS did not matched your code with someone else's code, you will lose 5 points (in a 100-point scale) for improper citation.

    Please note that a book that's not free is not a public source! If you want to use code from a book, please scan pages from the book and e-mail the pages to the instructor before the submission deadline.

    If this is too much trouble for you, you can simply choose not to use code from public sources! If you want to use code from public sources, this is a small price to pay.

    Office Hours
    The instructor's office hours are held three times a week for one hour each. If you are not available during the designated time for office hours, you are always welcome to make an appointment (and reserve a timeslot) to see the instructor.
    Extra Credits
    No extra credit assignments will be given for this class. So, there is no need to ask. Try your best from the beginning!
    Class Newsgroup
    A class Google Group is used as a class mailinglist and discussion forum for students-to-students discussions. The main purpose of this is for the students to discuss things about homework assignments with each other. Students may not exchange code here because it would violate academic integrity policy of USC. Posting of small code segments (less than or equal to 4 lines of code) is allowed as long as it is meant to clarify discussions.

    The instructor and the TA do not normally read this forum. Please do not post questions for them here.

    Please make sure that you have read the Academic Integrity Policy of this course.

    Implicit Student Agreement
    All work including homeworks, programming assignments and exams must be that of the individual student. It is often productive to study with other students. However, if any portions of homeworks or programming assignments are found to be shared between two (or more) students, zero credit will be given to all students concerned and all students will be disciplined. This policy is in the interest of those students who do their own work, which hopefully applies to all of you in this class.

    This policy also holds for programming assignments. In this class, we will use sophisticated automated program checkers to detect cheating. Be aware that the program checkers have demonstrated very good results and are widely used within the academic community. Any student caught cheating will be given zero credit and will be disciplined.

    It is the students responsibility to submit their assignments electronically in time.

    There is no specific prerequisites for this course. No special assistance or consideration will be offered if your background is inadequate.

    Student Responsibilities
    During the semester you are responsible for completing the assigned readings, homeworks, and exams.

    If you covered the background material for this course at some other school it is YOUR responsibility to fill in any missing background. Feel free to ask me for advice on appropriate introductory readings if you feel your background is insufficient.

    We expect you to attend every class meeting. If you do happen to miss a session, you are responsible for finding out what material was covered and if any administrative announcements were made. You must do so BEFORE the next session (e.g., if there is an assignment given during the missed session, you are still responsible for completing it by the next week along with the other students).  You are advised to read the textxbook for a particular lecture before attending the lecture. This will greatly enhance your understanding of the subject matter.

    The instructor must treat all students equally and cannot give special treatment to any particular student. Therefore, please do not ask special favors from the instructor because of your circumstances. This may seem unfair to you because you believe that your circumstances are special (understandably, everone does). But the rule the instructor must follow is that whatever he offers you, he must offer to the entire class.
    Auditing is not permitted for this class.
    Most class related announcements will be sent through the class Google Group. Therefore, you are required to be a member of this group. Please see instructions on how to get on this group (you should do this as soon as possible).

    Please do not ask the following types of questions in your e-mail:

    • Here is my understanding of X. Am I right (or is this correct)?
      (You can do this for just about everything and in many different ways. I do not have the bandwidth to deal with too many questions like this. However, often times, you should be able to ask a slightly different question and get the same answer that you are looking for. This type of questions is completely appropriate for office hours.)

    • I don't understand X. Could you explain X to me?
      (It's your responsiblity to come to lectures and ask questions during lectures if there is something you do not understand. If you did attend lectures, then it is appropriate to ask this during office hours.)
    Although this is not related to e-mails, it's a type of question I get often. Please do not ask this types of question:
    • Here is what I am thinking of or doing... is it acceptable (or is this okay)?

      (What you are really asking is whether you will receive full credit or not. Wouldn't it be great if you can ask this during exams? It's not an appropriate question for assignments for the same reason it is not appropriate for exams. Although there is a difference between programming assignments and exams, but since you are asking about grading, it's inappropriate. If you asking if it's okay to take a shortcut. The answer is always, "No" or "At your own risk.")

    Academic Integrity Policy
    Please make sure you read the Academic Integrity Policy of this course.
    Academic Calendar
    A link to the USC Spring 2013 academic calendar is provided here for your convenience.
    Additional Resources
    (These resources below are provided for your information. Please note that the instructor has not read most of them. Please use these resources at your own risk!)


    • C Programming (by Steve Holmes at the University of Strathclyde in Glasgow, England) - includes notes on make, separate compilation, file I/O, etc.
    • Makefile tutorial (at Colby College)
    • Steve's Software Trek (by Steve Karg) - includes some useful C/C++ source code for string manipulation, INI file manipulation, etc.
    • C Examples - lots and lots of sample C code for basic stuff.
    • C/C++ at USC from USC ITSWeb

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