Introduction to Complexity Theory

## Introduction

[edit | edit source]

Complexity theory is the study of the resources (especially computation time and memory) required by algorithms.

## Learning Project Summary

[edit | edit source]

* Project code:
* Suggested Prerequisites:
* Students should be familiar with the concepts of deterministic and nondeterministic computation, and formal models of computation, such as finite state automata and Turing machines.
* Students should also be familiar with the theory of formal languages
* Time investment:
* Assessment suggestions:
* School: School of Computer science
* Department: Institute for Complexity Theory
* Stream
* Level:

## Goals

[edit | edit source]

The introduction to complexity theory course will offer a comprehensive course in complexity theory .

## Course

[edit | edit source]

| Subject classification: this is a mathematics resource.

|

| Subject classification: this is an information technology resource.

|

| Educational level: this is a tertiary (university) resource.

|

### Lessons

[edit | edit source]

* Lesson 1—Big O Algorithm Analysis
* Lesson 2—Time Complexity
* Lesson 3—Space Complexity and Savitch's Theorem
* …

### Tests and Quizzes

[edit | edit source]

* Quiz 1—Big O Quiz

### Reading Material

[edit | edit source]

## Active participants

[edit | edit source]

Please sign below if you are participating in this topic. Use 4 tildes (~) to sign.

* Kinkydarkbird 03:35, 5 January 2009 (UTC)