SLR 25 - Algorithms 1

Question 1

What are some of the techniques and methods you could use to help you design and write algorithms?

Answer 1

• Psuedocode
• Abstraction

Question 2

What are the two standard sorting algorithms you need to know?

Answer 2

• Bubble sort
• Insertion sort

Question 3

What are the two standard searching algorithms you need to know?

Answer 3

• Linear search
• Binary search

Question 4

How does a linear search work?

Answer 4

The program will go through every item in a list in order checking if its the item youre looking for

Question 5

What is the code for a linear search?

Answer 5

found = False
index = 0
While found == False and index < len(items):
if items[index] == item_to_find:
found = True
else:
index = index + 1

Question 6

How does a binary search work?

Answer 6

This search starts at the middle of the list and repeatedly divides the list in half until it reaches the desired item

Question 7

What is the code for a binary search?

Answer 7

found = False
first = 0
last = len(items) - 1
While first <= last and found == False:
midpoint = (first + last) // 2
if items[midpoint == item_to_find:
found = True
else:
if items[midpoint] < item_to_find:
first = midpoint + 1
else:
last = midpoint - 1

Question 8

How does a bubble sort work?

Answer 8

The program will run through the list item by item and compare adjacent items and swap them if they arent in the required order.

Question 9

What is the code for a bubble sort?

Answer 9

n = len(items)
swapped = true
while n > 0 and swapped == True:
swapped = False
n = n - 1
for index in range(0,n):
if items[index] > items[index+1]:
temp = items[index]
items[index] = items[index=1]
items[index+1] = temp
swapped = True

Question 10

How does an insertion sort work?

Answer 10

An insertion sort inserts each item into its correct position in a data set one at a time

Question 11

What is the code for an insertion sort?

Answer 11

for index in range(1,n):
current = items[index]
index2 = index
while index2 > 0 and items[index2 - 1] > current:
items[index2] = items[index2 -1]
index2 = index2 - 1
items[index2] = current