WEEK 1-4 NOTES

COMPUTATIONAL
THINKING

INDEX
Week - 1
Week - 2
Week - 3
Week - 4
By :- Rushikesh Chavan
WEEK-1

WEEK 1 Page 2 By :- Rushikesh Chavan

 Computational Thinking
Week 1

Flow Charts
What is a Flowchart?
Flowchart is a graphical representation of an algorithm. Programmers often use it
as a program-planning tool to solve a problem. It makes use of symbols which are
connected among them to indicate the flow of information and processing.
The process of drawing a flowchart for an algorithm is known as “flowcharting”.

Basic Symbols used in Flowchart Designs

 Terminal : The oval symbol indicates Start , Stop and Halt in a program ’s logic
flow . A pause /halt is generally used in a program logic under some error
conditions. Terminal is the first and last symbols in the flowchart.

Input/Output: A parallelogram denotes any function of input/output type.

Program instructions that take input from input devices and display output
on output devices are indicated with parallelogram in a flowchart.

Processing: A box represents arithmetic instructions. All arithmetic

processes such as adding, subtracting, multiplication and division are
indicated by action or process symbol.

Computational Thinking 1
 Decision Diamond symbol represents a decision point. Decision based
operations such as yes/no question or true/false are indicated by diamond
in flowchart.

Connectors: Whenever flowchart becomes complex or it spreads over

more than one page, it is useful to use connectors to avoid any confusions.
It is represented by a circle.

Flow lines: Flow lines indicate the exact sequence in which instructions are
executed. Arrows represent the direction of flow of control and relationship
among different symbols of flowchart.

Advantages of Flowchart:

Flowcharts are better way of communicating the logic of system.

Flowcharts act as a guide for blueprint during program designed.

Flowcharts helps in debugging process.

With the help of flowcharts programs can be easily analyzed.

It provides better documentation.

Flowcharts serve as a good proper documentation.

Disadvantages of Flowchart:

It is difficult to draw flowchart for large and complex programs.

In this their is no standard to determine the amount of detail.

Computational Thinking 2
 Difficult to reproduce the flowcharts.

It is very difficult to modify the Flowchart.

Example : Draw a flowchart to input two numbers from user and display the
largest of two numbers

Example:

Sanity of Data
The sanity of data: what we observed
• We organized our data set into cards, each storing one data item
• Each card had a number of elements, e.g.:
• numbers (e.g. marks)
• sequence of characters (e.g. name, bill item, word, etc)
• We observed that there were restrictions on the values each element
can take:
• for example marks has to lie between 0 and 100
• name cannot have funny characters
• Constraints on the kinds of operations that can be performed:
• addition of marks is possible
• but a multiplication of marks does not make sense!

Computational Thinking 3
 • compare one name with another to generate a boolean type True or False)
• but cannot add a name with another!

Data Types
Data types are of 3 kinds

 Charecter - Alpha-Numerics, Special Symbols - We can't perform any

operations on this type of data - Result type - undefinded

 Integers - Numerics range from Minus infinty to plus infinity - operations

+,-,*,/,%, <,> - Result type: Integer or boolean

 Boolean True or False - operations AND, OR - result type Boolean

Subtypes:

Integers:
Dates, Marks, Quantity, Ranks, count

Charecter:

Gender

Strings:

Names, City Words, Catagory

4. Record - Data type with multiple fields - each of which has a name and a
value Struct or Tuple)

Examples of Record:

Marks card , Words in a Paragraph , Shopping bills

List
• A sequence of data elements (for example a sequence of records)
• MarksCardList - is the data type for our data set of all marks cards
• Each element in the sequence is of MarksCard Record data type
• ParagraphWordList - is the data type for our word data set
• Each element in the sequence is of WordInPara Record data type
• ShoppingBillList - data type for the shopping bill data set
• We need to define the Record data type for a shopping bill

Computational Thinking 4
WEEK-2

WEEK 1 Page 2 By :- Rushikesh Chavan

 Computational Thinking
Week 2

To find Max marks

 To Find max marks: Replace initialise with Max=0

 Replace Check for with Maths marks of Card X > max? if

so, update max

To find Maths max marks

 Initialise to MaxCardId=-1

 Replace do something to max = CardX.Maths, maxCardId =

CardX.id

Computational Thinking 1
Computational Thinking 2
Computational Thinking 3
Computational Thinking 4
WEEK-3

