Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

UNIT 1

COMPUTATIONAL THINKING AND PROBLEM SOLVING
Fundamentals of Computing – Identification of Computational Problems Algorithms, building blocks of algorithms (statements, state, control flow,
functions),

notation

(pseudo

code,

flow

chart,

programming language), algorithmic problem solving, simple strategies for
developing algorithms (iteration, recursion)
...


PROBLEM SOLVING
Problem solving is the systematic approach to define the problem and creating
number of solutions
...


PROBLEM SOLVING TECHNIQUES
Problem solving technique is a set of techniques that helps in providing logic
for solving a problem
...

Algorithms
...

Flowcharts
...

Pseudo codes
...

programs

ALGORITHM
It is defined as a sequence of instructions that describe a method for solving a
problem
...


Properties of Algorithms
v Should be written in simple English

v
v
v
v
v

Each and every instruction should be precise and unambiguous
...

Algorithm should conclude after a finite number of steps
...


Qualities of a good algorithm
The following are the primary factors that are often used to judge the quality
of the algorithms
...
The lesser is the time required, the better is the algorithm
...
The lesser is the memory required, the better is the algorithm
...

Example
Write an algorithm to print „Good Morning”
Step 1: Start
Step 2: Print “Good Morning”
Step 3: Stop

ALGORITHM
It is defined as a sequence of instructions that describe a method for solving a
problem
...


Properties of Algorithms
v Should be written in simple English
v Each and every instruction should be precise and unambiguous
...

v Algorithm should conclude after a finite number of steps
...


Qualities of a good algorithm
The following are the primary factors that are often used to judge the quality
of the algorithms
...
The lesser is the time required, the better is the algorithm
...
The lesser is the memory required, the better is the algorithm
...

Example
Write an algorithm to print „Good Morning”
Step 1: Start
Step 2: Print “Good Morning”
Step 3: Stop

BUILDING BLOCKS OF ALGORITHMS (statements, state,
control flow, functions)
Algorithms can be constructed from basic building blocks namely, sequence,
selection and iteration
...

In a computer statements might include some of the following actions
Ø input data-information given to the program
Ø process data-perform operation on a given input
Ø output data-processed result

State:
Transition from one process to another process under specified condition with
in a time is called state
...

The control can be executed in three ways
1
...

selection
3
...

Example:
Add two numbers:
Step 1: Start
Step 2: get a,b
Step 3: calculate c=a+b
Step 4: Display c
Step 5: Stop

Selection:
A selection statement causes the program control to be transferred to a specific
part of the program based upon the condition
...


Example
Write an algorithm to check whether he is eligible to vote?
Step 1: Start
Step 2: Get age
Step 3: if age >= 18 print “Eligible to vote”

Step 4: else print “Not eligible to vote”
Step 6: Stop

Iteration:
In some programs, certain set of statements are executed again and again based
upon conditional test
...
e
...
This type of execution
is called looping or iteration
...

Step 3: initialize i=1
Step 4: if (i<=n) go to step 5 else go to step 7
Step 5: Print i value and increment i value by 1
Step 6: go to step 4
Step 7: Stop

Functions:
v Function is a sub program which consists of block of code(set of instructions)
that performs a particular task
...


Benefits of Using Functions
v
v
v
v
v
v

Reduction in line of code
code reuse
Better readability
Information hiding
Easy to debug and test
Improved maintainability

Example:

Algorithm for addition of two numbers using function
Main function()
Step 1: Start
Step 2: Call the function add()
Step 3: Stop
sub function add()
Step 1: Function start
Step 2: Get a, b Values
Step 3: add c=a+b
Step 4: Print c
Step 5: Return

NOTATIONS
FLOW CHART
Flow chart is defined as graphical representation of the logic for problem
solving
...


Rules for drawing a flowchart
1
...

3
...

The flowchart must have a logical start and finish
...


4
...
However, two or three
flow lines may leave the decision symbol
...
Only one flow line is used with a terminal symbol
...
Within standard symbols, write briefly and precisely
...
Intersection of flow lines should be avoided
...

