topic: algorithms

Question 1

implementing a linear search

describe a linear search

Answer 1

finds an item in a sorted or unsorted list, by checking each item one by one starting with the first item in the list

Question 2

pros of a linear search

Answer 2

the data set doesn’t need to be ordered first
efficient for smaller data sets

Question 3

write an example of a linear search pseudocode

Answer 3

searchItem = (“enter a search item”)
found = False
i= 0
while (found = False AND index < items.length )
if item[i] == searchItem then
found == True
else
i ++
endif
endwhile

Question 4

what 4 things must a linear algorithm be able to do

Answer 4

1. locate an item in a data set - if it exists
2. beable to locate the item regardless if the dfataset is organised or not
3. run wihtout crashing even if data set does not exist
4. check each item sequentially, starting with the first item

Question 5

describe what binary search is

Answer 5

an algorithm for finding an item in a sorted list , it starts in the middle of the data set and then repeatedly divides the list in half -getting rid of the half that doesn’t contain the search item

Question 6

example of binary search pseudocode

Answer 6

found = False
first = 0
last = items.length-1

while first < = last AND found == False
midpoint= (first + last) DIV 2
if items [midpoint] == searchItem then
found = True
else
if items[midpoint] < searchItem then
first = midpoint + 1
else
last = midpoint - 1
endif
endif
endwhile

Question 7

Write the pseudocode for procedure that performs a binary search on a sorted array of data with the identifier studentNames. The procedure should take two parameters, one for the array of names and another called searchItem which is the item to search for. If the name is found in the array, the procedure should print found, if not print not found.

Answer 7

procedure search(studentNames, searchItem)
start = 0
end = studentNames.length - 1
found = false
while not found and start <= end
midPoint = (start + end) DIV 2
if studentNames[midPoint] == searchItem then
found = true
elseif studentNames[midPoint] > searchItem then
end = midPoint - 1
else
start = midPoint + 1
endif
endwhile
if found then
print(“Found”)
else
print(“Not found”)
endif
endProcedure

Question 8

what is a bubble sort algorithm

Answer 8

pne that works by repeatedly swapping the adjacent elements if they are in the wrong order, it is not efficient in large data sets as its average and worst-case time complexities are quite high

Question 9

example for the pseudocode for a bubble sort
write the algorithm as a function that takes in the array myNumbers as a parameter and returns the sorted array.

Answer 9

function bubbleSort(myNumbers[])

for (i = 0 to myNumbers.length - 2)
swapped = false
for (j = 1 to myNumbers.length - 1 - i)
if (myNumbers[j-1] > myNumbers[j])
temp = myNumbers[j-1]
myNumbers[j-1] = myNumbers[j]
myNumbers[j] = temp
swapped = true
endif
next j
if (swapped == false) then
break //breaks out of loop
endif
next i
return myNumbers
End function

Question 10

write the bubble sort procedure called, sortData and call it using the array data[] as a parameter by reference

Answer 10

procedure sortData(data[]:byRef)
swapped = true
while swapped == true
swapped = false
for j = 0 to data.length - 2
if data[j] > data[j + 1] then
temp = data[j]
data[j] = data[j + 1]
data[j+1] = temp
swapped = true
end if
next j
endwhile
endprocedure

Question 11

descirbe 2 disadvantages of using bubbles sort

Answer 11

1. bubbles ort is an inefficient algorithm, meaning it will take more time to sort lists than other sorting algorithms
2. the item to be sorted is at the end of the list, which is the worst case scenario for bubble sort (it can only move back one place per pass)

Question 12

A programmer has been tasked with writing a function that uses a binary search to return
a Boolean value. The function should return true if the target integer is found in a list of
integers. Using pseudocode, write an algorithm for the function.

Answer 12

function findItem (numberArray integer[2000], targetNumber:integer, leftPtr:integer,
rightPtr:integer): boolean
while (leftPtr <= rightPtr)
midPoint = (leftPtr + rightPtr) DIV 2
if (numberArray[midPoint] == targetNumber)
return true
else if (numberArray[midPoint] < targetNumber)
leftPtr = midPoint + 1
else
rightPtr = midPoint - 1
endif
endwhile
return false
endfunction

Question 13

The program needs a second procedure, sortData. It will be called taking the array data[]
as a parameter by reference.
The procedure will then perform a bubble sort on the data in the array.
95 10 5 33 100 77 45
Write, using pseudocode, the procedure sortData.

Answer 13

procedure sortData(data[]:byRef)
swapped = true
while swapped == true
swapped = false
for innerCount = 0 to data.length - 2
if data[innerCount] > data[innerCount + 1] then
temp = data[innerCount]
data[innerCount] = data[innerCount + 1]
data[innerCount+1] = temp
swapped = true
end if
next innerCount
endwhile
endprocedure