UNIT 10: Computational Thinking

Question 1

what is computational thinking?

Answer 1

‘the abilyt to think logically about a problem and apply techniques for solving it’

simply working out how to work things out

closely related to the skill of designing algorithms which can be turned into computer programs

Question 1

what is computer science about (no clue)

Answer 1

ts about using mathemical princples to solve problems

its not about how to use a spreadsheet, word or graphics package ephraim

it inovles learning to think computioanlly and applying the pricnpels of abstraction

Question 2

what is abstraction

Answer 2

its a way of separating the logicla and physical aspects of a problem

if you are learning to drive a car, you concentrate on the function of the steering wheel, accelerator, brakes and so on

if u are learning to be a mechanic you will concentrate on how these things actually work

Question 3

thinking abstractly what it involves

Answer 3

involves devising a model that represtns the reality- for example, think of a simple queue or sometjing as complex as a climate change model.

removing details that are not relevant to the problem

Question 4

abstraction and reality (info hiding)

Answer 4

abstraction is an important tool in problem solving

all the details that do not contribute to the essential charactersitcs of the porblem are ommited

the london underground map is a good exmpale of information hiding

Question 5

problem abstraction (what it involves)

Answer 5

involves removing details until the problem reduces to one which has already been solved

(types of recongition software kinda thing)

maps of diffrent places kinda thing

Question 6

modelling and simulation (abstraction)

Answer 6

building a model of a real world object or phenomenon may be used to help solve a particular problem

comp scientists have to decide what details are relevant to the problem and discard everything else

algorthims and data structures can then be designed to solve the problem

algorhtim is then implemented in program code and executed

Question 7

devising an abstract model

Answer 7

at its most abstract evel, a computational problem can be represented by a singl diagram

input - computational problem - output

input is info relevant to the problem, could for example be passed as parameters to a subroutine

output is the solution to the problem which could be passed back from a subroutine

Question 8

thinking ahead

Answer 8

we need to take the inital abstract model and add detail to it until its transformed into a prgram

two major challenges to producing a solution

• algorhtim must be correct, must work for all possible inputs
• algorhithm muse be efficent- often a problem involed huge amounts of data, ahndling of records blah blah - so finding most efficent algrothim is important

Question 9

identifying inputs and ouptus

Answer 9

subprocedure example

name - findmax
inputs - listint(1,2,3,3,45,)
ouptuts - an integer maxINT

advatnage of doucmenting inputs and outputs is that there is no ambiguity in what must be suplied to the subprocudure and what is returned

Question 10

ambiguity! - quote

Answer 10

“i saw a man on a hill with a telescope”

Question 11

specifying preconditions

Answer 11

precondtion - length of listINT > 0

must be fufilled before program works

Question 12

advantages of specifying preconditons

Answer 12

• making program components reusable
• cutting out unecessary checks
  with clear statemnt of preconditons, programmer knows what checks need to be made before calling the subprocedure and which are unnecessary
• making programs easier to debug and maintain

Question 13

resusable program components can be

Answer 13

added to a library and important whenever needed (cool stuff)

Question 14

programming stadnards

Answer 14

if program modules are to be resusable they need to confrom to certain programming stadnards

this will help to make them easy to use for other programmers

Question 15

typical progarmming stadnards for resusable modules

Answer 15

inputs outputs and preconditoins should be documented

variable identifiers should confrom to a stadnared convetion

all variables must be local to the module

doeumnetation should be in stadnard format, explaing what it does, who it was written by, date written

explaninongs / comments

no module should exceed one page of code

Question 16

thinking ahead (predicting)

Answer 16

ancipating what the user wants to do next

Question 17

caching

Answer 17

os systems think ahead using chaching

temporary storage of data and insturctions

last few instuctions of a program to be executed, the result of an earlier computation or data used ma y be stored in memeory so they xan be very quickyl retirved

ie web caching, pages and images and links what not

Question 18

advantages of caching

Answer 18

faster acces to chached rescources

saving on costly use of bandwidth

reduced load on web services in a client server environment

Question 19

disadvantages of caching

Answer 19

slower performance if the resource isnt found in the cache

being given a stale copy of a rescource when an up to date copty is needed

Question 20

thinking procedurally

Answer 20

most problems of any size needs to be broken down into their compopnent parts

• what are the different aspects of this problem?
• is this a computational problem?

Question 21

decompostion

Answer 21

breaking a problem into a number of sub probelms so that each sub problem accomoplishes an identifiable task

the sub problems may themselves be further sub divided

Question 22

structued programming defintion

Answer 22

aims to improve the clarity and quality of a program

method of writing comp programs which uses :

modulrization - for program structe and organistiation, breaking prbolem down into subroutines

structured code for indiuval moduels - uses sequence, selection and iteration

recursion

Question 23

what type of design model is structued programming ?

Answer 23

top down design

divded into subprodcueres or modules which are called from the main program

any of the subprocuedures may be further broken down into smaller subtasks with tthe samllest performing a single function

a HEIRARCHY CHART is often used to show the overall program stuructre

Question 24

heriachy chart

Answer 24

broken down until. no further execution taeks place left to right, lowest level compontnet seleaction and iteration not shown in herhacy chart

Question 25

benefits of modularisation

Answer 25

programs are more easily and quickly written - large programs are broken down - easier to manage and program - each subroutine can be easily tested - modules can be reused several times - freuqntly used modules can be saved in a library and used by other programs - several programmers can simultaneouslly work on different modueles - savin development time - more reliabble an dhave fewer errors - easier to find as they are self contatined - less time to test and debug - easier to maintain - easier to follow - easier to find which moduel needs to be cahnged - chagne doesent affect rest of the program - new features can be added by adding new moduels

