CSC 555 – Algorithm Analysis and Design

Course Syllabus, Fall 2009

COURSE INFORMATION

For Whom Planned: Upper undergraduate and graduate students
Credits:   3
Prerequisite:  grade of at least C in CSC 330
Meeting Times:  MW 2:00pm-3:15pm
Location:   Petty 223

INSTRUCTOR INFORMATION

Instructor: Dr. Lixin Fu
Office: Petty 162
Office hours: MW 10:00am – 12:00 noon or by appointment
Tel.: (336) 256-1137
Home page: http://www.uncg.edu/~l_fu
E-mail: lfu@uncg.edu

COURSE OBJECTIVES AND TOPICS

This course covers sequential algorithm design and analysis techniques. After this course students should be able to

• comprehend major powerful algorithm design approaches such as recursion, divide and conquer, greedy, and dynamic programming;
• apply these approaches  to a variety of application areas such as sorting and selection, graph problems, computational geometry, and algebraic problems; and
• analyze performance of algorithms using complexity measurement, and understand NP-completeness.

By designing and analyzing algorithms, you will improve your creative thinking, problem solving and analytical ability.
The topics that we will cover during the course of the semester include:

• Preliminaries (asymptotic notations, data structures)
• Randomized algorithms
• Divide and conquer
• Greedy algorithms
• Dynamic programming
• Graph algorithms
• NP-completeness and approximation algorithms

Here is the tentative schedule.

TEXTBOOK

Required textbook:
Thomas H. Cormen et al., Introduction to Algorithms, Second Edition, MIT Press, 2001. ISBN (MIT Press): 0-262-03293-7.

EVALUATION METHODS AND GUIDELINES FOR ASSIGNMENTS

1. Exams
There will be three closed exams. No books or notes are used as references during the exams.
The exams mainly focus on the material covered since the last exam (except the first one).

2. Homework
Five homework assignments are designed to help you better understand the material covered in class.
The submissions are preferably typed (e.g. using Microsoft WORD).  Handwriting must be legible and neat.
No late homework is accepted. Each student should complete the assignments independently.

3. Grading Scheme

Please notice that the grading schemes for graduate students and undergraduate students are different.

For undergraduate students:

Exam I:    20%
Exam II:   25%
Exam III:  25%
Homework:  30% (each assignment 6%)

For graduate students:

Graduate students who register in this course must write an additional term paper investigating a research topic in computer algorithms. The weight for this work is 20%, bringing the total for graduate students to 120%, which will be prorated to 100% to determine the grade. List of topics, resources, and guidelines for term papers will be provided in class.

The letter grade you will receive depends on the numerical scores in the exams and assignments, and your overall performance in this course. Roughly,

90-100      A
80-89        B
70-79        C
60-69        D
< 60          F

ATTENDANCE POLICY
Class attendance is required. If you will be absent for an exam due to extreme cases such as severe physical conditions,
let me know in advance so that we can arrange a make-up test. 

ACADEMIC HONOR CODE
The instructor will deal strictly with any violations of academic honesty and integrity in this course.
Refer to Academic Integrity Policy  or UNCG Undergraduate Bulletin for more details.

Please read the related textbook sections listed in the class schedule before class, attend all the lectures, and start on homework early.
If you have any questions or need assistance, please feel free to see me during my office hours, email me, or make an appointment.
I am more than happy to help you. I will try to make this class as interesting and fruitful as possible.

Thank you!

Lixin Fu