Click on any link below to view.

Dis 00. Template.

January 00, 2018.
Dis 11. Graphs.

April 3, 2018.
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.

Dis 10. Tree Traversals.

March 20, 2018.
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.

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?

The yellow path we traced here 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?

Dis 07 and 08. Asymptotics.

February 27, 2018.
We talked about the formal definition of the asymptotic bounds and
we made it our goal to gain intuition for how they work so that we don't have to setup a limit explictily every single time.
The summer CS61BL website has a great and thorough explanation of this again for you: **CS 61BL Lab 07**

Further, we plotted some lines using an iPython notebook just so that we can see what some functions look like and why it would make sense to want the asymptotic definitions we have. You can see the notebook we were looking at here:**iPython notebook**

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).*DFS Traversal*

We can traverse a graph in DFS-fashion by following this pseudocode:

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?

*(Source: CSM 61BL Su17, WS 6, Q6.)*

*Topological Sort*

Here's a special little graph!

*(Source: 61BL Su17, Final, Q1b.)*

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:

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

Further, we plotted some lines using an iPython notebook just so that we can see what some functions look like and why it would make sense to want the asymptotic definitions we have. You can see the notebook we were looking at here:

Some strategies for asymptotic analysis:

- 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).

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.

Dis 03. LinkedLists and Arrays.

January 30, 2018.
We started out with the raw

Next came the

Following that, we introduced

Finally, we allowed ourselves to have referenes in both directions, so that we could access both the previous and the next. This was the

Whenever you are asked to write a signficant amount of code by hand, first make a concrete example for yourself so that you understand what the problem is asking you to do, so that you get a feel for the operations that may be involved, and so that you have something to check against once you actually start writing code in a bit.

Next, break down the problem into functional parts or steps that you know how to do. If you are stuck, write out the parts of the code that are most obvious to you, even if you have to leave conditions or other things blank. For example, if we have to do an operation repeatedly, you know that there would have to be a loop or a recursive call, so you can set up the components for that first while you're still thinking (loop conditions, incrementations, base cases, etc.). Try to get the general situation working first, and then worry about the edge cases once you're done. Often times, those can be addressed by adding a simple if case at the top of your code later.

Finally, we informally made observations about the arrays and linkedlists that we worked with today. We'll cover these in more detail later when we study runtime analysis. But for now, we saw that it was easier to get items out of an array, but that it was harder to "resize" them since they are of fixed length and so that would actually require us to make a new array and to copy everything over. LinkedLists on the other hand, require that we traverse the list in order to access a particular item, but it only requires us to switch around a few pointers to insert or delete items.

Dis 02. Static and IntLists.

January 23, 2018.
Typical class definitions contain three sections of code.

First we have

Next are the

Finally we have

Here is an example of these three components in action.

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; } } |

Fields can be labeled as

For static fields, there is only one variable that is shared among all instances of the class, and thus consequently, all object instances see the same value for that field (again, because there is a single variable shared among all; there is not one variable per instance). To call upon a static field, we use dot notation on the class name rather than on a particular instance.

For static methods, an object instance is not required for the function to be called. As a consequence, it cannot access non-static fields. If you'd like, you can call static methods on an object instance, but in that case Java will lookup the class of the instance and call it as we've just described.

You'll often see statements such as

Think about what the equals sign means. For example, let's look at an assignment statement such as this:

We can see that

In the same way, the left side of the statement

Walk through this simple example and make sure you understand how this statement works and why.

When writing a destructive function, you want to destroy the original and so you should not be creating new objects. Thus, destructive functions do not use the

On the other hand, non-destructive functions want to preserve the original and return a new version. Thus, non-destructive functions should use the

Dis 01. Introduction to Reading and Writing Java!

January 16, 2018.
Java programs begin execution starting from a main method *public static void main (String[] args) {...}*.

*Primitives vs. Non-Primitives*

We keep track of data using variables. Variables come in two flavors: primitives and non-primitives.**Primitives** in Java include only the following: byte, short, int, long, float, double, boolean, char.
All other kinds of variables are **non-primitives**.
Variables representing primitives store the appropriate raw value, while
variables representing non-primitives store **references** to the actual data.

