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

Class Schedule

Day 1

Todo:

  • Take the class policy quiz in Canvas
  • Respond to the github username survey in Canvas
  • Do this BigO Estimation Worksheet and check against the key

Day 2

  • Tools review
  • Big O and Loops

Todo:


Day 3

  • Big O and functions
  • Quadratic sort review

Todo:


Day 4

  • Big O and recursion
  • Git and assignments

Todo:


You have a lot of freedom to choose when you get the work done each week.

There is a recommended schedule below to help you break up the work into manageable chunks. Trying to do all of your learning in one monster day of studying tends to be much less effective than working on smaller chunks of the material more often.

Although the major assignments are always due at the start of next week, there are often mid-week deadlines for other work (check Canvas for all due dates), so you can't wait until the weekend to get everything done.

If your schedule requires you to do most of your work for this class on the weekend, you should try to work ahead on the next week each weekend rather than playing catchup from the previous week. That way you have plenty of time to ask questions and get any needed help before your assignments are due.


Day 1


Day 2


Day 3


Day 4

Setting Up

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

  • VS Code including the Chemeketa worklog extension (Gitdoc). Make sure to install git and set up your identity as well.

  • Valgrind or Leaks. Including WSL if you are on Windows.

AddressSanitizer isn't available for Mac or Windows. And, there are a few types of errors it does not detect. So we are going to move to using valgrind (Linux) or Leaks (Mac)for memory issue checking.

On Windows, you can use WSL to run valgrind.

Both tools generate reports just like AddressSanitizer. The main difference is you do not set them up at compile time. Instead, you run your program through the tool. See the guides linked above for instructions.

Big O Basics

Read Ch 25.4-25.5. You may want to go back and skim 25.1-25.3 as well if you need a refresher on the basics of Big O.

This video covers the concepts from 25.4 and reviews the big ideas:


Some videos are marked "Important". Those have material not necessarily covered in the book, or that I think are particularly important to understand. You should make sure to watch those videos. Other videos, like the one above, are optional and just cover the material in the book. You can watch those if you want a review or a different explanation of the material, but they are not required.

This video covers using Big O to do estimations (25.5). This is a skill you will need on each assignment!


Big O Analysis

Read Ch 25.6-25.9

This video reviews ideas from 25.6-25.9 and gives some tips for doing Big O analysis:


Review Sorts

We covered some basic sorts in CS162. Refer to Ch 25.6-26.12 for a review of theses sorts. In particular, make sure you understand the terms Stability and Adaptivity, understand the strategy for each sort, and know the best/average case Big Os.

This video briefly reviews the terms and quadratic sorts (3:15-8:15 focus on bubble sort, which we will not cover, you can feel free to skip that portion):


Big O and Recursion

Read 25.11-25.13. Don't panic at the math (recurrence relations). As long as you learn to recognize the few basic patterns, you will be fine in this class. You won't have to solve any recurrence relations from scratch.

This video briefly reviews the key ideas:


Git and Assignments

You will use git to checkout and submit your assignment code.

This video explains/reviews some terminology and concepts behind git and GitHub that you will need to understand to work with the assignment repositories:

This video demonstrates the practical process of cloning a repository, making changes, and pushing those changes back to GitHub:


The video demonstrates making manual commits. You should be using the Chemeketa Worklog extension (gitdoc) to automatically generate your commits as you work. You will however have to handle pushing your commits.

There is a graded mini-assignment called Assignment 1 Prep due at the start of next week. It involves cloning your project, and pushing a change to it with the tag a0.

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