9.2.2 Planning and designing the solution Flashcards
(31 cards)
Name the four basic data types
Integer, float, string, boolean.
Name the 2 basic data structures
- Arrays, which could be multidimensional (arrays of arrays).
- Records, which is a single data item consisting of a number of named fields.
True or False - in this course, arrays must contain the same data type.
True!
In some languages like C and Java when the array is declared so must the data type of all the elements in the array.
However, many real-world languages like Python and JavaScript allow for arrays to be composed of many different data types.
Name and describe the 3 control structures used in algorithms and the various sub-types of each.
- Sequence - operations in an algorithm are performed in order.
-
Decision (branching) - different actions are taken depending on a particular condition.
- Binary decision (IF…ELSE…ENDIF)
- Multiway decision (CASEWHERE…ENDCASE)
-
Iteration (looping) - the same series of steps are
- Pre-test loop (WHILE…ENDWHILE)
- Post-test loop (DO…WHILE)
- Counting loop (FOR…NEXT)
How would the following algorithm snippet be represented with a flowchart?
FOR i = start to finish
DISPLAY arr(i)
NEXT i
Since there is no counting loop in a flowchart, the algorithm would have to be implemented with a pre-test loop.
Write an algorithm to iterate over an array arr and call a function someFunc on each element of the array.
BEGIN
FOR i=1 TO length of array
someFunc(arr(i))
NEXT i
END
Write an algorithm to find and return the minimum value of an array called numbers, given that each element in the array could take on any value.
BEGIN minimum
min = numbers(1)
FOR i = 2 to length of numbers
IF numbers(i) < min THEN
min = numbers(i)
ENDIF
NEXT i
RETURN min
END minimum
Write an algorithm to find and return the maximum value of an array called numbers, given that each element in the array could take on any value.
BEGIN maximum
max = numbers(i)
FOR i = 2 to length of numbers
IF numbers(i) > max THEN
max = numbers(i)
ENDIF
NEXT i
RETURN max
END maximum
Write an algorithm to return the sum of all the elements in an array called numbers.
BEGIN sum
sum = 0
FOR i = 1 TO length of numbers
sum = sum + numbers(i)
NEXT i
RETURN sum
END sum
Write an algorithm to return the average of all the elements in an array called numbers.
BEGIN average
sum = 0
FOR i = 1 TO length of numbers
sum = sum + numbers(i)
NEXT i
RETURN sum / length of numbers
END average
Write an algorithm SimpleFind(item, arr) that searches for a value item in an unsorted array arr and returns True or False, depending on whether the item was found. The algorithm need not terminate once the element has been found the first time.
Because the data are unsorted, a linear search must be used.
BEGIN Find(item, arr)
found = False
FOR i = 1 TO length of arr
IF arr(i) = item THEN
found = TRUE
END IF
NEXT i
RETURN found
END
Write an algorithm LinearSearch(item, arr) that returns True if item is found in arr or False otherwise. The algorithm should terminate once the item is found and only contain a single RETURN statement.
BEGIN LinearSearch(item, arr)
found = False
index = 1
WHILE index <= length of arr AND found = False
IF arr(index) = item THEN
found = True
END IF
index = index + 1
ENDWHILE
RETURN found
END LinearSearch
What are the two types of file access and how do they differ?
- Seqential - data is stored in a continuous stream, and must be accessed from beginning to end.
- Random access - Used to store records, an application is able to jump straight to any individual record.
What is a priming read?
In a sequential file, a pre-test loop is used to repeatedly read from the file, which exits when EOF or a sentinel value is found. There needs to be a priming read before this condition is checked so that the algorithm will work if the file is empty.
What is a sentinel value?
A sentinel value is a “dummy value” used to indicate the end of data within a file.
Note: While it is more commonly applied to sequential files, a sentinel may also be used when getting an unknown number of inputs from the user. For example, in a CLI application the user might be asked to repeatedly enter data, or a blank value to exit. In this case, the blank value is the sentinel.
Write an algorithm to open a sequential file and print the contents until EOF is found.
BEGIN
OPEN somefile for Input
READ item from somefile
WHILE NOT EOF
DISPLAY item
READ item from somefile
ENDWHILE
CLOSE filename
END
Write an algorithm to open a sequential file and print the contents until the sentinel value “-1” is found.
BEGIN
OPEN somefile for Input
READ item from somefile
WHILE item != -1
DISPLAY item
READ item from somefile
ENDWHILE
CLOSE filename
END
Write an algorithm printEmployee(empID, file) that prints the employee name with the given empID from the file. Each employee record includes the fields EmployeeID, FName and LName.
BEGIN printEmployee(empID, file)
OPEN file for relative access
READ EmployeeData INTO EmployeeID, FName, LName USING empID
PRINT FName, LName
CLOSE file
END printEmployee
Write an algorithm addLog(info) that appends info to the end of a file called ActivityLog.dat
BEGIN addLog(info)
OPEN ActivityLog.dat for Append
WRITE info to ActivityLog.dat
CLOSE ActivityLog.dat
END addLog
Explain how binary search works
On each pass of the algorithm, the middle value is compared against the search value. Based on the comparison, the list is split into 2, with 1 half discarded and the process repeated with the other half.
Crucially, the data must be sorted for binary search to work.
Under what circumstances would linear search be used instead of binary search?
Binary search is much quicker than linear search, but the data must be sorted.
So linear search would only be used if the data were unsorted.
Compare the cost (number of comparisons) of linear and binary search.
For linear search, the maximum number of comparisons is equal to the number of items in the list.
For binary search, the size of the list halves each time. This means that the maximum number of comparisons needed, n, is when 2n is greater than the size of the list.
For example, for a list with 1000 elements:
- A linear search could take 1000 comparisons.
- A binary search would at most take 10 comparisons, because 210 = 1024 (note that 29 = 512).
Explain how insertion sort works.
The list is divided into a sorted part and an unsorted part. For the first item in the unsorted part, find the correct position in the sorted part and insert the item into that position. Repeat until all items are sorted.
Explain how selection sort works.
The list is divided into a sorted part and an unsorted part. Use a linear search to find the smallest item in the unsorted part and swap with the front of the unsorted part. Repeat until all items are sorted.
