Exam Flashcards

Question

What is a disadvantage of using heuristics

Answer 1

They don't always return the correct or most optimal solution

Answer 2

Uniform distribution of keys minimal collisions fast computation

Answer 3

findShortestWeightedPaths(graph, sourceNode) { unvisitedNodes = graph.getAllNodes() // Set of all unvisited nodes for each node in unvisitedNodes { shortestDistance[node] = infinity // Initialize all distances to infinity } shortestDistance[sourceNode] = 0 // Distance to the source node is 0 while unvisitedNodes is not empty { currentNode = node in unvisitedNodes with smallest shortestDistance remove currentNode from unvisitedNodes // Mark the current node as visited for each edge connectedEdge incident on currentNode { neighborNode = graph.getOppositeNode(connectedEdge, currentNode) edgeWeight = graph.getEdgeWeight(connectedEdge) // Get the weight of the edge newDistance = edgeWeight + shortestDistance[currentNode] // Tentative distance if newDistance < shortestDistance[neighborNode] { shortestDistance[neighborNode] = newDistance // Update to smaller distance } }

Answer 4

BFS(Graph graph, startNode) { currentLevel = [startNode] // Start with the list containing the start node while currentLevel is not empty { nextLevel = [] // Prepare a new list for the next level of nodes for each node in currentLevel { visit(node) // Process or visit the node for each edge connected to node { // Explore all edges incident on the node if edge is unexplored { // Check if the edge has been explored neighborNode = graph.opposite(edge, node) // Find the other endpoint of the edge if neighborNode is undiscovered { // If the neighbor node hasn't been discovered yet label(edge, "discovery") // Label the edge as a discovery edge add neighborNode to nextLevel // Add the undiscovered neighbor node to the next level } else { label(edge, "cross") // If the neighbor node has already been discovered, label the edge as a cross edge } } } } currentLevel = nextLevel // Move to the next level, update 'currentLevel' with the new list of nodes } }

Answer 5

Choose a node as first node, mark as visited discover all neighbours that haven't been discovered visit each undiscovered node once all neighbours are visited move to their discovered neighbours

Answer 6

No need to traverse over entire list direct access to adjacency lists ensures o(1) removal time per edge

Answer 7

O(k) where k is the degree of the node edge removal is o(1)/edge as we can directly access adjacency lists

Answer 8

Find the node object remove from node list remove incident edges: access the nodes adjacent edge, for each adjacent edge remove the edge itself and update the adjacency list of the other endpoint to remove reference to this edge

Answer 9

O(m) where m is the number of edges

Answer 10

A weakly connected graph is when the graph is connected if we ignore the direction of edges

Answer 11

A graph is connected if there's a path between every pair of nodes

Answer 12

A subset of the original nodes and edges

Answer 13

A tree is an undirected graph in which any 2 nodes are connected by 1 path

Answer 14

Path length is number of edges in a graph

Answer 15

A path is a sequence of nodes and edges that link 2 nodes

Answer 16

The degree of a graph is the number of edges connected to it undirected graph: total edges connected to the graph directed graph: in degree - edges coming into the node Out degree - edges going out of the node

Answer 17

The degree of a graph is the number of edges connected to it undirected graph: total edges connected to the graph directed graph: in degree - edges coming into the node Out degree - edges going out of the node

Answer 18

A spanning tree is a subset of graph that connects all nodes, has no cycles and contains exactly n-1 edges where n is the number of nodes

Answer 19

Directed graphs: edges have a direction going from one way to another undirected graphs: edges have no direction the connection is bidirectional

Answer 20

Directed graphs: edges have a direction going from one way to another undirected graphs: edges have no direction the connection is bidirectional

Answer 21

A graph G =(V,E) V: a set of nodes E: a set of edges connecting the nodes

Answer 22

Uniform distribution of keys minimal collisions fast computation

Answer 23

Advantages: hashing provides o(1) for search insertion and deletion average compared to arrays o(n) for sorted arrays and o(logn) for unsorted arrays hash tables can also grow dynamically with resizing or extendible hashing unlike fixed size arrays hash tables can allocate memory dynamically for buckets whereas arrays allocate memory upfront and is fixed disadvantages: hash tables don't maintain the order of elements while arrays order ordered traversal Hashing works with unique keys and duplicate keys require extra handling unlike arrays where duplicates are inherently supported arrays allow direct access to elements via indices whereas hashing requires a hash code which adds extra overhead

Answer 24

Searching becomes o(log(n/m)) for binary search but adds overhead during insertion

Answer 25

A bucket overflows when it can't store any more key value pairs due to collisions

Answer 26

Worst case: hash function is poor and all keys map to the same bucket so it's essentially a linked list inserting is o(1) and searching/deleting becomes o(n) average case: hash function distributes keys evenly. search/delete is o(n/m) if load factor is low it's close to o(1)

Answer 27

Advantages: don't need to resize entire table, dynamically adjusts to varying data sizes, handles collisions efficiently disadvantages: more complex to implement and splitting buckets requires rehashing and reorganising data

Answer 28

A dynamic hashing technique where the hash code is treated as a bit string and the hash code splits when buckets overflow using more bits to differentiate keys

Answer 29

Advantages: minimises clustering by providing a better distribution of probes disadvantages: more complex to implement than quadratic and linear probing and requires careful choice of the second hash function to avoid infinite loops !=0

Answer 30

A second hash function is used to calculate the step size for probing

Answer 31

Advantages: reduces clustering in comparison to linear probing better distribution of keys in tables disadvantages: more complex than linear probing and can still fail to resolve collision if table size isn't a prime number suffer from secondary clustering where keys with the same initial hash code follow the same sequence

Answer 32

Leads to primary hashing where groups of filled slots form increasing chances of collisions and slowing future insertions and searches performance degrades as table fills up

Answer 33

Simple to implement and cache friendly due to sequential memory access

Answer 34

Quadratic probing skips slots in a quadratic pattern. h(k,i) = (h(k)+i^2) mod m

Answer 35

A collision handling technique where the next available slot is searched sequentially; h(k,i) = (h(k)+i) mod m

Answer 36

Open adddressing stores key value pairs directly in the hash table. If a collision occurs it probes for the next available slot using techniques such as linear probing quadratic probing secondary hashing

Answer 37

Handles collisions automatically buckets can grow dynamically performs well with a good hash function and low load factor

Answer 38

Each bucket stores a list (or chain) of key value pairs when keys collide they are added to the same buckets list

Answer 39

A collision occurs when 2 keys hash to the same bucket

Answer 40

The load factor is the ratio of the number of keys n to the number of buckets m LF=n/m

Answer 41

A bucket is a container at an array index where one or more key value pairs may be stored

Answer 42

Hashing maps keys to values using a hash function enabling efficient data storage and retrieval

Answer 43

A single rotation is an o(1) operation propagating changes is an o(logn) operation as after a rotation the height of the subtree may change which requires updates to the balance factors of its patent, grandparent and so on. In the worst case the propagation may need to travel up the height of the tree which js proportional to o(logn)

Answer 44

What's the balance factor in an AVL tree

Answer 45

The difference in heights between the left and right subtree of a node

Answer 46

After a node is added/removed the balance factor of any node isn't within [-1,1]

Answer 47

It's the smallest value larger than the deleted node or the largest value smaller than it. So the leftmost node on the right subtree

Answer 48

Leaf node node with one child node with 2 children

Answer 49

In a balanced binary search tree with n nodes its height is log base 2 n eaxh step the target value is compared with the current nodes value and move to either the left or right node. Each step halves the search space. The search path is proportional to the height of the tree so the search time is also o(Logn) if the tree becomes unbalanced its height can grow as large as n in the worst case. Its time complexity becomes O(n) as you may have to visit every node to find the target

Answer 50

For each node all labels in the left subtree are less than the nodes label and all labels in the right subtree are greater

Answer 51

First/ last: is simple to implement but can lead to unbalanced partitions (eg worst case o(n^2)) if the list is already sorted median: improves balance and avoids worst case scenarios but adds extra computation to find the median randomly: generally ensures balanced partitions on average, avoiding input specific patterns and is computationally cheap

Answer 52

Structural algorithms like merge sort: approach: divide the list based on structure (eg splitting by size) Advantages: predictable performance (o(nlogn)) for all cases and no reliance on input values disadvantages: uses extra space due to auxiliary arrays value driven algos: approach: divide based on value comparisons advantages: can be done in place using o(1) memory disadvantages: worst case performance is o(n^2) when partitions are imbalanced and requires careful pivot selection

Answer 53

Splitting is a log n operation and merging is o(n) operation making it o(nlogn)

Answer 54

It splits the list into two halves, recursively sorts them and merges the sorted halves

Answer 55

Selection sort is o(n^2) because it performs roughly n comparisons for each element since there are n elements the number of comparisons grows quadratically

Answer 56

Repeatedly find the smallest element and place it at the beginning of the list

Answer 57

Public void insertionSort(array){ for (int i =1; I=0 && array[j] > temp){ array[j+1] = array[j] j-- } array[j+1] = temp

Answer 58

It's average case is o(n^2) because well roughly have to do n/4 swaps for n elements giving you an average complexity of o(n^2) its worst case is o(n^2) and it occurs when it's reverse sorted. For each of the n elements it performs up to n shifts its best case is o(n) this is when the list is sorted because each element only needs a single comparison to check whether it's in the right place

Answer 59

They don't always return the correct or most optimal solution

Answer 60

They provide faster approximate solutions. Useful for when algorithms take too long or fail to terminate

Answer 61

Algorithms terminate for finite inputs heuristics aren't always guaranteed to terminate and give approximate results

Answer 62

Operators are after operands and derived using post order traversal

Answer 63

Infix notation uses in order traversal and brackets are used to surround each sub expression. Operators are inline with operands

Answer 64

Prefix notation uses pre order traversal, operators are before operands

Answer 65

Public void traverse(BinaryTreeNode node){ if(node.left!=null) traverse(node.left) visit(node.element) if(node.right!=null) traverse(node.right) }

Answer 66

Visit the first child them the node then the next child

Answer 67

Public void traverse (BinaryTreeNode node){ if(node.left != null) traverse(node,left) if(node.right!=null) traverse(node.right) visit(node.element) }

Answer 68

Visit the children then visit the node

Answer 69

public void traverse(BinaryTreeNode node){ visit(node.element) if(node.left!=null) traverse(node.left) if(node.right!=null) traverse(node.right) } private void visit(Object element){ print(element + ",") }

Answer 70

Visit the node then visit that nodes children

Answer 71

for (int I =0; I< array.length-1;I++){ int min = I for (int j = i+1; j array[j]){ min = j } } int temp = array[i] array[i]=array[min] array[min] = temp }

Answer 72

For (int I =0; I < array.length: I++ ){ For (int j =0;j array[j+1]){ int temp = array[j] array[j]=array[j+1] array[j+1] = temp } } }

Answer 73

Arrays have a fixed size so the stack can't be resized the user could easily overestimate or underestimate the amount of elements their stack will need to store which could lead to memory wasteage or unexpected errors

Answer 74

The implementation of an array based search is simple since it only requires an index to keep track of the top element pushing and popping from an array based stack runs in o(1) time so it's efficient array based implementations have lower memory overhead as they don't need to store references to pointers

Answer 75

this means the last element that is added to the stack is the first that is popped out

Answer 76

public class ArrayStack implements IStack{ private int size; private T[] elements; public ArrayStack(int maxSize){ size =0 elements = new (T[]) Object[maxSize] } Public void push ( T element){ if ( size < elements.length){ elements[size++] = element } else{ throw new StackOverflowException(); } public T pop(){ if (isEmpty()){ throw new StackEmptyException } else{ size-=1; return elements[size-1] } public T top(){ if(isEmpty()){ throw new StackEmptyException() } else{ return elements[size-1] } } public Boolean isEmpty(){ return size =0; } public void clear(){ size =0; }

Answer 77

public class ListNode{ public T element public ListNode next public ListNode(element){ this(element,null) } public ListNode(T element, ListNodenext){ this.element=element this.next = next } public class Queue implements IQueue { private ListNode front private ListNode back private int size =0 public Queue(){ this.front = null; this.back = null; size =0; } public void enqueue ( T element){ ListNode newNode = new ListNode(element) If ( isEmpty()){ front = newNode back = front } else{ back.next = newNode back = back.next } size++ } public T dequeue() throws QueueEmptyException(){ T frontElement = front.element front = front.next size- - return front.element; } public int size(){ return size } public Boolean IsEmpty(){ return size == 0 }

Exam Flashcards

(101 cards)