The University of Arizona

Courses

CS 445: Algorithms

Objective
Pre-Conditions
  • [CS342] Basic understanding of O-notation.
  • [CS344] Basic understanding of recurrence relations/recursion.
  • [CS344] Two semesters of induction.
  • [CS344] Predicate calculus, ability to write a simple logical proof.
  • [CS344] Relations and functions.
  • [CS342] Basic graphs: definitions, representations.
  • [CS342] Basic data structures: linked structures, stacks, queues, trees, graphs, hash tables, searching & sorting.
  • [CS344] Basic probability: probability space, random variables, events, expected value
Post-Conditions
(Topics)
  • Detailed understanding of O, Omega, & Theta.
  • Greater understanding of recurrence relations.
  • Induction as a means to formally prove algorithms correct.
  • Induction as an algorithm design principle.
  • Design paradigms: divide-and-conquer (e.g. order statistics), greedy algorithms (e.g. scheduling, Huffman codes), dynamic programming (e.g. optimal search trees, knap sack, sequence comparison).
  • Graph algorithms: topological sort, DFS & BFS (e.g. connectivity), shortest paths, minimum cost spanning trees, transitive closure.
  • String sorting and searching (includes radix sort).
  • As time permits: branch-and-bound, four-Russians, network flow.


Last revised on 28 February 1997 by John Hartman.