3. Flashcards
What does the binary search look like?
array myIntegers[5] = [12, 16, 19, 22, 25]
start = 0
end = 4
found = false
input searchItem(“Please enter search item”)
midPoint = 0
while (found == false AND start <= end)
midPoint = (start + end) DIV 2
if (myIntegers[midPoint] == searchItem) then
found = true
elseif (myIntegers[midPoint] > searchItem)
end = midPoint - 1
else
start = midPoint +1
endif
endwhile
if (found == true) then
print(“Item found at “ + midPoint)
endif
What does a bubble sort look like?
temp = 0
for i = 0 to arr.length-1
swapped = false
for j = 1 to arr.length - 1 - i
if (arr[j-1] > arr[j]) then
temp = arr[j-1]
arr[j-1] = arr[j]
arr[j] = temp
swapped = true
endif
next j
if (swapped == false) then
break
endif
next i
What does a insertion sort look like?
array myNumbers[4]
for (i = 1 to myNumbers.length – 1)
key = myNumbers[i]
j = i - 1
while (j >= 0 AND myNumbers[j] > key)
myNumbers[j + 1] = myNumbers[j]
j–
endwhile
myNumbers[j + 1] = key
next i
Pros of insertion sort?
Easy to implement
Good for small data sets that are almost sorted
Insertion sort generally performs quicker than bubble sort and is therefore preferable.
Cons of insertion sort?
Does not scale well so is not good for large data sets.
What is caching?
The process of storing previously used data in a location (cache) so that it can be quickly accessed to speed up retrieval if it is needed in future.
What is a library?
A collection of reusable subroutines that a programmer can “call” when writing code so that the programmer doesn’t have to write this code.
What are reusable components?
The use of existing assets in some form within the software product development process including code eg subroutines, designs and documentation.
What is pre-fetching?
Data is fetched and stored in a cache or buffer before it is needed. For example when streaming a video file, successive seconds/minutes of stream data are buffered. Algorithms must be able to correctly predict what will be needed.
Explain CPU cache?
Cache on CPU is faster to access frequently used data/instructions. This is because it’s physically located on the chip, cache uses SRAM not DRAM which is used for main memory.
Pros of CPU cache?
faster response time.
Cons of CPU cache?
small size
SRAM is expensive and fixed size.
What is the HDD cache (HDC)?
When requesting data, the HDD checks the HDC first before moving the slower mechanical parts for main memory, so is faster.
Pros of HDC?
faster response time
Cons of HDC?
small and fixed size
Pros of reusable components?
Saves time and resources, as every programmer doesn’t need to recode it.
Can sell code to a 3rd party, developer gets money, user knows it’s going to work.
Increased dependability, it has been tried and tested.
A particular element can be written by a specialist.
Update one library and every program that uses it is updated.
