Week 10 - Algorithms & The Standard Template Library (STL)

Learning objectives

Upon finishing this week, you should be able to:

  • Write MergeSort
  • Use std::algorithms
Quiz 4 is open this Thurs-Sunday. It covers weeks 8-10

Schedule

Day 1

  • MergeSort

Day 2

  • Std::Algorithms
  • Do Algorithms CPPLab

Day 3

  • Final review
  • Review guide in Files area of Elearn under Week 10

Day 4

  • Review for and take Quiz 4

Final Notes

Here are the big ideas you should feel confident writing code on/answering questions about:

  • Pointers & Shared memory
  • Container classes - especially memory management (copy ctor, destructor and assignment operator)
  • Templated functions/classes
  • Recursion
  • Searching & Sorting

These topics are important and may appear, but were covered on the midterm and thus will not be as big an emphasis on the final.

  • Objects & Composition
  • Inheritance, Polymorphism & Virtual Functions

Online Activity Outline

MergeSort

Read Liang Ch 19.4.

This video covers how MergeSort works:

These two video cover the theoretical efficiency and show a practical demonstration of the difference between O(n^2) and O(nlogn):

STL Algorithms

When a developer needs a standard algorithm like a sort, they generally reach for a library implementation of that algorithm. Once someone has built and tested a version of a sort algorithm, there isn't a need to reinvent the wheel.

In C++, there are a large collection of generic classes and algorithms known as the Standard Template Library (STL). As the name implies, these are templated constructs that can be used to work with any type of data. These constructs can be roughly divided into two categories of things: containers and algorithms.

The containers are things like vector - classes designed to hold data and handle the low level work of managing memory while allowing us to program using a higher level interface. In CS260 we will cover a number of other containers from the STL.

The algorithms are functions designed to do all kinds of jobs on data structures - find things, sort things, copy things, modify items, etc.... They are a powerful way to interact with data.

Read Ch 23.1-23.2. Use the rest of 23 as reference as you do CPPLabs. You should NOT try to memorize all the algorithms, just become familiar with what tools there are.

This video covers how the algorithms work:

And this one compares solving a problem with and without using the std::algorithms:

Do Algorithms CPPLab.

Quiz & Final Review

The last quiz includes material from weeks 8, 9, and 10.

There is a review guide for the final in the Files area of week 10.