Communication: - Flowcharts are better way of communicating the logic
of a system to all concerned
...

Effective analysis: - With the help of flowchart, problem can be analyzed
in more effective way
...

Proper documentation: - Program flowcharts serve as a good
program documentation, which is needed for various purposes
...

Efficient Coding: - The flowcharts act as a guide or blueprint during the
systems analysis and program development phase
...

Proper Debugging: - The flowchart helps in debugging process
...

Efficient Program Maintenance: - The maintenance of operating
program becomes easy with the help of flowchart
...


Disadvantages of flow chart:
1
...
In
that case, flowchart becomes complex and clumsy
...

Alterations and Modifications: - If alterations are required the flowchart
may require re-drawing completely
...

Reproduction: - As the flowchart symbols cannot be typed, reproduction
of flowchart becomes a problem
...

Cost: For large application the time and cost of flowchart drawing
becomes costly
...

v It does not include details like variable declaration, subroutines
...

v It gives us the sketch of the program before actual coding
...

v There is no standard syntax for pseudo code
...

1
...

2
...

3
...

4
...
5
...

6
...

7
...

8
...

9
...


Syntax for if else:
IF (condition)THEN
statement

...

ENDIF

Example: Greates of two numbers
BEGIN
READ a,b
IF (a>b) THEN
DISPLAY a is greater
ELSE
DISPLAY b is greater
END IF
END

Syntax for For:
FOR( start-value to end-value) DO
statement

...

ENDWHILE
Example: Print n natural numbers
BEGIN
GET n
INITIALIZE i=1
WHILE(i<=n) DO
PRINT i

i=i+1
ENDWHILE
END

Advantages:
v Pseudo is independent of any language; it can be used by most
programmers
...

v It can be easily modified as compared to flowchart
...


Disadvantages:
v It does not provide visual representation of the program’s logic
...

v It cannot be compiled nor executed
...

Example:
Addition of two numbers:
BEGIN
GET a,b
ADD c=a+b
PRINT c
END

PROGRAMMING LANGUAGE
A programming language is a set of symbols and rules for instructing a
computer to perform specific tasks
...
The user
has to communicate with the computer using language which it can
understand
...

2
...


Machine language
Assembly language
High level language

Machine language:
The computer can understand only machine language which uses 0’s and 1’s
...


Advantages:
Translation free:
Machine language is the only language which the computer understands
...
The program written in machine language

can be executed directly on computer
...

High speed
The machine language program is translation free
...


Disadvantage:
Ø It is hard to find errors in a program written in the machine language
...

Machine dependent: According to architecture used, the computer differs
from each other
...
So
a program developed for a particular type of computer may not run on other
type of computer
...

Ø Assembly language is symbolic representation of machine language
...
They are called low level
language because they are so closely related to the machines
...

Ø Easy to understand and use
...


Disadvantage
Machine dependent

The assembly language program which can be executed on the machine
depends on the architecture of that computer
...

Less efficient
Ø Execution time of assembly language program is more than machine
language program
...


High level language
High level language contains English words and symbols
...
The
interpreter or compilers are used for converting these programs in to machine
readable form
...


Compiler:
A compiler is a program which translates the source code written in a high
level language in to object code which is in machine language program
...
If any error is found it display error message
on the screen
...

The interpreter translates a high level language statement in a source program
to a machine code and executes it immediately before translating the next

statement
...


Advantages
Readability
High level language is closer to natural language so they are easier to learn and
understand
Machine independent
High level language program have the advantage of being portable between
machines
...
Programs
in high level language require more memory and take more execution time to
execute
...

2
...

4
...

6
...

8
...
The interpreter executes the

program directly translating each statement into a sequence of one or more
subroutines already compiled into machine code
...
They focus on the programming languages are
bound to mathematical calculations
Examples:
Clean
Haskell

Compiled Programming language:
A compiled programming is a programming language whose implementation
are typically compilers and not interpreters
...

