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

  • MergeSort

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:

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.

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

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.