WEEK 1 Page 2 By :- Rushikesh Chavan

 Computational Thinking
Week 3
Extraction of data and Creation of tables
1.Data on cards can be naturally represented using tables
2.Each attribute is a column in the table
3.Each card is a row in the table
4.Difficulty if the cards has a variable number of attributes Items in shopping
bill
5.Multiple rows | duplication of data
6.Split as separate tables and need to link via unique attribute
Tables

Procedures
A Procedure is a block of organized, reusable code that is used to perform a
single, related action. Procedure provide better modularity for your application
and a high degree of code reusing.

Example:

To call a Procedure,

Computational Thinking 1
 use the Procedure name followed by parenthesis

 A procedure may not return a value

 Procedure call is a separate statement

 Use a procedure when the same computation is used for

differentsituations

 Parameters fix the context

 Use variables to save values returned by procedures

 Keep track of the outcomes of multiple procedure calls

 Procedures help to modularize pseudocode

 Avoid descibing the same process repeatedly

 If we improve the code in a procedure, benet automatically applies to all

procedure calls

Computational Thinking 2
Computational Thinking 3
Computational Thinking 4
Computational Thinking 5
Computational Thinking 6
WEEK-4

WEEK 1 Page 2 By :- Rushikesh Chavan

 Computational Thinking
Week 4
Binning method is used to smoothing data or to handle noisy data. In this
method, the data is first sorted and then the sorted values are distributed into
a number of buckets or bins. As binning methods consult the neighborhood of
values, they perform local smoothing.

Example

Computational Thinking 1
Computational Thinking 2
Summary of concepts introduced in the course
What is computational thinking?

Expressing problem solutions as a sequence of steps for communication to a computer

Finding common patterns between solutions, apply these patterns to solve new problems

Summary of concepts introduced in the course 2 / 18

What is computational thinking?

Expressing problem solutions as a sequence of steps for communication to a computer

Finding common patterns between solutions, apply these patterns to solve new problems
Data science problems are usually posed on a dataset
which can be obtained from real life artefacts - time tables, shopping bills, transaction logs
... or may be available in a digital format - typically in the form of tables

Summary of concepts introduced in the course 2 / 18

What is computational thinking?

Expressing problem solutions as a sequence of steps for communication to a computer

Finding common patterns between solutions, apply these patterns to solve new problems
Data science problems are usually posed on a dataset
which can be obtained from real life artefacts - time tables, shopping bills, transaction logs
... or may be available in a digital format - typically in the form of tables
Computational thinking in datascience involves finding patterns in methods used to
process these datasets
Through this course, several concepts and methods were introduced for doing this
Typically involves first scanning the dataset to collect relevant information
Then processing this information to find relationships between data elements
Finally organising the relationships in a form that allows questions to be answered easily

Summary of concepts introduced in the course 2 / 18

Iterators and Variables

The most powerful construct to scan the dataset or to process intermediate information is
the iterator.
Whenever some task needs to be done repeatedly, an iterator is required
Iterator needs to be initialised
The steps that need to be repeated need to be made precise
We should know when and how to exit from an iteration, and where to go after the exit

Summary of concepts introduced in the course 3 / 18

Iterators and Variables

The most powerful construct to scan the dataset or to process intermediate information is
the iterator.
Whenever some task needs to be done repeatedly, an iterator is required
Iterator needs to be initialised
The steps that need to be repeated need to be made precise
We should know when and how to exit from an iteration, and where to go after the exit
Variables are storage units used to keep track of intermediate values during the iteration

Summary of concepts introduced in the course 3 / 18

Iterators and Variables

The most powerful construct to scan the dataset or to process intermediate information is
the iterator.
Whenever some task needs to be done repeatedly, an iterator is required
Iterator needs to be initialised
The steps that need to be repeated need to be made precise
We should know when and how to exit from an iteration, and where to go after the exit
Variables are storage units used to keep track of intermediate values during the iteration
Initialisation and updates of variables are done through assignment statements

Summary of concepts introduced in the course 3 / 18

Iterators and Variables

The most powerful construct to scan the dataset or to process intermediate information is
the iterator.
Whenever some task needs to be done repeatedly, an iterator is required
Iterator needs to be initialised
The steps that need to be repeated need to be made precise
We should know when and how to exit from an iteration, and where to go after the exit
Variables are storage units used to keep track of intermediate values during the iteration
Initialisation and updates of variables are done through assignment statements
Variables which assemble a value or a collection are called accumulators

