12 CS Gu ide R.M.K.MATRIC.HR.SEC.

SCHOOL - 601206

Namma Kalvi
UNIT
CHAPTER 1 FUNCTION
I
www.nammakalvi.in
1.What is a subroutine? 6. Which of the following is a normal function
 Subroutines are small sections of code. definition and which is recursive function definition
 Used to perform a particular task that can be used i) let rec sum x y:
repeatedly. return x + y
 In Programming languages subroutines are called as ii) let disp :
Functions print ‘welcome’
2. Define function with respect to programming iii) let rec sum num:
language. if (num!=0) then return num + sum (num-1)
 In Programming languages subroutines are called as else
Functions return num
 A function contains a set of code that works on i. Recursive function
many kinds of inputs, like variants, expressions and ii. Normal function
produces a concrete output. iii. Recursive function
3. Write the inference you get from X:=(78). 7.Mention the characteristics of Interface
 X:= (78) has an expression in it but (78) is not  The class template specifies the interfaces to enable
itself an expression. an object to be created and operated properly.
 (78) is a function definition.  An object's attributes and behaviour is controlled by
 Definitions bind values to names, sending functions to the object.
Here ,the value 78 being bound to the name ‘X’.
 Definitions are not expressions, Definitions can 8. Why strlen is called pure function?
have expressions nested inside them.  Strlen() is a pure function
4. Differentiate between interface and  because the function takes one variable as a
implementation. parameter, and accesses it to find its length.
Explain with an example interface and implementation  This function reads external memory but does
Interface not change it,
 An interface is a set of action that an object can do 9. What is the side effect of impure function. Give
 In object oriented programs classes are the example.
interface
Implementation  The variables used inside the function may cause
 Implementation carries out the instructions defined side effects though the functions which are not
in the interface passed with any arguments.
 How the object is processed and executed is the  When a function depends on variables or
implementation. functions outside of its definition block,
Ex. For example
let min 3 x y z := let Random number
if x < y then let a := random()
if x < z then x else z if a > 10 then
else if y < z then y else z return: a
In the above example , else
 Implementation of a function that finds the return: 10
minimum of its three arguments: Here the function Random is impure as it is not sure
5.What is recursive function? what will be the result when we call the function.
 A function definition which call itself is called
recursive function

Elangovan 9677515019 Page 1

 12 CS Gu ide R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

www.nammakalvi.in
10. Differentiate pure and impure function. (ii) Parameter with Type
Here , data types are mentioned with parameter in
Pure Function Impure Function function definition.
Pure functions are Impure functions are Ex . let rec pow (a: int) (b: int) : int :=
functions which will functions which will not if b=0 then 1
give exact result when give exact result when else a * pow b (a-1)
the same arguments the same arguments
are called. Ex. sin(0) are called Ex. date()
Explicitly annotating the types can help with debugging
The return value The return value does such an error message.
depends on its not depend on its 13.Explain with example Pure and impure functions
arguments passed. arguments passed.
Pure Function
same return values. different return values  Pure functions are functions which will give exact
They do not have They have side effects. result when the same arguments are called. Ex.
any side effects. sin(0)
They do not modify They may modify  The return value depends on its arguments passed.
the arguments which the arguments which
 same return values.
are passed to them are passed to them
 They do not have any side effects.
 They do not modify the arguments which are
11. What happens if you modify a variable outside the passed to them
function? Give an example. Example
One of the most popular groups of side effects is  Strlen() is a pure function
modifying the variable outside of function.
 because the function takes one variable as a
For example
parameter, and accesses it to find its length.
let y: = 0
(int) inc (int) x  This function reads external memory but does
y: = y + x; not change it,
return (y) Impure Function
 In the above example the value of y get changed  Impure functions are functions which will not give
inside the function definition. exact result when the same arguments are called
 Due to which the result will change each time. Ex. date()
 The side effect of the inc () function is to changing  The return value does not depend on its
the data of the external visible variable ‘y’. arguments passed.
 Different return values
12.What are called Parameters and write a note on  They have side effects.
(i) Parameter without Type (ii) Parameter with Type  They may modify the arguments which are passed
Define Parameters (and) arguments. to them
 Parameters are the variables in a function 14. Identify in the following program
