Carl Sable

Associate Professor of Electrical Engineering

ECE 365: Data Structures and Algorithms II

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 ECE 264.
  2. Priority queues: binary heaps, leftist heaps, binomial trees.
  3. Graph algorithms: representations of graphs; graph applications; topological sort; shortest path algorithms (Dijkstra's algorithm and the Bellman-Ford algorithm); minimum spanning trees (Prim's algorithm); network flow problems; maximum-flow problems (the Ford-Fulkerson method); the maximum-bipartite-matching problem; applications of depth-first search.
  4. Algorithm strategies: greedy algorithms (heuristics, tries, Huffman codes); divide-and-conquer (recursion, mergesort, Tower of Hanoi); dynamic programming (top-down versus bottom up, memoization, the longest-common-subsequence problem); randomized algorithms (random number generators, skip lists, the 8-queens puzzle); exhaustive search (backtracking, pruning).
  5. Theoretical computer science: Gödel's theorem, Turing machines, computability, and complexity theory.

Course Outcomes:

  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 ensure that students can recall basic knowledge and procedures on the fly.