1. COMP.CS.300 Data Structures and Algorithms 1 »
  2. Course week 8 - Amortized complexity »
  3. Week 8 of the course

Week 8 of the course

Self-study

The topics for this week are the following: (i) Amortized performance and std::vector (ii) Verifying asymptotic performance (iii) Tips for increasing actual performance and (iv) Randomization

The following links will take you to the video-lectures and the accompanying slides:

Amortized performance and std::vector

Amortized efficiency means
Suppose we use an STL vector \(v\) and all we do is add elements to the end of \(v\). Suppose also that the size of \(v\) is doubled in situations when \(v\) runs out of memory. Which of the following is true concerning the efficiency of adding a single element to \(v\)?

Verifying asymptotic performance

With regard to verifying an algorithm’s asymptotic efficiency, which of the following are true? (More than 1 statement may be true.)
Suppose for algorithm \(X\) we have a large collection of input data cases where the size of the input data spans several orders of magnitude. Suppose we run \(X\) for all inputs cases and we measure the execution time (say in seconds). If we want to say something about asymptotic efficiency of \(X\), why should we do some statistical analysis of the measurements?

Tips for increasing actual performance

Choose the methods that can be used to improve the actual performance of some program. (There may be more than 1 correct choice.)
Suppose in C++ we have stored a collection of \(n\) numbers in a vector \(v\) and \(n\) is very large. For which of the following situations does it make sense to first sort all the elements of \(v\)?
Suppose in C++ we have a large collection of numbers stored in an unsorted vector \(v\) and we often add new elements to \(v\), but we never remove elements from \(v\). Suppose in addition we often need the largest element in \(v\). Of the following, which is the least efficient way of calculating the largest element?

Randomization

What is a valid reason for using randomization in some algorithm?
When randomization is added to Quicksort to avoid Quicksort’s worst case behaviour, how is it typically added?
Suppose we have a vector \(v\) having \(n\) elements and we randomly shuffle all \(n\) elements. What can be said about this shuffling operation?
What is a central question, related to this course, whose answer can be found in this week’s videos?
Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?
Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

There is no shortage of opinions on how to improve the efficiency of C++ code. Here is one link and a warning. Some of information is quite technical. -A long discussion in stackoverflow:

Week08 - Glossary

Homework to be returned for the weekly exercises

Questions to be submitted this week