definition. let rec gcd a b :=
 Arguments are the values which are passed to a if b <> 0 then gcd b (a mod b)
function definition. else return a
(i) Parameter without Type i) Name of the function Ans: gcd
Here , data types are not mentioned with parameter in ii) Identify the statement which tells it is a recursive
function definition. function Ans : let rec gcd
Ex. let rec pow a b:= iii) Name of the argument variable Ans: a , b
if b=0 then 1 iv) Statement which invoke the function recursively
else a * pow a (b-1) Ans: gcd b (a mod b)
Some language compiler solves this type (data type) v) Statement which terminates the recursion
problem algorithmically, but some require the type to Ans: return a
be mentioned.
www.nammakalvi.in

Elangovan 9677515019 Page 2

 12 CS Gu ide R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

Namma Kalvi
UNIT
CHAPTER 2 DATA ABSTRACTION
I
www.nammakalvi.in
1.Define abstraction. 6. What is a List? Give an example.
 The process of providing only the essentials and  List is constructed by placing expressions within
hiding the details is known as abstraction. square brackets separated by commas.
2. What is abstract data type?  In a list elements can be changed.
 The process of providing only the essentials and  List can store multiple values.
hiding the details is known as abstraction. Ex. lis[10,12]
 Abstract Data type (ADT) is a type for objects
whose behavior is defined by a set of value and a 7.Differentiate Concrete data type and abstract
set of operations. datatype.
 The definition of ADT only mentions what Concrete data type Abstract data type.
operations are to be performed but not how these
The data representation The data representation is
operations will be implemented.
is known unknown
3. Differentiate constructors and selectors.
Concrete data types or Abstract Data Types
Constructors
structures (CDT's) are (ADT's) offer a high level
 Constructors are functions that build the abstract
direct implementations view (and use) of a
data type.
of a relatively simple concept independent of
 Constructors create an object, bundling together concept. its implementation
different pieces of information,
Ex. city = makecity (name, lat, lon) ---- Constructors
Selectors 8. Which strategy is used for program designing?
 Selectors are functions that retrieve information Define that Strategy.
from the data type.  A powerful strategy for designing programs: 'wishful
 selectors extract individual pieces of information thinking'.
from the object.  Wishful Thinking is the formation of beliefs and
getname(city) making decisions according to what might be
getlat(city) -------- Selectors
pleasing to imagine instead of by appealing to
getlon(city) reality.
9. Identify Which of the following are constructors and
4. What is a Pair? Give an example. selectors? (a) N1=number() (b) accetnum(n1)
 Any way of bundling two values together into one (c) displaynum(n1) (d) eval(a/b)
can be considered as a pair. (e) x,y= makeslope (m), makeslope(n) (f) display()
 Pair is a compound structure which is made up of a) Constructors
list or Tuple b) Selector
 Therefore List can be called as Pairs. c) Selector
Ex. d) Constructors
 lst[(0, 10), (1, 20)] e) Constructors
here ,(1, 20) (0, 10) - are pairs f) Selector

5. What is a Tuple? Give an example.

 A tuple is a comma-separated sequence of values
surrounded with parentheses ( ).
 Tuple is similar to a list.
 In a tuple elements cannot be changed
 Ex. : colour= ('red', 'blue', 'Green')

Elangovan 9677515019 Page 1

 12 CS Gu ide www.nammakalvi.in R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

10. What are the different ways to access the elements 12.Write an ADT for rational numbers
of a list. Give example. - constructor
 List is constructed by placing expressions within - - constructs a rational number with numerator n,
square brackets separated by commas. denominator d
 In a list elements can be changed. rational(n, d)
 List can store multiple values. - - selector
The elements of a list can be accessed in two ways. numer(x) → returns the numerator of rational number x
1. Multiple assignment denom(y) → returns the denominator of rational
lst := [10, 20] number y.
x, y := lst ; here x will become 10 and y is 20 13.How to Representation of Tuple as a Pair
2. Element selection operator Example 1
 Accessing the elements in a list is by the element lst[(0, 10), (1, 20)] - where
