Please enable JavaScript.
Coggle requires JavaScript to display documents.
Computer Science: Data Structures and Algorithms - Coggle Diagram
Computer Science: Data Structures and Algorithms
Big O
how efficient the algorithm is
a formal expression of an algorithm's complexity in relation to the growth of the input size.
time complexity = how long it takes something to run
The worst case scenario!!
Binary Search Tree ( BST )
is like a linked list, only is sorted
it has at most 2 children nodes per node
AVL Trees
Single rotation to left or right
is a subset of BTSs trees
Spatial Complexity
How much space needs an algorithm to complete
Bubble Sort
Bubble sort algorithm is an algorithm that sorts the array by comparing two adjacent elements and swaps them if they are not in the intended order. Here order can be anything like increasing order or decreasing order.
Insertion Sort
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Algorithm
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.
Recursion
Write a function that accepts an array that only contains two types of things: numbers and arrays. Those nested arrays contain also only numbers, or other, nested arrays.
Example:
nestedAdd([[[2]], 1, [1, 3]]) = 7
nestedAdd([1, 2, [3]]) = 6;
Solution:
function nestedAdd(array) {
let sum = 0;
for (let i = 0; i < array.length; i++) {
const current = array[i];
if (Array.isArray(current)) {sum += nestedAdd(current);
} else { sum += current; } }
return sum;
}
Merge Sort
Two functions: mergeSort and merge => it takes 2 sorted lists and makes 1 sorted list.
Big O = n log n
it breaks big arrays down into small arrays => concatenates the things that came back from its merge sort recursive calls and passes those into merge.
Quick Sort
Take the last element in the array and call it PIVOT
Everything that's smaller that the pivot gets put into a LEFT list
Everything that's grater than the pivot gets put into a RIGHT list
then you Quick Sort on the left and right lists independently
After those sorts come back, you CONCATENATE the sorted left list, the pivot and the right list.
Radix Sort
Example: [109, 224, 901, 58]
We sort all the numbers in the ones place from 0 to 9. => [ 901, 224, 58, 109 ]
then we sort on the tens place => [901, 109, 224, 58 ]
then we sorts by the hundreds => [ 58, 109, 224, 901]
A non-comparison sorting, we sort parts of the array
Binary Search
It works only if the array is already sorted!!!
ArrayList
is used to store dynamically sized collection of elements. Contrary to Arrays that are fixed in size, an ArrayList grows its size automatically when new elements are added to it.
Linked List
a collection of nodes where each node is connected to the next node through a pointer
Depth First Tree Traversals
when you need to put the numbers from tree in an array
As DFS suggests, we will first focus on the depth of the chosen Node and then go to the breadth at that level.
Breadth First Tree Traversals
Breadth-first search involves search through a tree one level at a time. We traverse through one entire level of children nodes first, before moving on to traverse through the grandchildren nodes.
Heap Sorting
We first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.
Heap sort works by transforming the list of items to be sorted into a heap data structure, a binary tree with heap properties.
Graphs
it's a tree that doesn't have a root
depth-first search (DFS) and breadth-first search (BFS) => the goal of these algorithms is to find all nodes reachable from a given node, or simply to explore all nodes in a graph.
A graph consists of a finite set of vertices or nodes and a set of edges connecting these vertices. Two vertices are said to be adjacent if they are connected to each other by the same edge.
Pathfinding
a pathfinding method searches a graph by starting at one vertex and exploring adjacent nodes until the destination node is reached, generally with the intent of finding the cheapest route.
Tries
a tree that was optimezed for search by prefix
Bloom Filters
a data structure designed to identify of a element's presence in a set in a rapid and memory efficient manner.
A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.