Week 1 - Algorithm Complexity

Learning objectives

Upon finishing this learning module, you should be able to:

  • Analyze simple functions in terms of BigO
  • Reason about the relative efficiencies of different BigO categories
  • Use a makefile to build a C++ program
  • Implement MergeSort on a plain array

Class Schedule

Monday

  • Intro and Big-O review
  • Read the syllabus
  • Take the background survey
  • Work on Setup
  • Do BigO Efficiency WS

Tuesday

  • Big-O Math & Analysis
  • Do BigO Analysis Worksheet

Wednesday

  • Quadratic Sort review
  • Git and Makefiles
  • Check out assignment 1 make a makefile for it. (See Git Crash Course and Makefile Tutorial)

Thursday

  • BigO analysis for recursion
  • Mergesort review
  • Do Mergesort WS and CPPLab

Setting Up

You will want to get the following setup on your computer if they are not already from CS162:

  • VS Code - not required, but my sample code is set up as VS Code projects. You probably will want some IDE with a debugger. See the Resource Links.

  • Valgrind - including WSL if you are on Windows. See install and use instructions under Resource Links.

CPPLab

If you are not familiar with CPPLab, watch the video below. We will use it to get some of the small scale practice required to really understand what you are doing.

Topics

Big O

  • This video is from CS162 - give it a quick watch if you are feeling like you could use a quick review of Big O:
  • This video covers using Big O to do estimations. This is a skill you will need on each assignment!

Big-O Math & Analysis

  • Readings: Liang, Ch 18.1-18.3

  • This video covers the mathematics of Big O and why we can do things like ignore constant factors:

  • This one covers analyzing code to determine Big O:
  • Do BigO Analysis Worksheet

Review Quadratic Sorts

We covered quadratic sorts (sorting algorithms with a run time efficiency of O(n^2) ) like Insertion sort and Selection sort in CS162. Watch this video to review them and two important terms we will use to help decide when to use what sorting algorithm: Stability and Adaptivity.

Git Crash Course

  • Watch

  • Use part 1 of the Git Crash Course to get access to my samples.

  • Use part 4 of the Git Crash Course instructions to make a repository for assignment 1. In that repository, edit the README.md and/or add a main.cpp file. Then commit the changes and push it to github. Look at your github account on the web to verify that your changes appear there.

  • Optional: See the Resources Links for optional advanced Git resources.

Makefiles

Makefiles are a mechanism for automating tasks like building code. Given a new codebase, instead of trying to figure out what files to compile and what options to specify to the compiler, a makefile allows you to just say something like make -f MyMake to execute a prewritten build recipe.

Each assignment you turn in will need to include a makefile called MyMake that I can use to build your code. Although makefiles can be very complex, they can be very simple. We will be building simple ones.

  • Work through the Setup and Simple Program section of the Makefile Tutorial. (For future reference, you can find a link to the tutorial in the Resources Links area of the sidebar).

    You will NOT need to worry about Multiple Builds or Complex Recipes for assignment 1.

Recursion & Big O

  • Video review:

Mergesort

You learned about Mergesort in CS162. But that was a simple version that used vectors and literally split the list into two parts. When implemented for a plain array, we generally do not actually "split" the array (something that is impractical to do without just copying to new arrays) - instead we use indexes to focus on different parts of the array at any given moment. Functions will take a low and high index that mark the part of the array they are working on. "Splitting" that part simply means finding the midpoint between low and high and recursively handling low to mid and mid to high.

  • Optional - if you need in depth review. Read Liang Ch 18.4.1-18.4.4, Ch19.4.
Please note that the merge sort shown in the book is slightly different than the one I talk about and ask you to build. The book version makes a new array for each merge. This ends up making O(N) memory allocations to sort an array of size N. That is wildly inefficient, even if it still runs in nlogn time.
  • Do the Merge Sort Worksheet to think through the work needed to do a merge
  • Do the Merge Sort CPPLab

Sorting Resources

Assignment 1 Prep

We won't finish with the material for assignment 1 until next week. But you should be ready to do parts 0-2 now.

There is a graded mini-assignment called Assignment 1 Prep due at the start of next week. It involves doing part 0 and pushing your code to Github. See Canvas for details.