Computational Thinking Elements

Elements of Computational Thinking

• Computer programs use abstractions like variables and objects to represent reality
• Objects hide complexity through encapsulation of internal data and methods

Thinking Ahead

• When planning a system, a computer scientist determines required outputs, necessary inputs, resources, and user expectations
• Strategies such as identifying achievable goals, prerequisites, and possibilities are important

Computer Examples: Caching

• Storing recently used data in cache/RAM for faster future access

Reusable Program Components

• Modular software using objects/functions allows transplanting into new software or sharing through program libraries,
• Modules that are tested are more reliable and reduce development time

Thinking procedurally

• This involves decomposition, dividing large problems into smaller sub-problems
• Eventual sub-problems equate to program modules or groups of modules
• The order of execution needs to be considered in the design phase

Thinking logically

• The steps of a solution need to be considered so the solution provides the right results
• Consider existing information, what is needed, and what is unnecessary

Thinking concurrently

• Modern computers can process multiple instructions simultaneously through multi-core processors and pipelining
• Modules processed at the same time should be independent
• Project planning optimizes processing stages simultaneously to expedite completion

Concurrent Processing

• Concurrent processing is carrying out more than one task at a time, where a program has multiple threads
• Each processor performs simultaneously, with threads overlapping and running independently

Programming Techniques: Sequence

• All instructions are executed once in the order in which they appear in sequence in the function or program

Iteration

• Code loops execute repeatedly until a condition is met or for a set number of times
• WHILE loops are controlled at the entry point, testing the condition before each iteration which repeats while the condition is true

Iteration Loops Details

• WHILE loops are useful when the number of iterations is unknown and may not execute at all if the condition is initially false
• REPEAT UNTIL loops are controlled at the exit point and execute at least once
• FOR loops are controlled by an automatic counter, with a fixed number of iterations based on start/end values and can count in steps other than 1

Selection

• A condition determines sections of code to execute
• In High-Level Languages, selection implemented using IF statements or SELECT CASE statements

IF Statement and SELECT CASE Statement

• IF statements offer two options at a time
• SELECT CASE statements handle multiple choices based on variable values or expressions
• SELECT CASE makes code clearer, more readable, and allows easier addition/branching

Recursion

• is when a function calls itself from within the function
• The original call is halted until subsequent calls return

Recursion Conditions

• Recursion reaches a stopping or base case and can be an alternative to iteration
• Some functions are naturally recursive allowing for quicker writing and fewer lines of code,
• Tail recursion can avoid running out of stack space

Advantages and Disadvantages of Recursion

• Easy to read and implement since its closer to natural language
• Recursion is difficult to debug since each frame on the stack has its own set of variables.
• Requires more memory and resources than iteration and is generally slower

Variable Scope: Global Variable

• A global variable is declared at the start of a program, outside of subprograms
• They are visible throughout the entire program in all modules

Global Variable Usages

• Used where a value needs to be accessible from various parts of the program

Disadvantages of Global Variables

• They make integration difficult, increases program complexity, and may cause name conflicts
• They may also be inadvertently altered when the program is complex and are dangerous due to accidental changes
• Global variables have the same value, irrespective of where it is accessed eg today's date or VAT rate

Variable Scope: Local Variable

• A local variable is declared within a subroutine, accessible only in that program section
• It make functions/procedures reusable and can be used as parameters
• All local variables should have the same name as global variables which will override global values

Execution of Local Variables

• Data contained in a local variable ceases to exist at the end of the subroutine
• Same variable names in different modules will not interfere

Modularity

• Programs are divided into separate, specific modules or tasks that can be further subdivided
• Each individual module focuses on a small sub-task for easier problem-solving, understanding, testing, and debugging

Advantages of Modularity

• Easy updating without affecting the rest of system
• Modular development happens faster since the programming can be split across teams
• Different modules can can be programmed, reduces code needed via reuse of code and standard library routines

Modularity Design

• Modules are allocated according to programmer expertise, and interfaces between modules must be planned with their links tested

Functions and Procedures

• Functions and procedures are types of subroutines or modules
• Function performs a task and returns a value, used within expressions

Function Details

• They are called using their identifier as part of an expression
• The returned value replaces the function call in the main program

Procedures

• Procedure is given an identifier and performs a task without necessarily returning a value
• Receives parameter values for use multiple times with different data and can be called from main programs or other procedures

How Procedures are Ran

• Code is executed when the procedures are called and control is passed back to wherever the procedure was called from
• Procedures behave the same as any other program instruction or statement

Parameters with By Value and By Reference

• Parameters describe data supplied to a subroutine, identified by a name when defined and substituted by an actual value

BY VAL

• A copy is made of the actual value and passed into the procedure
• Changes are made to a local copy so the original values are unaffected
• BY VAL creates a new memory space

BY REF

• An address/pointer/location of the value is passed into the procedure
• Actual value is not sent or received which changes the the data even once the procedure ends
• BY REF uses existing memory

The IDE

• IDE programs are used for developing programs and have many components
• Common IDE features include editing, program building, version control, debugging, testing, and compilation

IDE Tools - Debugging

