Algorithms part I
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 the Burrows-Wheeler transform. Prerequisites. The 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).
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 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.