Unit6 -- Csc 115 Spring 2005 SO1/S02
Learning Objectives for this unit
- To understand concerns with efficiency
- To understand and to be able to use Big O notation
- To be able to calculate the running times and space requirements for
simple algorithms and data structures
Learning Resources for this week
Lecture slides:
6-Efficiency.ppt
Sample programs as found in the source directory of this project.
- No sample programs this week --
pseudocode for various examples is shown in the slides and in the book.
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:
- Why do we care about the running time of an algorithm?
- 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.
- What are the limitations of using experimental analysis of a program to determine
its running time?
- What is meant by constant, logarithmic, linear, quadratic and exponential complexity classes?
- Justify using a picture why the following proposition holds:
1 + 2 + 3 + ..... + (n - 2) + (n -1) + n = n(n+1)/2.
- Why is it sufficent to use pseudocode for analyzing our algorithms?
- 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:
- R-3.2
- R-3.6
- R-3.8
- R-3.9
- R-3.21
Go to the course website