CS 5114 Course Outline

Topic Week

Introduction: 1

Mathematical induction, examples

Complexity of Algorithms: 1-2

Asymptotic notation

Worst case/average case bounds

Recurrence relations

Design of Efficient Algorithms: 3-4

Polynomial evaluation

Divide and conquer

Dynamic programming

Sorting and Searching: 5-7

Binary search

Radix sort, insertion sort, mergesort

Quicksort, heapsort

Order statistics

Graph Algorithms: 8-9

Graph traversal

Minimum spanning trees

Shortest path problems

Hamiltonian tours

Geometrical Algorithms: 10-11

Convex hulls and related problems

Optimal placement

Intersection problems

Algebraic and Numeric Problems: 11-12

Polynomial multiplication

Matrix multiplication and related problems

Fast Fourier Transform

NP-Completeness: 13-14

Intractable problems

Cook's theorem

NP-Completeness proofs

Coping with NP-complete problems

Parallel Algorithms 15

Algorithms for shared-memory machines

Algorithms for interconnection networks