Topic 4: Computational Thinking and Programming Flashcards
Describe the characteristics of the linear search (sequential search) algorithm.
Simple, takes at most n comparisons on a list of length n, does not required the list to be ordered.
Construct pseudocode for the linear search/sequential search algorithm.
See image.
Describe the characteristics of the binary search algorithm.
Only works on sorted arrays, relies on divide and conquer strategy, half of the elements are eliminated at each step, much more efficient than linear search for large arrays, requires at most log(n) comparisons on an array of size n.
Construct pseudocode for the binary search algorithm.
See image.
Describe the characteristics of the bubble sort algorithm.
A simple sorting algorithm that steps through the array, compares adjacent elements and swaps them if they are out of order. Makes repeated passes through the array until no swaps are made and the array is sorted. Slow and impractical for most cases.
Construct pseudocode for the bubble sort algorithm.
See image.
Describe the characteristics of the selection sort algorithm.
A simple and inefficient sorting algorithm, divides the array into a sorted subarray and an unsorted subarray. It finds the smallest element in the unsorted subarray and swaps it with the first element in the unsorted subarray, putting it in sorted order. Now the sorted subarray is one element larger and the unsorted one element smaller. This is repeated until the sorted subarray is the entire array.
Construct pseudocode for the selection sort algorithm.
See image.
Outline the standard operations on a collection (like an array or list).
addItem(): used to add an item to the collection (like using items.append(value) in Python).
getNext(): returns the first item in a collection when it is first called, will then return subsequent items when it is called again.
resetNext(): restarts iteration through the collection. When getNext() is called after resetNext() it will return the first element of the collection again.
hasNext(): Returns true if there are remaining elements in the collection that have not yet been accessed durign the current iteration (through calling getNext()).
isEmpty(): Returns true if the collection contains no elements, and returns false otherwise.
Suggest two design considerations that could be made to an algorithm that would make it more efficient.
The algorithm could use loops;
To remove the necessity to process extra lines of code;
Use of arrays/data structures;
So data can be stored/re-used/re-entered;
Use of flags;
To stop a search routine when an item has been found so that all elements don’t have to be searched;
State the fundamental operations of a computer.
Add, compare, retrieve, and store data. Complex operations are composed of combinations of a large amount of these simple operations.
Distinguish between fundamental and compound operations of a computer.
Compound operations involve multiple fundamental operations. For example, a program that finds the maximum of four numbers would have to use multiple fundamental operations to read, compare and store these numbers.
Explain the essential features of a computer language.
Has fixed vocabulary, unambiguous meaning, consistent grammar and syntax.
Explain the need for higher level languages.
Computer programs have grown sufficiently complex that writing all programs in machine code (code using the fundamental operations that can run directly on the device) becomes too tedious and difficult. Higher level languages were developed to be much easier to use and closer to natural language, however programs written in them need to be translated to machine code before they can be executed.
Outline the need for a translation process from a higher level language to machine executable code.
(The program written in HLL must be translated into machine code) so that the computer can execute the program; as the computer only understands machine language / as code written in HLL can only be understood by humans and cannot be interpreted by the computers (which work in binary);
