Week 1: Algorithm Complexity and Analysis

Textbook Choices:

You may use either the new online 4th edition of the Introduction to Programming With C++ book, or the physical 3rd edition.
  • The discussion board has a link to access the correct class for the online 4th edition. It has interactive practice questions and the readings will be broken up by due date.
  • For the physical 3rd edition, you will also need Chapters 18+ which are available as PDF's from publisher's website. You will need the code from the inside cover of your book to download the PDF chapters. If that code has been used already (used book), you can purchase a code via their website (~$25).

Activities

Setup

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 tools links above and Week 1 of 161 for setup instructions.
  • Chemeketa Linux Dev Environment (VirtualBox & Vagrant). See instructions under tools link at top of page. See this video for how to use it.

Monday

Tuesday

  • Git crash course
    • Use the Git Crash Course instructions (from Tools link above) 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.
    • At home, use part 1 of the Git Crash Course to get access to my samples.
    • Extra git resources:
  • Makefiles
    • Work through Parts 0 and 1 in my Makefile Tutorial file in the classroom files folder below. You will need the skills from Part 1A for assignment 1. You will not need Part 2 until assignment 2. There is also a copy of my Command Line Quick Reference in the same folder.
    • Extra info:

Wednesday

  • Big-O Continued
  • Do BigO Analysis WS
  • Readings: Liang, Ch 18.1-18.4 (18.4.1-18.4.3 we will talk about in more detail next week - you can skip them for now).

Friday

  • C++ timing and memory reminders
  • Searching algorithms
  • Readings: Ch 7.9 and 17.5.2 (linear search and binary search done iteratively and recursively)
  • Do Search Worksheet
  • Extra resources:

Extra Practice

The TRAKLA website has lots of cool data structures related practice tools: http://www.cse.hut.fi/en/research/SVG/TRAKLA2/. Unfortunately, they are written as Java applets and most current browsers refuse to run that style of program. To use them, you will have to:
  • Install Java: https://java.com/en/download/
  • Download the .jar file of the TRAKLA practice apps. See the Data Structures Tools & Tutorials section in the menu at the top of this page and find the Trakla .jar file link. If Java is installed, you should be able to run it by double clicking it.
  • Below are links to instructions for various practice activities. Use those instructions with the .jar program. Warning: the .jar file version of the applets use different names in paraentheses after each link to instructions is the applet to look for in the Trakla .jar.

Classroom slides/examples:

Directory of classroom files from the week
Right click files and save to your computer

Assignment:

Assignment #1 (due Monday 10/7 at midnight)

Notes:

  • Please do the elearn survey in the next day or two.