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

T-Th 2-5 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%

Programming Assignments: 50%

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.
  • 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 (Scheme, Java, …).
  • I’ll post a review for the midterm and the final exams.
  • Midterm and Final exams are different for graduates and undergraduates.
  • There will be additional programming assignments for graduates than for 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

If you have a documented disability, as described by the Rehabilitation Act of 1973 (P.L. 933-112 Section 504) and the Americans with Disabilities Act (ADA) and subsequent amendments and would like to request academic and/or physical accommodations, please contact the Office of Disability Services in the Schuster Student Success Center (room 221),706-507-8755, as soon as possible. Course requirements will not be waived, but reasonable accommodations may be provided as appropriate.