Week 10 - Algorithms & The Standard Template Library (STL)
Learning objectives
Upon finishing this week, you should be able to:
- Write MergeSort
- Use std::algorithms
The final is next week is an in-person, pen and paper exam.
I will have two blocks of time available next week where you can drop in and take the exam. See discussion board for details.
If you can't make one of those times, you can book an appointment in the testing center, or the math hub, or get my approval to have it proctored somewhere else. You will NOT be able to make an appointment at one of these location and take the test in the same day. Book your appointment NOW if you intend to use one.
Suggested pacing
Day 1
- Std::Algorithms
- Do Algorithms CPPLab
Day 2
- Regular Expressions
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
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.
Regular Expressions
Regular expressions don't really relate to anything else from this week, but they are an invaluable tool for searching and modifying strings - they are the go to tool of programmers who need to search and extract information from big text files.
To learn about regular expressions, check out the video below and then do the activities in the Regular Expression worksheet (see Files in elearn)
You may see a couple of quiz questions that deal with simple regexes. But you do not have to write any C++ code to work with regexes. If you are interested, there is a project provided in the cs162Code repository (check the Extras folder) that you can check out to see regexes in action.
Regex Tools and References
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.