Yushan Li
0 followers · 803 views
on the atlas — 18
- Lab 21: Counting-Based Sorts | CS 61BL Summer 20241 savers
- Lab 20: Comparison-Based Sorts | CS 61BL Summer 20241 savers
- Unit Economics vs Growth | LinkedIn1 savers
- Lab 19: Minimum Spanning Trees | CS 61BL Summer 20241 savers
- Project 3: CS61BYoW | CS 61BL Summer 20241 savers
- Lab 14: Heaps and Priority Queues | CS 61BL Summer 20241 savers
- Lab 13: Hash Tables | CS 61BL Summer 20241 savers
- Let’s Ditch the Singularity and Focus on Multiplicity | by Ken Goldberg | Medium2 savers
- A Century of Art and Technology in the Bay Area | by Ken Goldberg | Silicon Valley Robotics | Medium1 savers
- Lab 12: Balanced Search Trees | CS 61BL Summer 20241 savers
- Project 2: Gitlet | CS 61BL Summer 20241 savers
- Lab 10: Trees and Traversals | CS 61BL Summer 20241 savers
- Lab 8: Persistence and Gitlet | CS 61BL Summer 20241 savers
- Lab 6: ADTs and Inheritance | CS 61BL Summer 20241 savers
- Lab 5: Linked List Enhancements | CS 61BL Summer 20241 savers
- Project 0: 2048 | CS 61BL Summer 20241 savers
- Lab 03: Debugging & Test-Driven Development | CS 61BL Summer 20241 savers
- Lab 2: Intro to Objects and Primitives | CS 61BL Summer 20241 savers
highlights — 40
The root of the tree will be in position 1 of the array (nothing is at position 0). The left child of a node at position 𝑁 is at position 2 𝑁 . The right child of a node at position 𝑁 is at position 2 𝑁 + 1 . The parent of a node at position 𝑁 is at position 𝑁 / 2 .
Lab 14: Heaps and Priority Queues | CS 61BL Summer 2024First sort everything on the least important key. Then sort everything on the next key. Continue, until you reach the highest key. Note: This strategy requires the sorts to be stable. First sort everything on the high key. Group all the items with the same high key into buckets. Recursively radix sort each bucket on the next highest key. Concatenate your buckets back together.
Lab 21: Counting-Based Sorts | CS 61BL Summer 2024The radix of a number system is the number of values a single digit can take on (also called the base of a number). Binary numbers form a radix-2 system; decimal notation is radix-10. Radix sorts examine elements in passes, and a radix sort might have one pass for the rightmost digit, one for the next-to-rightmost digit, and so on.
Lab 21: Counting-Based Sorts | CS 61BL Summer 2024radix sort, another linear-time non-comparison sort that can be practical.
Lab 21: Counting-Based Sorts | CS 61BL Summer 2024A comparison-based sort is one in which all decisions are based on comparing keys (generally done by “if” statements). All actions taken by the sorting algorithm are based on the results of a sequence of true/false questions. All of the sorting algorithms we have studied so far are comparison-based.
Lab 21: Counting-Based Sorts | CS 61BL Summer 2024EVERY comparison-based sorting algorithm takes Ω ( 𝑁 log 𝑁 ) worst-case time.
Lab 21: Counting-Based Sorts | CS 61BL Summer 2024The idea behind divide and conquer can be broken down into the following 3-step procedure. Split the elements to be sorted into two collections. Sort each collection recursively. Combine the sorted collections. Compared to selection sort, which involves comparing every element with every other element, divide and conquer can reduce the number of unnecessary comparisons between elements by sorting or enforcing order on sub-ranges of the full collection. The runtime advantage of divide and conquer comes largely from the fact that merging already-sorted sequences is very fast.
Lab 20: Comparison-Based Sorts | CS 61BL Summer 2024Another way to think about it is if we can do the entire algorithm within the original given list, without creating an additional data structure. All the algorithms we discuss today are in-place and do not need to create another data structure.
Lab 20: Comparison-Based Sorts | CS 61BL Summer 2024An in-place algorithm is one that doesn’t use a significant amount of additional memory.
Lab 20: Comparison-Based Sorts | CS 61BL Summer 2024comparison-based sorts including insertion sort, selection sort, heap sort, merge sort and quick sort.
Lab 20: Comparison-Based Sorts | CS 61BL Summer 2024Comparison-based sorts, which rely on making pairwise comparisons between elements. Counting-based sorts, which group elements based on their individual digits before sorting and combining each group. Counting sorts do not need to compare individual elements to each other.
Lab 20: Comparison-Based Sorts | CS 61BL Summer 2024The growth at all costs mentality was predominantly fueled by the Zero interest-rate policy (ZIRP) business cycle, which prevailed during a period of historically low interest rates. This environment incentivized outsized risk-taking as investors, hungry for higher yields beyond treasuries, eagerly pursued investment opportunities.
Unit Economics vs Growth | LinkedInrevisit the data structure that specializes in determining if connections exist, the disjoint sets data structure
Lab 19: Minimum Spanning Trees | CS 61BL Summer 2024A minimum spanning tree (MST for short) 𝑇 of a weighted undirected graph 𝐺 is a spanning tree where the total weight (the sum of all of the weights of the edges) is minimal. That is, no other spanning tree of 𝐺 has a strictly smaller total weight. The MST for a graph is not necessarily unique.
Lab 19: Minimum Spanning Trees | CS 61BL Summer 2024There are two common methods of dealing with collisions in hash tables, which are listed below: Linear Probing: Store the colliding keys elsewhere in the array, potentially in the next open array space. This method can be seen with distributed hash tables, which you will see in later computer science courses that you may take. External Chaining: A simpler solution is to store all the keys with the same hash value together in a collection of their own, such as a linked list. This collection of entries sharing a single index is called a bucket.
Lab 13: Hash Tables | CS 61BL Summer 2024Today we routinely trust machines like auto-pilots and pacemakers to make important decisions that require precision and speed. Multiple modules and voting are often used to reduce errors. The cutting edge of research now is on machines that can learn.
Let’s Ditch the Singularity and Focus on Multiplicity | by Ken Goldberg | MediumTimothy Leary allegedly observed: “California is the end of the genetic runway.” The Northern California / Bay Area Art and Technology counterculture paves that runway with a true love of science and engineering, a deep resistance to authority, and an undaunted belief in Power to the People. The Bay Area is quick to forgive and embrace projects that don’t go the way they were intended. This ecosystem continues to explore and experiment with new ways to express ideas that could not be expressed before.
A Century of Art and Technology in the Bay Area | by Ken Goldberg | Silicon Valley Robotics | MediumThe root node must be colored black. Our interpretation of red nodes is that they are in the same 2-3 node as their parent. The root node has no parent, so it cannot be red. If a node has one red child, it must be on the left. This makes the tree left-leaning. No node can have two red children. If a node has two red children, then both children are in the same 2-3 node as the parent. This means that the corresponding 2-3 node contains 3 elements, which is not allowed. No red node can have a red parent; or every red node’s parent is black. If a red node has a red parent, then both the red child…
Lab 12: Balanced Search Trees | CS 61BL Summer 2024“serialization” refers to the conversion from some arbitrary structure (array, tree, graph, etc.) to a serial sequence of bytes.
Project 2: Gitlet | CS 61BL Summer 2024It also gives you a convenient way to compare two files (blobs) to see if they have the same contents: if their SHA-1s are the same, we simply assume the files are the same.
Project 2: Gitlet | CS 61BL Summer 2024blobs: The saved contents of files. Since Gitlet saves many versions of files, a single file might correspond to multiple blobs: each being tracked in a different commit. trees: Directory structures mapping names to references to blobs and other trees (subdirectories). commits: Combinations of log messages, other metadata (commit date, author, etc.), a reference to a tree, and references to parent commits.
Project 2: Gitlet | CS 61BL Summer 2024Saving the contents of entire directories of files. In Gitlet, this is called committing, and the saved contents themselves are called commits. Restoring a version of one or more files. In Gitlet, this is called restoring those files. Viewing the history of your backups. In Gitlet, you view this history in something called the log. Maintaining related sequences of commits, called branches. Merging changes made in one branch into another.
Project 2: Gitlet | CS 61BL Summer 2024TreeNode node = fringe.pop(); if (node.right != null) { fringe.push(node.right); }
Lab 10: Trees and Traversals | CS 61BL Summer 2024it picks the most recent entry to our stack and "explores" it. Exploring it requires visiting the node and adding its children to the fringe, since we must eventually visit them too. */
Lab 10: Trees and Traversals | CS 61BL Summer 2024A queue is a waiting line. As with stacks, access to a queue’s elements is restricted. Queue operations include: Adding an item to the back of the queue. Accessing the item at the front of the queue. Removing the front item. Checking if the queue is empty.
Lab 10: Trees and Traversals | CS 61BL Summer 2024A stack models a stack of papers, or plates in a restaurant, or boxes in a garage or closet. A new item is placed on the top of the stack, and only the top item on the stack can be accessed at any particular time. Stack operations include the following: Pushing an item onto the stack. Accessing the top item of the stack. Popping the top item off the stack. Checking if the stack is empty.
Lab 10: Trees and Traversals | CS 61BL Summer 2024Useful Utils Functions For this lab and Gitlet, we provide you with a Utils class that has many useful helper functions for file operations. Some of the methods that you may find useful are: writeContents - writes out strings/byte arrays to a file readContentsAsString - reads in a file as a string readContents - reads in a file as a byte array writeObject - writes a serializable object to a file readObject - reads in a serializable object from a file. You can get a Class object by using .class, e.g. Dog.class. join - joins together strings or files into a path. e.g. Utils.join(".capers", "dogs…
Lab 8: Persistence and Gitlet | CS 61BL Summer 2024Note: Naming a folder or file with a period in the front makes it hidden - to be able to see it in the terminal, run ls -a instead of just ls. If you want to remove all saved data from your program, just remove the .capers directory (NOT the capers directory) with rm -rf .capers. Be very careful with the rm -rf command – it will delete anything you tell it to as quickly as it can!
Lab 8: Persistence and Gitlet | CS 61BL Summer 2024A map is a collection of key-to-value mappings, like a dictionary from Python. A map is not necessarily ordered. Maps must support at least the following operations:
Lab 6: ADTs and Inheritance | CS 61BL Summer 2024You might be wondering now why Java has both interfaces and abstract classes, when they seem to serve rather similar purposes and have similar functionality. Interfaces are particularly useful to represent blueprints for classes that may or may not be obviously related; for example, we might have a Fluffy interface that can be implemented by both a Poodle and a CottonBall, which really don’t have much else in common. This stands in contrast to abstract classes, which use the extends keyword and therefore strictly adheres to a superclass-subclass inheritance. Because of this, abstract classes a…
Lab 6: ADTs and Inheritance | CS 61BL Summer 2024Implementing classes must implement all method signatures from the interface We can’t partially implement an interface, because the implementation then does not meet all the requirements we have said it does. The one exception to this is if the method has the default keyword, then the method is already filled in the interface. @Override This method annotation is not required when implementing a method from an interface, but enforces that the method does override an interface method. This helps prevent typos, like accidentally defining void ad(int i, int k), or void add(int i), when we wanted t…
Lab 6: ADTs and Inheritance | CS 61BL Summer 2024inheritance in Java, which comes in three main forms: interface implementation, abstract class extension, and concrete class extension.
Lab 6: ADTs and Inheritance | CS 61BL Summer 2024/** * sentinel is a dummy node that points to the first real node. That is, * sentinel.item is a dummy value, while sentinel.next.item is our true * first item. */ private IntListNode sentinel; private int size; /* ... more methods to operate on ... */ }
Lab 5: Linked List Enhancements | CS 61BL Summer 2024Although encapsulation shields users of our data structure from having to deal with cumbersome null checks, we as the implementors of our linked list class still have to handle them. However, we can eliminate null checks and simplify our code greatly with usage of a sentinel node instead of the head pointer. The sentinel node always exists (even when our list is empty), and does not represent an actual node in the list. Its next field represents the front of the list, unless the list is empty. The sentinel’s item is some meaningless value (in this example, we have chosen 42, but it doesn’t mat…
Lab 5: Linked List Enhancements | CS 61BL Summer 2024In future assignments, it’ll be your job to figure out how to break problems into smaller pieces. For this project, here’s an outline of how we’ve decided to tackle the tilt problem: Score updating: This will be easier once we have the logic for moving all the tiles, so let’s save this for later (Task 10). Four directions: Instead of worrying about tilting in all four directions at once, let’s start with just the up direction. Later, in Task 9, we’ll show you a clever trick to generalize your code and deal with the other three directions with just two extra lines of code. Key observation: When…
Project 0: 2048 | CS 61BL Summer 2024For loops with a fixed amount of iteration, we use two iterations. We choose to go through the loop twice rather than once because failing to reinitialize after the first time through a loop is a common programming error. We also make certain to include among our tests all possible ways to terminate the loop. For loops with a variable amount of iteration, we include zero, one, and two iterations, and in addition, we include test cases for all possible ways to terminate the loop. The zero iteration case is another situation that is likely to be a source of program error.
Lab 03: Debugging & Test-Driven Development | CS 61BL Summer 2024We often write tests using the Arrange-Act-Assert pattern: Arrange the test case, such as instantiating the data structure or filling it with elements. Act by performing the behavior you want to test. Assert the result of the action in (2).
Lab 03: Debugging & Test-Driven Development | CS 61BL Summer 2024The toString method is used by Java to determine how to represent an object as a string, like when printing objects to display to the user. In the example below, we create a new point at the origin, ( 0 , 0 ) . When calling System.out.println, Java needs to figure out what exactly to print, so it invokes the toString method which returns (0.0, 0.0). Then, that string is displayed to the screen.
Lab 2: Intro to Objects and Primitives | CS 61BL Summer 2024These defaults will correspond to a zero value. 0 for int, float, double, etc. false for boolean, and null for Object types
Lab 2: Intro to Objects and Primitives | CS 61BL Summer 2024The constructor is a special method that creates and returns a new instance of your class. This method is where we will initialize all the variables associated with the class’s instance. Unlike other methods, there is no return type in the constructor’s signature, and it must have the same name as the class itself. Although we do not specify a return type in the method name and there is no return statement, the constructor creates an instance of the class and returns it. This is a unique property of constructor methods.
Lab 2: Intro to Objects and Primitives | CS 61BL Summer 2024