Section 8 Chapter 46 and 47

Question 1

Linear search

Answer 1

Searching for an object in a list by checking each object in order until the desired object is found

Question 2

Linear search complexity

Answer 2

O(n)

Question 3

Why you would use a linear search

Answer 3

To search an unordered list

Question 4

Time complexity of binary search

Answer 4

O(log n)

Question 5

Time complexity of bubble sort

Answer 5

O(n^2)

Question 6

Time complexity of merge sort

Answer 6

O(nlog n)

Question 7

What merge sort and binary search are examples of

Answer 7

Divide and conquer

Question 8

Space complexity

Answer 8

The amount of resources, for instance memory, that an algorithm requires

Question 9

How to code depth first search

Answer 9

Recursion

Question 10

How to code breadth first search

Answer 10

Just do it in a function, use a queue and when adding, check that the node is not in visited AND not in the queue

Question 11

Application of depth first search

Answer 11

Navigating through a maze

Question 12

Applications of breadth first search (2)

Answer 12

• Finding the shortest path between two nodes

- Web crawlers going through links

Question 13

Data structure associated with a depth first search

Answer 13

stack

Question 14

Data structure associated with a breadth first search

Answer 14

queue

Question 15

What traversal is the same as the depth first search

Answer 15

pre order