Question 26

good programming practice

Answer 26

meangiful identifiers (varaible and procedure naems) define and document i and o and p for each sub procuedure add comments at bottom level each sub procuedure should eprfrom a single task keep each sub procuedure self contaitned by passing parameters and using local varaibles

Question 27

idenfiying components (then you can...)

Answer 27

once idenfiited u can plan overall method of solution involved writing procuedures or functions and passing parameters

Question 28

modular programming is most useful for

Answer 28

large complex programs in small programs less thatn a page of code it may not be wroth writing individual modules for every subtask

Question 29

a good algorithm has..

Answer 29

clear and precisely stated steps that produce the correct output for any set of valid inputs should allow for invalid inputs mkust always terminate at some point should execute efficenty, in as few steps as possible should be designed in such a way that other people will be able to understand it and modify it if necessary

Question 30

3 tools for designing algorithms

Answer 30

hierachy charts - useful for dientifying the major task and breaking these down into subtasks flowcharts.- useful for getting down initial ideas for individual subroutines pseudocode - will trasnalte easily into program code

Question 31

writing decision statements

Answer 31

decision or conditonal statments include IF and CASE statements WHILE FOR AND REPEAT loops also implicitly involve deecisions - boolean condition determines whether contorol will pass back to the beginning of teh loop of continue with the next statement probably the most common cause of logic errors in a program is a mistake in a conditional statement or a loop condition

Question 32

hand tracing (trace table)

Answer 32

useful for figuing out hjow it works and why its not working properly trace table used to write down the contents of each varaible as it changes during execution if the program contains a loop a helpful technique is to put the loop condition as the first column in the trace table even if other varaibles have been defined before it

Question 33

validation routines

Answer 33

to check that a user has entered a value fit for processing can involve tricky Boolean conditions Routines to check that a password is correct also involve several decisions

Question 34

thinking concurrently

Answer 34

(concurrnely means same time) what tasks can be done at the same time

Question 35

concurrent processing

Answer 35

in computing, c p means taht multp[le processors execute instructions simultaneously tasks are broken down into subtasks that cna be assigned to seperate processors to perform simultanusly

Question 36

parallel processing

Answer 36

parallel and concurrent processing are sometijmes used interchangebly most commonly concurettn preocssing implies that a single processor is switching between separate tasks so that all tasks appear to be being processed at the same time the distctiion is sometimes blurred, for example when many processors are working concurrently on a single tasks, such as image processing or performign throusand of celaucaltoiaions to vslcauret eh best move in chess or smth

Question 37

dual core and quad core processors

Answer 37

many personal computers and mobile devices have 2,3 or more CPU's or cores OS allocates sperate tasks to differetn CPUs

Question 38

examples of concurrent processing on mobile devices include;

Answer 38

video editing image processing facial recognition 2d stereo games and apps virus scans

Question 39

pattern recognition

Answer 39

used in edical diagnosis, speed camera, detecting a dagnrously overcrowded platform on an undergroudn railway

Question 40

non computable problems

Answer 40

face recognition or fluing an airliner across the atlantic with no human intervention may once have seemed non computable but are now routinely solved however alub turing proved in 1936 that some problems are non computable computer science is somtimes defined as the study of problems that are and are not computable

Question 41

methods of problem solving

Answer 41

trial and error enumeration - list all cases simulation theoriretcal approach creative solution

Question 42

simulation problems

Answer 42

process fo designing a model of a real system in order to understand the behaviour of the system and to evaulate various strategies for its operation fincical risk anayliss amunsement park rides population preditctions managing inventory systems queueing problems

Question 43

enumeration

Answer 43

every possible output anagram solver thingy

Question 44

strats for algorithm design - divide and conquer

Answer 44

very efficetn involves finding a solution to a sequence of smaller realted problems until the instance is small enough to be solved directly

Question 45

divide and conquer is the pricniple of what search?

Answer 45

binary search

Question 46

the euclidian algorithm

Answer 46

GCD algotithm 2000 years ago by euclid desinged to find the greatest common divsor of two numbers

Question 47

exhaustive search

Answer 47

tests every possible way

Question 48

backtracking

Answer 48

you go some way along one route then backtrack to see if there is a better route

Question 49

herusitc methods

Answer 49

herustic meanining - enabling someone to discover or learn something for themselves. include rules of thumb, educated guesses, intutive judgements or common sense find a method that is good enough even though it might not be optimal

Question 50

an intractable problem - TSP

Answer 50

travelling salesman problem cannot be solved problem is to find the shortest route which visits every city and returns to the start

Question 51

data mining

Answer 51

process of collecting and then analysing huge amounts of data

Question 52

applications of data mining

Answer 52

increaing response rates to marketing campaings by being able to target them more accuraetly to the needs of each customer anticipating resouce demands detecting fraud and cybersecutiy issues finding oncnnceitons between seemingly unconnected events

Question 53

big data

Answer 53

often used in conn with data mining impleies that huge amounts of data are collected and stored defined by 3 major features, kown as the 3Vs - VOLUME VARIETY AND VELOCITY parallel compuying, on which agothim tasks are exectuted concurrently on a cluster of machines of super comuters is fundamental to managing big data tasks

Question 54

performance modellnign

Answer 54

how efficent is your algothm? one measure of effiecny is the Big O notation measures the suitability of algorithms in terms of execution time and space you can time different algorithms using built in timer functions

Question 55

pipeling

Answer 55

implementation thecnique where multiple instructins are overlapped in execution instruction enter the pipeline at one end and at each stage part of the instruction is completeed and moves to the next stage while another instruction enters teh pipeline rather like an assembly line