Summary of concepts introduced in the course 3 / 18

Pseudocode and flowchart for processing a dataset

Start

Initialise variables Initialisation: Arrange cards in

Pile 1; keep free space for Pile 2
while (Pile 1 has more cards) {
Pick a card X from Pile 1
Move X to Pile 2 More cards No (False)
End
Update values of variables in Pile 1?

}
Yes (True)
Pick a card X from Pile 1 and and move
it into the Pile 2; Update variables

Summary of concepts introduced in the course 4 / 18

The set of items need to have well defined values

Variables can be of different datatypes

Basic data types: boolean, integer, character and string
Subtypes put more constraints on the values and operations allowed
Lists and Records are two ways of creating bigger bundles of data
In a list all data items typically have the same datatype
Whereas, a record has multiple named fields, each can be of a different datatype
A Dictionary is like a record to which we can add new fields

Summary of concepts introduced in the course 5 / 18

Iteration with Filtering

Filtering allows us to select the relevant data elements for processing and ignore the rest
Requires complex boolean conditions to be defined
We can make compound conditions using boolean connectives - and, or, not
... or we can do condition checking in sequence
... or we can make nested condition checks

Summary of concepts introduced in the course 6 / 18

Iteration with Filtering

Filtering allows us to select the relevant data elements for processing and ignore the rest
Requires complex boolean conditions to be defined
We can make compound conditions using boolean connectives - and, or, not
... or we can do condition checking in sequence
... or we can make nested condition checks
The conditions can work on the (fixed) data elements or on variables:
Compare the item values with a constant - example count, sum. The filtering condition does
not change after each iteration step
compare item values with a variable - example max. The filtering condition changes after an
iteration step

Summary of concepts introduced in the course 6 / 18

Iteration with Filtering

Filtering allows us to select the relevant data elements for processing and ignore the rest
Requires complex boolean conditions to be defined
We can make compound conditions using boolean connectives - and, or, not
... or we can do condition checking in sequence
... or we can make nested condition checks
The conditions can work on the (fixed) data elements or on variables:
Compare the item values with a constant - example count, sum. The filtering condition does
not change after each iteration step
compare item values with a variable - example max. The filtering condition changes after an
iteration step
Using filtering with accumulation, we can assemble a lot of intermediate information
about the dataset

Summary of concepts introduced in the course 6 / 18

Procedures and parameters

Sometimes we have to write the same piece of code again and again with small differences
A piece of pseudocode can be converted into a procedure by separating it out from the
rest of the code
Some variables (or constants) used in this piece of code can be replaced by a parameter,
so that the same procedure can be called with different parameter values to work on
different data elements

Summary of concepts introduced in the course 7 / 18

Procedures and parameters

Sometimes we have to write the same piece of code again and again with small differences
A piece of pseudocode can be converted into a procedure by separating it out from the
rest of the code
Some variables (or constants) used in this piece of code can be replaced by a parameter,
so that the same procedure can be called with different parameter values to work on
different data elements
A procedure can return a value, and the return value can be assigned to a variable. This
makes the code much more compact and easy to read and manage

Summary of concepts introduced in the course 7 / 18

Procedures and parameters

Sometimes we have to write the same piece of code again and again with small differences
A piece of pseudocode can be converted into a procedure by separating it out from the
rest of the code
Some variables (or constants) used in this piece of code can be replaced by a parameter,
so that the same procedure can be called with different parameter values to work on
different data elements
A procedure can return a value, and the return value can be assigned to a variable. This
makes the code much more compact and easy to read and manage
The procedure can have side-effects
it can change the value of variables that are passed as parameters
or those that are made accessible to the procedure, such as the data set elements or lists and
dictionaries created from them
Procedures with side-effects need to be used carefully

Summary of concepts introduced in the course 7 / 18

Multiple iterations

Two iterations can be carried out in sequence or nested

Summary of concepts introduced in the course 8 / 18

Multiple iterations

Two iterations can be carried out in sequence or nested

In a sequential iteration, we make multiple passes through the data, using the result of
one pass during the next pass.
first pass could collect some intermediate information, and the second pass can filter
elements using this information
It establishes a relation between elements with the aggregate
e.g. find all the below average students

Summary of concepts introduced in the course 8 / 18

Multiple iterations

Two iterations can be carried out in sequence or nested