selection operator, also expressed using square
brackets
Ex.
lst[0]
10 Example 2
nums := (1, 2)
lst[1]
nums[0]
20 1
Method III nums[1]
Represent list similar to a set. 2
1.) lst[(0, 10), (1, 20)] - where 14.How will you facilitate data abstraction. Explain it
with suitable example
 The process of providing only the essentials and
hiding the details is known as abstraction.
To facilitate data abstraction, you will need to create
 Any way of bundling two values together into two types of functions: constructors and selectors.
one can be considered as a pair. Constructors
 Lists are a common method to do so.  Constructors are functions that build the abstract
Therefore List can be called as Pairs. data type.
 Constructors create an object, bundling together
11. Identify Which of the following are List, Tuple and different pieces of information,
class ? For example,
(a) arr [1, 2, 34] (b) arr (1, 2, 34)  you have an abstract data type called city.
(c) student [rno, name, mark]  This city object will hold the city’s name, and its
(d) day= (‘sun’, ‘mon’, ‘tue’, ‘wed’) latitude and longitude.
(e) x= [2, 5, 6.5, [5, 6], 8.2]  To create a city object, you’d use a function like
(f) employee [eno, ename, esal, eaddress] city = makecity (name, lat, lon) ----- -- Constructors
Selectors
 Selectors are functions that retrieve information
a) List b) Tuple c) Class d) Tuple e) List f) Class
from the data type.
 selectors extract individual pieces of information
from the object.
To extract the information of a city object, you would
use functions like

getname(city)
getlat(city) ------- Selectors
getlon(city)

Elangovan 9677515019 Page 2

 12 CS Gu ide R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

15.What is a List? Why List can be called as Pairs.

Explain with example person=['Padmashri', 'Baskar', '994-222-1234',
 List is constructed by placing expressions within 'compsci@gmail.com']
square brackets separated by commas.  Instead of using a list, you can use the structure
 In a list elements can be changed. construct (In OOP languages it's called class
 List does not allow to name the various parts of a construct) to represent multi-item objects.
multi-item object Consider the following pseudo code:
 List can store multiple values. class Person:
The elements of a list can be accessed in two ways. creation( )
1. Multiple assignment firstName := " "
lst := [10, 20] lastName := " "
x, y := lst ; here x will become 10 and y is 20 id := " "
Method II email := " "
 Accessing the elements in a list is by the element
selection operator, also expressed using square The new data type Person is pictorially represented
brackets as
Ex. Let main() contains
lst[0] p1:=Person() .
10 firstName := " Padmashri "
lastName :="Baskar
lst[1]
id :="994-222-1234"
20 email="compsci@gmail.com"
Method III
Here, Person is referred to as a class or a type,
Represent list similar to a set. while p1 is referred to as an object or an instance.
1.) lst[(0, 10), (1, 20)] - where
 class Person as a cookie cutter, and p1 as a
particular cookie.
 Using the cookie cutter you can make many cookies.
Same way using class you can create many objects
 Any way of bundling two values together into
of that type.
one can be considered as a pair.
 Lists are a common method to do so.
 Therefore List can be called as Pairs.

16.How will you access the multi-item. Explain with

example.
 lists do not allow us to do is name the various
parts of a multi- item object.
For example , www.nammakalvi.in
 A person, we have a multi- item object where
each 'item' is a named thing:
 the firstName, the lastName, the id, and the email.
 One could use a list to represent a person:

Person - class name with multi - item

creation ( ) - function
first Name -
last Name - Variables
id -
email -

Elangovan 9677515019 Page 3

 12 CS Gu ide R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

Namma Kalvi
UNIT CHAPTER 3 SCOPING
I www.nammakalvi.in
Local(L) scope
1.What is a scope?  Local scope refers to variables defined in current
 Scope refers to the visibility of variables, function.
parameters and functions in one part of a  Always, a function will first look up for a variable
program to another part of the same program. name in its local scope.
2.Why scope should be used for variable.State the  Only if it does not find it there, the outer scopes are
reason. checked.
 Normally, every variable defined in a program For example
has global scope.
 Once defined, every part of your program can
