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 Binary Search

Class Schedule

Monday

• Intro and Big-O review
• Read the syllabus. Take the background survey and class policies quiz in elearn.
• Read CS160 Reader chapter 8.10 and 8.13.
• Do BigO Estimation WS. See Files link in elearn for this and all future worksheets.

Tuesday

• Git. Tackle part 1 & 4 of Git Crash Course (see below).
• Makefiles. Work through the Setup and Simple Program pages in the Makefile tutorial
• Check out assignment 1.

Wednesday

• Prewatch Big-O Details video and take reading quiz before class.
• Big-O
• Readings: Liang, Ch 18.1-18.3
• Do BigO Analysis Worksheet

Thursday

• Prewatch Search video and take reading quiz before class.
• Memory and Timing
• Searches
• Read Liang Ch 7.9 and 17.5.2 (linear search and binary search done iteratively and recursively)
• Optional second source reading: Linear and Binary search in the CS160 Reader Algorithms Chapter
• Do Searching WS
• Do Searching CPPLab - you can find the code as a QTCreator project in the Search project in the cs260Code repository

Set Up

Software On Your Computer

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.

• A C++ compiler and the make utility available from the command line on your computer. If you installed QTCreator, you have these available, although if you are on Windows, you need to make sure that they are on the PATH.

• Software to connect to the CS Student Server. You will be expected to use it to test your code for memory issues.

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.

Day 1 Materials

• Review Videos:

Day 2 Materials

Git

• 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, make a file README.md and add some text to it. Then commit the change and push it to github. Look at your github account on the web to verify the push.

• Extra Git resources:

  • Visual Git Reference - Visual explanation of basic git commands
  • LearnGitBranching - Interactive tour of basic git commands.
  • Pro Git Book - Free book on Git.

• Review Video:

Makefiles

• Work through the setup and Simple Program pages of the Makefile tutorial. For assignment 1, that is all you will need to make use of. You will need the Multiple Builds information in assignment 2.

• Extra info:

  • Extended Command line tutorial

  • Extended Make tutorial (Most of the examples are C based. Just sub in g++ instead of gcc for C++.)

Day 3 Materials

• Review Videos:

Day 4 Materials

C++ timing and memory

• Review Videos:

• Sample code is in the ClockTesting project in the cs260Code repository

Searching Algorithms

• Videos:

Assignment 1

We won't finish with the material for assignment 1 until next week. But, as soon as your learn how to use git to setup the assignment, you are ready to get started on parts 1 & 2 - they are CS161 level code. Get this done this week. Really. You will be sad if you do not.