This course is an introductory undergraduate course on the design and analysis of algorithms. The goal of this course is to introduce basic- fundamental algorithm design techniques that are interesting both from a theoretical and practical point of view. We will cover basic algorithm design techniques such as divide-and-conquer, dynamic programming, and greedy techniques for optimization. We will cover techniques for proof of the correctness of algorithms, and also asymptotic analysis of algorithm time bounds by the solution of recurrence equations. Some specific algorithm topics include: deterministic and randomized sorting and searching algorithms, depth and breadth first search graph algorithms for finding paths and matchings, and algebraic algorithms for fast multiplication and linear system solving. Student computer background should include recursive procedures, and data structures from object orientated programming such as arrays, queues, binary trees, graphs, and linked lists. Student mathematical background should include mathematical induction and elements of calculus. This course will employ pseudo code for which an understanding of a high-level programming course is required. Students are expected to have experience in a high-level programming language.

Computer Science Elective Credit