The creators of Java made this design decision for the language due to efficiency justifications. Imagine that you're in at an interview for your dream job. The manager really loves you and is almost ready to hire you, but first, they'd like to ensure that everything you've said about yourself is true. And so, the manager would like to verify with your best friend that you have indeed been truthful. But now the question is, would it be appropriate for you to clone your best friend so that the manager can chat with them? Probably not...your friend might not appreciate that very much. It makes much more sense to provide the manager with a*reference* to your friend, a phone number perhaps.
This is why Java handles "complicated" (non-primitive) variables using references.

This goes hand-in-hand with what Professor Hug calls the**Golden Rule of Equals**.
When we are drawing **box and pointer diagrams**, when a variable's contents are asked of,
we provide whatever is inside that variable's corresponding box.
This means that for primitives we copy the raw value,
while for non-primitives we copy the arrow that we have drawn, such that
our copied arrow points to the same destination.
Given this distinction, if a function takes in both a primitive and a non-primitive
as arguments, and it mangles both during the function call, when the function is over,
which of the two (or both?) were actually changed?
See the example below to find out:

*Iteration and Recursion*

Often times, we want to write code that does something over and over again. We have two techniques for doing this: iteration and recursion.

**Iteration** involves using a loop.
In Java, one kind of loop is the *while* loop.
To evaluate it, we follow these steps in order:
*break* statement, an *Exception* is thrown, etc.).
Another kind of loop is the *for* loop.
This kind of loop was introduced because programmers noticed that loops in general typically
contained the initialization of some counter variable, the check of some condition against that counter variable,
and the modification of this counter variable as iterations occur.
For loops simply bundle these three elements together into a visually convenient place.
We evaluate for loops following these steps in order:
**recursion**.
This occurs anytime we have a function and that function's body of code contains a statement in which it calls upon itself again.
To prevent infinite recursion, we want our recursive functions to contain *base cases*,
which are if statements that provide direct results of the simplest situations,
and in all other cases our recursive calls should aim to move our complicated situation
closer and closer to one of our base cases.

With the classic Fibonacci exercise (#3 on the worksheet), we saw how there may be many ways to solve the same problem and to arrive at the correct answer. Therefore, simply solving a problem one way is cute and all, but in the real world, that doesn't mean you're done--we want to find the "best" solution. What does "best" mean? It means code that is not only correct, but also fast, memory efficient, and clear to other human readers. In other words, in this class we will learn to consider time efficiency, space efficiency, and style/documentation.

We keep track of data using variables. Variables come in two flavors: primitives and non-primitives.

The creators of Java made this design decision for the language due to efficiency justifications. Imagine that you're in at an interview for your dream job. The manager really loves you and is almost ready to hire you, but first, they'd like to ensure that everything you've said about yourself is true. And so, the manager would like to verify with your best friend that you have indeed been truthful. But now the question is, would it be appropriate for you to clone your best friend so that the manager can chat with them? Probably not...your friend might not appreciate that very much. It makes much more sense to provide the manager with a

This goes hand-in-hand with what Professor Hug calls the

Often times, we want to write code that does something over and over again. We have two techniques for doing this: iteration and recursion.

- Evaluate the loop condition.
If it is
*false*the loop is over and execution continues starting after the closing curly bracket of the loop. - If it is
*true*, then we start at the top of the loop's body of code and execute those lines in order until we reach its end. - At this point, we go back to step 1 and check the condition again.

- Initialize the counter variable.
- Evaluate the loop condition.
If it is
*false*the loop is over and execution continues starting after the closing curly bracket of the loop. - If it is
*true*, then we start at the top of the loop's body of code and execute those lines in order until we reach its end. - Adjust the counter value according to the specified fashion. Usually an incrementation or decrementation.
- At this point, we go back to step 2 and check the condition again.

With the classic Fibonacci exercise (#3 on the worksheet), we saw how there may be many ways to solve the same problem and to arrive at the correct answer. Therefore, simply solving a problem one way is cute and all, but in the real world, that doesn't mean you're done--we want to find the "best" solution. What does "best" mean? It means code that is not only correct, but also fast, memory efficient, and clear to other human readers. In other words, in this class we will learn to consider time efficiency, space efficiency, and style/documentation.