Carl Sable

Catalog Data:

A continuation of ECE 264, also with an emphasis on practical implementation issues and good programming methodology. Topics include graphs, graph related algorithms and dynamic programming techniques. Also an introduction to some advanced topics such as Turing machines, computability, and NP-complete systems. Assignments include programming projects and problem sets.

Topics:

1. Review of topics from ECE264.
2. Priority queues: binary heaps, leftist heaps, binomial queues.
3. Graph algorithms: representations of graphs; graph applications; topological sort; shortest path algorithms (e.g., Dijkstra's algorithm and the Bellman-Ford algorithm); minimum spanning trees and related algorithms (e.g., Prim's algorithm); flow networks, the maximum-flow problem, and the Ford-Fulkerson method; the maximum-bipartite-matching problem; applications of depth-first search.
4. Algorithm strategies: greedy algorithms (scheduling problems, Huffman coding); divide-and-conquer algorithms (recursion, divide-and-conquer sorts, the Tower of Hanoi); dynamic programming (top-down versus bottom-up, memoization, the longest-common-subsequence problem); randomized algorithms (random number generators, the 8-queens puzzle); exhaustive search (backtracking, pruning).
5. Introduction to theoretical computer science: Gödel's theorem, Turing machines, computability, complexity theory, the P = NP? questions, NP-complete problems.

Course Outcomes:

This course provides both a theoretical understanding of advanced data structures and algorithms as well as practical knowledge as to when each is the most appropriate for a specific task. Students become comfortable implementing important data structures and algorithms from scratch, as well as applying existing implementations of data structures and algorithms to solve more general problems. The course also provides insight into advanced computer science topics, including Turing machines, computability, and complexity theory.

Students will attain:

1. In depth understanding of advanced data structures and algorithms.
2. Ability to efficiently implement data structures and algorithms from scratch.
3. Ability to apply data structures and algorithms to solve complex problems.
4. Insight into advanced topics related to theoretical computer science.

Assessment Methods:

Individual programming assignments to ensure that students can implement fundamental data structures and algorithms from scratch to solve complex problems; examinations to assess conceptual understanding and to ensure that students can recall basic knowledge and procedures on the fly.