Data Structures and Algorithms: Class Notes (PDF)

Course description:

In CS 315, Algorithm Design and Analysis, you learn how to design and analyze algorithms. You see many algorithms that are standard tools for the working programmer, especially algorithms for searching and sorting lists, manipulating graphs, string matching, and numeric algorithms. You learn how to analyze time and space requirements of algorithms and see the concept of NP-completeness.

This course assumes that you are familiar with basic concepts of programming in a general purpose programming language such as C, C++, or Java, including programming features such as variables, control flow, iteration, and recursion, and structures such as arrays and records. The course reviews and extends your knowledge of queues, stacks, trees, and graphs. It covers asymptotic rate of growth, big-O, big-Theta, big-Omega, and recurrences, including the Master Theorem. You should be facile with college algebra (especially polynomial, logarithmic, and exponential functions), basic concepts of logic, set theory, and proof construction, counting techniques, and basic graph theory. The course only uses a small amount of calculus.

Although many modern programming languages provide libraries or built-in functions that implement data structures and algorithms we cover in the class, you will be coding them from basic elements in order to learn the underlying principles. Not using built-ins and libraries will be frustrating.