Syllabus

CPSC 5115G Algorithm Analysis and Design

Instructor: Dr. David E. Woolbright

Office: CCT 439

E-mail:

Phone: (706) 507-8179

Web Site:

Web Site:

Office Hours

M-Th 10-12 am

M-W 2-3 pm

And also by appointment

Catalog Description

CPSC5115. Algorithm Analysis and Design (3-0-3)Prerequisites: CPSC 2108 and MATH 5125, both with grades of "C" or better. This course emphasizes the understanding of data structures and algorithms from an analytical perspective rather than from an implementation standpoint. The concepts developed allow discussion of the efficiency of an algorithm and the comparison of two or more algorithms with respect to space and run-time requirements. Analytical methods are used to describe theoretical bounds as well as practical ones. In general, this course addresses the constraints that affect problem solvability.

Textbook

Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. McGraw-Hill, 2008, ISBN: 978-0-07-352340-8.

The text is also available free, online at .

Course Outcomes

After successfully completing this class:

1)You should know the definitions of O(g), Ω(g), and Ɵ(g).

2)You should be able to describe the algorithms we study using the definitions above.

3)You will be able to describe several sorting algorithms and analyze their running times.

4)You will know the theoretical lowest bound of sorting by making comparisons.

5)You will be able to describe some standard graph algorithms.

6)You will have written a collection of programs that implement some standard graph algorithms.

7)You will have written some programs that use divide-and-conquer, greedy, and dynamic programming algorithms.

8)You willbe able to define basic terms in the theory of NP-Completeness.

Grading

Midterm Exam: 25%

Homework Problems: 10%

Programming Assignments: 40%

Final Exam: 25%

Web Sites

The main web site for this course is . This is the site that will contain the content of the course.

We will also use as a place to post homework, drop assignments, and as a place I can post your grades. You can send me e-mail through webct, but the fastest way to contact me is at my regular address: . Beware! I have a son who is currently a CSU student and whose name is David Bret. Don’t send your mail to him by mistake.

What to Expect
  • I will post a weekly reading assignment for the book.
  • I will post a weekly list of homework problems. If you solve one, you can post it in webct for everyone to view. Others in the class are free to comment on your work. I view this as a place we can discuss current topics. The 10% grade you get for this part of the course is based on your meaningful participation. You don’t have to solve more problems than everyone else. You don’t even need to contribute a solution each week, but I do expect you to join in and hold up your end of the conversation with an occasional solution, good comment, or question. Everyone is expected to contribute as we go through the class. On the other hand, if you don’t have something meaningful to add to the conversation, don’t contribute.
  • Occasionally I’ll post a video for you to watch or point you to one on the web that is relevant to our study.
  • Occasionally I’ll ask you to implement an algorithm in a programming language (probably Java).
  • I’ll post a review for the midterm and the final exams.
  • Midterm and Final exams are different for graduates and undergraduates.
Policy on academic integrity

Students are encouraged to study together; however, each student must individually prepare his/her own submission. Cheating or plagiarism is not permitted and will be sanctioned according to the CSU policy on academic standards. You should carefully read the section on Academic Misconduct in the Student Handbook. Your continued enrollment in this course implies that you have read it, and that you subscribe to the principles stated therein.

Policy prohibiting sexual harassment

As your instructor, one of my responsibilities is to treat all students fairly and equally and to abide by the policies and procedures governing faculty/student relationships, including those concerning sexual harassment as stated in the Faculty Handbook.

ADA information

Students with a documented disability as described by the Rehabilitation Act of 1973 (P.L. 933-112 Section 504) and Americans with Disabilities Act (ADA) that affect their ability to participate fully in class or to meet all course requirements are encouraged to bring this to the attention of the instructor so that appropriate accommodations can be arranged. Further information is available from the Office of Disability Services in the Center for Academic Support and Student Retention, Tucker Hall (706) 568-2330. Course requirements will not be waived but reasonable accommodations may be provided as appropriate.