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

Day 3

  • Quadratic Sorts
  • CPP Lab Quadratic Sorts

Day 4

  • Holiday

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 CPP Lab . In it, you will need to implement binary search on a vector—both 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 CPP Lab.

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 CPP Lab . 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 CPP Lab.

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.

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.