Unit6 -- Csc 115 Spring 2005 SO1/S02

Learning Objectives for this unit

Learning Resources for this week

Lecture slides: 6-Efficiency.ppt


Sample programs as found in the source directory of this project.

Reading Assignment:

Read Chapter 3 (you may omit section 3.5, recommended reading for students wanting to take Csc 225)

Activities:

Short Answer Questions

Answer the following questions:
  1. Why do we care about the running time of an algorithm?
  2. The choice of a data structure in a program can impact both the running time and the space requirements for the program. Try to consider how you would describe this fact to a non-computer specialist.
  3. What are the limitations of using experimental analysis of a program to determine its running time?
  4. What is meant by constant, logarithmic, linear, quadratic and exponential complexity classes?
  5. Justify using a picture why the following proposition holds:
    1 + 2 + 3 + ..... + (n - 2) + (n -1) + n = n(n+1)/2.
  6. Why is it sufficent to use pseudocode for analyzing our algorithms?
  7. If computers are getting faster and faster -- one day will we not care about how fast our algorithms run?

Problems in the textbook, Chapter 3:




Go to the course website