Chapter 9&10 - Algorithm Design And Program Solving + Data Types & Structures Flashcards
Abstraction
The process of extracting information that is essential while ignoring what is not relevant for the provision of a solution
Decomposition
The process of breaking a complex problem down into smaller parts
Pattern recognition
Identification of parts of a problem that are similar and could use the same solution
Structured English
Method of showing the logical steps in an algorithm, using an agreed subset of straightforward English words for commands and mathematical operations
Flowchart
Diagrammatic representation of an algorithm
Algorithm
Ordered set of steps to be followed in the completion of a task
Pseudocode
Method of showing the detailed logical steps in an algorithm, using key words, identifiers with meaningful names, and mathematical operators
Stepwise refinement
The practice of subdividing each part of a larger problem into a series of smaller parts, and so on, as required
Benefits of abstraction (3)
Time required to develop the program is reduced so the program can be delivered to the customer more quickly
Program is smaller in size so takes up less space in memory and download times are shortened
Customer satisfaction is greater as their requirements are met without any irrelevant features
Process of abstraction (3)
Identify purpose of the model of the situation
Identify sources of information
Use information gathered from appropriate sources to identify what details aren’t necessary and need to be removed
Data type
Classification attributed to an item of data, which determines the types of value it can take and how it can be used
Identifier
Unique name applied to an item of data
Record (data type)
Composite data type constructed using several of the basic data types available in a particular programming language
Array
Data structure containing several elements of the same data type
Index [array]
Numerical indicator of an item of data’s position in an array
Lower bound
Index of the first element in an array, usually 1 or 0
Upper bound
Index of the last element in an array
Linear search
Method of searching in which each element of an array is checked in order to
Bubble sort
Method of sorting data in an array into alphabetical/numerical order items and swapping them if they are in the wrong order
File
Collection of data stored by a computer program to be used again
ADT
Abstract data type
Collection of data and a set of operations on that data
Stack
List containing several items operating on the last in, first out principle
Queue
List containing several items operating on the first in, first out principle
Linked list
List containing several items in which each item in the list points to the next item in the list
Basic data types (6)
String
Boolean
Char
Date
Integer
Real
Uses of stacks (3)
Memory management
Expression evaluation
Backtracking in recursion
Uses of queues (3)
Management of files sent to a printer
Buffers used with keyboards
Scheduling
Uses of linked lists (3)
Using arrays to implement a stack
Using arrays to implement a queue
Using arrays to implement a binary tree
3 ADTs
Linked lists
Stacks
Queues