Examples:
C
C++
C#
JAVA

Procedural programming language:
Procedural (imperative) programming implies specifying the steps that the
programs should take to reach to an intended state
...
Procedures help in the reuse of code
...

Examples:
Hyper talk
MATLAB

Scripting language:
Scripting language are programming languages that control an application
...
They are mostly
embedded in the application that they control and are used to automate
frequently executed tasks like communicating with external program
...

Examples:
HTML
XML

Concurrent programming language:
Concurrent programming is a computer programming technique that
provides for the execution of operation concurrently, either with in a single
computer or across a number of systems
...

Examples:

Lava
Moto

FLOW CHART
Flow chart is defined as graphical representation of the logic for problem
solving
...


Rules for drawing a flowchart
1
...

3
...

The flowchart must have a logical start and finish
...


4
...
However, two or three
flow lines may leave the decision symbol
...
Only one flow line is used with a terminal symbol
...
Within standard symbols, write briefly and precisely
...
Intersection of flow lines should be avoided
...

Communication: - Flowcharts are better way of communicating the logic
of a system to all concerned
...

Effective analysis: - With the help of flowchart, problem can be analyzed
in more effective way
...

Proper documentation: - Program flowcharts serve as a good
program documentation, which is needed for various purposes
...

Efficient Coding: - The flowcharts act as a guide or blueprint during the
systems analysis and program development phase
...

Proper Debugging: - The flowchart helps in debugging process
...

Efficient Program Maintenance: - The maintenance of operating
program becomes easy with the help of flowchart
...


Disadvantages of flow chart:
1
...
In
that case, flowchart becomes complex and clumsy
...

Alterations and Modifications: - If alterations are required the flowchart
may require re-drawing completely
...

Reproduction: - As the flowchart symbols cannot be typed, reproduction
of flowchart becomes a problem
...

Cost: For large application the time and cost of flowchart drawing
becomes costly
...

v It does not include details like variable declaration, subroutines
...

v It gives us the sketch of the program before actual coding
...

v There is no standard syntax for pseudo code
...

1
...

2
...

3
...

4
...
5
...

6
...

7
...

8
...

9
...


Syntax for if else:

IF (condition)THEN
statement

...

ENDIF

Example: Greates of two numbers
BEGIN
READ a,b
IF (a>b) THEN
DISPLAY a is greater
ELSE
DISPLAY b is greater
END IF
END

Syntax for For:
FOR( start-value to end-value) DO
statement

...


ENDWHILE

Example: Print n natural numbers
BEGIN
GET n
INITIALIZE i=1
WHILE(i<=n) DO
PRINT i
i=i+1
ENDWHILE
END

Advantages:
v Pseudo is independent of any language; it can be used by most
programmers
...

v It can be easily modified as compared to flowchart
...


Disadvantages:
v It does not provide visual representation of the program’s logic
...

v It cannot be compiled nor executed
...

Example:

Addition of two numbers:
BEGIN
GET a,b

ADD c=a+b
PRINT c
END

PROGRAMMING LANGUAGE
A programming language is a set of symbols and rules for instructing a
computer to perform specific tasks
...
The user
has to communicate with the computer using language which it can
understand
...

2
...


Machine language
Assembly language
High level language

Machine language:
The computer can understand only machine language which uses 0’s and 1’s
...


Advantages:
Translation free:
Machine language is the only language which the computer understands
...
The program written in machine language

can be executed directly on computer
...

High speed
The machine language program is translation free
...


Disadvantage:
Ø It is hard to find errors in a program written in the machine language
...

Machine dependent: According to architecture used, the computer differs
from each other
...
So
a program developed for a particular type of computer may not run on other
type of computer
...

Ø Assembly language is symbolic representation of machine language
...
They are called low level
language because they are so closely related to the machines
...

Ø Easy to understand and use
...


Disadvantage
Machine dependent

The assembly language program which can be executed on the machine
depends on the architecture of that computer
...

