unit 12 Flashcards

Question

what is a breadth first traversal?

Answer 1

explore all neighbours of the current node then the neighbours of each of those nodes and so on

Answer 2

traverse as far as down one path as possible and backtrack

Answer 3

job scheduling where some jobs are prioritised finding a path between two vertices solving maze puzzles

Answer 4

finding shortest path between two points a web crawler uses bdf to analyse sites

Answer 5

sparse graph = O(n) graph with max edges = O(n^2)

Answer 6

shortest path A* and Dijkstra

Answer 7

designed to find the shortest path between a start node and every node in a weighted graph

Answer 8

represent distances, time, cost,

Answer 9

uses a priority queue to keep record of which node to visit next starts by setting temporary distance of 0 to start node and infinity to every other node

Answer 10

a problem is defined as computable if there is an algorithm that can solve every instance of it in a finite number of steps

Answer 11

problems for which there exist no efficient algorithms to solve them have no polynomial time solution

Answer 12

limits of computation for example cannot be solved due to time or speed

Answer 13

algorithmic complexity hardware

Answer 14

all possible routes tested

Answer 15

a problem with polynomial time solution or better

Answer 16

use heuristics

Answer 17

using an estimate or rule of thumb to find a solution

Answer 18

g(x) - real cost from source to a given node h(x) - the approximate cost from node(x) to goal node

Answer 19

f(x) = g(x) + h(x)

Answer 20

h(x) should never be greater than g(x) h(x)

Answer 21

A* focuses only on reaching end node, DJ finds shortest path to end node A* uses heuristics

Answer 22

both optimisation algorithms

Answer 23

array = [] i = 0 while i < len.array - 1 for j = 0 to len.array - i - 2 if array[j] > array[j+1] temp = arrat[j] array[j] = array[j+1] next j i += 1

Answer 24

procedure insert(list) n = len(list_ for i = 1 to n -1 item = list[i] position = i while position > 0 and list[position -1] > item list[position] = list[position - 1] list[position- = item

Answer 25

is top pointer < 0? isEmpty() if top < o return True else return false

Answer 26

is top pointer = len stack?

Answer 27

peek() if isEmpty() return error else return stack[top]

Answer 28

push(item) top+=1 stack[top] = item

Answer 29

pop () if isEmpty(): return error else index = stack[top] stack[top] = " " top -= 1 return index

Answer 30

size() isEmpty() peek() enqueue() dequeue()

Answer 31

isEmpty() if front == back return True else return False

Answer 32

peek() return queue[front]

Answer 33

enqueue(item) queue[back] = item back += 1

Answer 34

dequeue() if isEmpty() return Error else index = queue[front] queue[front] = " " front += 1 return index

Answer 35

array Queue = [] front = -1 rear = -1 is full () FUNCTION enqueue(queue, front, rear, data) IF isFull() return null ELSE rear = rear + 1 MOD max queue[rear] = "" IF front = -1 THEN front = 0

Answer 36

FUNCTION dequeue(queue, front, rear) IF is empty() return null ELSE dequeued = queue[front] IF front == rear front = -1, rear = -1 ELSE front = front +1 MOD maxsize

Answer 37

current = node1 while current is not NONE: print(current.data) current = current.next

Answer 38

new_node = Node() if node1 is None node1 = new_node else current = node1 while current.next is not None current = current.next current.next = new_node

Answer 39

while current is not None if current.data == "" if previous is None node1 = current.next else previous.next = current.next previous = current current - current.next

Answer 40

PROCEDURE pre_order_traversal(node) PRINT(node.data) IF node.left != Null THEN pre_order_traversal(node.left) ENDIF IF node.right != Null THEN pre_order_traversal(node.right) ENDIF ENDPROCEDURE

Answer 41

PROCEDURE in_order_traversal(node) IF node.left != Null THEN in_order_traversal(node.left) ENDIF PRINT(node.data) IF node.right != Null THEN in_order_traversal(node.right) ENDIF ENDPROCEDURE

Answer 42

PROCEDURE post_order_traversal(node) IF node.left != Null THEN post_order_traversal(node.left) ENDIF IF node.right != Null THEN post_order_traversal(node.right) ENDIF PRINT(node.data) ENDPROCEDURE

unit 12 Flashcards

(69 cards)