• Debugging allows inspection of variable values and run-time detection of errors
• Can produce a crash dump showing variable states, and display stack contents

IDE Tools - Translator diagnostics & Breakpoint

• Translator diagnostics suggests solutions and reports on syntax errors and informs the programmer
• Breakpoint is used to test the program works up to specific points or at specified lines code.

IDE Tools - Variable Watch & Stepping

• Variable watch monitors the status of variables and objects as you step through code
• Can halt execution if a condition is met such as a variable changing.

Stepping

• Stepping sets the program up to step through code one statement at a time
• The ability to slows down execution to observe path of execution and changes to variable value

Objects

• Objects are program building blocks that are self-contained
• They are made from data (attributes) and program code (methods) and are based on classes

Computational Methods: Computability

• Computational methods break problems down into sections
• These techniques use stats, new situations, simulations and variables to represent data
• Algorithms are used to test solutions

Computational Methods: Computability

• Solvable problems by computational methods include quantifying issues, input, outputs.
• The problem also involves logical reasoning

Computability: Problem Decomposition

• Splits problems into sub-problems that can be solved and use algorithms to do this
• Allows use of divide and conquer, increases production speed and lets you assign specialities

Problem Decomposition advantages and disadvantages

• Allows use/reuse of pre-existing modules to solve problems modularly
• The program may produce more errors due to these issues and introduce errors
• Reducing processing/memory requirements

Computability: Divide and Conquer

• Can be used within a task in order to split in smaller tasks that are then tackled.

Computability: Abstraction

• The Abstraction technique involves separating ideas from particular instances/reality,

Abstraction - How it works

• It's a representation of reality using symbols to show real-life features
• Involves removing unneeded complexities from the design, detail, elements, features, programming and computational resources which would require unnecessary programming, resources etc..
• Examples of abstraction are variables, data structures, and symbols on a map

Computability: Backtracking

• Strategy for moving systematically towards a solution
• The method involves looking at a progression of finding the problem i.e. try and improve upon it.

Backtracking - Easy to Impliment

• easy to see in some Prolog programs and when traversing a tree
• Backtracking can be used to fix - by saving and trying to fix

Computational Methods: Data Mining

• A process of searching through large or massive sets of data from different databases by using methods like pattern matching and anomaly detection algorithms

Data Mining and its Capabilities

• Data mining can be used to cluster analysis and regression analysis
• No pre-determined conditions may be needed and is possible using brute force algorithms

Examples of how to use Data Mining

• Business applications - modeling, filtering spam - detecting emails habits and purchasing etc...
• Shows relationships between components,facts and events. - It identifies factors of the plan for future events and processing requirement

Computability: Heuristics

• Using “rules of thumb” educated guess approach to arrive at a solution when it's unfeasible

Heuristics Details

• Scans the data to find the likelihood that an issue can be resolved.
• Helpful when the solution provides and are useful when the issue contains undefined areas
• Produces a “Good enough” solution - the results are not 100%

Uses of Heuristics

• Used to prevent malware by finding the structure of the behavior
• Helps speed up the process of the solution finding algorithm like the A*
• Should NOT excessively be used when determining between life and death decisions

Computational Methods: Performance Modeling

• One of many instances of modeling in a computer system
• Used as an example of abstraction that performs in a virtual environment

How to use Performance Modelling

• Should only be used in computer when predicting behaviors - before the action has happened
• Only useful when the action that can come is expensive or dangerous to use

Computability: Pipelining

• Data arranged in series of directing the output of one process into the input of the next
• It is essential that the processes that are processed must happen only in sequential instances

Examples of Pipelining

• Used in queuing operations up to the processor. Graphics and Passing through data between programs, like the | symbol on Unix or Popen() on C

Simultaneous Operations with Pipelining

• Simultaneous procession possible by the processing chips that support it

Visualization

• This makes it so a process' data is easily seen by a human.
• This allows certain patterns and trends to be easily be conveyed to and analyzed by the developer/user.
• This model creates a mental visualisation for the developers.

Algorithm - Complexity

• Measure Time /Memory / resources and increases the amount of data

Big - O Notation

• Represents the average complexity
• Shows high-order component with constants removed

Algorithms: Complexity with Big-O Notation

• Shows limited behavior of algorithm and to classify the worst scenario

Constant Complexity O(1)

• Algorithm stays the same regardless of size of data
• i.e. displays only first letter despite of it being large

Linear Complexity o(n)

• This is where the time taken for an algorithm increases proportionally or at the same rate with the size of the data set.
• Fnding a list in largest number - size has doubled than time taken has doubled

Polynomial Complexity O(nk)

• The time for an algorithm increases proportionally to n to the power of a constant.
• Bubble sort algorithms here

Exponential Complexity O(kn)

• Increases the time exponentially as the dataset increases Like for Travelling Salesman Problem

Logarithmic Complexity O(logn)

• Where the algorithms increase logarithmically with its data
• Increases the data but the time take increase at slower rate with exponential growth
• Scales up well does not increase significantly due to nature of data

Stacks

• The Push method uses the procedure AddToStack
• The Pop method uses DeleteFromStack()

Queues