Less efficient
Ø Execution time of assembly language program is more than machine
language program
...


High level language
High level language contains English words and symbols
...
The
interpreter or compilers are used for converting these programs in to machine
readable form
...

Compiler:
A compiler is a program which translates the source code written in a high
level language in to object code which is in machine language program
...
If any error is found it display error message
on the screen
...

The interpreter translates a high level language statement in a source program
to a machine code and executes it immediately before translating the next
statement
...


Advantages
Readability
High level language is closer to natural language so they are easier to learn and
understand
Machine independent
High level language program have the advantage of being portable between
machines
...
Programs
in high level language require more memory and take more execution time to
execute
...

2
...

4
...

6
...

8
...
The interpreter executes the
program directly translating each statement into a sequence of one or more
subroutines already compiled into machine code
...
They focus on the programming languages are
bound to mathematical calculations
Examples:
Clean
Haskell

Compiled Programming language:
A compiled programming is a programming language whose implementation
are typically compilers and not interpreters
...

Examples:
C
C++
C#
JAVA

Procedural programming language:
Procedural (imperative) programming implies specifying the steps that the
programs should take to reach to an intended state
...
Procedures help in the reuse of code
...

Examples:
Hyper talk
MATLAB

Scripting language:
Scripting language are programming languages that control an application
...
They are mostly
embedded in the application that they control and are used to automate
frequently executed tasks like communicating with external program
...

Examples:
HTML
XML

Concurrent programming language:
Concurrent programming is a computer programming technique that
provides for the execution of operation concurrently, either with in a single
computer or across a number of systems
...

Examples:
Lava
Moto

ALGORITHMIC PROBLEM SOLVING:
Algorithmic problem solving is solving problem that require the formulation
of an algorithm for the solution
...

v It is very important to specify exactly the set of inputs the algorithm needs
to handle
...
Ascertaining the Capabilities of the
Computational Device
v If the instructions are executed one after another, it is called sequential
algorithm
...


Choosing between Exact and Approximate Problem Solving
v The next principal decision is to choose between solving the problem exactly
or solving it approximately
...


Deciding a data structure:
v Data structure plays a vital role in designing and analysis the algorithms
...


Algorithm Design Techniques
v An algorithm design technique (or “strategy” or “paradigm”) is a general
approach to solving problems algorithmically that is applicable to a variety of
problems from different areas of computing
...

v First, they provide guidance for designing algorithms for new problems,
v Second, algorithms are the cornerstone of computer science

Methods of Specifying an Algorithm
v Pseudocode is a mixture of a natural language and programming languagelike constructs
...

v In the earlier days of computing, the dominant vehicle for specifying
algorithms was a flowchart, a method of expressing an algorithm by a
collection of connected geometric shapes containing descriptions of the
algorithm’s steps
...

Instead, it needs to be converted into a computer program written in a
particular computer language
...


Proving an Algorithm’s Correctness
v Once an algorithm has been specified, you have to prove its correctness
...

v A common technique for proving correctness is to use mathematical
induction because an algorithm’s iterations provide a natural sequence of steps
needed for such proofs
...
But in order to show
that an algorithm is incorrect, you need just one instance of its input for which
the algorithm fails
...
Efficiency
...

2
...

v An algorithm should be precisely defined and investigated with
mathematical expressions
...

v Simple algorithms usually contain fewer bugs
...
Programming an algorithm presents both a peril and an
opportunity
...
Such an analysis is based on
timing the program on several inputs and then analysing the results obtained
...

2
...
Iterations:
A sequence of statements is executed until a specified condition is true is called
iterations
...

for loop
2
...

ENDFOR
Example: Print n natural numbers
BEGIN
GET n
INITIALIZE i=1
FOR (i<=n) DO
PRINT i
i=i+1
ENDFOR
END
Syntax for While:
WHILE (condition) DO
Statement

...

