Journals

Journal 1: Information in Memory

The main point in this chapter is talking about how variables work in memory. Strings and arrays are both types of variables that are stored in memory. This chapter also discusses the complications that come with sorting and reorganizing arrays. Even something as simple as adding an element in the middle of an array would require you to edit each element’s index.

Journal 3: Dynamic Data Structures

The main example of Dynamic Data Structures are Linked Lists. Linked Lists work like arrays but each node has a pointer to the next node. This allows you to easily travel throughout the entire list. A benefit to this is there is a set order that can be altered by adjusting the pointer to the next node. Doing this allows you to add, delete, edit, or insert new nodes wherever needed.

Journal 4: Stacks and Queues

Stacks work by using an array and only adding or removing to the last entry in the array. This means that in order to access previous entries, you must remove the most recent one. These are good for keeping track of the current entry while storing old entries when needed. Queues work similarly, but you add to the top but remove from the bottom. These are useful for when there needs to be a set order for something in which things are constantly coming in and out.

Journal 5: Binary Search Trees

Binary Search Trees work by storing information in a tree form where each entry is either greater or less than the previous node on the tree. It starts with a base node, and if the new entry is less than, it goes on the left node, while greater than goes on the right node. This continues onto the next nodes and so on until there are no new nodes. This data structure works with sorted lists and has many more complex attributes that can be helpful.

Journal 6: Tries and Adapting Data Structures

Tries work similar to Binary Trees where they take a starting node and branch off, but tries typically use letters and can branch off in more than 2 nodes. Tries also mark each node to whether or not its a valid entry, since there are many intermediete nodes between larger entries. Tries are often used for keeping track of words, since each letter new letter in a word marks a new node. These can be used for tools like dictionaries where you might want to know which words follow from a specific prefix.

Journal 7: Priority Queues and Heaps

Priority Queues work similarly to regular queues, except each entry contains a priority number. This allows each new entry to be inserted into it’s correct location in the queue, while removing always happens from the start. This can be useful for things that require a specific deadline to complete. Heaps are also sorted, but take the form of a tree structure. The important detail of heaps is that each node is always less than the nodes above them, meaning the node at the top is always the largest. This allows for a different method of sorting and storing data.

Journal 8: Grids

Grids work like how a normal grid would work in graphing. By setting up the grid into x and y and giving each data point a set x and y value, you can “graph” each point on the map. By subdividing the graph into different square “bins,” you can easily check which point is closest to another point by finding the points in the closest bins, searching for all points in a circular radius around that point, and checking the distance between those points and the main point using Euclidean distance. This type of data structure can be useful for mapping or charting any type of data that has more than 1 axis of continuous data.

Journal 9: Spatial Trees

Spatial Trees act like a combination between grid and trees. A Spatial Tree marks points based on x and y location similarly to grids, but instead of sorting points by bins, it creates a fractal-like pattern where the grid is subdivided up until there is only one data point within a bin. This is set up like a tree, where at each division, a point is sorted into up-left, up-right, down-left or down-right. Spatial trees help with finding closest neighbors as the bins get more precise the further down you get on the tree.

Journal 10: Hash Tables

Hash Tables work by using an array as a base and accessing specific entries of the array by using keys. These keys are deterministic, meaning that every time you enter that key into the hash function, you’ll always get the same output. This data structure is useful since it allows direct mapping from a key into specific bins of smaller size, which can save on memory when the data space is particularly large.

Journal 11: Caches

Caches work by saving the input and output of a Hash Table-type data structure into a queue, allowing the most recently used data to be stored for easy access. This is common when accessing data is quite expensive. Caches allows that data to be stored, saving time and computer power since frequently accessed information is more likely to be accessed again. Caches work by having a set queue size, which is filled up with information. Once the Queue reaches its limit, the item that was added first is removed, leaving only the X most frequently accessed items.

Journal 12: B-trees

B-trees work similarly to binary trees where numerical data is stored in tree form. However, B-trees dont have 2 branches at every point. They work by sorting each branch into x+1 branches, where x is the amount of nodes underneath that parent. For example, if the numbers were 10, 20, 30, and 40, the bins would be sorted into <10, 10-20, 20-30, 30-40, and >40. While this data structure is a bit more complex when it comes to rebalancing, its benefit comes from its efficiency when it comes to branching. Since there are less branches, the B-tree allows for faster retrieval of data.

Journal 13: Bloom Filters

[Text]

Journal 14: Skip Lists

[Text]

Journal 15: Graphs

[Text]