In a sequential iteration, we make multiple passes through the data, using the result of
one pass during the next pass.
first pass could collect some intermediate information, and the second pass can filter
elements using this information
It establishes a relation between elements with the aggregate
e.g. find all the below average students
Nested iterations are used when we want to create a relationship between pairs of data
elements
Nested iterations are costly in terms of number of computations required
We could reduce the number of comparisons by using binning wherever possible
The relationships produced through nested iterations can be stored using lists, dictionaries
(or graphs)

Summary of concepts introduced in the course 8 / 18

Lists

A list is a sequence of values

Write a list as [x1,x2,...,xn], combine lists using ++
[x1,x2] ++ [y1,y2,y3] 7→ [x1,x2,y1,y2,y3]

Extending list l by an item x

l = l ++ [x]

foreach iterates through values in a list

length(l) returns number of elements in l
Functions to extract first and last items of a list
first(l) and rest(l)
last(l) and init(l)
Summary of concepts introduced in the course 9 / 18
Sorted lists

Sorting is an important pre-processing step

Insertion sort is a natural sorting algorithm
Repeatedly insert each item of the original list into a new sorted list
The list can be sorted in ascending or descending order

Sorted lists allow simpler solutions to be found to some problems - example identify the
quartiles for awarding grades

Summary of concepts introduced in the course 10 / 18

Dictionaries

A dictionary stores a collection of Iterate through a dictionary using

key:value pairs keys(d)
Random access — getting the value foreach k in keys(d) {
for any key takes constant time 1 Do something with d[k]
}
Dictionary is sequence
{k1:v1, k2:v2, ..., kn:vn} isKey(d,k) reports whether k is a
key in d
Usually, create an empty dictionary
if isKey(d,k){
and add key-value pairs
1d[k] = d[k] + v
d = {} }
d[k1] = v1 else{
d[k7] = v7 1d[k] = v
}
Summary of concepts introduced in the course 11 / 18
Graphs

Graphs are a useful way to represent relationships

Add an edge from i to j if i is related to j

Summary of concepts introduced in the course 12 / 18

Graphs

Graphs are a useful way to represent relationships

Add an edge from i to j if i is related to j

Use matrices to represent graphs

M[i][j] = 1 — edge from i to j
M[i][j] = 0 — no edge from i to j

Summary of concepts introduced in the course 12 / 18

Graphs

Graphs are a useful way to represent relationships

Add an edge from i to j if i is related to j

Use matrices to represent graphs

M[i][j] = 1 — edge from i to j
M[i][j] = 0 — no edge from i to j

Iterate through matrix to aggregate information from the graph

Graphs are useful to represent connectivity in a network
A path is a sequence of edges
Starting with direct edges, we can iteratively find longer and longer paths

Summary of concepts introduced in the course 12 / 18

Graphs

Graphs are a useful way to represent relationships

Add an edge from i to j if i is related to j

Use matrices to represent graphs

M[i][j] = 1 — edge from i to j
M[i][j] = 0 — no edge from i to j

Iterate through matrix to aggregate information from the graph

Graphs are useful to represent connectivity in a network
A path is a sequence of edges
Starting with direct edges, we can iteratively find longer and longer paths
We can represent extra information in a graph via edge labels - e.g. distance
Iteratively update labels - e.g. compute shortest distance path between each pair of stations
Summary of concepts introduced in the course 12 / 18
Matrices

Matrices are two dimensional tables

Support random access to any element m[i][j]

Summary of concepts introduced in the course 13 / 18

Matrices

Matrices are two dimensional tables

Support random access to any element m[i][j]

We can implement matrices using nested dictionaries

Summary of concepts introduced in the course 13 / 18

Matrices

Matrices are two dimensional tables

Support random access to any element m[i][j]

We can implement matrices using nested dictionaries

Use iterators to process matrices row-wise and column-wise
foreach r in rows(mymatrix)
foreach c in columns(mymatrix)

Summary of concepts introduced in the course 13 / 18

Recursion

Many functions are naturally defined in an inductive manner

Base case and inductive step

Summary of concepts introduced in the course 14 / 18

Recursion

Many functions are naturally defined in an inductive manner

Base case and inductive step

Use recursive procedures to compute such functions

Base case: value is explicitly calculated and returned. Has to be properly defined to ensure
that the recursion terminates
Inductive case: value requires procedure to evaluated on a smaller input
Suspend the current computation till the recursive computation terminates

Summary of concepts introduced in the course 14 / 18

All the best for your exams, and for the rest of the programme !