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 performance and std::vector

slides for Amortized performance and std::vector

Verifying asymptotic performance¶

Verifying asymptotic performance

slides for Verifying asymptotic performance

Tips for increasing actual performance¶

Tips for increasing actual performance

slides for Tips for increasing actual performance

C++ examples

Randomization¶

Randomization: part 1.

Randomization: part 2

Randomization: part 3

slides for Randomization

Amortized performance and std::vector¶

Verifying asymptotic performance¶

Tips for increasing actual performance¶

Randomization¶

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 these topics¶

Questions to be submitted this week

Course 9 topics¶

Self-study¶

The topics for this week are (i) The heap data structure, (ii) Implementing a heap as an array

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

The heap data structure¶

The heap data structure (part 1)

The heap data structure (part 2)

The heap data structure (part 3)

slides

Implementing a heap as an array¶

Implementing a heap as an array (part 1)

Implementing a heap as an array (part 2)

Implementing a heap as an array (part 3)

slides

Heap and heap operations¶

A Heap as an array¶

Extra links on the topic:

Typically a priority queue is implemented as a binary tree heap. An alternative data structure that can be used for a priority queue is a binomial tree heap

Week09 - Glossary