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

Setting Up

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

  • QTCreator - not required, but my sample code is set up as QTCreator 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. Your username is the same as your my.chemeketa gmail username. Your starting password is "changeme"; you can change it on the login screen.

Each week's outline is broken into four days, roughly corresponding to what an in person class would be doing. You can pace yourself, but trying to do multiple "days" of learning all at once is likely to be both less effective and less efficient than spreading it out.

Day 1

Class startup

Read the syllabus and class policies. Take the background survey and class policies quiz in elearn.

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!

Day 2

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

Day 3

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 (look at the Makefile that QTCreator generates in the Debug folder for an example), 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.

Day 4

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.