end of year exam Flashcards
(56 cards)
What are the characteristics of Binary search?
- Requires the data to be sorted
- keeps dividing the data in halves til the target is found or when the minimum more than the maximum
- Efficent for large data sets as dividing is alot quicker than going through each value in the data set
What structures are used in bubble sort
Nested loop
What is sequential search
iterates through a set of data until the target is found
What are the characteristics of sequential search
- works by iterating through a set of data sequentially till the target is found
- it is the simplest search al;gorithm
- data does not need to be sorted
- might need to go through the whole array or most of it
What is the code for sequential search
N = [ 2, 9, 5, 6, 7, 8] // Array of unsorted elements
X = 7 // Search value
FOUND = false //
loop COUNTER from 0 to 5
if N[COUNTER] = X then
FOUND = true
output N[COUNTER], “found at position” , COUNTER
end if
end loop
if FOUND = false then
output X, “ not found “
end if
What is binary search
divides a range of valyes into halves and continues that process narrowing it down till the target is found
code for binary search
ARR =
X = // target
MIN = 0
HIGH = 12 // number of elements in the array - 1
FOUND = false
MID = 0
loop while FOUND != true AND MIN <= HIGH
MID = ((MIN + HIGH) div 2)
if ARR[MID] = X then
FOUND = true
else if X > ARR[MID] then
MIN = MID + 1
else
HIGH = MID - 1
end if
end while loop
if FOUND = true then
Output X, “FOUND AT THE ARRAY INDEX” , MID
else
Output X, “ was not found”
end if
Advantages and disadvantages of binary search
Advantages
-Fewer Comparisons as it eliminates half each time
-Efficient for Large Datasets
Disadvantages
- requires a sorted list of data
- harder to implement
- Not as efficent for constantly changing lists
Advantages and disadvantages for sequential search
Advantages
- Works on Unsorted Data
- simple to implement
- Effective on Small Datasets
Disadvantages
- Inefficient for Large Datasets
- might have to go thorugh the whole data set to find the target or worst case scenario iterate through the entire array
What is bubble sort
compares adjacent elements and exchanges them if they are not in the right order. after each loop one less element needs to be compared
characteristics of bubble sort
After each loop, one less element needs to be compared
The algorithm is very slow and impractical for most cases
Repeatedly steps through the array to be sorted
Simple sorting algorithm
code for bubble sort
Temp = 0
ARR = [. . . . .]
loop M from 0 to ARR .length-1
Loop N from 0 to ARR.length - M
If ARR[N] > ARR [ N + 1] then
Temp = ARR[N+1]
ARR[N+1] = ARR[N]
ARR[N] = Temp
end if
end loop
What is selection sort
divides the array into two sections, the first section is already sorted elements and the second section is unsorted elements. it finds the smallest element in the unsorted section and replaces it with the leftmost element in the unsorted section
Characteristics of selection sort
Simple and inefficient sorting algorithm
Divides array into two sections
First section contains already sorted elements
The second contains the unsorted elements
At the beginning the section that contains the sorted elements is empty
And the section with the unsorted elements is the entire array
The algorithm finds the smallest element ( or largest depending on sorting order) in the unsorted section and exchanges it with the leftmost element in the unsorted section
Code for selection sort
ARR = [1, 663,8,2,4,3]
N = 0
TEMP = 0
loop MIN from 0 - ARR.length - 2
N = MIN
loop UNSORTED from MIN + 1 to ARR.length -1
if ARR[UNSORTED] < ARR[N] then
N = UNSORTED
end if
end loop
TEMP = ARR[N]
ARR[N] = ARR[MIN]
ARR[MIN] = TEMP
end loop
Suggest a suitable algorithm to solve a specific problem what do u need to look at
Efficiency: amount of the computer resources required to perform its functions. Minimizing the use of various resources such as the CPU and memory is important.
Correctness: the extent to which the algorithm satisfies its specification, free from fault, and fulfills all objectives set during the design and implementation.
Reliability: refers to the capability of the algorithm to maintain a predefined level of performance
Flexibility: effort required to modify the algorithm for other purposes
Need for Pre-Conditions
describes the starting state before the execution of an algorithm, indicates what needs to be true before the sub-procedure is called
Need for post conditions
indicates what will be true when the sub-procedure completes its task,describes the final states after the execution of an algorithm
What is a collection
a data structure that stores a group of elements of the same or different data types. Collections have a set of methods that can be called on to help access data and iterate through
what are the collection operations
add.item()
get.Next()
resetNext()
hasNext()
isEmpty()
what is a sub program
A sub-program is a unit that contains a sequence of computer instructions that perform a specific and predefined task.
Advantages of breaking a program into sub programs
-breaking complex programming jobs into smaller simpler jobs
- enables code reuse
-reduces programming code duplication
characteristics of a collection
Resizeable
stores different data types
has a set of methods that can be called upon to help iterate through the data and access it