v Recursion is a process by which a function calls itself repeatedly until some
specified condition has been satisfied
...
14*r*r
Step 4: Calculate C=2
...
14*r
Step 5: Display A,C
Step 6: Stop

BEGIN
READ r
CALCULATE A and C
A=3
...
14*r
DISPLAY A
END

Write an algorithm for Calculating simple interest

Step 1: Start
Step 2: get P, n, r value
Step3:Calculate
SI=(p*n*r)/100
Step 4: Display S
Step 5: Stop

BEGIN
READ P, n, r
CALCULATE S
SI=(p*n*r)/100
DISPLAY SI
END

Write an algorithm for Calculating engineering cutoff

Step 1: Start
Step2: get P,C,M value
Step3:calculate
Cutoff= (P/4+C/4+M/2)
Step 4: Display Cutoff
Step 5: Stop

BEGIN
READ P,C,M
CALCULATE
Cutoff= (P/4+C/4+M/2)
DISPLAY Cutoff
END

To check greatest of two numbers
Step 1: Start
Step 2: get a,b value
Step 3: check if(a>b) print a is greater
Step 4: else b is greater
Step 5: Stop

BEGIN
READ a,b
IF (a>b) THEN
DISPLAY a is greater
ELSE
DISPLAY b is greater
END IF
END

To check leap year or not
Step 1: Start
Step 2: get y
Step 3: if(y%4==0) print leap year
Step 4: else print not leap year
Step 5: Stop

BEGIN
READ y
IF (y%4==0) THEN

DISPLAY leap year
ELSE
DISPLAY not leap year
END IF
END

To check positive or negative number
Step 1: Start
Step 2: get num
Step 3: check if(num>0) print a is positive
Step 4: else num is negative
Step 5: Stop

BEGIN
READ num
IF (num>0) THEN
DISPLAY num is positive
ELSE
DISPLAY num is negative
END IF
END

To check odd or even number
Step 1: Start
Step 2: get num
Step 3: check if(num%2==0) print num is even
Step 4: else num is odd

Step 5: Stop

BEGIN
READ num
IF (num%2==0) THEN
DISPLAY num is even
ELSE
DISPLAY num is odd
END IF
END

To check greatest of three numbers
Step1: Start
Step2: Get A, B, C
Step3: if(A>B) goto Step4 else goto step5
Step4: If(A>C) print A else print C
Step5: If(B>C) print B else print C
Step6: Stop

BEGIN
READ a, b, c
IF (a>b) THEN
IF(a>c) THEN
DISPLAY a is greater
ELSE
DISPLAY c is greater
END IF
ELSE
IF(b>c) THEN
DISPLAY b is greater
ELSE
DISPLAY c is greater
END IF
END IF
END

Write an algorithm to check whether given number is +ve, -ve or
zero
...

Step 3: if (n ==0) print “Given number is Zero” Else goto step4
Step 4: if (n > 0) then Print “Given number is +ve”

Step 5: else Print “Given number is -ve”
Step 6: Stop

BEGIN
GET n
IF(n==0) THEN
DISPLAY “ n is zero”
ELSE
IF(n>0) THEN
DISPLAY “n is positive”
ELSE
DISPLAY “n is positive”
END IF
END IF
END

Write an algorithm to print all natural numbers up to n
Step 1: Start
Step 2: get n value
...
14*r*r
Step 4: Calculate C=2
...
14*r
Step 5: Display A,C
Step 6: Stop

BEGIN
READ r
CALCULATE A and C
A=3
...
14*r
DISPLAY A
END

Write an algorithm for Calculating simple interest

Step 1: Start
Step 2: get P, n, r value
Step3:Calculate
SI=(p*n*r)/100
Step 4: Display S
Step 5: Stop

BEGIN
READ P, n, r
CALCULATE S
SI=(p*n*r)/100
DISPLAY SI
END

Write an algorithm for Calculating engineering cutoff

Step 1: Start
Step2: get P,C,M value
Step3:calculate
Cutoff= (P/4+C/4+M/2)
Step 4: Display Cutoff
Step 5: Stop

