CSCI 492 - Algorithms And Complexity

Institution:

Virginia State University

Subject:

Description:

Recommended for students pursuing a graduate degree in Computer Science, definitions of algorithm and its complexity, proof of correctness of an algorithm, notion of time and space complexity, the complexity hierarchy, average and worst case complexity, complexity of search and sorting algorithms, recurrence relations arising from basic algorithms, linear and non-linear recurrences, divide-and-conquer algorithms, dynamic programming. Prerequisite: CSCI 387 Data Structures Basic problem-solving strategies, heuristic search, problem reduction AND/OR graphs, knowledge representation, expert systems, generating explanations, uncertainty reasoning, game playing, planning, machine learning, computer vision, and programming systems such as Lisp or Prolog. Formal models of computation such as finite state automata, pushdown automata and Turing machines. Formal definitions of languages, problems, and language classes including recursive, recursively enumerable, regular, and context free languages. Halting problems, undecidable problems, recursive functions, Chomsky hierarchy, Church's thesis and the limits of computability. Proofs of program properties including correctness.

Credits:

3.00

Credit Hours:

Prerequisites:

Corequisites:

Exclusions:

Level:

Instructional Type:

Lecture

Notes:

Additional Information:

Historical Version(s):

Institution Website:

www.vsu.edu

Phone Number:

(804) 524-5000

Regional Accreditation:

Southern Association of Colleges and Schools

Calendar System:

Semester

The Course Profile information is provided and updated by third parties including the respective institutions. While the institutions are able to update their information at any time, the information is not independently validated, and no party associated with this website can accept responsibility for its accuracy.