CS 570 Analysis of Algorithms Department of Computer Science
Spring 2006 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 analyze a class of algorithms 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

Office hours:

Mondays & Wednesdays 5:15-6:15pm or by appointment.

Teaching assistant:

Islam Elkabani, ielkaban@cs.nmsu.edu, Office: SH 133, Phone: 505-646-6231.

TA office hour:

Thursdays 11:00am-1:00pm

Prerequisites:

At least a grade of C in CS 372 Data Structures and Algorithms or 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.

Class Schedule

Class meets 4:00-5:15 pm Mondays & Wednesdays in Room SH 115. There will be no class on 3/20/06 or 3/22/06 due to spring break. The midterm exam will be in class on March 15, 2006. The final exam week is 5/8/06-5/12/06.

Grading

• Homework assignments (20%).
• Quizzes (20%): Close book.
• Midterm exam (25%): Close book on March 15, 2006.
• 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 two weeks 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).

Code of Conduct

Please see the “Student Code of Conduct” in the current “Student Handbook.” 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.

Students with Disabilities

Please contact Office of Services for Students with Disabilities, located in Garcia Annex Room 102 (Phone: 646-6840) for appropriate accommodations. For general questions about the Americans with Disabilities Act, call Elva Telles, the coordinator at 646-3635.

Syllabus Modifications

During the course, syllabus will be updated to best serve the particular students in this class. Significant modifications will be posted online and announced in class.