access that variable.
3.What is Mapping?
 The process of binding a variable name with an
In output, the variable a displays the value 7, because it
object is called mapping.
 = (equal to sign) is used in programming languages is defined and available in the local scope
to map the variable and object. Global(G) Scope
4.What is meant by namespaces?  A variable which is declared outside of all the
 Namespaces are containers for mapping names functions in a program is known as global variable.
of variables to objects.  This means, global variable can be accessed inside
 Programming languages keeps track of all or outside of all the functions in a program.
mappings with namespaces. For example
5.What is the life time of variable?
 The duration for which a variable is alive is called its
‘life time’.
6.Define LEGB rule
 The LEGB rule is used to decide the order in which In output, the variable a displays the value 7 for the
the scopes are to be searched for scope resolution. function call Disp() and then it displays 10, because a is
 The scopes are listed below in terms of hierarchy defined in global scope.
(highest to lowest). Enclosed(E) scope
 A variable which is declared inside a function,
Local(L) Defined inside function/class  which contains another function definition with in
it, the inner function can also access the variable of
the outer function.
Enclosed(E) Defined inside enclosing functions
(Nested function concept)  This scope is called enclosed scope.
When a compiler or interpreter search for a variable in
a program,
Global(G) Defined at the uppermost level
 It first search Local, and then search Enclosing
scopes. Consider the following example
Built-in (B) Reserved names in built-in
functions (modules)

7.Explain the Types of Variable Scope

There are 4 types of Variable Scope, They are  In the above example Disp1() is defined with in
Local(L) , Enclosed(E), Global(G), Built-in (B) Disp().

Elangovan 9677515019 Page 1

 12 CS Gu ide R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

 The variable ‘a’ defined in Disp() can be even used  The code is stored across multiple files.
by Disp1() because it is also a member of Disp().  Code is short, simple and easy to understand.
Built-in(B) Scope  Errors can easily be identified, as they are localized
 The built-in scope has all the names that are pre- to a subroutine or function.
loaded into the program scope when we start the  The same code can be used in many applications.
compiler or interpreter.  The scoping of variables can easily be controlled.
 Any variable or module which is defined in the
library functions of a programming language has 12.What is Access control? Why access control is
Built-in or module scope. required?
 They are loaded as soon as the library files are  Access control is a security technique that regulates
imported to the program. who or what can view or use resources in a
computing environment.
 It is a fundamental concept in security that
minimizes risk to the object.

13.What are the three access modifiers?

Private,Protected ,public are the access modifier
8.Define Module.
 Public members are accessible from outside the
 A module is a part of a program. class.
 Programs are composed of one or more  Protected members of a class are accessible from
independently developed modules. within the class and are also available to its sub-
 A single module can contain one or several classes
statements closely related each other  Private members of a class are access only from
9.What is Modular programming? Uses and types. within the class not the outside of the class.
 The process of subdividing a computer program into
separate sub-programs is called Modular 14.Identify the scope of the variables in the following
programming pseudo code and write its
 The examples of modules are procedures, output
subroutines, and functions color:= Red
mycolor():
10.What are the Characteristics of Modules? b:=Blue
 Modules contain instructions, processing logic, and myfavcolor():
data. g:=Green
 Modules can be separately compiled and stored in a printcolor, b, g
library. myfavcolor()
 Modules can be included in a program. printcolor, b
 Module segments can be used by invoking a name mycolor()
and some parameters. print color
 Module segments can be used by other modules.
Scope of the variables:
11.What are the benefits of using modular Variable Scope
programming include? color:= Red Global
 Less code to be written. b:=Blue Enclosed
 A single procedure can be developed for reuse, g:=Green Local
eliminating the need to retype the code many
times.
 Programs can be designed more easily because a
small team deals with only a small part of the entire www.nammakalvi.in
code.
 Modular programming allows many programmers
to collaborate on the same application.

Elangovan 9677515019 Page 2

 12 CS Gu ide R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

Namma Kalvi
UNIT CHAPTER 4 ALGORITHMIC STRATEGIES
I ALGORITHMIC STRATEGIES
www.nammakalvi.in

1. What is an Algorithm? 5.Design an algorithm to find square of the given

 An algorithm is a finite set of instructions to number and display the result
