The Last Algorithm Course Flashcards
What is the simplest Data Structure?
An array
What is Big O?
It is a way to categorize an algorithms time or memory requirements based on input
Why do we use Big O?
It will help us make decisions about what data structures and Algorithms to use. Knowing how they perform can help us make the best possible program.
What is the running time of this algorithm?
function sum_char_codes (n: string): number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
sum += n. charCodeAt (i) ;
}
return sum;
}
O(N)
What are the 3 concepts for time and space complexity?
1.Growth with respect to input
2.Constants are always dropped
3.Worst case is usually the way we measure
What is the running time of this algorithm?
function sum_ char_ codes (n: string) : number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
sum += n. charCodeAt (i) ;
}
for (let i = 0; i < n.length; ++i) {
sum += n. charCodeAt (i) ;
}
return sum;
}
O(N)
What is the running time of this algorithm?
function sum_ char_ codes (n: string) : number {
let sum = 0;
for (let i = 0; i < n.length; ++i) {
const charCode = n. charCodeAt (i) ;
// Capital E
if (charCode === 69) {
return sum;
}
sum += charCode;
}
return sum;
}
O(N)
(O of N)
What is the running time of this algorithm?
function sum char codes (n: string): number {
let sum = 0;
for (let i = 0; i < n. length; ++i) {
for (let j = 0; j < n.length; ++j) {
sum += charCode;
}
}
return sum;
}
O(N^2)
What is the running time of this algorithm?
function sum char_codes (n: string): number {
let sum = 0;
for (let i = 0; i < n. length; ++i) {
for (let j = 0; j < n.length; ++j) {
for (let k = 0; k < n. length; ++k) {
sum += charCode;
}
}
}
return sum;
}
O(N^3)
An example of O(n log n)
Quicksort
An example of O(log n)
Binary search trees
This is an example of what?
export default function bs_list(haystack: number[], needle: number): boolean
{
6 }
let 10 = 0;
let hi = haystack. length;
do {
const m = Math. floor(lo + (hi - 10) / 2);
const v = haystack[m];
if (v === needle) {
return true;
7 else if (v > needle) §
hi = m;
† else {
10 = m + 1;
구
} while (lo < hi);
return false;
Binary Search
What is the running time of Bubble Sort?
O(n^2)
What sucks about an array?
Deletion ( you can’t delete but can zero out something)
Insertion (you can’t insert, but you can write)
It’s Ungrowable
What is the running time from deleting or inserting in a linked list?
O(1)
What kind of structure is a queue?
FIFO (First In First Out)
What is the opposite of a Queue?
A Stack
For a linked list, what’s the only way you’re able to search for an item?
Using linear search
TRUE or FALSE:
There is no such thing as a binary search on a linked list
True
Which one is better? An array list or linked list?
It depends on the situation. If you are popping or pushing from the end, then any can work well.
There’s a trade off
Getting sucks on linked list. Removing from the front sucks on array list because then you have to move all the other values to the left by one.
What is Recursion?
The simplest way to think of recursion is a function that calls itself until the problem is solved
What is a Base Case?
A base case is the point in which the problem is solved at.
When do you use recursion?
When you can’t use a for loop
What is bubble sort?
It is a sorting algorithm that works by comparing the two elements next to each other and swapping them if they are not in order.
It goes back and repeats until it’s all sorted.
What is QuickSort?
What is Divide and Conquer?
Is to be able to split your input into 2 chunks, 3 chunks, or whatever the splitting is and be able to go over those smaller subsets and solve things faster and be able re split it again and again
What is the running time of QuickSort?
O(nlogn)
What running time can QuickSort also be besides O(nlogn)?
O(n^2)
What is a doubly linked list?
In a tree, what is a root?
The most parent node. The first
In a tree, what is the height?
The longest path from the root to the most child node
What is the running time of a tree?
O(n)
(O of n)
Where is the root in a pre order?
In the beginning
Where is the root in an in order?
The beginning
Where is the root in a post order?
The end
What is the Depth First Search data structure?
Stack
What is a Breadth First Search data structure?
Queue
What is the running time of a Breadth-First Search?
O(n) but with JavaScript it’s an O(n^2)
What is the running time of the find() algorithm?
O(h) which is between O(logn) and O(n)
(O of height)
What is a Heap data structure?
It is a binary tree where every child and grandchild is smaller (MaxHeap) or larger (MinHeap) than the current node.
What is a Heap data structure also known as?
A priority queue
Is a Heap always a full/complete tree?
Yes. It is always adding from left to right and never has an empty space/gap
What is the running time of delete or insert in a Heap?
O(logn)
What is a trie tree? (pronounced tree but people call them try trees)
Used for storing and searching a specific key from a set.
TRUE OR FALSE:
All Trees are graphs
True
What is the running time of BFS (Breadth First Search and DFS (Depth First Search) in a Graph?
O(V + E)
(O of vertex + edge)
What is the run time of Dijkstra’s Sortest Path?
O(logV(V + E)
What is the run time of search, insert, and delete in a hash table ?
O(1)
What does LRU stand for?
Least Recently Used
What is LRU?
It’s a cashing mechanism that we will evict the least recently used item
