CS 570 Analysis of Algorithms Department of Computer Science
Spring 2007 New Mexico State University

Course Information

The objective of this course is to learn techniques for design and analysis of algorithms. Techniques include how to analyze time and space complexity and prove correctness of algorithms. Particular algorithms such as sorting, searching, dynamic programming, and graph manipulating will be covered. NP completeness will be introduced to characterize a class of problems that are unlikely to be solved efficiently in polynomial time.

Instructor:

Dr. Joe Song, joemsong@cs.nmsu.edu, Phone: 505-646-4299, Office: SH 141

Class Schedule:

Class meets 9:30-10:20am Mondays & Wednesdays & Fridays in Room SH 113.

Office hours:

Mondays, Wednesdays, Fridays 8:30-9:20am or by appointment.

Teaching assistant:

Brian Cloteaux, bcloteau@cs.nmsu.edu, Office: SH 135 , Phone: 505-646-6244.

TA office hour:

Tuesdays 10:30am-11:30pm and Fridays 2:00pm-3:00pm.

Prerequisites:

At least a grade of C in CS 372 Data Structures and Algorithms or an equivalent. If you do not have the prerequisites or equivalent, please talk to the instructor.

Required text:

Introduction to Algorithms (Second Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, published by MIT Press and McGraw-Hill. 2001.

Important Dates

Midterm exam (in class) ................................................ (Monday) March 5, 2007

Last day to withdraw with a “W” ....................................... (Monday) March 12, 2007

No class (spring break) ......................... ......................... 3/19/07, 3/21/07, 3/23/07

No class (spring day) ..................................................... (Friday) April 6, 2007

Final exam ..............................................(Monday) 8:00-10:00am on May 7, 2007

Grading

• Homework assignments (10%).
• Quizzes (30%): Close book.
• Midterm exam (25%): Close book on March 5, 2007.
• Final exam (35%): Close book. It will be cumulative but emphasize materials after the midterm exam. Date to be determined.

Grading Policies

• All homework assignments must be finished independently. While discussions about homework are allowed, solutions must be written in your own language. Substantially similar homework will receive no credit.
• Homework is due one week after posted. Late homework will not be accepted.
• No incomplete grades will be assigned unless there is a legitimate emergency.
• There will be no make-up for missed quizzes or exams.

Topics

The course will cover an introduction (ch.2), growth functions (Ch. 3), recurrences (Ch. 4.1-4.3), Strassen’s algorithm (Ch. 28.2), quick sort (Ch. 7), order statistics (Ch. 9), dynamic programming (Ch. 15), greedy algorithms (Ch. 16), amortized analysis (Ch. 17), elementary graph algorithms (Ch. 22), minimum spanning trees (Ch. 23), single-source shortest paths (Ch. 24.2-24.3), all-pairs shortest paths (Ch.25.1-25.2), and NP-Completeness (Ch. 34).

Plagiarism and Code of Conduct

Please see the “Student Code of Conduct” in the current “Student Handbook.” (URL http://www.nmsu.edu/%7Evpsa/SCOC/misconduct.html) regarding academic misconduct and plagiarism. The penalty for plagiarism or other forms of academic misconduct (as defined in the Student Code of Conduct) leads to failure of the course.

Non-Discrimination Policy

Feel free to call Jerry Nevarez, Director of Institutional Equity, at 505-646-3635 with any questions you may have about NMSU’s Non-Discrimination Policy and complaints of discrimination, including sexual harassment.

Students with Disabilities

Feel free to call Michael Armendariz, Coordinator of Services for Students with Disabilities, at 505-646-6840 with any questions you may have on student issues related to the Americans with Disabilities Act (ADA) and/or Section 504 of the Rehabilitation Act of 1973. All medical information will be treated confidentially.