accomplish a particular task. Step 1 – start
 It is a step-by-step procedure for solving a given Step 2 – get the input x
problem. Step 3 –calculate the square by multiplying the input
 An algorithm can be implemented in any suitable value ie., square ← x* x
programming language. Step 4 − display the result square
2.What is algorithmic strategy? Step 5 − stop
 The way of defining an algorithm is called
algorithmic strategy. 6.What is an algorithmic solution?
3.What are the Characteristics of an Algorithm  An algorithm that yields expected output for a
Input : valid input is called an algorithmic solution.
 Zero or more values to be supplied. 7.Differentiate between Algorithm and Program
Output:
 At least one value is produced. Algorithm
Finiteness :  Algorithm helps to solve a given problem logically
 Algorithms must terminate after finite number of and it can be contrasted with the program
steps.  Algorithm can be categorized based on their
Definiteness: implementation methods, design techniques etc
 All operations should be well defined.  Algorithm can be implemented by structured or
Effectiveness: object oriented programming approach
 Every instruction must be carried out effectively.  There is no specific rules for algorithm writing but
Correctness: some guidelines should be followed.
 The algorithms should be error free.  Algorithm resembles a pseudo code which can be
Simplicity : implemented in any language
 Easy to implement.
Unambiguous : Program
 Each of its steps and their inputs/outputs should be  Program is an expression of algorithm in a
clear and unambiguous must lead to only one programming language
meaning.  Program should be written for the selected
Feasibility: language with specific syntax
 Should be feasible with the available resources.  Program should be written for the selected
Portable: language with specific syntax
 An algorithm should be able to handle all range of  Program is more specific to a programming
inputs. language
Independent:
 An algorithm should be independent of any 8.Draw picture to show the process of an algorithm.
programming code
4.Who is an Algorist?
 One who practices algorism is known as algorist.
 A person skilled in the design of algorithms an
algorithmic artist.

Elangovan 9677515019 Page 1

 12 CS Gu ide www.nammakalvi.in R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

9.What is an algorithm analysis? 15.What is Space-Time tradeoff

 An estimation of the time and space complexities of  A space-time or time-memory tradeoff is a way of
an algorithm for varying input sizes is called solving in less time by using more storage space
algorithm analysis
10.What are the phases in analysis of algorithms? 16.Write a short note on Asymptotic Notations.
1. A Priori estimates: Asymptotic Notations are languages that uses
 This is a theoretical performance analysis of an meaningful statements about time and space
algorithm. complexity.
 Efficiency of an algorithm is measured.
2. A Posteriori testing: There are three asymptotic notations,
 This is called performance measurement.
 Running time required for the algorithm (i) Big O
executions are measured. Big O is used to describe the worst-case of an
11.What is Complexity of an Algorithm? algorithm.
 The complexity of an algorithm gives the running (ii) Big Ω
time and/or the storage space required by the  Big Omega is the reverse Big O,
algorithm .  Big Omega is used to describe the lower bound.
(best-case).
12.Name the two factors , which decide the efficiency (iii) Big Θ
of an algorithm.  When an algorithm has a complexity with lower
1. Time factor 2. Space factor bound = upper bound,
 An algorithm has a complexity O (n log n) and
13.What are the factors that influence time and space Ω (n log n), it’s actually has the complexity
complexity. Θ (n log n),
The two main factors are , 17.What are the techniques used in algorithm for
 Time Factor -Time is measured by counting the searching?
number of key operations like comparisons in the Explain the Linear search techniques in algorithm for
sorting algorithm. searching.
 Space Factor - Space is measured by the 1.Linear search
maximum memory space required by the  Linear search also called sequential search
algorithm.  It is a sequential method for finding a particular
value in a unordered list.
14.Explain the Complexity of an algorithm.  This method checks the search element with each
element in sequence until the desired element is
Time Complexity found.
 The Time complexity of an algorithm is given by the Pseudo code
number of steps taken by the algorithm to 1. In the array using for loop
complete the process. 2. In every iteration, compare the target search key
Space Complexity value with the current value of the list.
 Space complexity of an algorithm is the amount  If the values match, display the current index and
