STRUCTURED PROGRAMMING IN C LANGUAGE

Ma 599

Prerequisites: Discrete Structures, The Calculus

Course Description

Realistic models of computation used to study resource requirements. Topics include Turing machines, computation models and techniques, upper bounds, sorting, searching, matrix multiplications, fast Fourier transforms, Sauer bounds, NP-complete problems.

Goals of the Course

1. To enable students to determine resource requirements of computational problems

2. To enable the student to design resource-efficient algorithms

3. To enable students to give a precise analysis of the dynamic behavior of algorithms

4. To enable students to design for optimal solutions

5. To enable students to design algorithms for problems whose solution is intractable.

Course Content

A. Background

1. Turing machine models and Markov algorithms

2. Random access models

3. Circuits and straightline programs

4. Complexity measures in various models

5. Computation techniques: divide and conquer, dynamic programming, linear recurrences, proofs of correctness.

B. Upper Bounds

1. Data structure algorithms, binary search, union find Droblems, prioritv sieves

2. Radix sorting, sorting in time o, upper and lower bounds

3. Combinatorial and graph algorithms

a. Depth first search

b. Graph isomorphism

c. Path Droblems

4. String matching problems

C. Algebraic Algorithms

1. Matrix multiplication

a. Strossen's algorithm

b. Problems reducible to matrix multiplication

2. Fast Fourier transform

a. Discrete fast Fourier transform

b. Polynomial multiplication, interpolation

D. Lower Bounds

1. Diagonalization

2. Reducibilities

3. NP - complete problems

4. DSPACE, DTIME, NSPACE, NTIME hierarchies