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
The final next week is an in-person, pen and paper exam during the scheduled final time.

Suggested pacing

Day 1

Day 2

Day 3

  • More algorithms

Day 4

  • Final and quiz review
  • Review guide in Files area of Canvas under Week 10

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

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):

Do the MergeSort CPP Lab .

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 chapter 23 as reference as you do the CPP Labs. 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 the Algorithms CPP Lab .

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.