of memory required to run to its completion. value of the array
 The space required by an algorithm is equal to  If the values do not match, move on to the next
the sum of Fixed and Variable part array element.
 A fixed part is defined as the total space required 3.If no match is found, display not found.
to store certain data and variables for an Example
algorithm. Input: values[] ={13,31,28,11,2}
 A variable part is defined as the total space Target = 28
required by variables, which is in loop. Output:2

Elangovan 9677515019 Page 2

 12 CS Gu ide www.nammakalvi.in R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

18.Explain the Binary search techniques in algorithm mid = low + (high - low) / 2
for searching. =5+(9 – 5)/2 = 7 new mid is 7
The element stored at 7 is not match with search
2.Binary Search element
 Binary search also called half-interval search Current mid value is 7
algorithm. Now search element is less than the middle element.
 It finds the position of a search element within a So take left element
sorted array. Now mid value is 6
 The binary search algorithm can be done as
divide-and-conquer search algorithm and
executes in logarithmic time.
Pseudo code for Binary search
Calculate mid again
 Start with the middle element:
high = mid – 1 = 6 – 1 = 5 current low value = 5
 If the search element = middle element of the
mid = low + (high - low)/2 = 5 +(5 – 5) /2 = 5
array , then return the index of the middle
new mid is 5
element.
Now we compare the value stored at location 5 with
If not, then compare
our search element. We found that it is a match.
if search element > middle element , if TRUE
19.Explain the Bubble sort algorithm with example.
 select the elements to the right side of the
 The algorithm starts at the beginning of the list of
middle index, and go to Step-1.
values stored in an array.
Otherwise
 It compares each pair of adjacent elements and
 select the elements to the left side of the
swaps them if they are in the unsorted order.
middle index, and start with Step-1.
 This comparison and passed to be continued until
 When a match is found, display FOUND message.
no swaps are needed, which indicates that the list
 If no match is found for all comparisons, then of values in an array is sorted.
display NOT FOUND message. Pseudo code
Binary Search Working principles  Start with the first element i.e., index = 0,
 compare the current element with the next
List of elements in an array must be sorted first .
element of the array.
For example,
 If the current element is greater than the next
Consider the following array of elements;
element of the array, swap them.
 If the current element is less than the next
element, move to the next element.
Search element is 60  Go to Step 1 and repeat until end of the index is
First, find index of middle element by using formula: reached.
mid = low + (high - low) / 2 For example, Let's consider an array with values
mid =0+(9 – 0) / 2 = 4 {15, 11, 16, 12, 14, 13}

Now compare search element = middle element

Index 4 is 50 ,so it is not match
Search value is greater than 50

Now we change our low to mid + 1 and find the new

mid value .
low= 4+1 = 5
Elangovan 9677515019 Page 3
 12 CS Gu ide R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

At the end of all the iterations we will get the sorted 21.Explain the Insertion sort algorithm with example.
values in an array as given below:  It works by taking elements from the list one by
one and inserting then in their correct position in
to a new sorted list.
Pseudo code
20.Explain the Selection sort algorithm with example.  If it is the first element, it is already sorted.
 Pick next element
 This algorithm will first find the smallest elements  Compare with all elements in the sorted sub-list
in array and swap it with the element in the first  Shift all the elements in the sorted sub-list that is
position of an array, greater than the value to be sorted
 then it will find the second smallest element and  Insert the value
swap that element with the element in the second  Repeat until list is sorted
position,
 and it will continue until the entire array is sorted
in respective order.

Pseudo code

 Start from the first element i.e., index-0,

 Find the smallest element in the array, and replace
it with the element in the first position.

 Then find the second smallest element and swap

that element with the element in the second
position

 This is repeated, until the array is completely

sorted. 22.Write a short note on Dynamic programming.
For example  Dynamic programming approach is similar to divide
and conquer.
 The given problem is divided into smaller and yet
smaller possible sub-problems.
Steps to do Dynamic programming

 The given problem will be divided into smaller

overlapping sub-problems.
 An optimum solution for the given problem can be
achieved by using result of smaller sub-problem.
 Dynamic algorithms uses Memoization.
