CS midterm 2!!

When using an interface backed by an array what is the complexity of the get() and set() methods? Why?

O(1) or constant. Because indexing an array is an equation based on the index.

When using an interface backed by an array what is the complexity of the remove() method ignoring resize? Why?

It is O(n-i) when n = number of elements and i = the index. This is because you have to copy all the elements over when deleting something.

How are things stored in memory?

Randomly, as 4 contiguous bytes

How is an array stored in memory?

In contiguous bytes big enough to hold all the elements

List ADT

Ordered, indexable

How are linked structures stored in memory?

randomly with links (references) to each other

What is the time complexity of addFirst / removeFirst in an ArrayList?

O(N) because all elements have to be moved over

What is the time complexity of addFirst / removeFirst in an SinglyLinkedList?

O(1) because your just change nodes pointer

What is the time complexity of getLast in an SinglyLinkedList?

O(N) because you have to traverse it to find it

What is the time complexity of addLast / removeLast / get() in an SinglyLinkedList? What about a DoublyLinkedList?

O(N) in single because you have to traverse to get to the end. O(1) in double because you have a pointer to the last element.

Functionality of a Stack

An ADT that provides access to the last added (most recent) element. FILO (First In, Last Out)

What is the time complexity of the push() / pop()/ peek() methods in a stack backed by an array? Why?

Peek and Pop are always O(1) because they just access the back of the array. If push doubles the backing array is can be O(N) otherwise it is O(1).

What is the time complexity of the push() / pop()/ peek() methods in a stack backed by a LinkedList? Why?

All O(1) because the head of the list acts as the top of the stack. You just move the head pointer for push() / pop() and peek just accesses the head.

Functionality of a Queue

An ADT that provides access to the first added element (least recent) FIFO (First In, First Out)

Offer (enqueue)

add item to back

Poll (dequeue)

remove and return item from the front

Peek

return front item without removing

What is the complexity of the Peek() / Offer() / Poll() methods of a Queue backed by an array? Why?

They are all O(1) because the array has a pointer to the head and the back and functions move the pointer. It also wraps around the array.

What is the average case for adding to an array? Best / worst?

Average/Best is O(1) for some crazy

What is a graph?

