Week 8 - Algorithms

Learning objectives

Upon finishing this week, you should be able to:

  • Classify operations on an array based list based BigO time complexity
  • Write a binary search
  • Write various quadratic sort algorithms
  • Implement mergesort

Suggested pacing

Monday

  • Binary Search
  • Binary Search CPPLab
  • Read assignment 8. Part 1 just involves reading in some data and parsing it using 161-level code. If you are fuzzy on that, start work on part 1 now. Chip away on assignment 8 as you work on the material for this week - many parts of the assignment simply involve adapting your CPPLab code to work on the more complex data.

Tuesday

Wednesday

Thursday

  • Regular Expressions
  • Work on assignment 8
  • Check out the practice final questions and review guide in the files area

Friday

  • Take quiz 4
  • Take the final

Read Liang Ch 7.9 and 17.5.2 (linear search and binary search done iteratively and recursively)

Review Welcome to CS chapter 8.12 on the efficiency of search algorithms.

These videos review the two approaches and their efficiency:

Do the Binary Search - Vector CPPLab. In it, you will need to implement binary search on a vector - both an iterative and recursive versions. There are projects in the cs162Code repository you can use to do the work (where debugging is much easier) and then just copy/paste the final results into CPPLab.

Quadratic Sorts

Read Liang Ch7.10 and 19.1-19.3.

Review Welcome to CS chapter 8.13 on the efficiency of basic sorting algorithms.

These videos review the various algorithms and their efficiencies:

Do the Quadratic Sorts CPPLab. Again, there are projects in the cs162Code repository (one for Insertion Sort and one for Selection Sort) you can use to do the work (where debugging is much easier) and then just copy/paste the final results into CPPLab.

There are many sort visualization tools out there. Here are few that you can try:

  • Hackerearth This one is nice in that it allows you to specify the exact values to sort if you like and change the array size. Use the sidebar to switch which sort you are viewing.
  • visualgo This one animates pseudocode as it runs, allowing you to see how the steps of the algorithm match up with the work.
  • toptal This one allows you to compare different sorts against each other. To see one particular sort in detail, click on it.

MergeSort

Read Liang Ch 19.4.

This video covers how MergeSort works:

These two video cover the theoretical efficiency and show a practical demonstration of the difference between O(n^2) and O(nlogn):

Regular Expressions

Regular expressions don't really relate to anything else from this week, but they are an invaluable tool for searching and modifying strings - they are the go-to tool of programmers who need to search and extract information from big text files.

To learn about regular expressions, check out the video below and then do the activities in the Regular Expression worksheet (see Files in elearn)

In quiz 4, you will have a couple of quiz questions that deal with simple regexes. But you are NOT expected to master all the syntax and you do NOT have to write any C++ code to work with regexes. (We are just shooting for awareness on this topic.)

If you are interested, there is a project provided in the cs162Code repository (check the Extras folder) that you can check out to see regexes in action.

Regex Tools and References