CS 61B, Data Structures
Matt's Notes
Welcome! Here are some notes from our sections together!
Click on any link below to view.
Dis 00. Template.
January 00, 2018.
Dis 06. Asymptotics.
October 2+3, 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: Remember that your usage of Big-O, Big-Omega, or Big-Theta depends on the exact question being asked.

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).
Dis 04+05. Inheritance.
September 18+19+25+26, 2018.
Click here to view slides from this discussion.
Dis 03. Static and Arrays.
September 11+12, 2018.
Static Methods and Variables
Fields can be labeled as static (class variables), and methods can also be labeled as static.

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.

Problem Solving Strategies
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.

Arrays vs LinkedLists
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.
Lab 03. Doubly Linked Lists.
September 6+7, 2018.
Our Story of LinkedLists
We started out with the raw IntList. This was a nice a simple data structure that we could use to store individual integers in a series of connected links.

Next came the Singly Linked List, which allowed us to encapsulate our raw IntList. The advantage of encapsulation is that it allows us to provide for our users methods for performing operations on our data structure so that they do not need to be knowledgeable about the underlying intricacies of our implementation in our to use it; they can simply refer to an API or list of our methods and their descriptions and they can use our data structure like a black box.

Following that, we introduced Sentinels into our Singly Linked List. This was a "dummy" node that had an unimportant item that was always included. The purpose of a sentinel is to remove the need for null checks, since those can be messy in our code or it may be easy to miss a couple situations. Thus, instead of checking if an instance is null, we can check if it has returned back to the sentinel.

Finally, we allowed ourselves to have referenes in both directions, so that we could access both the previous and the next. This was the Doubly Linked List.
Dis 02. Destructive/Non-Destructive IntLists.
September 4+5, 2018.
Java Files for the Discussion Exercises
Use these files to test your solutions after you're satisfied with them on pencil and paper! IntLists
You'll often see statements such as L.tail.tail = L.tail.tail.tail;, but sometimes it seems like the way you follow the "tails" seem different for the left and right sides of the equals sign. Why is that?

Think about what the equals sign means. For example, let's look at an assignment statement such as this: String var = "object";. What this the box and pointer diagram look like?



We can see that var corresponds to a variable box in the diagram, and that the right hand side of the assignment statement was a String object.

In the same way, the left side of the statement L.tail.tail = L.tail.tail.tail; is a variable box in the diagram, and the right hand side is an IntList object. Therefore, when we count the number of "tails" for the left hand side, we stop counting in time so that we are left with the last "tail" variable box so that we can reassign it. When we count for the right hand side, we follow the final "tail" to an Object, and assign the left hand side to reference it.

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



Destructive vs. Non-Destructive
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 new keyword.

On the other hand, non-destructive functions want to preserve the original and return a new version. Thus, non-destructive functions should use the new keyword to create fresh objects as the necessary modifications are applied.
Lab 02. Git Demo.
August 30+31, 2018.
Today we did a git demo in standard git commands and merge conflict resolution.

