Algorithms & Data Structures Flashcards
Linear Search
Searches through a set of data (i.e. an array) one element at a time.
Time Complexity O(n).
Binary Search
Searches through an ordered data set (i.e. an array of numbers in ascending order) by finding a midpoint between the start and end of a data set, then removing half the set on each iteration. (I.e. if looking for a number and array[midpoint] is greater than that value, move the start to midpoint and find a new midpoint, effectively removing the first half of the array from the search).
Time Complexity: O(log n)
Bubble Sort
A sorting algorithm where the largest values “bubble up” to the top. (i.e. end of the array). Iterates through array and checks each two value pair to see which is greater, then swaps them if necessary. Can be optimized by tracking swaps and breaking loop if no swaps are made during an iteration.
Time Complexity: O(n^2), unless optimized and array is nearly sorted, in which case it’s O(n)
Selection Sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
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.
Merge Sort
A sorting algorithm that uses a divide & conquer strategy to recursively halve an array into 1 or 0 element long arrays, then merges each each half (series of halves) back into a sorted array
Time Complexity: O(n log n), Space Complexity: O(n)
Tree
In computer science, a tree is a widely used abstract data type that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes.
Binary Tree
A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.
Binary Search Tree
Binary Search Tree is a node-based binary tree data structure which has the following properties:
The left subtree of a node contains only nodes with keys lesser than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
The left and right subtree each must also be a binary search tree.
Stack
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Queue
A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.
Stack vs Queue
The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.
Breadth First Search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.
Depth First Search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
