CS201 Study Guide

Unit 6: Algorithm Efficiency

6a. Examine algorithms relative to their resource utilization

  1. What are the various resources consumed when a program is running?
  2. Why is it important to balance resource utilization when examining program efficiency?
  3. What is an effective empirical approach to resource analysis?
  4. Why are considerations of algorithm efficiency are important?
  5. What are the classical equations that describe the efficiency of various resource utilizations?
  6. Why does one better concentrate on the underlying efficiency equations rather than their magnitude?

An understanding of algorithm efficiency is part of creating effective applications. Realizing their importance (as described in this video from 31:30 to the end), you can guide algorithm development to achieve the most satisfying results. Many applications depend on code modules running within a given length of time, even if the application only requires soft-real-time. A major topic within this domain is Big-O analysis. This is a means of discovering an algorithm implementation's efficiency measure. Most discussion in this arena focuses on runtime. However, you must also consider other resources. An example is the tradeoff between memory and time. For distributed systems, you must also consider the volume of data on the network.

 

Unit 6 Vocabulary

This vocabulary list includes terms that might help you with the review items above and some terms you should be familiar with to be successful in completing the final exam for the course.

Try to think of the reason why each term is included

  • Big-O analysis
  • cO(f(n))
  • efficiency vs. effectiveness
  • space/time tradeoff
  • constant, linear, logarithmic, quadratic resource consumption growth rates
  • difference between best, worst, average cases
  • resource utilization growth with increasing data loads
  • hardware/software tradeoffs
  • upper bound
  • lower bound
  • empirical analysis