- Department of Computer Science
- Vision, Mission, & Values
- Degrees & Programs
- Courses
- First Year Transfer Students
- Current Students
- Prospective Students
- Faculty & Staff
- Professors Emeritus
- Industrial Advisory Board
- Financial Assistance
- Employment Opportunities
- Donate
- Graduate Capstone
- Careers for Majors
- Resources
- Contact Us
- Help for Students
CS 4245 Analysis of Algorithms (4) 2005
Catalog Description
Design, analysis and implementation of algorithms. Methods of algorithm design, including recursion, divide and conquer, dynamic programming, backtracking. Time and space complexity analyses in the best, worst, average cases. NP-completeness; computationally hard problems. Applications from several areas of Computer Science. Prerequisites: MATH 2101, MATH 2304, CS 3240 CROSS-LISTED: MATH 4245
Course Outline
- Growth rate of functions: O, o, theta, other notations
- Methods of Algorithm Design: recursion, divide and conquer, backtracking, and others
- Applications to algorithms
Sorting and searching (e.g., quicksort, mergesort, heapsort)
Set and Graph Theoretic (e.g.,depth-/breadth-first search, min. spanning tree, shortest paths)
String Matching (e.g., KMP, Boyer-Moore)
Polynomial and Matrix (e.g., Strassen's method) - Introduction to complexity: brief overview of P and NP
Recommended Text:
- Baase & Van Gelder, Computer algorithms, Addison-Wesley
- Levitin, Anany, Intro to the Design and Analysis of Algorithms, Addison Wesley