Exam 1 will cover all material presented in lecture since the beginning of the semester, with the exception of classes (9/28 lecture). Use the topics below as a guide in studying for the exam.

• Software Development
  • What the five phases in the Software Development Life Cycle are and what basically happens in each (in the "real world", not for CMSC202 projects)

• Recursion
  • The concepts of the runtime stack and activation records
  • How to follow and diagram the execution of a recursive function
  • How to write a recursive function
  • What the following types of recursion are: direct, indirect, mutual, tail, linear, tree

• Searching and Sorting
  • How linear and binary searches work conceptually
  • How each sort (bubble, selection, merge, quicksort) works conceptually
  • How to code the bubble and selection sorts
  • How to code the recursive functions (only) for the merge and quick sorts
  • How the merge sort and quicksort work conceptually
  • Why one might choose one search or sort over another

• Runtime Efficiency and Asymptotic Analysis
  • The concept of Big-Oh
  • The Big-Oh for all of the searches and sorts above
  • The most common functions encountered in Big-Oh analysis, from slowest to most rapid growth
  • The effect of constants and factors in Big-Oh functions
  • How to choose which algorithm to use based on its Big-Oh and other factors

  Last Modified: