Mr. K. Lillis
Office: Ambrose Hall 429
Phone: (563) 333-6429
e-mail: LillisKevinM at sau dot edu
Office Hours: Posted on office door. Also available at web.sau.edu/LillisKevinM/Schedule.htm
This course introduces formal techniques to support the design and analysis of algorithms, focusing on both the underlying mathematical theory and practical considerations of efficiency. Topics include algorithm design techniques (divide and conquer, dynamic programming, greedy), asymptotic complexity bounds, recursion relationships, search and sort algorithms, searching, basic graph algorithms, and NP-completeness.
Upon completion of this course students will be able to:
· Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms.
· Determine the time and space complexity of simple algorithms.
· Compare iterative and recursive solutions.
· Implement, test, and debug simple recursive functions and procedures.
· Describe the shortcoming of brute-force algorithms.
· Create and implement greedy, divide-and-conquer, backtracking, and heuristic based algorithms
· Implement the most common quadratic and O(N log N) sorting algorithms.
· Discuss the computational efficiency of the principal algorithms for sorting and searching
· Implement fundamental graph algorithms, including depth-first and breadth-first search, single-source and all-pairs shortest paths, topological sort, and minimum spanning tree
· Define the classes P and NP and explain the significance of NP-completeness.
CSCI 180 – Discrete Structures
CSCI 310 – Data Structures
Foundations of Algorithms Using Java Pseudocode, by Neapolitan and Naimipour.
© 2004 by Jones and Bartlett. ISBN 0-7637-2129-8.
The class will meet on Monday, Wednesday, and Friday from 1:00 to 1:50 p.m. in McMullen 202.
There will be no class on the following days: Jan. 21; Mar. 3, 5, 7, 21, 24
The final exam is on Wednesday, May 7, from 1:00 to 2:50 p.m.
There will be regular homework assignments as well as a midterm and final exam. All reading is to be completed prior to the class in which the material is to be covered. Students are expected to participate in class discussions.
A web site has been created for this class at http://web.sau.edu/LillisKevinM/csci393/2008Spring. Students should check this web site often during the semester.
Attendance is mandatory. Students are expected to attend all classes. Two late arrivals count as one absence. Missed lectures are the responsibility of the student.
You are encouraged to discuss homework and other parts of the class with other students. Such discussions about ideas are not cheating, whereas the exchange of finished, written answers is cheating. Never give finished answers to someone else or use someone else's finished answers. Plagiarism/cheating are considered grounds for a failing grade for that particular piece of work. Furthermore, it would weigh heavily in the final grade, possibly resulting in a failing grade for the entire course.
Students are encouraged to go to the Student Success Center in Ambrose Hall 243 or to call 333-6631 for information regarding tutoring in this class. The SSC provides free peer tutoring for most 100 and 200 level courses, writing tutorials for papers in all classes, and study strategy advice. Supplemental Instruction and study groups are also available in some classes. The center staff suggests that students seek help early, although drop in and contractual tutorials are arranged throughout the semester.
Midterm Exam 30 %
Final Exam 35 %
Homework Assignments 30 %
Attendance 5 %
Letter grades will be assigned based on the following
A = 90-100 B+ = 86-89 B = 80-85 C+ = 76-79 C = 70-75
D = 60-69 F = Below 60
In determining borderline grades, the instructor reserves the right to consider perceived student initiative and class participation.
An incomplete will be given only when a student meets the conditions stated in the latest St. Ambrose University catalog. Earning a low grade is not a valid reason for an incomplete.
Students with disabilities who believe that they may need accommodations in this class are encouraged to contact the Office of Services for Students with Disabilities at 333-6161 as soon as possible to better ensure that such accommodations are implemented in a timely fashion.