A data structure. Made up of nodes (the element) and vertexes (what connects them, stored randomly in memory

Undirected Graph

A graph in which the edges have no direction

Directed graph

In a directed graph, the order of the vertices in the pairs in the edge set matters.

What does the degree of a graph refer to?

Number of edges connected to a vertex

What is an indegree?

The numberof edges going into a vertex

What is an outdegree?

The number of edges going out of a vertex

What is an adjacency matrix?

A tabular way to store a graph where each vertex is assigned a row and a column.

What is an adjacency list?

A way to store a graph where each vertex has a list of other vertices its connected to.

What is a dense graph?

When a graph has most of the possible edges. |E|≈ |V|2

What is a sparse graph?

When a graph has only a few edges for each vertex. |E| ≈ |V|

What kind of storage should you use for a dense graph? What about a spares one?

Dense graphs should use an adjacency matrix to save storage and access time. Sparse graphs should use adjacency list to be effective with storage.

What is a Acyclic graph?

A graph that contains no cycles

What is a Directed acyclic graph (DAG)?

A graph that is directed and has no cycles

What is a connected graph?

A graph where there is at least one path between all pairs of vertices/nodes

What is depth-first search?

Explore in one direction till you reach the end then go back. It will find a path if it exists but it's not guaranteed to be the shortest path. Visually this looks like going down first.

What is the pseudo code for Depth-first search?

(Vertex current, Vertex goal)

Check if current is the goal

Mark current as visited

If neighbor has not been visited recursively call neighbor

Record where this visit is coming from

What is the complexity of a dense graph on average? Why?

O(|V|^2) because dense graphs have way more edges for each vertex.

What is the complexity of a sparse graph on average? Why?

O(|V|) because there is going to be way more vertices then edges in a sparse graph.

What is Breadth-first search?

Explore all of the closest vertices, then move further. It will find a path if it exists and it will be the shortest one. Visually this looks like going left to right outward.

What is the pseudo code for Breadth-first search?

get an empty Queue, add the stating vertex

While queue is not empty:

1. Poll current vertex

2. For each neighbor of current:

3. If not visited, add to back of queue and mark visited.

What is the requirement for Breadth-first search to work?

The graph must be unweighted.

What is topological sort?

Used for sorting a Directed Acyclic Graph (DAG) graph by the vertices, in a linear way. Such that for every directed edge u-v, vertex u comes before v in the ordering. there are multiple possible orderings

What is the pseudo code of topological sort?

For each vertex in the graph if vertex has an indegree of 0 add it to the queue

while the queue is not empty

get the next vertex

for each neighbor of the vertex decrement the indegree

if neighbor has an indegree of 0 add to queue

What is Dijkstra's algorithm?

Will find the shortest path in a graph with non-negative edge weights. Find distance from a source to every other vertex.

What is a tree?

A data structure. It is a special kind of directed graph where every vertex as exsactly one parent (except the root) there are no cycles.

What is the difference between height and depth of a tree?

The depth is how far from the root that specific node is. The height is how far the deepest possible leaf node is.

What is preorder traversal?

node, left, right (recursive)

What is post-order traversal?

left, right, node (recursive)

What is in-order traversal?

left, node, right (recursive)

What is level order traversal?

Like BFS

Traversal pseudo code

traversal(current, list)

What is a BST? Why is it epic?

Combines a binary tree with ordering. So everything on the left is less then its parent and everything on the right is more then the parent. Searching for a node in a BST is like binary search.

What is the complexity of the get() / contains() method in a BST? Why?

O(H) where H is the height of the BST. Because its ordered each time you check a node you go down by one depth. And effectively get rid of another half of the tree.

What is the complexity of the min() / max() method in a BST?

O(H) where H is the height of the BST. Because you only have to travel the height of the tree to get all the way left / right.

What are the three cases you run into when removing an item form a BST?

1. the node has no children, so set it to null and set it parent pointer to null

2. the node as one child, set the node.parent to point to node.child

3. the node as two children, replace it with a predecessor or successor

What is a sucessor?

The left-most node of the right subtree. (The minimum of the node's right subtree)

What is a predecessor?

the right-most node of the left subtree. (The maximum of the node's left subtree)

What is the complexity of the remove() / add() method in a BST? Why?

O(H) where H is the height of the tree. Because most of the work is in find the node (or where it should be) operations to add/remove fall off.

When a tree is balanced what is O(H) equal to? Why? What is the root closer to?

O(log|V|) because each time you advance you effectively cut off half of the tree. The root is close to the median.

When a tree is not balanced what is O(H) equal to? Why? What is the root closer to?

O(|V|) because there are about as many vertexes as there are edges. The root is close to the maximum or minimum.

How to create a balanced BST out of sorted list? How to make it unbalanced?

Add the median of each side of the array recursively. Add the items in order.

What makes a BST balanced?

For every node, the height of left and right subtrees differs by 0 or 1

What is a hash function? What is a hash code?

A hash code is a unique integer for an object. A hash function generates a hash code.

What is a Hash table?

A data structure that is backed by an array and uses a hash function to choose the index of an element

What is the complexity of searching / inserting / removing for a hash table? Why?

O(1) because to find the index of an array is O(1).

If two objects have the same hash function do they equal each other? Why or why not?

No. Because many objects could return the same hash code

If two objects equal each other do they have the same hash function? Why or why not?

Yes. Because equal objects should return the same hash code.

How do you find the index of your object in a hash table?

object.hashCode() % table.size() -1

(-1 because the index is 0 - size - 1)

What is linear probing?

A way to deal with collisions in hash tables. If a cell is already full put it in the next one. Uses 'lazy deletion' to save time

What is Separate chaining?

A way to deal with collisions in hash tables by adding collisions to a linked list in the cell.

What is quadratic probing?

A way to deal with collision's when inserting, if the cell is already full, try a later one with increasing gap. Uses 'lazy deletion' to save time i^(th) collision = index + i^(2)

What is the load factor of a hash table?

(λ) number of elements in the hash table / size of the array

λ = 0

table completely empty

λ = 1

same number of cells and elements

λ > 1

more elements than cells

To keep operations O(1) what should the load factor be for separate chaining? Why?

λ < 10 because all operations are O(λ ) and it is equal to 10 the complexity becomes O(1)

To keep operations O(1) what should the load factor be for linear probing?

0 ≤ 𝜆 < 1 but using linear probing will probably cause many collisions and not be O(1)

To keep operations O(1) what should the load factor be for quadratic probing?

λ < 0.5 and the capacity has to be a prime number.

What is lazy deletion?

Keeping the object but marking it as deleted

What is required for growing a hash table?

When the table grows, every item must be rehashed. So we find hash code again and % with the new capacity. It is a really expensive operation.

What is the complicity of finding the min / max of a hash table? Why?

O(cellCount).

What is a map?

An ADT it stores (key, value) pairs

What is an ADT?

Specifies what the data is and the operations that can be performed on it, without going into how the data is actually stored in memory.

What is a data structure?

Define how data is organized in memory and how operations on that data are performed efficiently.