Unit 1 Fundamentals of Programming Flashcards
What is an algorithm?
A sequence of steps that can be followed to complete a task
What is abstraction?
Abstraction involves removing unnecessary detail from a problem so that you can focus on the essentials.
What is decomposition?
Breaking a problem down into smaller sub-problems, making the overall problem easier to solve
Advantages of decomposition
- The problem becomes easier to solve when it consists of a number of smaller subtasks or modules
- Some modules may be reusable in other programs, saving development time
Processing
Any operations carried out by a computer system
What is a variable?
A variable is a location in memory in which you can temporarily store text or numbers
Data types
- Integer
- Real
- Boolean
- Character
- String
Integer
A whole number
Real
A number with a decimal point
Boolean
Can only be TRUE or FALSE
String
One or more characters enclosed in quote marks
Sequence
The statements are executed in the order they are written
Selection
- An IF statement is a selection statement
- The next statement to be executed depends on whether the condition being tested is true or false
Iteration
- Iteration means repetition
- A set of statements are repeated a fixed number of times, or until a condition is met
Three types of iteration statements
- FOR…ENDFOR
- WHILE…ENDWHILE
- REPEAT…UNTIL
FOR…ENDFOR loop
Used when you want to execute the loop a specific number of times
WHILE…ENDWHILE
- Used when you want to execute the loop while a certain condition is true
- The condition is tested at the beginning of the loop
REPEAT…UNTIL
- Used when you want to execute the loop until a certain condition is true
- The condition is tested at the the end of the loop, it is always executed at least once
- So an IF statement is needed as well as the Repeat loop
Describe the process of a binary search
- Examine the middle item of the list first and determine whether the correct data item has been found
- If not, check whether it is before or after the current item in the data set
- Discard the half of the data set that does not contain the item
- Repeat the algorithm until the data item is found or it is not in the data set
- Only works if the data items are in sequence
Describe the process of a linear search
- If the list to be searched is not sorted, it is not possible to do a binary search. A linear search may be carried out instead
- Examine each item in turn until the item is found or the end of the data structure/file is reached
Comparison of searches
- Linear search the list can be ordered or unordered, but for a binary search the list must be ordered
- A binary search is much more efficient than a linear search because with every iteration of the algorithm, the size of the range of items that needs to be searched decreases by half
Explain the process of bubble sorting
- Each item in a list is compared to the one next to it, and if it is greater, they swap places
- At the end of one pass through the list, the largest item is at the end of the list
- This is repeated until all the items are sorted
Explain the process of a merge sorting algorithm
- Divide the unsorted list into n sublists, each containing one element
- Repeatedly merge two sublists at a time to produce new sorted sublists until there is only one sublist remaining. This is the sorted list
Comparing merge sort to bubble sort
- The merge sort requires more memory to store the sublists, and with a very large number of items this can be a disadvantage
- Merge sort is much more efficient than the bubble sort, the bubble sort is slow and inefficient for more than a few items
