Problem Solving and Algorithms Flashcards
What is an algorithm?
A set of unambiguous instructions for solving a problem or sub-problem in a finite amount of time using a finite amount of data.
What are the two methodologies used to develop computer solutions?
Top down and Object-oriented design.
What is top-down design?
It’s where the design focuses on the tasks to be done?
What is object-oriented design?
A design that focuses on the data involved on the solution.
What are simple data types?
Data types which are not further broken down into other data types. This includes integers, characters, Boolean values…
What are composite data types?
Data types which are aggregation of other data types in some way. These aggregated types themselves may be composite or atomic.
What are records?
A heterogenous (multiple data types) collection of individual items that are accessed by name. Can contain different atomic types.
What are arrays?
A homogenous (same type of data) collection of items in which an individual item is accessed by its position within the collection.
How does a sequential search work on an unsorted array?
A linear search that looks through every element in the array until a value is found or the end of the array has been reached, thus the value not in the array.
What is a sequential search with a sentinel value?
Similar to a sequential search with the only difference being that the search item is indexed at the end of the array so that if it’s found at the position equal to the size of the array the desired value is not in it. This gets rid of one of the conditions in the array.
What is the worst case scenario for the sequential search algorithm?
O(n)
What is a sorted array?
An array where elements are indexed in ascending or descending order within the array.
How does a binary search work?
Search begins in the middle of the array and checks if the value is in the middle. If not it determines whether the search value is less than or greater than the middle value. If value is less it will eliminate the upper half of the program and repeat the same process on the remaining data until found or not found.
What condition must be met in order for a binary search to work?
The list/array must be sorted.
How does selection sort work?
On each pass it goes through the list and searches for the smallest value and once found inserts it into the first index. On the next pass it finds the next smallest value and inserts it into the second index. This process is continued until all elements are inserted into the correct position.