BEGIN
READ P,C,M
CALCULATE
Cutoff= (P/4+C/4+M/2)
DISPLAY Cutoff
END

To check greatest of two numbers
Step 1: Start
Step 2: get a,b value
Step 3: check if(a>b) print a is greater
Step 4: else b is greater
Step 5: Stop

BEGIN
READ a,b
IF (a>b) THEN
DISPLAY a is greater
ELSE
DISPLAY b is greater
END IF
END

To check leap year or not
Step 1: Start
Step 2: get y
Step 3: if(y%4==0) print leap year
Step 4: else print not leap year
Step 5: Stop

BEGIN
READ y
IF (y%4==0) THEN
DISPLAY leap year
ELSE
DISPLAY not leap year
END IF
END

To check positive or negative number
Step 1: Start

Step 2: get num
Step 3: check if(num>0) print a is positive
Step 4: else num is negative
Step 5: Stop

BEGIN
READ num
IF (num>0) THEN
DISPLAY num is positive
ELSE
DISPLAY num is negative
END IF
END

To check odd or even number
Step 1: Start
Step 2: get num
Step 3: check if(num%2==0) print num is even
Step 4: else num is odd
Step 5: Stop

BEGIN
READ num
IF (num%2==0) THEN
DISPLAY num is even
ELSE
DISPLAY num is odd
END IF
END

To check greatest of three numbers
Step1: Start
Step2: Get A, B, C
Step3: if(A>B) goto Step4 else goto step5
Step4: If(A>C) print A else print C
Step5: If(B>C) print B else print C
Step6: Stop

BEGIN
READ a, b, c
IF (a>b) THEN
IF(a>c) THEN
DISPLAY a is greater
ELSE
DISPLAY c is greater
END IF
ELSE
IF(b>c) THEN
DISPLAY b is greater
ELSE
DISPLAY c is greater
END IF
END IF
END

Write an algorithm to check whether given number is +ve, -ve or
zero
...

Step 3: if (n ==0) print “Given number is Zero” Else goto step4
Step 4: if (n > 0) then Print “Given number is +ve”
Step 5: else Print “Given number is -ve”

Step 6: Stop

BEGIN
GET n
IF(n==0) THEN
DISPLAY “ n is zero”
ELSE
IF(n>0) THEN
DISPLAY “n is positive”
ELSE
DISPLAY “n is positive”
END IF
END IF
END

Write an algorithm to print all natural numbers up to n
Step 1: Start
Step 2: get n value
...
14*r*r
c=2*3
...
24
the circumference of circle
25
...
0

Calculate engineering cutoff
p=eval(input(“enter physics marks”))
c=eval(input(“enter chemistry marks”))
m=eval(input(“enter maths marks”))
cutoff=(p/4+c/4+m/2)
print(“cutoff =”,cutoff)
Output
enter physics marks 100
enter chemistry marks 99
enter maths marks 96
cutoff = 97
...
0

convert the temperature
def ctof():
c=eval(input("enter temperature in centigrade"))
f=(1
...
8
print("the temperature in centigrade is",c)
ctof()
ftoc()
Output
enter temperature in
centigrade 37
the temperature in
Fahrenheit is 98
...
77

program for basic calculator
def add():
a=eval(input("enter a value"))
b=eval(input("enter b value"))
c=a+b
print("the sum is",c)
def sub():
a=eval(input("enter a value"))
b=eval(input("enter b value"))
c=a-b
print("the diff is",c)
def mul():
a=eval(input("enter a value"))
b=eval(input("enter b value"))
c=a*b
print("the mul is",c)
def div():
a=eval(input("enter a value"))
b=eval(input("enter b value"))
c=a/b
print("the div is",c)
add()
sub()
mul()

div()
Output
enter a value 10
enter b value 10
the sum is 20
enter a value 10
enter b value 10
the diff is 0
enter a value 10
enter b value 10
the mul is 100
enter a value 10
enter b value 10
the div is 1



---