10 - Algorithms 3 (Search)

Question 1

What is searching?

Answer 1

Searching for an item in a collection

Question 2

Why may you want to search?

Answer 2

Want to know if an item is there at all

Want to know an item’s position

Question 3

Name 3 applications of searching

Answer 3

Parsing strings

Database queries

Finding files on a disk

Question 4

What is linear searching?

Answer 4

Going through all items and checking if any equal the key

Question 5

What’s the worse case of linear searching?

Answer 5

Going through all elements

Question 6

What is the work and step complexity of linear search?

Answer 6

O(n)

Question 7

What does the performance of linear search depend on?

Answer 7

The data distribution

Question 8

What do databases and other applications use to accelerate searching?

Answer 8

Sorted lists or B-trees

Question 9

What is binary search?

Answer 9

A divide and conquer searching technique

Question 10

What is the process of binary searching?

Answer 10

Recursively/iteratively check if the middle location contains the key, if not then discard one half which cannot contain the value, check the middle location of the remaining half and so on

Question 11

What is the parallel search input split?

Answer 11

Divide input into p parts (number of processing elements) and run a serial search for each part

Question 12

What are the effects of the input split?

Answer 12

A potential speed up of p times

But need to wait for all threads to finish

Some threads might need to perform the worst case scenario

Latency corresponding to the slowest search

Question 13

What is the parallel search multiple keys?

Answer 13

Perform multiple searches at the same time

Question 14

What are the effects of multiple keys searching?

Answer 14

A potential speed up of p times

Underutilisation if a number of searches is smaller than p - lots of idle threads

Early exit

Larger p makes it more likely that the worst case execution time will happen

Question 15

How does a parallel binary search benefit from parallelism?

Answer 15

Parallel implementation using p PEs can perform p searches simultaneously

Question 16

Discuss memory access in parallel search?

Answer 16

Binary parallel search cannot benefit from coalesced memory access

Linear parallel search might be faster for small arrays

In general, binary parallel search is preferable

Question 17

What is the P-ary search?

Answer 17

A divide and conquer strategy on sorted arrays

Question 18

What is the process of P-ary search?

Answer 18

Divide input into p parts, all p threads searching for the same key in a different part, each thread checks if the key can be in their part, the selected part is again assigned in equal shares to all threads, and the process is repeated until the search key is found

Question 19

How does the p-ary search check for the key?

Answer 19

Assuming sorted arrays, each thread needs to look only at first and last elements of part of its subset to determine which part contains the search key

This part is again assigned in equal shares to all threads, and process is repeated until search key is found

Question 20

What is the complexity of the p-ary search?

Answer 20

O(logpn)

Question 21

What are search trees?

Answer 21

Another way of representing data in pre-ordered format

Question 22

What are binary search trees?

Answer 22

Where each node can have two children

Question 23

How do you traverse a binary search tree?

Answer 23

Compare out key with a node and select left child if its value is lower or right child if it is highter

Question 24

What is the complexity of binary search tree?

Answer 24

O(log n)

Question 25

What is a B-tree?

Answer 25

A generalisation of binary search trees where each node can have multiple children

When searching, more than two paths diverge from a single node

Very efficient when combined with p-ary parallel search

Question 26

The binary search requires the input data to be sorted. What applications might justify that additional step?

Answer 26

Multiple searches, such as database queries. Searching performance depends on data distribution so its better if the key is more likely to be near the start of the collection.

Question 27

What’s the totally rad thing about the step complexity of p-ary?

Answer 27

It scales with the increasing number of threads