Course Topics:
A course for first- and second-year college undergraduates which covered the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations.
Algorithms Part I
Focused on elementary data structures, sorting, and searching.
Topics include:
- Union-find, binary search, and Graham scan
- Stacks, queues, bags, binary heaps, separate-chaining and linear-probing hash tables
- insertion sort, selection sort, shellsort, quicksort, 3-way quicksort, mergesort, heapsort
- Binary search trees, 2-3 search trees, red−black trees, and kd-trees
- Order-of-growth classifications
Algorithms Part II
Focused on graph and string-processing algorithms.
Topics include:
- Depth-first and breadth-first search on directed graphs, undirected graphs, and digraphs, and used Kosaraju−Sharir algorithm
- Topological sort, LSD radix sort, MSD radix sort, and 3-way radix quicksort
- Multiway and ternary search tries
- Finding minimum spanning trees through greedy, Kruskal, and Prim algorithms
- Solving shortest-path problems with Dijkistra and Bellman−Ford-Moore algorithms
- Implementing max-flow and min-cut algorithms like Ford−Fulkerson and studied potential applications like bipartite matching and baseball elimination
- Applying Knuth−Morris−Pratt, Boyer−Moore, and Rabin−Karp algorithms to substring search problem
- Intractability, complexity classes, and P?=NP
