This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. We will look at general techniques (e.g., divide-and-conquer, dynamic programming, graph algorithms), as well as specific problem areas (e.g., sorting, searching, polynomial and matrix calculations). We will also look at issues of intractability, i.e., a discussion of the classes P (problems solvable in polynomial time) and and NP (problems for which a conjectured solution can checked in polynomial time), with the attendant issues of NP-completeness and the famous open problem of whether P=NP or not.
Time permitting: