Click on any link below to view.

Summer 2017

Lab 02. Object Oriented Waffle-gramming.

June 20, 2017.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public class Waffle { // Fields private boolean isDelicious; private int numStrawberries; // Constructors public Waffle(boolean isDelicious, int numStrawberries) { this.isDelicious = isDelicious; this.numStrawberries = numStrawberries; } // Methods public boolean isDelicious() { return isDelicious; } public void addStrawberries(int num) { this.numStrawberries += num; } } |

Can you draw a box and pointer diagram for the execution of the following lines?

1 2 3 4 5 | public static void main(String[] args) { int numStrawberries = 35; Waffle mattsWaffle = new Waffle(true, numStrawberries); mattsWaffle.addStrawberries(10); } |

Lab 04. Waffle Inheritance.

June 23, 2017.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public class Food { private boolean isDelicious; public static String shout = "YAAAAAAAS!"; public Food(boolean isDelicious) { this.isDelicious = isDelicious; } public boolean isDelicious() { return isDelicious; } public void consume() { System.out.println("nibble nibble"); } } |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 | public class Waffle extends Food { int numStrawberries; public Waffle(int numStrawberries) { super(true); this.numStrawberries = numStrawberries; } @Override public void consume() { System.out.println("nom nom nom"); } } |

What will Java display for each of the following?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | // Example 1 Food mmm = new Food(true); mmm.consume(); // Example 2 Waffle mmm = new Waffle(35); mmm.consume(); // Example 3 Waffle mmm = new Food(true); mmm.consume(); // Example 4 Food mmm = new Waffle(35); mmm.consume(); |

We also learned about access modifiers in Java.

*public*allows for access within the class, package, subclasses, and globally.*protected*allows for access within the class, package, and subclasses.- When
*no modifier*is specified, there is access within the class and package. *private*allows for access within the class only.

Lab 05. Iteration and Recursion over LinkedLists.

June 26, 2017.
Here are iterative and recursive approaches to counting the number of nodes with val of 42 in a non-encapsulated IntList.

1 2 3 4 5 6 7 8 9 10 11 | public int count42Iter() { IntList curr = this; int count = 0; while(curr != null) { if (curr.val == 42) count++; curr = curr.next; } return count; } |

1 2 3 4 5 6 7 8 9 10 11 12 13 | public int count42Recur() { if (next == null) { if (val == 42) return 1; else return 0; } else { if (val == 42) return 1 + next.count42Recur(); else return next.count42Recur(); } } |

Lab 06. Arrays vs LinkedLists.

June 27, 2017.
Compare and contrast each of these data structures according to the guiding questions below: Array, Singly LinkedList, Doubly LinkedList.

- How do you
*access*an element at a given index? - How do you
*search*for a particular value? - How do you
*insert*a new element at a particular index for arrays or after a particular reference for LinkedLists? - How do you
*delete*the element at a particular index for arrays or corresponding to a particular reference for LinkedLists?

Lab 07. Asymptotic Analysis.

June 29, 2017.
Some strategies for asymptotic analysis:

If you are simply asked for the runtime of the function and you find that you cannot give a tight bound, you should give an upper bound and possibly a lower bound as well if it is meaningful. These bounds would describe the range of runtimes for all possible cases of inputs.

If for the same code you are asked specifically for the best case or worst case runtime, then you would give the same magnitude answer as your lower or upper bound, respectively, but you would present it as a tight bound. This is because the best (or worst) case is one particular case (one particular input) and thus you would state that that one case is tightly bound by a particular function; it doesn't really make sense to say that one case is lower or upper bounded (it's vague to state that when you can provide a tight bound instead).

- Try some test inputs to see what the function does and to get a feel for its flow.
- Label lines of code with their runtime to determine if some are insignficant compared to more expensive lines.
- If there are nested loops, draw bars.
- If there is a recursion, draw a tree representing the function calls.
- Perhaps represent and simplify a mathematical expression.

If you are simply asked for the runtime of the function and you find that you cannot give a tight bound, you should give an upper bound and possibly a lower bound as well if it is meaningful. These bounds would describe the range of runtimes for all possible cases of inputs.

If for the same code you are asked specifically for the best case or worst case runtime, then you would give the same magnitude answer as your lower or upper bound, respectively, but you would present it as a tight bound. This is because the best (or worst) case is one particular case (one particular input) and thus you would state that that one case is tightly bound by a particular function; it doesn't really make sense to say that one case is lower or upper bounded (it's vague to state that when you can provide a tight bound instead).

Lab 08. Exceptions with Minions

June 30, 2017.
1 2 3 4 5 6 7 8 9 10 11 | try { bello(); } catch (NullPointerException e) { System.out.println("Po-ka?"); throw new ArrayIndexOutOfBoundsException(); } catch (Exception e) { System.out.println("Hana, dul, sae!"); } finally { System.out.println("Bee-do Bee-do!"); throw new NoSuchElementException(); } |

What happens if

Some subtleties to take note of:

- Exceptions thrown in a catch block are not caught by later catch blocks.
*finally*always, always runs.- Only the last-thrown exception propagates up the call stack.

Finally, here's our vocabulary for the day!

Lab M1. Midterm 1 Review.

July 03, 2017.
Topics represented here are based upon your self-reflection responses of which topics were most challenging;
inclusion or exclusion of topics here does not imply inclusion or exclusion of topics on any upcoming exams.

Practice problems:

Practice problems:

- Static/Dynamic Typing, Casting.
- Asymptotics.
- Box/Pointer Diagrams, Exceptions
- LinkedLists

Lab 09. Interfaces and Abstract Classes.

July 06, 2017.
- Compare and contrast interfaces and abstract classes. (CSM 61BL Su17, WS 3a, Q1a.)
- When resizing the underlying array within an ArrayList, is it better to increase the size of the array by 10,000 elements or to double the size of the array? Defend your answer using asymptotic analysis. (CSM 61B Sp17, WS 8, Q2.)

Lab 10. Generics and Iterators at Disney.

July 07, 2017.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | public static void main(String[] args) { DisneyRides2 d = new DisneyRides2(); d.add("Space Mountain"); d.add("Splash Mountain"); d.add("Small World"); // METHOD 1: // for loop as we've seen before. for (int i = 0; i < d.size(); i++) { System.out.println(d.get(i)); } // METHOD 2: // Using an iterator to abstract away underlying implementation. Iterator<String> iter = d.iterator(); while(iter.hasNext()) { System.out.println(iter.next()); } // METHOD 3: // Short hand for-each loop that uses iterators behind the scenes. for (String s : d) { System.out.println(s); } } |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | import java.util.ArrayList; import java.util.Iterator; public class DisneyRides implements Iterable<String> { /** Fields **/ // ArrayList of Objects. Requires cast in get() method. // private ArrayList rides = new ArrayList(); // ArrayList of Strings. Generics eliminates need to cast by specifying static type of contained items. private ArrayList<String> rides = new ArrayList<String>(); /** Methods **/ // Add an item to our list after putting it in all-caps. void add(String ride) { rides.add(ride.toUpperCase()); } // Retrieves item at index i. String get(int i) { // return (String)rides.get(i); return rides.get(i); } // Retrieves number of total items. int size() { return rides.size(); } @Override // Provides a new iterator that starts from beginning of list. public Iterator<String> iterator() { return new DisneyRidesIterator(); } /** Nested subclass to define the iterator for our data structure. **/ class DisneyRidesIterator implements Iterator<String> { // Counter for our iterator. private int i = 0; @Override // Tells us if there are still more items. // Cannot modify current state of data structure in any way. public boolean hasNext() { return i < rides.size(); } @Override // Retrieves next item. // Updates state of data structure for next time. public String next() { String result = rides.get(i); i++; return result; } } } |

Lab 11. Equality, Comparison, and Java 8.

July 10, 2017.
If we had

If we also had

When defining new classes, if we wanted to be able to sort an array of our object through

There is also the

But having to define an entire object comparator class just to sort a particular way is cumbersome. We can produce the same result by using a lambda instead:

The

The data structures we've seen so far (arrays, ArrayLists, LinkedLists) are known as collections and they were designed with the efficient management of and access to elements in mind. On the other hand, we can convert these to streams for parallel (or at least automatically optimized) processing since streams are concerned with performing aggregate computational operations on a source of elements.

The typical strategy to using streams is to first convert your collection to a stream, performing intermediate operations to manipulate the stream, and then converting it out of a stream using a terminal operation.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 | List<Integer> l = new ArrayList<>(); for (int i = 0; i <= 30; i++) { l.add(i); } l = l.stream() .filter(o -> o%2==0) .collect(Collectors.toList()); int a = l.stream() .map(o -> o*o) .reduce((o1, o2) -> o1+o2) .orElse(0); |

Lab 12. Pre-, In-, Post-Order.

July 11, 2017.
Pre-order, In-order, and Post-order are ways to describe when nodes in a binary tree are processed (an example of processing a node would be printing its value).
A binary tree is a tree in which nodes can have up to 2 children each.

Pre-order means to process the current node before pre-order traversing down the left and right of the current node. In-order means to first in-order traverse the left of the current node, process the current node, and then in-order traverse down the right of the current node. Post-order means to post-order traverse down the left and right of the current node before finally processing the current node.

Visually, you can determine the order nodes are processed during pre-, in-, or post-order traversal by drawing a peg on the west, south, or east side of each node, respectively, and tracing a line around the tree diagram as shown below. The nodes are processed in the order the yellow line touches each red peg.

*
Pre-order has pegs on the west side of each node.*

A, B, C, D, E.

*
In-order has pegs on the south side of each node.*

B, A, D, C, E.

*
Post-order has pegs on the east side of each node.*

B, D, E, C, A.

More formally, we can write this pseudocode to reflect the definitions of when pre-, in-, and post-order processing occurs:

Pre-order means to process the current node before pre-order traversing down the left and right of the current node. In-order means to first in-order traverse the left of the current node, process the current node, and then in-order traverse down the right of the current node. Post-order means to post-order traverse down the left and right of the current node before finally processing the current node.

Visually, you can determine the order nodes are processed during pre-, in-, or post-order traversal by drawing a peg on the west, south, or east side of each node, respectively, and tracing a line around the tree diagram as shown below. The nodes are processed in the order the yellow line touches each red peg.

A, B, C, D, E.

B, A, D, C, E.

B, D, E, C, A.

More formally, we can write this pseudocode to reflect the definitions of when pre-, in-, and post-order processing occurs:

1 2 3 4 5 6 7 8 | binaryTreeTraversal(node): preorder(node) if left != null: binaryTreeTraversal(left) inorder(node) if right != null: binaryTreeTraversal(right) postorder(node) |

- Taking the tree from above and this pseudocode, can you come up with the same list of letters for each of the traversals that we had when we did it visually?
- Looking at this pseudocode, why does the red peg/yellow line visual trick work?
- Why does in-order only make sense in the context of binary trees and not with trees that allow nodes to have more than 2 children?

Lab 13. DFS and BFS.

July 13, 2017.
The yellow path we traced in mini-lecture 12 for pre/in/post-order is known as depth-first search traversal (

On the other hand, breadth-first search traversal (

Before we continue, recall that a

The pseudocode below describes the algorithm for DFS traversal. Note that just like how when we traverse an array we need an index/counter variable or when we traverse a LinkedList we need a node pointer, for tree traversal, we can use certain data structures to help us keep track of where we are. This is called a

1 2 3 4 5 6 7 | Use STACK as fringe. Add root to fringe. while fringe not empty: Remove next from fringe. Add its children to fringe. Process removed node. |

The procedure for performing BFS traversal is almost identical! The only difference is that we instead use a queue has our fringe:

1 2 3 4 5 6 7 | Use QUEUE as fringe. Add root to fringe. while fringe not empty: Remove next from fringe. Add its children to fringe. Process removed node. |

- Try using the pseudocode to perform DFS and BFS traversals on the given tree above.
- Did you get the same answers as provided conceptually? If not, would adding the children to the fringe in a different order yield the desired result?
- Specifically, in what order should we add children to the fringe in order to DFS traverse starting with the left-most path first?
- Similarly, in what order should we add children to the fringe in order to BFS traverse each layer from left to right?
- Challenge question: DFS is naturally pre-order. How would you modify this algorithm to get a post-order traversal?

Lab 14. BST Challenge Excersises.

July 17, 2017.
These are the solutions to the optional excersises from Lab 14 that we live-coded together in class.

*Constructor from Pre-Order and In-Order Lists*

Create a constructor that instantiates the specified tree structure as given by lists of the pre-order and in-order traversals. (Lab 14, Part C, Ex. 5).

Let's take a look at a sample input to gain intuition for how this task is possible.

Pre-order: C A B E D.

In-order: A B C D E.

From the perspective of the root C, how do the locations of the nodes in the tree correspond to the positions of the letters in these two lists? How can you tell which correspond to the left and right side of the root?

Can you extend that to see how the*subList()* indices below match up in the example above?
(Note that the first argument of *sublist()* is inclusive while the second is exclusive.)

*Deletion from a BST*

In Part D, the procedure for deleting a BST is described and the implementation is provided to you. Perform the following deletions to check your understanding of what should happen conceptually. What will each of these trees look like after the indicated node is deleted?

Example 1:

Example 2:

Example 3:

Answer 1: Not possible since 2 is not in the tree to begin with.

Answer 2: The node with 2 is located and removed. Since it only had one child, it can simply move up to take the removed node's place.

Answer 3: We must find the in-order successor, which is 5. 5 takes the place of 3 in the tree, and 6 moves up to take 5's place.

Now here is the implementation that was provided to you in the skeleton, but with annotations added. Can you see how all of the cases above are handled within the code below?

*Getting the kth Largest Element*

For a typical Binary Search Tree implementation, to obtain the kth largest element, we must traverse in-order k times until we receive the desired element. This would have linear runtime.

But, we can take advantage of the tree structure and avoid this if we record for each node, the number of nodes in that subtree if that node were the "root", as described in Part E. Assuming we have implemented this invariant of maintaing the size at each node, we can then write a method to complete our task in time proportional to the depth of our tree. (Note the use of a helper method. Why is it neccessary for us to have a way to pass an extra argument from recursive call to recursive call?)

Both of the following reside in*BinaryTree.java* (inside the BinaryTree class but outside the nested node class).

Create a constructor that instantiates the specified tree structure as given by lists of the pre-order and in-order traversals. (Lab 14, Part C, Ex. 5).

Let's take a look at a sample input to gain intuition for how this task is possible.

Pre-order: C A B E D.

In-order: A B C D E.

From the perspective of the root C, how do the locations of the nodes in the tree correspond to the positions of the letters in these two lists? How can you tell which correspond to the left and right side of the root?

Can you extend that to see how the

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | public BinaryTree(ArrayList<T> pre, ArrayList<T> in) { root = listHelper(pre, in); } private TreeNode listHelper(ArrayList<T> pre, ArrayList<T> in) { if (pre.isEmpty()) return null; TreeNode subtreeRoot = new TreeNode(pre.get(0)); int rootIndex = in.indexOf(pre.get(0)); subtreeRoot.left = listHelper( new ArrayList<>(pre.subList(1, rootIndex + 1)), new ArrayList<>(in.subList(0, rootIndex)) ); subtreeRoot.right = listHelper( new ArrayList<>(pre.subList(rootIndex + 1, pre.size())), new ArrayList<>(in.subList(rootIndex + 1, in.size())) ); return subtreeRoot; } |

In Part D, the procedure for deleting a BST is described and the implementation is provided to you. Perform the following deletions to check your understanding of what should happen conceptually. What will each of these trees look like after the indicated node is deleted?

Example 1:

Example 2:

Example 3:

Answer 1: Not possible since 2 is not in the tree to begin with.

Answer 2: The node with 2 is located and removed. Since it only had one child, it can simply move up to take the removed node's place.

Answer 3: We must find the in-order successor, which is 5. 5 takes the place of 3 in the tree, and 6 moves up to take 5's place.

Now here is the implementation that was provided to you in the skeleton, but with annotations added. Can you see how all of the cases above are handled within the code below?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | public T delete(T key) { TreeNode parent = null; TreeNode curr = root; TreeNode delNode = null; TreeNode replacement = null; boolean rightSide = false; // Find node to be removed. while (curr != null && !curr.item.equals(key)) { if (((Comparable<T>) curr.item).compareTo(key) > 0) { parent = curr; curr = curr.left; rightSide = false; } else { parent = curr; curr = curr.right; rightSide = true; } } delNode = curr; // Target was not found. if (curr == null) { return null; } // Only has a left child. Remove target and let this take its place. if (delNode.right == null) { if (root == delNode) { root = root.left; } else { if (rightSide) { parent.right = delNode.left; } else { parent.left = delNode.left; } } // Either has two children or just a right child. } else { curr = delNode.right; replacement = curr.left; // There was only a right child. Remove target and let this take its place. if (replacement == null) { replacement = curr; // There were two children. } else { // Find inorder successor replacement. // Leftmost node of target's right child. while (replacement.left != null) { // curr is the parent of replacement. curr = replacement; replacement = replacement.left; } // replacement does not have a left child. // remove replacement by letting its right child take its place. curr.left = replacement.right; // replacement takes delNode's place. replacement.right = delNode.right; } // replacement takes delNode's place. replacement.left = delNode.left; if (root == delNode) { root = replacement; } else { if (rightSide) { parent.right = replacement; } else { parent.left = replacement; } } } // return value of delNode. return delNode.item; } |

For a typical Binary Search Tree implementation, to obtain the kth largest element, we must traverse in-order k times until we receive the desired element. This would have linear runtime.

But, we can take advantage of the tree structure and avoid this if we record for each node, the number of nodes in that subtree if that node were the "root", as described in Part E. Assuming we have implemented this invariant of maintaing the size at each node, we can then write a method to complete our task in time proportional to the depth of our tree. (Note the use of a helper method. Why is it neccessary for us to have a way to pass an extra argument from recursive call to recursive call?)

Both of the following reside in

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | public T getKthValue(int k) { return getKthValueHelper(k, root); } private T getKthValueHelper(int k, TreeNode node) { if (node == null) return null; if (k >= node.size || k < 0) throw new IndexOutOfBoundsException(); int numOnLeft; if (node.left != null) numOnLeft = node.left.size; else numOnLeft = 0; if (k < numOnLeft) { return getKthValueHelper(k, node.left); } else if (k == numOnLeft) { return node.item; } else { return getKthValueHelper(k - 1 - numOnLeft, node.right); } } |

Lab M2. Midterm 2 Review.

July 25, 2017.
Topics represented here are based upon your responses of which topics were most challenging;
inclusion or exclusion of topics here does not imply inclusion or exclusion of topics on any upcoming exams.

Practice problems:

Practice problems:

- Trees.
- Iterators.
- Streams
- Functional Interfaces.
- Runtime.

Lab 19. Graph Traversals.

July 28, 2017.
We can traverse a graph in DFS-fashion by following this pseudocode:

1 2 3 4 5 6 7 8 9 10 11 | Use STACK as fringe. Maintain SET of visited vertices. Add start vertex to fringe. while fringe not empty: Remove next from fringe. if not visited: Process removed node. for each neighbor: Add to fringe. Mark removed node as visited. |

Just as before with trees, it is important to note that the order in which we add our neighbors to the fringe may alter our final result. Further, some variations of this pseudocode may check whether a node has been visited at a different point of the algorithm, and this may also lead to differing results.

For the graph below, start at node 0 and execute the DFS-traversal algorithm. What is the list of nodes processed?

- Are all vertices reachable if we start a node 0?
- What if we were looking for the BFS-traversal instead?
- How about pre-order and post-order DFS? Can we easily get these from this iterative pseudocode?
*No, we should translate this to a recursive solution so that we can proccess vertices either before or after the recursive call.*

Here's a special little graph!

This graph is directed and acyclic (it contains no cyclic loops). You can see that if we started from vertex A, we would eventually end up at vertex G one way or another. To topologically traverse this graph, we say that before a node can be visited, all nodes before it must have been visited already. For example, if above, vertex A represented me waking up, vertex E was me brushing my teeth, C was me making a waffle, and D was me eating my waffle, then I can only brush my teeth and make my waffle after I wake up, and I can't eat my waffle until I've brushed my teeth and made my waffle (in either order).

Here is pseudocode for Topological Sort:

1 2 3 4 5 6 7 8 9 10 | Maintain a FRINGE. Maintain ARRAY of current in-degrees of all vertices. Add in-degree 0 vertices to fringe. while fringe not empty: Remove next from fringe. Process removed node. for each neighbor: Decrement its current in-degree. Add to fringe all new in-degree 0 vertices. |

List all possible topological orderings of the directed, acyclic graph above.

Lab 20. Dijkstra.

July 31, 2017.
Dijkstra's algorithm is used to find the shortest path from one vertex to another in a graph that has edge weights.
Here is the pseudocode:

Now run Dijkstra's algorithm on the graph shown below until you have found the shortest path to each vertex from vertex A. Break ties alphabetically.

*(Source: CSM 61B Sp17, WS 12, Q3.)*

For review and extra practice, find the DFS and BFS traversals of the graph above as well.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 | Use PRIORITY QUEUE as fringe. Maintain SET of visited vertices. Remember shortest paths to each vertex found so far. Add start vertex to fringe. while fringe not empty: Remove next from fringe. Mark as visited. The shortest path to the removed vertex has now been finalized. for each neighbor: if not visited && (shortest path to removed vertex + distance from removed vertex to neighbor) < current shortest path to neighbor: Either add to fringe or if already in fringe, update current shortest path to neighbor. |

Now run Dijkstra's algorithm on the graph shown below until you have found the shortest path to each vertex from vertex A. Break ties alphabetically.

For review and extra practice, find the DFS and BFS traversals of the graph above as well.

Lab 21. Comparison-Based Sorting.

August 01, 2017.
Take a look at Insertion, Selection, Merge, and Quick sorts
through __this visualizer__!

Now, here is an unsorted list:

5 3 1 6 2 4 8 7

For each of these independent lines below, identify the sort mentioned above that is characteristic of the intermediate step shown.

Now, consider each sort we mentioned:

Now, here is an unsorted list:

5 3 1 6 2 4 8 7

For each of these independent lines below, identify the sort mentioned above that is characteristic of the intermediate step shown.

- 3 1 2 4 5 6 8 7
- 1 2 3 5 6 4 8 7
- 1 3 5 6 2 4 8 7
- 3 5 1 6 2 4 7 8

Now, consider each sort we mentioned:

- What scenario gives the best case runtime and what is that runtime?
- What scenario gives the worst case runtime and what is that runtime?
- Is this sort stable?

Lab 22. Count-Based Sorting.

August 03, 2017.
Radix sorts look at one digit at a time.
I like to think about it as a __giant spreadsheet of data__,
in which each row represents an item,
and the digits of each item are each in their own individual columns.

Then, running*LSD* (least significant digit) radix sort would be analogous to sorting
the items in your spreadsheet first by the right-most (least significant) column,
then the next one over, and so on and so forth until the first column is used to sort upon.
Download the file above and do this if you're not convinced about why this works.
Do note that *stability* is a must-have in order for radix sort to work--
that is, elements that have the same value for the digit currently being looked at are guaranteed to remain
in the same order relative to each other once sorting for the digit has been finished.

But if you try doing*MSD* (most significant digit) radix sort in a similar fashion
(sorting with the first, left-most column, then the second, etc.),
you'll find that this wouldn't work.
This is why after each digit, we must recursively sort each of these group of items with the same first digit.

For both radix sorts, we had to sort by the value in a particular digit place. We can use*Counting Sort* to accomplish this.
Using an array of 10 counters (one of each possible digit value), we tally up the number of items that belong
to each of the digit value counters.
We then convert those counters to an array representing the starting indices of each group of items with this same digit
(this can be done with some simple addition arithmetic).
Then we go through the original list again and place them into a result array
according to the designated starting indices of each group.

Therefore, the runtime for counting sort is tightly bounded by the (number of items to sort) + (number of possible digit values), since we traverse both of these lists, one after the other. For LSD radix sort, we multiply the (runtime of counting sort) * (length of each item), since we must sort by digit for each digit place. For MSD radix sort, the worse case is the same as the runtime for LSD, but in the best case, we might not have a need to recurse if each digit place only ends up with a single item, and so then we have the (runtime of counting sort) one time only as the runtime.

Then, running

But if you try doing

For both radix sorts, we had to sort by the value in a particular digit place. We can use

Therefore, the runtime for counting sort is tightly bounded by the (number of items to sort) + (number of possible digit values), since we traverse both of these lists, one after the other. For LSD radix sort, we multiply the (runtime of counting sort) * (length of each item), since we must sort by digit for each digit place. For MSD radix sort, the worse case is the same as the runtime for LSD, but in the best case, we might not have a need to recurse if each digit place only ends up with a single item, and so then we have the (runtime of counting sort) one time only as the runtime.

Lab 23. Disjoint Sets, Kruskal.

August 07, 2017.
Now complete: 61BL Su16, Final, Q1c-e.

Lab 24. Regex.

August 08, 2017.
Alison's Regex Chart.

- For Regex quantifiers (such as ? + * )
- Regex is naturally
*greedy*-- it will try to match as much as possible and give up characters until a full match is found. - Add another ? after the quantifier to make it
*lazy*-- starts by matching as little as possible and reluctantly to consume characters until a full match is found.

1 2 3 4 5 | <body> <h1>Oolong</h1> <a href=”www.earl-gray.io”>50% sugar, less ice</a> <center><b>Pumpkin Spice Latté</b></center> </body> |

Lab 00. Title.

July 06, 2017.