Instructor: Dr. Teresa Leyk

Office: Richardson Bldg. 901E

phone: 845-4456

e-mail: teresa@cs.tamu.edu

Course web page: (all information about the course will be there):

http://courses.cs.tamu.edu/teresa/cpsc311/cpsc311-index.html

Class Time MWF 9:10–10:00 am, 105B ZACH

Office Hours: MWF 10:15–11:15 am, other times by appointment.

TA: Thomas George

TA’s E-mail: tgeorge@cs.tamu.edu

TA’s Office Hours: MTWR - 11:30-12:30 pm

PT: Jonthatan Leake

PT’s E-mail: jona527than@neo.tamu.edu

PT’s Office Hours: MW 1:40-2:40 pm 128D ZACH, TR 9:50-10:50 pm 214 HRBB, F 1:40-2:40 pm 214 HRBB.

Course Description: Credit 3. Design of computer algorithms for numeric and non-numeric problems, relation of data structures to algorithms; analysis of time and space requirements of algorithms; complexity and correctness of algorithms.

Prerequisite: CPSC 211 (Data Structures), C/C++ programming language and Math 302 (Discrete Mathematics).

Required Textbook: T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein “Introduction to Algorithms”, 2nd ed., McGraw-Hill, 2001.

Learning Objectives: At the end of this course students will be able to:

1. Understand the relation between the amount of work done by an algorithm and Big-O, Ω, Θ asymptotic notations.
2. Analyze the time and space complexity of fundamental algorithms.
3. Determine recurrence for recursive algorithms and solve elementary recurrence relations.
4. Design efficient algorithms using different algorithmic strategies like brute-force, greedy, divide and conquer, backtracking, dynamic programming, approximation algorithms.
5. Justify correctness of algorithms using loop invariant and contradiction proving techniques.
6. Design, implement and compare asymptotic notation and computational time for sorting and search algorithms.
7. Classify problems using P and NP classes. Prove that a problem is NP-complete by reducing NP-complete problem to it.

Course Content:

• Introduction and Mathematical Foundations (Chap. 1-4, Appendix A,B,C)
• Sorting (Chap. 6-8)
• Median and Selection (Chap. 9)
• Data Structures (Chap. 10)
• Binary Search Trees (Chap. 12, 13)
• Hashing (Chap. 11)
• Graph Algorithms (Chap. 22-26)
• Operations on disjoint sets (Chap. 21)
• Amortized Analysis (Chap. 17)
• Dynamic Programming and Greedy Techniques (Chap. 15 and 16)
• Maximum Flow (Chap. 27)
• NP-Completeness (Chap. 34, 35)

Grading: Your grade will be determined based on homework assignments, quizzes, mid-term exams and the final exam. Exams and quizzes are closed book. All homework assignments will be announced in class and posted on the course web page. There will be two types of homework assignments: individually written and two group projects each of them will contain a programming part. You can get 100 points for each written assignment and 200 points for each project. All programs must be written in Standard C or C++, compiled and run on the Unix CS machines and transferred to a course directory for grading using the turnin program. Each project will be graded focusing on: algorithm design and its implementation; 40%; its correctness and tests: 30%; and typed report with comparison between theory and a computational experiment: 30%. A late homework assignment will be accepted up to four working days with a 5% penalty for each late day. There are no make-up quizzes or exams. Please discuss unusual circumstances in advance with the instructor.

• Exam I (Wednesday, September 24) – 15%
• Exam II (Wednesday, October 22) – 15%
• Exam III (Wednesday, November 24) – 15%
• Final (comprehensive) Exam –15% Monday, December 8, 8:00 am-10:00 am
• Homework Assignments – 30%
• Quizzes – 10% (once a week)

Grading Scale: Grades will be assigned according to the following scheme:

90% –100% –> A, 80% – 89% –> B, 70% – 79% –> C, 60% – 69% –> D, 0% – 59% –> F

• Scholastic Dishonesty: Discussion of solutions is encouraged, but all assignments must be done on your own. If you use sources other than the textbook or lecture notes, list them. Any homework, which in the opinion of the instructor shows evidence of copying, will receive a lower grade or even zero. See the latest issue of the "Texas A&M University Student Rules" under the section "Scholastic Dishonesty" posted see the site http://student-rules.tamu.edu/.
• Attendance Policy: Student attendance is required but it is not counted as part of the final grade. Class attendance will not be taken, but you are responsible to learn all material covered in class and read the assigned text from the textbook and do homework. Make-up exams will only be given with documented University-approved excuses (see University Regulations). No make-up quizzes and late assignments will be accepted. Discuss unusual circumstances in advance with the instructor.
• Students with Disabilities: According to the federal law, all students with disabilities have to have a special learning environment. For more information, please contact the Department of Student Life, Services for Students with Disabilities in Cain Hall, Rm. B118, or call 845-1637.