Week 9 - Algorithms

Learning objectives

Upon finishing this week, you should be able to:

  • Classify operations on an array based list based BigO time complexity
  • Write a binary search
  • Write various quadratic sort algorithms

Suggested pacing

Day 1

  • BigO review and classification of vector operations

Day 2

  • Binary Search

Day 3

  • Quadratic Sorts

Day 4

  • Regular Expressions

Online Activity Outline

Big-O

Review Big O in Welcome to CS chapter 8.10 and 8.12 and/or Liang Ch 18.2.

This video reviews the core ideas:

Then watch these videos that cover the efficiency of various array based list algorithms:

Asking VS Code to run a program for you (Run button or F5) can sometimes introduce unpredictable overhead. For accurate and repeatable results, you should always do timing by running your program by hand from the terminal.

Read Liang Ch 7.9 and 17.5.2 (linear search and binary search done iteratively and recursively)

Review Welcome to CS chapter 8.12 on the efficiency of search algorithms.

These videos review the two approaches and their efficiency:

Do the Binary Search - Vector CPPLab. In it, you will need to implement binary search on a vector - both an iterative and recursive versions. There are projects in the cs162Code repository you can use to do the work (where debugging is much easier) and then just copy/paste the final results into CPPLab.

Quadratic Sorts

Read Liang Ch7.10 and 19.1-19.3.

Review Welcome to CS chapter 8.13 on the efficiency of basic sorting algorithms.

These videos review the various algorithms and their efficiencies:

Do the Quadratic Sorts CPPLab. Again, there are projects in the cs162Code repository (one for Insertion Sort and one for Selection Sort) you can use to do the work (where debugging is much easier) and then just copy/paste the final results into CPPLab.

There are many sort visualization tools out there. Here are few you can try:

  • Hackerearth This one is nice in that it allows you to specify the exact values to sort if you like and change the array size. Use the sidebar to switch which sort you are viewing.
  • visualgo This one animates pseudocode as it runs, allowing you to see how the steps of the algorithm match up with the work.
  • toptal This one allows you to compare different sorts against each other. To see one particular sort in detail, click on it.

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 are NOT expected to master all the syntax and you do NOT have to write any C++ code to work with regexes. (We are just shooting for awareness on this topic.)

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

Final Assignment

The final assignment involves applying the algorithms from this week (as well as MergeSort from next week) to a large collection of real data.

You should get started on the assignment now, it is split into fairly discrete parts and the only part you are not ready for at this point is Part 3.