Exam 2 Study Guide

You MUST present a picture ID upon turning your exam in.

Exam Date: Tuesday, April 16

Use the list of topics below as a guide when studying for Exam 2. It is by no means a comprehensive list of all material that you are responsible for. In general, you are responsible for the material presented in lecture from searching and sorting through copy constructors and overloaded assignment. (Inheritance and polymorphism will be covered on the final exam.) You are also responsible for all associated reading assignments.

• Searching and Sorting
  • The concepts of linear and binary searches.
  • How to improve the efficiency of a linear search.
  • The concepts of selection, bubble, merge, and quick sorts.
  • How to improve the efficiency of a bubble sort.
  • Be able to diagram and explain (as we did in class) how a bubble, merge, or quick sort works.
  • Be able to write the code for a bubble, merge, or quick sort. (For merge sort, you you need to be able to write only the mergesort() function code. For quick sort, you need to be able to write only the quicksort() function code.)

• Runtime Efficiency and Asymptotic Analysis
  • The concept of Big-Oh
  • How the 90/10 Rule and the "critical 10%" apply to improving algorithm efficiency
  • 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

• Pointers and Dynamic Memory Allocation
  • For a given code segment, be able to draw a picture, using the notation that was presented in class, of the data structure that it would generate.
  • For a given picture of a data structure, be able to write a code segment that would generate that data structure.
  • The concepts of memory leaks and dangling pointers and how they occur
  • How a program calculates the address of an array element
  • How to draw a picture of a dynamically allocated multi-dimensional array (as generated by a C++ program)
  • How to write the code to dynamically allocate or deallocate a multi-dimensional array

• Copy Constructors and Overloaded Assignment
  • Under what situation(s) a copy constructor is needed (i.e., when is it invoked?)
  • How to write the code for a copy constructor
  • Under what situation(s) an overloaded assignment operator is needed
  • How to write the code for an overloaded assignment operator
  • Why it is necessary to check for self-assignment
  • How to allow for cascading (i.e., a = b = c;)