CHAPTER 4 - COMPUTATIONAL THINKING Flashcards
Algorithm
a series of unambiguous instructions designed in order to solve a problem and achieve a certain goal in a finite number of steps
Explain how data is sorted by the selection sort
Selection sort is a sorting algorithm that sorts data by dividing the array into two sub-arrays: the first one containing already sorted data and the second contains the unsorted elements of the array. At the start, the sub array containing the list of sorted elements is empty while the sub array containing the unsorted data refers to the entire array. The algorithm continues by finding the smallest/largest element in the array and exchanges it with the leftmost unsorted element, to put it in a sorted order. The algorithm then moves the first sub array borders one element to the right and repeatedly does this until the whole array is sorted
Outline one difference between a bubble sort algorithm and a selection sort algorithm
Bubble sort algorithm is a sorting algorithm that repeatedly steps through the array from the left to the right, exchanging adjacent data elements, to sort it from ascending or descending order. On the other hand, selection sort is a sorting algorithm that works by dividing the array of data into two separate sub arrays, and then exchanging the data element which is the smallest/largest with the leftmost data of the array, to sort it into either ascending/descending order.
Outline why a sub-program is considered an example of abstraction
A sub program is an example of abstraction as it breaks down the whole computer program into separate smaller programs which hides unnecessary details of specific objects within the program and speeds up the program development process. Maintaining and operating these sub programs will also be easier as they are smaller in size and can be repeatedly used throughout the entire program.
Evaluate the use of designing and developing different parts of software products concurrently.
The process of designing and developing different parts of a program concurrently means creating program modules all at the same time by multiple processors to achieve the fastest development progress. This helps reduce development time and time to release the program, bringing improved productivity and lower costs. Additionally, any concerns/errors regarding the program can be solved instantly during the design process.
Outline one way in which users can be informed of software updates.
Users can be reminded by software updates through email or SMS messages online. The program’s support team can remind users of software updates (e.g. bug fixes) by contacting their email addresses or sending messages through their phone numbers, in case they add the information in their account details.
For an identified application, explain why a binary search would be preferred to a linear search.
Binary search refers to a searching algorithm which relies on the divide and conquer strategy to accomplish its purpose whereas, linear search relies on brute force strategy and does not require the use of ordered elements (sorted arrays). Linear search is fairly simple compared to binary search, however for large data sets, it operates far slower compared to binary search. This is because linear search finds an element in the list by searching it subsequently until it is found in the list while binary search uses the middle value in the list repeatedly until the middle element is matched with a searched element.
Properties of an algorithm
- Finiteness: must always terminate after a series of steps
- Definiteness: every step of the algorithm must be precisely defined
- Input: quantities which are given to it initially before the algorithm begins
- Output: quantities which have a specified relation to the inputs
- Effectiveness: all operations performed must be sufficiently basic that they can be done exactly in a finite number of time by pen and paper
Explain about variables
A variable is used to store a data element of a program. The stored value can be changed during the program execution. It also has a name (or identifier) and a type.
Thematic map
A thematic map is an abstraction of reality that shows the spatial distribution and emphasizes a particular theme, such as the average distribution of income in a specific geographic area.
Topographic map
Topographic maps show abstractions of selected physical features of the three dimensional real world at a reduced scale in two-dimensions, paper or a screen
Political maps
Political maps are designed to show data such as the boundaries of countries, states and the location of major cities.
Explain about object-oriented programming
Object-oriented programming uses abstraction, and is based on the principle that all everyday tasks can be considered as entities. These entities are either objects or events.
Define abstract thinking
Abstract thinking means reflecting on events, ideas, attributes and relationships in a general manner that hides all unnecessary details of specific objects. For example, a concrete thinker may identify and count two cats and two cars, while an abstract thinker may identify their common relationship which is the number two.
Define collections
A collection is an object that assembles and contains a lot of elements in a single structure.
For example, queues and stacks. It is also used to add, store, manage, retrieve, manipulate, and communicate the data using predefined methods.
Sequential/linear search
A sequential/linear search algorithm is a very simple method to find a particular element in an array. The implementation of this algorithm does not require the use of ordered elements (sorted arrays). It relies on brute force strategy to accomplish its purpose.
Binary search
Binary search/half interval search algorithm is a searching method used only in sorted arrays. It relies on divide and conquer strategy to accomplish its purpose.
Define bubble sort
Bubble sort is a simple sorting algorithm that repeatedly steps through the array to be sorted. It compares adjacent items (pairs of adjacent array elements) and exchanges them if they are not in the correct order (ascending or descending). The algorithm makes multiple passes until no swaps are necessary and the elements of the array are sorted.
Define selection sort
Selection sort is a very simple and inefficient sorting algorithm that divides the array into two sub-arrays: the first sub-array contains the already sorted elements, and the second sub-array contains the unsorted elements and occupies the rest of the array. The algorithm continues by finding the smallest/largest element in the sub-array that contains the unsorted elements, exchanging it with the leftmost unsorted element (located in the lowest index position) and putting it in sorted order. The algorithm then moves the first sub-array borders one element to the right.
Define an array and give one example of an array
An array can hold multiple data elements of the same type (integers, strings, boolean etc). It has a name, a size that cannot be changed during program execution (in most cases is a static data structure) and a data type that describes the type of data that it can store. For example: int array [10] = { 32, 33, 34, 35, 49, 19, 21, 58, 20, 42 }
Explain why abstraction is required in the design of algorithms
Abstraction refers to reflecting on ideas, events or attributes in a general manner that hides all unnecessary details of specific objects. This is required as it speeds up the designing process and helps programmers have a general idea of the problem. This would help them further develop proper solutions/algorithms to the problem.
Explain the importance of using coding style and naming conventions when programming
Coding style helps programmers make source codes that are organized and easily readable. It also helps programmers focus on sources of errors that may appear throughout their code. Additionally, naming conventions help programmers easily identify functions or attributes in the source code and differentiate between the types of variables and parameters in their code.
Ways to express an algorithm
- simple english
- flow chart
- pseudocode
- programming language