CPSC–5115 G: Algorithm Analysis and Design
Instructor
Dr. Edward L. Bosworth
Center for Commerce and Technology 443
(706) 565-4128
e-mail:
website: http://csc.colstate.edu/bosworth/
Office Hours – Fall 2007
Monday:No office hours on Monday.
Tuesday:10:00 AM– 12:00 Noon,
2:00 PM– 3:20 PM.
Wednesday:10:00 AM– 12:00 Noon
2:00 PM– 4:00 PM.
Thursday:10:00 AM– 12:00 Noon,
2:00 PM– 3:20 PM.
Friday:No office hours on Friday.
Class Meetings:
Tuesday and Thursday 6:00 – 7:15 PM
Center for Commerce and Technology, Room 405
Course Prerequisites
Graduate students should be aware of the prerequisites for the undergraduate offering.
Data Structures,(CPSC 2108) and
Discrete Mathematics(One of CPSC 3115, MATH 2125, or MATH 3125)
The student is expected to be able to program in either C++ or Java and be familiar with: searching, sorting, arrays, linked lists, binary trees, and directed and undirected graphs.
Textbook
Textbook Selected for the Course:
Introduction to the Design and Analysis of Algorithms
Anany Levitin
Pearson/Addison-Wesley, 2nd Edition, 2007
ISBN 0 – 321 – 35828 – 7
Recommended Extra Book
Algorithmics: The Spirit of Computing
David Harel
Addison-Wesley, 1992
ISBN 0-201-50401-4
Page 1 of 7GraduateLast Revised On May 19, 2019
CPSC 5115G – Algorithm Analysis and Design
Course Description
This course focuses on a number of the major strategies for designing computer algorithms to solve specific problems. The problems (such as graph traversals) are used only as examples upon which the discussion of algorithm design techniques can be based.
The course begins with a definition of the term “algorithm”, then moves to a discussion of techniques for analyzing algorithms, focusing on run-time complexity issues. A number of design strategies are then discussed and illustrated with some of the classic algorithms.
Course Objectives (Learning Outcomes)
At the end of the course the student will be able to:
1.Define and give simple examples of algorithms.
2.Analyze the run-time complexity of simple algorithms, both iterative and
recursive, using the O, , and notation.
3.Understand and describe brute-force as a strategy for designing algorithms.
4.Understand and describe divide-and-conquer as a strategy for designing algorithms.
5.Describe and implement the following graph algorithms: BFS (breadth-first search),
DFS (depth-first search), and topological sorting.
6.Describe and implement simple sort algorithms, including heapsort and quicksort.
7.Understand and describe the dynamic programming strategy for algorithm design.
8.Understand and describe the greedy strategy for algorithm design.
9.Give a basic intuitive definition of the computational complexity classes
P, NP, NP-Hard, and NP-Complete.
Please note that this list will probably be changed as the course proceeds.
Student Responsibilities
1.Attend class regularly.
2.Complete all reading assignments and all homework assignments.
3.Actively participate in all class discussions.
4.Ask the instructor questions.
Instructor Responsibilities
1.Give lectures on the course material.
2.Assign appropriate homework that illustrates the concepts of the course, and
grade and return the homework in a timely manner with adequate explanation.
3.Give tests over the material and grade and return the tests in a timely manner.
4.Provide a website that supports the course.
5.Provide at least four hours of office time primarily designated for assistance of
students in this class, at times expected to be convenient for the students. It is
expected that the instructor be available to the students during these hours.
Course Methods
This course has three sectionsCRN 81179, CRN 81180, and CRN 81181.
It will be taught face–to–face with lecture slides and audio being posted on my web site at
http://csc.colstate.edu/bosworth/. All students, including those taking the course in person will require access to the CougarView (Vista) system.
This course will be structured around development of an algorithm for a popular search problem, called Sudoku. Students will be assigned in teams to develop data structures and algorithms to solve the classic Sudoku puzzle and write a program (in either C++ or Java) to implement this algorithm. For information on the puzzle, see
Mid-Term and Final Exams All exams for this course will be open-book, open-notes.
Class Participation: In addition to homework submissions, each student is expected to send the instructor one miscellaneous e–mail each week. The subject may be academic, but does not need to be. We can discuss anything you want, but need to stay in touch.
Homework Policy
All homework is due at the beginning of the class on the day assigned. Homework handed in after the start of class will be considered to be late. The penalty for late homework (if assessed) will be 10 points per class period. Homework may not be submitted after the solution has been discussed in class.
Methods for Evaluating Students
Homework20%
The Programming Project10%
Research Project10%
Class Participation 5%
Mid-Term Exam25%(Tuesday, October 2)
Final Exam30%(Thursday, December 13)
Assignment of Letter Grades
The method of assigning letter grades based on overall course averages is fairly standard. The basic method is described as follows:
GRADEPOINTS
A90 – 100
B80 – 89
C65 – 79
FBelow 65
Policy on Tests and Final Exams
All in-class quizzes and tests (but not the final exam) will be graded and returned on the following class period. The class meeting immediately preceding the test is devoted to review for the test, and the class period immediately following the test is devoted to return of the test and discussion of all test questions and possible answers.
For all in-class quizzes and tests (but not the final exam), the deadline for requesting a review of the grade is either two weeks after the test is returned or one week before the scheduled date for the final exam, whichever date is earlier.
Please note that a grade review will never lead to reduction of an assigned grade.
CPSC 5115 Topics for the Course
1.Fundamentals of Algorithmic Problem Solving
Definition of an algorithm
Exact algorithms and heuristics
Techniques for describing an algorithm
Analysis of algorithms
Difference between and algorithm and a program.
2.Analysis of Algorithm Efficiency
Measuring input size.
Measuring running time and orders of growth.
The O, , and notation.
Methods for obtaining the asymptotic run-time efficiency of iterative algorithms.
Methods for obtaining the asymptotic run-time efficiency of recursive algorithms.
The “master theorem” on run-time efficiency.
3.Brute Force
Brute force as a strategy for designing algorithms
Selection sort and bubble sort.
Sequential search.
Exhaustive search.
4.Divide-And-Conquer
Divide-and-conquer as a strategy for designing algorithms.
Mergesort.
Quicksort.
Binary search.
5.Decrease-and-Conquer
Decrease-and-conquer as a strategy for designing algorithms.
Depth-first search and breadth-first search.
Topological sorting.
6.Transform-and-Conquer
Transform-and-conquer as a strategy for designing algorithms.
Gaussian elimination.
Heaps and heapsort.
7.Dynamic Programming
Dynamic programming as a strategy for designing algorithms.
Warshall’s algorithm.
Floyd’s algorithm
The knapsack problem.
8.Greedy Algorithms
Greedy as a strategy for designing algorithms.
Prim’s algorithm.
Kruskal’s algorithm.
Dijkstra’s algorithm.
Fractional knapsack and a proof of optimality.
9.Lower-Bound Arguments
Adversary arguments.
Search by comparison.
Sorting by comparison.
10.Methods for Attaching Hard Problems
Backtracking.
Branch and bound.
Approximate algorithms
The Graduate Research Project
In addition to the requirements placed on the undergraduate students, graduate students are expected to do a literature research project on a subject related to advanced topics in algorithm design and analysis. The students are expected to produce a paper of at least three pages in length (single spaced) that conforms to expected standards for grammar, logical organization, and citation of references.
The schedule for the paper:Tuesday, 10/30Draft of paper due to instructor.
Monday, 11/29Final copy of the paper due.
All work submitted must be based on electronic formats. MS–Word, Adobe PDF, and RTF formats are examples of acceptable formats; paper copies of these are acceptable. Hand written submissions are not acceptable. Unless otherwise noted, each submission should be at least one and a half pages in length and not exceed three pages. One inch margins should be used. The paper should be single spaced, using a blank line to separate paragraphs.
[Students should keep electronic copies of all work submitted, for possible submission to the commercial plagiarism tool TurnItIn.] It is now considered illegal to use this tool.
Other Course Policies
Attendance Policy
I do not take roll, but believe that it is important for students to attend class regularly. If you find it necessary to miss one or more classes, you are still responsible for all material covered in the class. You should notify me in advance of expected class absences to avoid late penalties on homework due on the date you miss. For more information on class attendance and withdrawal, refer to http://aa.colstate.edu/advising/a.htm#Attendance%20Policy.
Excused Absences
Absences from class fall into this category when they occur for medical and unavoidable emergencies, travel related to the student’s primary occupation, or official events (such as athletic events) that are sanctioned by the university. With the exception of absences for emergencies, absences will be excused only if the instructor has been given prior notification.
“Make–Up” Tests
While the instructor will attempt to publicize test dates, it is the student’s responsibility to know the dates of the mid-term and final exams. Make–up tests will be given only when a student misses a test due to an excused absence (see above).
Parking
Parking is a problem at CSU; for this we apologize. It is the student’s responsibility to arrive at class on-time and submit any homework before the beginning of class.
ADA Accommodation Notice
If you have a documented disability as described by the Rehabilitation Act of 1973 (P.L. 933-112 Section 504) and the Americans with Disability Act (ADA) that may require you to need assistance attaining accessibility to instructional content to meet course requirements, we recommend that you contact the Center for Academic Support in Tucker Hall, room 100 or at (706)568-2330, as soon as possible. It is then your responsibility to contact and meet with the instructor. It is also your responsibility to present the instructor with a letter from the Center for Academic Support. Without this letter detailing the required accommodations, the instructor cannot help you. The Center for Academic Support can assist you and the instructor in formulating a reasonable accommodation plan and provide support in developing appropriate accommodations for your disability. Course requirements will not be waived but accommodations may be made to assist you to meet the requirements. Technical support may also be available to meet your specific need. For more information on services and support available, refer to http://uc.colstate.edu/disability_services.htm.
Dropping The Course
We hope that you will complete the course and profit from it. If it is necessary for you to withdraw from the course during the semester, you must follow all official CSU procedures for withdrawing. It is not sufficient to notify the instructor; you must use the ISIS system and withdraw officially. For details on how to withdraw from a course, see the web page http://aa.colstate.edu/advising/w.htm#Withdrawal%20from%20a%20Course.
I would appreciate it if you were first to consult with me before starting the procedure for withdrawing from the course. In some cases, we can agree on an arrangement that will allow you to complete the course with minor adjustments.
Academic dishonesty
Academic dishonesty includes, but is not limited to, activities such as cheating and plagiarism. It is a basis for disciplinary action. Collaboration is not permitted on assignments or exams/quizzes in this course. Any work turned in for individual credit must be entirely the work of the student submitting the work. All work must be your own. You may share ideas but submitting identical assignments (for example) will be considered cheating. A simple way to avoid inadvertent plagiarism is to talk about the assignments, but don't read each other's work or write solutions together. Keep scratch paper and old versions of assignments until after the assignment has been graded and returned to you. If you have any questions about this, please see me immediately.
For assignments, access to notes, textbook, books and other publications is allowed. Stealing, giving or receiving any code, diagrams, drawings, text or designs from another person (CSU or non-CSU) is not allowed. Having access to another person’s work on the system or giving access to your work to another person is not allowed. It is your responsibility to keep your work confidential, so that other students do not have access to it without your knowledge. Properly dispose of all your scratch work.
No cheating in any form will be tolerated. The penalty for the first occurrence of academic dishonesty is a zero grade on the assignment or exam/quiz; the penalty for the second occurrence is a failing grade for the course. For exams/quizzes, discussion of any kind (except with me) is not allowed.
(http://aa.colstate.edu/advising/a.htm#Academic Dishonesty/Academic Misconduct)
Page 1 of 7GraduateLast Revised On May 19, 2019