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