---
tags: summer 2018 cs61bl
---
# CS 61BL Week 7 Notes
Hi! Every week, I like to compile notes based off confusing concepts about and good questions that I've been asked! If you’re already familiar with all the topics, check out the **Resources** section for practice problems or insights.

Also, if there’s anything that doesn’t make sense or seems confusing, feel free to shoot me an [email](mailto:[e-mail]).

## Table of Contents
[TOC]

## Sort Searching
A really common question on the exam is that we're given a column of numbers that are partially sorted and we have to determine which sort they're referring to. Refer to my [Week 6 Notes](https://hackmd.io/s/rJBu3gC4m) for understanding sorts.


### Strategy
The **best approach** to search problems is to actively look for a sort through all of the columns instead of looking at every column one-by-one and determining the sort. The latter strategy is not as effective because many sorts look very similar to each other.

Identify "easy to identify" sorts before progressing to more difficult ones. Then, use process of elimination to get the "difficult to identify" sorts and the ones you're unsure of.

### Easy To Identify
* **LSD Radix Sort:** Check if one column of **digits** is correctly sorted. Start from the right-most column of digits and move left.
* **MSD Radix Sort:** The **leftmost digits** should be sorted.
* **Selection Sort:** Check if the first part of the list is sorted using all the smallest numbers.

### Moderately Difficult to Identify
* **Merge Sort:** Merge Sort sorts things in groups of 2. Check if **pairs of numbers** are sorted the right order.
* **Heap Sort:** Heap sorts usually rely on a **max heap**. Check that the bottom is in sorted order with the the max numbers and the first number is the next max element.

### Difficult to Identify
* **Insertion Sort:** Check if the first part of the list is sorted by all the numbers you've seen so far. This requires you to run through insertion sort a bit.
* **Quick Sort:** If the pivot is given, run through the unsorted column of numbers with quicksort and see if any other column matches. If no pivot is given, try process of elimination. I recommend looking for quicksort **last** because it's the most time-consuming sort to actively search for.

Try the strategies above to reach the answer below:

## Resources
### Compiled by Tina

**Weekly Notes**
* [Week 1 Notes](https://hackmd.io/s/H1tr_k3bQ): covers Class Architecture, Primitive Types, Objects, 'Static' keyword, Equals vs ==, Constructors, Lookup, Access modifiers, and Recursion tips
* [Week 2 Notes](https://hackmd.io/s/BJIQ6vVGm): covers Inheritance, Abstract Classes, Interfaces, and Asymptotics
* [Week 3 Notes](https://hackmd.io/s/BkFrjIb77): covers Generics, Comparators and Comparables, Functions, Iterables and Iterators, and Exceptions
* [Week 4 Notes](https://hackmd.io/s/BkeKrctXQ): covers Data Structures and Tree Traversals
* [Week 5 Notes](https://hackmd.io/s/rJ2KvrG4Q): covers 2-3-4 Trees, Red-Black Trees, and Heaps
* [Week 6 Notes](https://hackmd.io/s/rJBu3gC4m): covers Djikstra's Algorithm, MSTs, and Sorting

**Note:** Check **Week 6 Notes** for more final review resources

**Weekly Problems**
* [Week 1 Resources](https://drive.google.com/open?id=180f9opglO7kWzNEvQbfiYpBDv_mrlv6n)
* [Week 2 Resources](https://drive.google.com/open?id=1R0ebAidVcnrhYV6NUkpqGdwjxZ-llbsN)
* [Week 3 Resources](https://drive.google.com/open?id=16qbiOzEZo99XIoRPJOKmgzeqvQIlf25M)
* [Week 4 Resources](https://drive.google.com/open?id=113zG4_9jo655emP3Re3bP6voMN3-xQkf)
* [Week 5 Resources](https://drive.google.com/open?id=16qbiOzEZo99XIoRPJOKmgzeqvQIlf25M)
* [Week 6 Resources](https://drive.google.com/open?id=13H_u9SJAFAgDkyd25ObnXyxYsY3CS335)
* [Week 7 Resources](https://drive.google.com/drive/folders/1rT4OPNVYlr8K6iOeDpO17didwgoNq2Rc?usp=sharing)