Dannys Cards Flashcards
What is the time complexity of Counting Sort?
O(n)
What is a Sequential Structure?
We can only access an element after we have accessed all the elements before it
Whats the difference between Direct Access and Hash Tables?
Direct Access: key “k” is stored in slot k
Hash Table: key “k” is stored in hash(k)
How does Counting Sort work?
Creates array to store count of all elements
Changes the array so the count also adds all the elements prior
Iterates through main list and takes count number and places it in new list with index of the count number
Repeat until done, -1 from count when used
Why do collisions happen in Hash Tables?
Because we’re mapping elements to normally smaller domain of slots, collisions are likely to happen
How does MSD radix sort work?
Unlike LSD radix sort, it starts from left most (most significant) digit groups those together, then goes to next digit on the right and groups those together in sub groups, then groups the next digits on the right in sub sub groups and so on.
540,330,545,350,333,578,570
First grouping of digit of 100s
Eg. 330,350,333 540,545,570,578
2nd grouping of 10’s
330,333 350 540, 545 570,578
3rd and final grouping of 1’s to make completed list
330,333,350,540,545,570,578
What is a Circular List?
The link member of the last node points to the first node
What are the rules of Binary Search Trees?
the value of left node must be smaller than the parent node, and the value of right node must be greater than the parent node
What is the benefit of a Balanced Tree?
Increases efficiency of searching
If a tree is balanced we can perform most operations in O(log n)
How does Quicksort work?
- Pick an item, is called the “pivot”
- Sort the other elements so that smaller elements are on its left and bigger are on its right
- Now you have two piles of items repeat this until each pile has 1 card
- Once sorted add all piles together
What is a Direct Access Structure?
Any element of the structure can be accessed directly
How long does a Simple Step take in RAM?
1 time step
How do Lists differ from Arrays?
They don’t have a fixed size, but like arrays then can only store elements of the same type
-> Homogenous Structure
Explain O(n^2) time
Quadratic
Relatively efficient for non large input sizes
Typical of algorithms that have to analyse all pairs of element of the input
Define an edge
A connection between 2 nodes
What is an Insertion Sort?
Builds the final sorted array one element at a time by inserting elements into their correct positions
Define a leave
Nodes that have no children
What is the Bernoulli Process?
A series of executions of Bernoulli trials
What type of algorithm is Quick Sort?
Divide and Conquer
How does Merge Sort work?
Splits list into separate lists then merges the lists back together in order
Define a Dense Graph?
graph with a large number of edges in relation to the number of vertices, and the number of edges is close to the maximum possible number
E is close to V^2
E = O(V^2)
Explain O(n^3) time
Cubic
Not very efficient but still polynomial
Example is Matrix Multiplication
Explain O(n) time
Linear, algorithms that are forced to pass through all elements of the input, a number of times
What is the worst case of an Insertion Sort?
O(n^2)
Same as selection sort
Define a Graph?
Collection of vertices(nodes) and edges (arcs)
G = (V,E)
What is the best and worst case of Hash Search?
Worst case: O(n)
Best case: O(1) (and average case)
What is a Forest?
A collection of trees
Disjoint
What is the worst case of Quicksort?
O(n^2)
What structure is a Stack and what structure is a Queue
Stack: Last-In-First-Out (LIFO)
Queue: First-In-First-Out (FIFO)
Are loops and subroutines considered simple operations?
NO, they’re considered the composition of many simple step operations
What is the worst case for Bubble Sort?
O(n^2)
What is the worst case for Selection Sort?
O(n^2)
What is Big O notation used for?
Primarily used for worst case or upper bound of the growth rate of a function
Define a Stable Sort?
Sorting method is said to be stable if it preserves the relative order of the items with duplicated keys on the list
What is a Heap (binary tree)?
Special kind of binary tree structure where each node is smaller (or larger) than its children
What is 1 advantage or disadvantage of an array?
Provides direct access to elements
BUT has fixed size
What are weak and strong connected Directed Graphs?
Directed Graphs can be:
Weakly Connected: there exists a path between every pair of nodes, regardless of the direction of the edges
Strongly Connected: Same but there must be a path between every pair of nodes
Explain O(1) time
Constant time
What is the worst case for Merge Sort?
O(nlog n)
What is considered:
a) exponential
b) polynomial
a) K^x where k is constant
b) x^k where k is constant
What is Big Omega (Ω) notation used for?
Represents the best-case performance of an algorithm (lower bound of an algorithm as lower bound is less time)
Explain O(log(n)) time
Logarithmic, common in searching and in same tree algorithms
How do you search a Hash Table?
- Hash the target
- Take the value of the Hash of the target and go to the slot. If the target exists it must be in that slot
- Search in the list in the current slot using a Linear Search
What is a Bernoulli Trial?
The term is used to refer to an experiment on a random process that could have 2 possible outcomes
- Success or failure
- (Processes are independant)
What is a Priority Queue?
An abstract data type where items are removed based on their priority (highest to lowest)
What is different about traversal in a Directed Graph?
Edges have directions which makes traversal of a graph slightly different
How does LSD Radix Sort work?
Sorts numbers or strings one digit at a time starting from right most digit (least significant) and moving to left most digit (most significant)
What is an AVL tree?
*Each tree has a root node (at the top)
*Every node has 0,1 or 2 child nodes
*Value of left descendants are less than the right descendants
What is a Min Heap and a Max Heap Trees?
Min Heap: parent node is smaller than children
Max Heap: parent node is larger than children (most common)
What is a M-ary Tree?
Entire tree has a maximum of m children and the tree is ordered
Binary tree is a 2-ary tree
Define a nan- terminal
Node with at least one child
What algorithm was proposed by Tony Hoare?
Quick Sort Algorithm
Define an Edge
Connects Nodes
normally dont have properties (values) but they may have if its a weighted graph
What is Heap Sort? (priority queue sorting)
Turn list into heap
Then remove elements systematically to get list ordered from big to small
What is a Linked List?
Where nodes each contain one member that gives the location of the next node in the list
Define a Vertice
Vertices(v) are objects that have properties associated with them
What is Reverse Polish Notation?
Eliminates need for brackets- simpler and better for computers
5 8* = 40
141 12/ = 11.75
Explain O(n^k log n) time
Polylogarithmic
Typical of algorithms that use divide and conquer
Explain O(2^n) time
Exponential
Bad as testing all possible answers to problem
When algorithms fall into this catagory designers go in search of approximation algorithms
What is Order Preservation in Hash Tables?
Given an ordering of keys to be hashed from:
k1 < k2 < k3<… <kj
then we should expect that
hash(k1) < hash(k2) < hash(k3) <… M hash(kj)
When you hash the keys the hashes should follow the same hierarchy in size
What is Dijkstras Algorithm?
Finding shortest path between nodes in a graph
What are the 4 rotation types?
Single Right
Single Left
Double Right
Double Left
What is Big Theta (θ) notation used for?
Represents average case of the growth rate of a function
Define a Sparse Graph
A graph in which the number of edges is much less than the possible number of edges
E is much less than V^2
E = O(V)
What are the cons of Quick Sort?
Its recursive (more costly)
Is O(n^2) in worst case
Its fragile
What is a Doubly Linked List?
every node includes a link to the next node and previous node
<>node1<->node2<->node3<->node4<>
node1 and node 4 also connected
Define a Simple Path
A path where no node is repeated
For the average case what is Radix Sort’s time complexity
O(n)
How does the Selection Sort work?
Finds the index of the minimum element each time and puts it at the start until list is sorted
What is the worst case of Quicksort using Recurrence?
O(n^2)
T(n) = O(n) + T(n-1)
When are Tree Rotations used?
When the tree becomes unbalanced. They depend on balanced factors and on the location where the tree is unbalanced
What are the disadvantages of Linked Lists (Dynamic Lists)?
Algorithms are more complex, harder to read and debug
Allocation and deallocation of memory space requires extra resources (overhead)
What is the time complexity cost of rebalancing a tree?
O(log n)
Which recurrence relation yields a running time of O(log n)?
T(n) = T(n/2) + 1
What are the advantages of Linked Lists (dynamic lists)?
their ability to efficiently handle insertions and deletions at any position within the list
Size of the structure does not need to be declared in advance
Define a Node?
An object that has a name and normally info
Why is the worst case of Merge Sort O(n log n)?
Merge of a list size n requires O(n) comparisons
Each time list is halved and halves are sorted recursively
So divide and conquer recurrence applies:
T(n) = 2T(n/2) + O(n)
What makes a good Hash Function?
One that satisfies the assumption of uniform hosting
Meaning each key is equally likely to hash any of the m slots available
Define a Tree
A non-empty collection of nodes and edges which may carry properties
Define a Complete Graph
every pair of distinct vertices is connected by a unique edge so no vertices with no edges
Maximum no. of edges ( E = V(V-1)/2)
What is the best case analysis of Quicksort?
T(n) = 2T(n/2) + O(n)
Which equals O(n logn)
What are the pro’s of the Quicksort?
Not difficult to implement
Works in variety of situations - good general purpose
Works at O(n log n) at average case
What is a Multilist?
A linked list whos nodes contain multiple link fields that form independant linked lists
What are Algorithms?
Specific instructions for getting answers
Define a Spanning Tree?
A connected subgraph that contains all nodes of the graph but has no cycles or loops
What is a Graph?
When one or more path exists between any pair of nodes its a graph
Define a Cycle
a path that starts from a given vertex and ends at the same vertex is called a cycle
What is the master theorem for Divide and Conquer?
T(n) = 2T(n/2) + O(n)
How to heapify a Tree?
4 ways
Bottom Up:
Systematically swim/ sink nodes in reverse level-order traversal
Top Down:
Systematically swim/sink nodes in level-order traversal
Define a Path?
A sequence of adjacent nodes connected by edges
What is algorithm efficiency split into?
Running Time
Memory Space
Define a Balanced Tree?
Where no leaf is more than a certain amount further from the roots of any other to keep efficiency
What is the worst case for Radix Sort?
O(n log n)
What is a Balance Factor?
the height of the subtree rooted at its left child minus the height of the subtree rooted at its right child
eg. +1, 0 ,-1
