Topic 4 - Computational thinking, problem-solving and programming

Problem

a situation that needs attention and

needs to be dealt with or solved

Decision Making

Intelligence Gathering, Design, and Choice

Computer Program

a sequence of instructions, written to instruct a computer to perform a specified task

Algorithm

a series of unambiguous instructions designed in order to solve a problem and achieve a certain goal in a finite number of steps

Properties of an Algorithm

finiteness, definiteness, input, output, effectiveness

Finiteness

An algorithm must always terminate after a finite number of steps a very finite number, a reasonable number

Definiteness

Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case

Input

quantities which are given to it initially before the algorithm begins

Output

quantities which have a specified relation to the inputs

Effectiveness

all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil

Purpose of Pseudocode

to help programmers develop computer programs. Because pseudocode is written for humans the syntax used is not as strict as the one used in computer languages. 

Thinking Procedurally

step-by-step problem solving

Thinking Logically

Decision-making and conditions

Thinking Ahead

Pre-planning inputs, outputs, etc

Thinking Concurrently

the execution of different instructions simultaneously by multiple processors so as to achieve the best performance. 

Thinking Abstractly

Simplification and focus on essentials

Top-Down Design/Stepwise refinement

the complex problem is decomposed and for each sub-problem, an appropriate sub-procedure is developed

Sub-Procedure

contains a series of commands that perform a task: so the procedure is divided into a series of sub-procedures; this process is referred as a modular programming approach.

Identifier

the name that is used by the programmer to uniquely identify a variable, an object a sub-procedure etc.

Iteration

the process of repeating a series of instructions

Example of Pre-Planning

use of software libraries e.g Numpy or Pandas

Gantt Chart

a type of bar chart widely used for project schedule and project management, as a way of showing activities, tasks and events against time

Exception

an act or event that disrupts the anticipated flow of the program’s execution

Sequential Processing

is the execution of all sub-procedures one after the other by a single processor

Requirements of Concurrent Processing

better planning and coordination of resources

Abstraction

the process of taking away or removing characteristics from something in order to reduce it to a set of essential characteristics.

a technique for managing complexity of computer systems.

Collection

a data structure that consists of the data and the predefined methods which operate on the data.

Abstract Data Type

a group of operations and data

Mathematical Modelling

a system is understood well enough and scientists describe it using mathematical language

Computer Simulation

runs on a computer and reproduces the behavior of a real system. 

Variable

acts as a storage location that can be used to store a value. Value can be changed during execution. Can store a particular type of data

One Dimensional/Linear Array

can hold multiple data elements of the same type. Has a name, size (cannot be changed), and a data type

Parallel Array

A data structure consisting of multiple arrays where corresponding elements across the arrays are related by their index position. Each array typically holds a different type of data, but they are logically connected.

2 Dimensional Array

data come in the form of a data table

Examples of Algorithms

Sequential Search, Binary Search, Bubble Sort, Selection Sort

Sequential Search

finds specific element by going through the list 1 element at a time. Runs in O(n) time

Binary Search

method of finding element in sorted numerical array. Works by halving the index between a left and a right bound until it narrows onto the item it is looking for. Runs in O(logn) time

Bubble Sort

Method of sorting array by looping through it and switching adjacent elements if the right one is larger. Runs in O(n²) time

Selection Sort

Method of sorting lists. Splits into two parts, one sorted, 1 unsorted. Finds the minimum number in the unsorted section, and moves it onto the end of the sorted section. Repeats this until list is fully sorted. Is useful when memory is limited