Matthew@Matthew-PC MINGW64 ~/Desktop/temp
    $ ls
    repo/  repo2/

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp
    $ cd repo

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ touch chickenpotpie

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ ls
    chickenpotpie  hw0/  lab1/  lab2/

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ vim chickenpotpie

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ cat chickenpotpie
    celery
    carrots
    flour
    covfefe

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ git status
    On branch master
    Your branch is up-to-date with 'origin/master'.
    Untracked files:
      (use "git add <file>..." to include in what will be committed)

            chickenpotpie

    nothing added to commit but untracked files present (use "git add" to track)

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ git add chickenpotpie
    warning: LF will be replaced by CRLF in chickenpotpie.
    The file will have its original line endings in your working directory.

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ git status
    On branch master
    Your branch is up-to-date with 'origin/master'.
    Changes to be committed:
      (use "git reset HEAD <file>..." to unstage)

            new file:   chickenpotpie


    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ git commit -m "adding my recipe!"
    [master 1153f51] adding my recipe!
    warning: LF will be replaced by CRLF in chickenpotpie.
    The file will have its original line endings in your working directory.
     1 file changed, 4 insertions(+)
     create mode 100644 chickenpotpie

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ git status
    On branch master
    Your branch is ahead of 'origin/master' by 1 commit.
      (use "git push" to publish your local commits)
    nothing to commit, working directory clean

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ git push
    Counting objects: 3, done.
    Delta compression using up to 4 threads.
    Compressing objects: 100% (2/2), done.
    Writing objects: 100% (3/3), 399 bytes | 0 bytes/s, done.
    Total 3 (delta 0), reused 0 (delta 0)
    To cs61b-taa@derby.cs.berkeley.edu:students/cs61b-tap
       34d16ce..1153f51  master -> master

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ cd ..

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp
    $ cd repo2

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo2 (master)
    $ git pull
    remote: Counting objects: 4, done.
    remote: Compressing objects: 100% (2/2), done.
    remote: Total 3 (delta 0), reused 0 (delta 0)
    Unpacking objects: 100% (3/3), done.
    From derby.cs.berkeley.edu:students/cs61b-tap
       34d16ce..1153f51  master     -> origin/master
    Updating 34d16ce..1153f51
    Fast-forward
     chickenpotpie | 4 ++++
     1 file changed, 4 insertions(+)
     create mode 100644 chickenpotpie

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo2 (master)
    $ ls
    chickenpotpie  hw0/  lab1/  lab2/

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo2 (master)
    $ vim chickenpotpie

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo2 (master)
    $ cat chickenpotpie
    celery
    carrots
    flour
    chicken

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo2 (master)
    $ git commit -am "fix typo"
    [master 3e75d1e] fix typo
     1 file changed, 1 insertion(+), 1 deletion(-)

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo2 (master)
    $ git push
    Counting objects: 3, done.
    Delta compression using up to 4 threads.
    Compressing objects: 100% (2/2), done.
    Writing objects: 100% (3/3), 285 bytes | 0 bytes/s, done.
    Total 3 (delta 1), reused 0 (delta 0)
    To cs61b-taa@derby.cs.berkeley.edu:students/cs61b-tap
       1153f51..3e75d1e  master -> master

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo2 (master)
    $ cd ..

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp
    $ cd repo

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ vim chickenpotpie

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ git commit -am "add more ingredients"
    warning: LF will be replaced by CRLF in chickenpotpie.
    The file will have its original line endings in your working directory.
    [master warning: LF will be replaced by CRLF in chickenpotpie.
    The file will have its original line endings in your working directory.
    92a8e3f] add more ingredients
    warning: LF will be replaced by CRLF in chickenpotpie.
    The file will have its original line endings in your working directory.
     1 file changed, 2 insertions(+)

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ git push
    To cs61b-taa@derby.cs.berkeley.edu:students/cs61b-tap
     ! [rejected]        master -> master (fetch first)
    error: failed to push some refs to 'cs61b-taa@derby.cs.berkeley.edu:students/cs61b-tap'
    hint: Updates were rejected because the remote contains work that you do
    hint: not have locally. This is usually caused by another repository pushing
    hint: to the same ref. You may want to first integrate the remote changes
    hint: (e.g., 'git pull ...') before pushing again.
    hint: See the 'Note about fast-forwards' in 'git push --help' for details.

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ git pull
    remote: Counting objects: 5, done.
    remote: Compressing objects: 100% (2/2), done.
    remote: Total 3 (delta 1), reused 0 (delta 0)
    Unpacking objects: 100% (3/3), done.
    From derby.cs.berkeley.edu:students/cs61b-tap
       1153f51..3e75d1e  master     -> origin/master
    Auto-merging chickenpotpie
    CONFLICT (content): Merge conflict in chickenpotpie
    Automatic merge failed; fix conflicts and then commit the result.

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master|MERGING)
    $ cat chickenpotpie
    celery
    carrots
    flour
    <<<<<<< HEAD
    covfefe
    eggs
    love
    =======
    chicken
    >>>>>>> 3e75d1e0e0e85eb6a0b59b7f59e1801b655b1882

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master|MERGING)
    $ vim chickenpotpie

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master|MERGING)
    $ cat chickenpotpie
    celery
    carrots
    flour
    eggs
    love
    chicken

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master|MERGING)
    $ git commit -am "resolve merge conflict"
    [master 1716c63] resolve merge conflict

    Matthew@Matthew-PC MINGW64 ~/Desktop/temp/repo (master)
    $ git push
    Counting objects: 6, done.
    Delta compression using up to 4 threads.
    Compressing objects: 100% (4/4), done.
    Writing objects: 100% (6/6), 603 bytes | 0 bytes/s, done.
    Total 6 (delta 2), reused 0 (delta 0)
    To cs61b-taa@derby.cs.berkeley.edu:students/cs61b-tap
       3e75d1e..1716c63  master -> master
    
Dis 01. Introduction to Reading and Writing Java!
August 28+29, 2018.
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:
  1. Evaluate the loop condition. If it is false the loop is over and execution continues starting after the closing curly bracket of the loop.
  2. 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.
  3. At this point, we go back to step 1 and check the condition again.
It is important to note that even if the condition becomes false in the middle of executing the loop body, the loop does not magically quite immediately. The loop can only quit in between executions of its body (unless there is a 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:
  1. Initialize the counter variable.
  2. Evaluate the loop condition. If it is false the loop is over and execution continues starting after the closing curly bracket of the loop.
  3. 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.
  4. Adjust the counter value according to the specified fashion. Usually an incrementation or decrementation.
  5. At this point, we go back to step 2 and check the condition again.
The other option we have is 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.