Example
Fibonacci Iterative Algorithm with Dynamic
 In the first pass, the smallest element will be 11, so programming approach
it will be placed at the first position.
Initialize f0=0, f1 =1
 After that, next smallest element will be searched
step-1: Print the initial values of Fibonacci f0 and f1
from an array. Now we will get 13 as the smallest, step-2: Calculate fibanocci fib ← f0 + f1
so it will be then placed at the second position. step-3: Assign f0← f1, f1← fib
 keep doing this until array is sorted. step-4: Print the next consecutive value of fibanocci fib
step-5: Goto step-2 and repeat until the specified
number of terms generated.

Elangovan 9677515019 Page 4

 12 CS Gu ide www.nammakalvi.in R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

For example a) Overlapping sub-problems b) Optimal substructure

if we generate fibobnacci series upto 10 digits, the c) Memorization d) Greedy
algorithm will generate the series as shown below: 10. In dynamic programming, the technique of
storing the previously calculated values is called ?
The Fibonacci series is : 0 1 1 2 3 5 8 13 21 34 55 a) Saving value property b) Storing value property
23.Define Memoization c) Memorization d) Mapping
 Memoization or memoisation is an optimization 11. A(n) ____ is a finite set of instructions to accomplish
technique used primarily to speed up computer a particular task.
programs by storing the results of expensive a. Algorithm b. Flow chart c. Walkthrough d. None
function calls and returning the cached result when 12. ____ is a step-by-step procedure for solving a given
the same inputs occur again. problem.
24.What are the various data manipulations? a. Algorithm b. Flow chart c. Walkthrough d. None
Data manipulations are 13. ____ are maintained and manipulated effectively
 Searching through data structures.
 Sorting a. Algorithm b. Data c. Program d. None of these
 Inserting 14. ____ is an example for data structure.
 Updating a. arrays b. structures / list
 Deleting an item. c. tuple / dictionary d. All the above
15. The way of defining an algorithm is called ____
strategy.
a. problem solving b. solution c. algorithmic d. None
CHOOSE THE BEST ANSWER 16. The word ____ has come to refer to a method to
solve a problem.
1. The word comes from the name of a Persian a. Algorithm b. Flow chart c. Solution d. None
mathematician Abu Ja’far 17. Identify the correct statement from the following:
Mohammed ibn-I Musa al Khowarizmi is called? a. Algorithms are generic and not limited to computer
a) Flowchart b) Flow c) Algorithm d) Syntax alone b. An algorithm can be implemented in any
2. From the following sorting algorithms which suitable programming language.
algorithm needs the minimum number of swaps? c. Algorithm cannot be used in various real time
a) Bubble sort b) Quick sort c) Merge sort d) activities. d. Both a and b
Selection sort 18. A program can be implemented by ____
3. Two main measures for the efficiency of an algorithm programming approach.
are a) Processor and memory b) Complexity and a. Structured b. Object Oriented c. Both A and B d.
capacity c) Time and space d) Data and space None of these
4. The complexity of linear search algorithm is 19. Efficiency of an algorithm is defined by the
a) O(n) b) O(log n) c) O(n2) d) O(n log n) utilization of ____ complexity. a. Time and Space b.
5. From the following sorting algorithms which has Time c. Space d. None of these
the lowest worst case complexity? 20. ____ is a theoretical performance analysis of an
a) Bubble sort b) Quick sort c) Merge sort d) algorithm.
Selection sort a. Priori estimate b. Posteriori testing
6. Which of the following is not a stable sorting c. Both A and B d. None of these
algorithm? 21. ____ is called performance measurement.
a) Insertion sort b) Selection sort c) Bubble sort d) a. Priori estimate b. Posteriori testing
Merge sort c. Both A and B d. None of these
7. Time complexity of bubble sort in best case is 22. In ____ analysis, actual statistics like running
a) θ (n) b) θ (n log n) c) θ (n2) d) θ (n(log n)2) time and required for the algorithm executions are
8. The Θ notation in asymptotic evaluation represents collected. a. Priori estimate b. Posteriori testing
a) Base case b) Average case c) Worst case d) NULL c. Both A and B d. None of these
case 23. ____ factor is measured by counting the
9. If a problem can be broken into sub-problems which number of key operations like comparisons in the
are reused several times, the problem possesses which sorting algorithm.
property? a. Time b. Space c. Both A and B d. None of these

