CIS 500

Prerequisites by Topic

  • working knowledge of a high-level language, preferably Java, C, or C++;
  • ability to use and implement common data structures such as lists, stacks, queues, and trees;
  • ability to use and understand recursion; and
  • ability to understand, manipulate, and graph algebraic formulas including polynomials, exponentials and logarithms.

Knowledge and Skills Acquired

  • Mastery of:
    • Use of Hoare logic for proving correctness of simple algorithms
    • Mathematical induction
    • Worst-case analysis of algorithms involving for-loops
    • Deriving recurrences describing the worst-case time complexity of recursive algorithms
    • Obtaining asymptotic solutions to certain types of recurrences
    • Application of the above theory to various data structures and to graph algorithms
  • Familiarity with:
    • Average-case analysis
    • Amortized analysis
    • Techniques for analyzing time-complexity of nontrivial loop structure
    • Techniques for implementing advanced data structures, including graphs
    • Application of the above theory to actual programs