• The Push method uses AddToQueue
• The Pop method uses DeleteFromQueue()

Trees - Breadth Vs Depth First Algorithms

• Depth works with all Nodes and has been processed can now
• Breadth works through the subnodes first - takes requires more memory but looks depth first

Depth-first (post-order) Tree Traversal

• Go through all Nodes
• Repeat the points for the each node used

Breadth First (pre-order) Tree Traversal

• The main purpose here is to visit all root notes + all subnodes of the tree
• Needs the three points for all the subnode visited

Trees Precautions Required

• Depth First is not guarenteed to return quickest solution - If you have to restart or revisit pervious visited nodes - it then has not been solved

Linked List Data

• Output linked lis tin order
• All steps have been used

LinkedList Code

• All code to determine the steps

LinkedList Data - Search

• Search for the items in the list
• Show all the actions

Bubble Sort

• Intuition easy way to understand. - Useds temp elemnt
• It will then useds / move through all data and list repeatly

Bubble Sort Algorithms

• Start compare 1 list / item and swaps to make true swap
• At the end the Swaps are false the sort has been solved and stopped
• Swap methods shown here

Bubble Short C++ Code

swapMade
= True
WHILE swapMade
==
True
swapMade
=
False
position
=
0
FOR position
=
0 TO length(list)
2
IF items[position] > items[position + 1] THEN
temp
=
items[position]
items[count]
=
items[count + 1]
items[count + 1]
=
temp
swapMade
=
True
ENDIF
NEXT position
ENDWHILE
PRINT(items)
ENDPROCEDURE

Insertion Sort Details

Dividing into list is 2 parts - shorted and also unsorted Elements insert the items by shuffeling them in left

• Ineffecient with large data

Insertion Sort Pseudocode

item
= length(list)
FOR index
= 1 TO item 1
currentvalue
= list[index]
position
= index
WHILE position > 0 AND list[position
list[position]
position
ENDWHILE
= list[position 1]
position 1
list[position]
= currentvalue
NEXT index
ENDPROCEDURE

Merge Sort Details

• Splits the data items into sub-lists of single items. These are then re-merged into two, four and eight, which are lists of single entities.
• Its a recursive list and requires more space + very effective when using sort function on bigger volumes

Merge Sort Algorithm

PROCEDURE MergeSort (listA, listB):
a
= 0
b
= 0
n = 0
WHILE length(listA) > 1 AND length(listB) > 1
IF listA(a) < listB(b) THEN
newlist(n)
= listA(a)
a = a + 1
ELSE
newlist(n)
= listB(b)
b = b + 1
n = n + 1
 - Quick-sort
     ### Quick Sort Algorithims
 - The aim for the algorithm is divide and conqure
 - Select and item that picks up `povit`
 - Then creatse new sub list for large and small
 - the processes are uses as recursivley
### Quick-List Implementation of C++
```C++
QuickSort (list, leftPtr, rightPtr):
leftPtr
=
rightPtr

=
WHILE leftPtr

!=
rightPtr AND leftPtrlist
=
templist[leftPtr]
list[rightPtr]

=
templist[

rightPtr]

Dijkstra Code

• Finds the shortest paths from two set of nodes on a graph
• Keeps track of the shore path as it has used all the start nodes
• It continues until it has completely all destiny notes been found

FUNCTION Dijkstra ():
start node distance from itself
= 0
all other nodes distance from start node
= infinity
WHILE destination node
= unvisited
current node
= closest unvisited node to A 1/1 initially this will be A
itself
distance = distance to current node + distance of edge to unvisited node
IF distance < currently recorded shortest distance THEN
distance
= new shortest distance
NEXT connected node
current node
= visited
ENDWHILE

A* Alogrithms

• Is it the improve of Dijkstra the Algorithms

A* Details and Algorithms

• By used heurstic estimtes to find the shorteth path. + Also the estimtes
• It used both Dijkstra's the short path and start + Estimtes to the endpoints
• the correct option is takes with with the node

A* Pseudocode

FUNCTION AStarSearch ():
start node
= current node

= unvisited
WHILE destination node
FOR each open node directly connected to the current node
Add to the list of open nodes.
distance from the star
 - Recursive Algorithms - The Algorithms have not been 

Requires Order Information - BinarySearch

• The list item uses item on sides to allow for discarded data
• The list data is then searched - List are for is searched and then if its larger of larger it means a new lower.

Advantages of Bianry - No need for processsing but faster

• The fast performace of big data becasue it list and data has been checked + fast

• Processors - it means additonals data has been use by using processings

  Iteration Process of Algorithms

FUNCTION BinaryS (list, value, leftPtr, rightPtr): Found = False IF rightPtr { leftPtr] > value rightPtr = mid

• LinearSearch - There needs no list 1 by 1 as it search from alogithms A The most perfomance happens and list of small searches are to start by list of the alogtihms

  List of Processor - Can hav multi use same types

• Can have mutple process are and is very strong in use for additionals process - The code that can and list to look

Code

• List code implmated her

WHILE Ptr

=

 ### Complex Summary
- the summary shows what type and shows diffucult to find best
- The time data to list to do what types