Elangovan 9677515019 Page 5

 12 CS Gu ide R.M.K.MATRIC.HR.SEC.SCHOOL - 601206

24. ____ is measured by the maximum memory space 38. ____ search is a sequential method for finding a
required by the algorithm. particular value in a list.
a. Time b. Space c. Both A and B d. None of these a. Linear b. Sequential c. Binary d. Either A or B
25. Identify the correct statement from the following: 39. In ____ searching algorithm, list need not be
a. The efficiency of an algorithm is defined as the ordered.
number of computational resources used by the a. Linear b. Sequential c. Binary d. Either A or B
algorithm. 40. ____ search also called half-interval search
b. A variable part is defined as the total space required algorithm.
by variables, which sizes depends on the problem and a. Linear b. Sequential c. Binary d. Either A or B
its iteration. 41. The ____ search algorithm can be done as divide-
c. A fixed part is defined as the total space and-conquer search algorithm.
required to store certain data and variables for an a. Linear b. Sequential c. Binary d. None of these
algorithm. d. All the above 42. The ____ search algorithm executes in logarithmic
26. The execution time of an algorithm depends on time.
factor. a. Speed of the machine b. Compiler and other a. Binary b. Sequential c. Linear d. All of these
system Software tools c. Operating System d. All the 43. List of elements in an array must be sorted first for
above ____ search.
27. The execution time of an algorithm depends on a. Linear b. Sequential c. Binary d. Unary
factor. a. Programming language used b. Volume of 44. ____ sort is a simple sorting algorithm.
data required c. Speed of the machine d. All a. Bubble b. Merge c. Insertion d. Selection
28. ____ trade off refers to a situation where we can 45. ____ sort algorithm is too slow and less efficient
reduce the use of memory at the cost of slower when compared other sorting methods.
program execution a. Bubble b. Merge c. Insertion d. Selection
a. Time b. Space c. Cost d. None of these 46. ____ sort algorithm works by taking elements
29. ____ trade off refers to a situation where we can from the list one by one and inserting then in their
reduce the running time at the cost of increased correct position in to a new sorted list.
memory usage. a. Bubble b. Merge c. Insertion d. Selection
a. Time b. Space c. Cost d. None of these 47. ____ algorithm uses n-1 number of passes to get
30. The best algorithm to solve a given problem is one the final sorted list.
that ____ a. requires less space in memory b. takes a. Bubble b. Merge c. Insertion d. Selection
less time to execute its instructions 48. Dynamic programming approach is similar to ____
c. Both A and B d. None of these a. Divide and Conquer b. Integration
31. How many asymptotic notations are mostly used to c. Merging d. None of these
represent time complexity of algorithms? 49. ____ programming is used whenever problems
a. Five b. Four c. Three d. Two can be divided into similar sub-problems.
32. ____ is an asymptotic notation used to represent a. Static b. Dynamic c. Concrete d. None of these
time complexity of algorithm. 50. Dynamic algorithms uses ____ technique.
a. Big O b. Big Ω c. Big Θ d. All the above a. Memorization b. Memorize c. Memory d. None
33. ____ is often used to describe the worst-case of an 51. ____ sort algorithm compares each pair of adjacent
algorithm. elements and swaps them if they are in the unsorted
a. Big O b. Big Ω c. Big Θ d. All the above order. a. Bubble b. Merge c. Insertion d. Selection
34. ____ is used to describe the best-case of an
algorithm.
a. Big O b. Big Ω c. Big Θ d. All the above
35. ____ is used to describe lower bound of an
asymptotic function. www.nammakalvi.in
a. Big O b. Big Ω c. Big Θ d. All the above
36. ____ is used to describe upper bound of an
asymptotic function.
a. Big O b. Big Ω c. Big Θ d. All the above
37. Linear search also called ____ search.
a. Binary b. Sequential c. Random d. quick

Elangovan 9677515019 Page 6