CSC 445 Comp Complexity & Modeling

Prerequisite: CSC 236 Data Structures

A study of a variety of types of interdisciplinary computational problems, including decision, search, counting, optimization, and verification. In our search to understand the fundamental limitations and capabilities of efficient computation, we will explore and model extremely important, but inherently challenging, computational problems which require a huge run time to solve perfectly no matter how clever an algorithm one employs. Hence, we will explore heuristics which model imperfectly but much more rapidly. We will consider not only run time, but also space/memory, non-determinism, randomness, error, and algebraic operations. This course counts in the Foundations area of the Computer and Information Science Major. Noncredit for students who completed it as CSC386JP.