Description. An introduction to fundamental data types, algorithms, and data structures. Our emphasis is on applications and scientific performance analysis of Java implementations.
- Part I focuses on elementary data structures, sorting, and searching. Topics include union−find, binary search, stacks, queues, bags, insertion sort, selection sort, shellsort, quicksort, 3-way quicksort, mergesort, heapsort, binary heaps, binary search trees, red−black trees, separate-chaining and linear-probing hash tables, Graham scan, and kd-trees.
- Part II focuses on graph and string-processing algorithms. Topics include depth-first search, breadth-first search, topological sort, Kosaraju−Sharir, Kruskal, Prim, Dijkistra, Bellman−Ford, Ford−Fulkerson, LSD radix sort, MSD radix sort, 3-way radix quicksort, multiway tries, ternary search tries, Knuth−Morris−Pratt, Boyer−Moore, Rabin–Karp, regular expression matching, run-length coding, Huffman coding, LZW compression and Burrows−Wheeler transform. Part II also introduces reductions and intractability, including the P = NP problem.
Prerequisites. The programming prerequisite for the course is familiarity with Java, including loops, arrays, functions, recursion, and objects. We introduce advanced features of Java as necessary (such as generics and iterators). The mathematics prerequisite is high-school algebra.
Lectures. There are two lectures (75 minutes each) per week. Each lecture is broken up into about 4−6 segments, separated by interactive quiz questions to help you process and understand the material.
Readings. Our textbook is the basic reference for the material we will be covering. Although the lectures are designed to be self-contained, we will assign suggested (but optional) readings for students who wish more extensive coverage of the material.
- Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011, ISBN 0-321-57351-X.
Our booksite is open to everyone and contains a wealth of supplementary information, including synopses of the textbook and Java code that you will be using throughout the course.