Suggestion on Algorithm for Diploma in Computer Science & Technology,

Semester 3rd under West Bengal State Council of Technical Education.

Chapter-1# Fundamentals of Algorithm.

**Q-1. Define Algorithm. Write the Characteristics/Properties/features of an Algorithm?

Solution:
Algorithm: An Algorithm is nothing but a step-by-step process for solving a particular
problem where a set of finite logical instructions carried out in a sequential order to
accomplish some computational operations.
Characteristics/Properties/features of an Algorithm:
An Algorithm belongs to the following characteristics-
1. Input: An Algorithm requires some input values to execute a particular
computational task. Thus an algorithm can be given one/more well defined
value(s), other than 0 (no value) as input.
2. Output: The algorithm must clearly define what output will be yielded and it
should be well defined as well. It should produce at least one output.
3. Finiteness: An algorithm must be finite in nature. Finiteness in this context means
that the algorithm belongs to a set of finite logical instructions that are countable
step-by-step.
4. Unambiguity: A perfect algorithm is defined as unambiguous which means that all
the algorithmic instructions should be meaningful, transparent and
straightforward.
5. Effectiveness: Algorithm must be simple, generic and practical such that it can be
executed with the available resources to generate the desired result(s).
6. Language Independent: An algorithm must be language independent. It means
that an algorithm can be implemented in any programming language and capable
produce the same result(s) as output.
*Q-2. Explain an algorithm with a suitable example?
Solution:
Example of an Algorithm:
An Algorithm designing technique to find out the greatest number among three
integers.

STEP-1: Start
STEP-2: Declare three integer variables x, y and z;
STEP-3: if x>y and x>z print x is the greatest.
STEP-4: else if y>x and y>z print y is the greatest.
STEP-5: else print z is the greatest.
 STEP-6: Stop.
*Q-3. What is Flow Chart? Write the Significance/Benefit/Advantage of Flow
Chart?
Solution:
Flow Chart: A flowchart is a type of diagram that represents a workflow or process. A
flowchart can also be defined as a diagrammatic representation of an algorithm, a step-
by-step approach to solving a task.
Significance/Benefit/Advantage of Flow Chart:

1. Effective Communication: Flowcharts are better way of communicating the logic

of the program.
2. Effective Analysis: Using flowchart problem can be analysed more efficiently.
3. Easy Debugging and Efficient Testing: It helps in debugging and testing process.
4. Efficient Coding: It is very useful during program development phase.
5. Proper Documentation: Flowcharts serves as a good program documentation,
which is needed for various purpose.

**Q-4. Describe about the different standard flow chart symbols?

Solution:
Q-5. Describe an algorithm of a program using flow chart.
Solution:
An Algorithm designing technique to find out the greatest number among three integers.
Q-6. What is data abstraction? Write the Characteristics/Properties/features of
data abstraction?
Solution:
Data Abstraction: Data abstraction is a principle of data modeling theory that emphasizes
the method of hiding the details information about the internal implementation
strategies over the data from the user, but it only provides the functionalities of the data.
Characteristics/Properties/features of data abstraction:
1. Abstraction is the method of hiding the internal details of the unwanted
information from the end user.
2. It can be implemented using abstract classes and interfaces.
3. Data abstraction is useful to solve an issue at the design level.
4. In data abstraction, implementation complexities are hidden using abstract
classes and interfaces.
5. It only focuses on the external lookout of the data used in a program.
***Q-7. Write the significance/advantages and disadvantages of data abstraction?
Solution:
Significance/Advantages:
1. Data abstraction allows users to focus on the basic functionalities of the data
without having to understand its complex operations.
2. Data abstraction makes things simpler as well as easier to change, implement and
document.
 3. It is very useful for simplify the design, optimization and indexing and ultimately
increase the maintainability of the solution.
Disadvantages:
1. Data abstraction offers complexity at many levels of the database that might
create confusion for developers.
2. The navigation becomes extremely difficult when an extra layer is added to the
code.

Q-8. Write a short note on data abstraction?

Solution:
See Answer of the question 6 & 7.

Q-9. Define Set. Write the Characteristics/Properties/features of Set?

Solution:
Set: Sets are associative containers that store unique elements following a specific
order.

Characteristics/Properties/features of Set:
 Stores the values in sorted order.
 Stores only unique values. It means that in Set duplicate values are not allowed to get
stored.
 Elements can only be inserted or deleted but cannot be modified.
 We can erase more than 1 element by giving the start iterator and end iterator
position.
 Traversal using iterations.
 Sets are implemented as Binary Search Tree.

Q-10. Define Multi-set. Write the Characteristics/Properties/features of Multi-set?

Solution:
Multi-set: Multi-sets are associative containers that store multiple elements having
equivalent values following a specific order.

Characteristics/Properties/features of Multi-set:
 Stores elements in sorted order.
 It allows the storage of multiple elements. It means that in Multi-set duplicate values
are allowed to get stored.
 We can erase more than 1 element by giving the start iterator and end iterator.
Q-11. What is Stack? Write the Characteristics/Properties/features of Stack?
Solution:
Stack: stack can be defined as a container in which data insertion and data deletion
operations can be done from the one end known as the top of the stack.

Characteristics/Properties/features of Stack:
1. Stack is a linear type data structure and abstract data type in nature.

2. It contains only one pointer called top pointer which is used for pointing to the
topmost element of the stack.

3. Whenever an element is added in the stack, it is added on the top of the stack and
the element can be deleted only from the top of the stack.
4. Stack follows the LIFO (Last In First Out) of FILO (First In Last Out) working
principle to insert and delete the elements.
5. It is called as stack because it behaves like a real-world stack, piles of books, etc.
6. A Stack is an abstract data type with a pre-defined capacity, which means that it
can store the elements of a limited size.

Q-12 Write the Significance/Advantages and Disadvantages of Stack?

Solution:
Significance/Advantages of Stack:

1. Efficient data management: Stack helps you manage the data in a LIFO (last in, first
out) method, which is not possible with a Linked list and array.
2. Efficient management of functions: When a function is called, the local variables are
stored in a stack, and it is automatically destroyed once returned.
3. Control over memory: Stack allows you to control how memory is allocated and de-
allocated.
4. Smart memory management: Stack automatically cleans up the object.
5. Not easily corrupted: Stack does not get corrupted easily; hence it is more secure
and reliable

Disadvantages of Stack:

1. Limited memory size: Stack memory is very limited.

2. Chances of stack overflow: Creating too many objects on the stack can increase the
risk of stack overflow.
3. Random access is not possible: In a stack, random accessing the data is not possible.
4. Unreliable: When variable storage will get overwritten, it will sometimes leads to
undefined behaviour of the function or program.
 5. Undesired termination: The stack will fall outside of the memory area, which might
lead to an abnormal termination.

***Q-13. Write a short note on Stack.

Solution:

See the Answer of the question 11 & 12.

***Q-14. Write the simple working principles of Stack?

(Or) Explain the data insertion and deletion operation over Stack with a suitable
example?

Solution:

Insertion of data elements in Stack:

Insertion of data elements in a Stack is manipulated by PUSH() function. The steps

involved in the PUSH operation is given below:

o Before inserting an element in a stack, we check whether the stack is full.

o If we try to insert the element in a stack, and the stack is full, then
the overflow condition occurs.
o When we initialize a stack, we set the value of top as -1 to check that the stack is
empty.
o When the new element is pushed in a stack, first, the value of the top gets
incremented, i.e., top=top+1, and the element will be placed at the new position
of the top.
o The elements will be inserted until we reach the max size of the stack.
Deletion of data elements in Stack:

Deletion of data elements in a Stack is manipulated by POP() function. The steps involved
in the POP operation is given below:

o Before deleting the element from the stack, we check whether the stack is empty.
o If we try to delete the element from the empty stack, then
the underflow condition occurs.
o If the stack is not empty, we first access the element which is pointed by the top
o Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.
Q-15. What is Queue? Write the Characteristics/Properties/features of Queue?
Solution:
Queue: A Queue can be defined as a container in which data insertion and data deletion
operations can be done from the rear and front end of the queue respectively.
Characteristics/Properties/features of Queue
1. Queue is a linear type data structure and abstract data type in nature.

2. It contains two ends, one end is called Rear and another end is called Front.

3. The insertion and deletion operation on an element for the Queue should be
done from the Rear and Front end of the Queue respectively.
4. Queue follows the FIFO (First In First Out) or LILO (Last In Last Out) working
principle to insert and delete the elements.
5. A Queue is an abstract data type with a pre-defined capacity, which means that it
can store the elements of a limited size.

Q-16 Write the Significance/Advantages and Disadvantages of Queue?

Solution:
Advantages of Queue:
 A large amount of data can be managed efficiently with ease.
 Operations such as insertion and deletion can be performed with ease as it follows
the first in first out rule.
 Queues are useful when a particular service is used by multiple consumers.
 Queues are fast in speed for data inter-process communication.
 Queues can be used in the implementation of other data structures.

Disadvantages of Queue:
 The operations such as insertion and deletion of elements from the middle are time
consuming.
 Limited Space.
 In a classical queue, a new element can only be inserted when the existing elements
are deleted from the queue.
 Searching an element takes O(N) time.
 Maximum size of a queue must be defined prior.

***Q-17. Write a short note on Queue?

Solution:

See the Answer of the question 15 & 16.

***Q-18. Write the difference between Queue and Stack?

Solution:

Stack Queues

Stacks are based on the LIFO

principle, i.e., the element inserted Queues are based on the FIFO principle, i.e., the
at the last, is the first element to element inserted at the first, is the first element
come out of the list. to come out of the list.

Insertion and deletion in queues takes place

Insertion and deletion in stacks from the opposite ends of the list. The insertion
takes place only from one end of takes place at the rear of the list and the
the list called the top. deletion takes place from the front of the list.

Insert operation is called push

operation. Insert operation is called enqueue operation.

Delete operation is called pop

operation. Delete operation is called dequeue operation.

In queues we maintain two pointers to access

In stacks we maintain only one the list. The front pointer always points to the
pointer to access the list, called first element inserted in the list and is still
the top, which always points to the present, and the rear pointer always points to
last element present in the list. the last inserted element.

Stack is used in solving problems Queue is used in solving problems having

works on recursion. sequential processing.

Queue is of three types – 1. Circular Queue 2.

Stack does not have any types. Priority queue 3. double-ended queue.

Can be considered as a vertical Can be considered as a horizontal collection

collection visual. visual.

***Q-19. Write a short note on Asymptotic Notation?

(Or) Discuss different Asymptotic Notation?
Solution:
Asymptotic Notation: Asymptotic analysis of an algorithm refers to defining the
mathematical bound/framing of its run-time performance. Using asymptotic analysis, we
can precisely conclude the best case, average case, and worst case scenario of an
algorithm.

Asymptotic analysis refers to computing the running time of any operation in

mathematical units of computation. For example, the running time of one operation is
computed as f (n) and may be for another operation it is computed as g (n2). This means
the first operation running time will increase linearly with the increase in n and the
running time of the second operation will increase exponentially when n increases.
Similarly, the running time of both operations will be nearly the same if n is significantly
small.

Following are the commonly used asymptotic notations to calculate the running time
complexity of an algorithm.

 Big Oh - Ο Notation.
 Big Omega - Ω Notation.
 Theta - θ Notation.

 Big Oh - Ο Notation: The function f (n) = O (g (n)) if and only if there exist positive
constants c, n0 such that f (n) ≤ c * g (n), ∀n ≥ n0. Big-oh can be used to denote all
upper bounds on the time complexity of an algorithm. Big-oh also captures the
worst case analysis of an algorithm.
Examples:
10n2 + 4n + 2 = O (n2), such that 10n2 + 4n + 2 ≤ 11.n2, where c = 11, ∀n ≥ 5
Note that 10n2 + 4n + 2 is O(n2 ), O(n3 ), O(2n ), O(10n) as per the definition. i.e., it captures
all upper bounds. For the above example, O (n) is a tight upper bound whereas the rest
are loose upper bounds.
The notation Ο (n) is the formal way to express the upper bound of an algorithm's running
time. It measures the worst case time complexity or the longest amount of time an
algorithm can possibly take to complete.

 Big Omega - Ω Notation: The function f (n) = Ω (g (n)) if and only if there exist
positive constants c, n0 such that f (n) ≥ c * g (n), ∀n ≥ n0. Omega can be used to
denote all lower bounds of an algorithm.

Example:
2n2 + n log n + 1 = Ω (n2) such that 2n2 + n log n + 1 ≥ 2.n2, where c = 2, ∀n ≥ 1

Note that 2n2 + n log n + 1 is Ω (1), Ω (n), Ω (log n), and Ω (n log n) as per the definition.
i.e., it captures all lower bounds. For the above example, Ω (n2) is a tight lower bound
whereas the rest are loose lower bounds.
The notation Ω (n) is the formal way to express the lower bound of an algorithm's running
time. It measures the best case time complexity or the best amount of time an algorithm
can possibly take to complete.

 Theta - θ Notation: The function f (n) = Θ (g (n)) if and only if there exist positive
constants c1, c2, n0 such that c1 * g (n) ≤ f (n) ≤ c2 * g (n), ∀n ≥ n0. Theta can be used
to denote tight bounds of an algorithm. i.e., g (n) is a lower bound as well as an
upper bound for f (n). Note that f (n) = Θ (g (n)) if and only if f (n) = Ω (g (n)) and f
(n) = O (g (n)).

Example:
2n2 + n log n + 1 = Θ (n2) such that 2n2 ≤ 2n2 + n log n + 1 ≤ 5n2, where ∀n ≥ 2, c1 = 2, c2 = 5
The notation θ (n) is the formal way to express both the lower bound and the upper
bound of an algorithm's running time.

Q-20. Explain Divide and Conquer algorithm with a suitable example.

(Or) Write a short note on Divide and Conquer algorithm?
Solution:
Divide and Conquer Algorithm: In divide and conquer approach, the problem in hand, is
divided into smaller sub-problems and then each problem is solved independently. When we
keep on dividing the sub-problems into even smaller sub-problems, we may eventually reach a
stage where no more division is possible. Those "atomic" smallest possible sub-problem
(fractions) are solved. The solution of all sub-problems is finally merged in order to obtain the
solution of an original problem.
Divide/Break
This step involves breaking the problem into smaller sub-problems. Sub-problems
should represent a part of the original problem. This step generally takes a recursive
approach to divide the problem until no sub-problem is further divisible. At this stage,
sub-problems become atomic in nature but still represent some part of the actual
problem.
Conquer/Solve
This step receives a lot of smaller sub-problems to be solved. Generally, at this level, each
sub-problem is solved recursively; i.e. calling the same function for a smaller input size.
Here recursion will automatically do the work to solve the sub-problems.
Merge/Combine
When the smaller sub-problems are solved, then this stage recursively combines them
until they formulate a solution of the original problem.

Example:
Let the given array be

Step-1: Divide the array into two halves.

Again divide each sub-problem recursively into two halves until the single element is
found.

Divide the array into the smallest sub-problem.

Step-3: Now, combine the individual elements in a sorted manner. Here, conquer and
Combine steps go side by side.

Q-21. Write a short note on Greedy algorithm?

Solution:

Greedy Algorithm: The greedy method is one of the strategies like Divide and conquer
used to solve the problems. This method is used for solving optimization problems. An
optimization problem is a problem that demands either maximum or minimum results.

The Greedy method is the simplest and straightforward approach. It is not an algorithm,
but it is a technique. The main function of this approach is that the decision is taken on
the basis of the currently available information. Whatever the current information is
present, the decision is made without worrying about the effect of the current decision in
future.
This technique is basically used to determine the feasible solution that may or may not
be optimal. The feasible solution is a subset that satisfies the given criteria. The optimal
solution is the solution which is the best and the most favourable solution in the subset.
In the case of feasible, if more than one solution satisfies the given criteria then those
solutions will be considered as the feasible, whereas the optimal solution is the best
solution among all the solutions.

Characteristics of Greedy method

o To construct the solution in an optimal way, this algorithm creates two sets where
one set contains all the chosen items, and another set contains the rejected items.
o A Greedy algorithm makes good local choices in the hope that the solution should
be either feasible or optimal.

Applications of Greedy Algorithm

o It is used in finding the shortest path.

o It is used to find the minimum spanning tree using the prim's algorithm or the
Kruskal's algorithm.
o It is used in a job sequencing with a deadline.
o This algorithm is also used to solve the fractional knapsack problem.

Advantages of the Greedy Approach:

 The greedy approach is easy to implement.
 Typically have less time complexity.
 Greedy algorithms can be used for optimization purposes or finding close to
optimization in case of Hard problems.

Disadvantages of the Greedy Approach:

 The local optimal solution may not always be globally optimal.

Q-22. Explain Dynamic Programming with a suitable example.

(Or) Write a short note on Dynamic Programming?
Solution:
Dynamic Programming:
Dynamic programming approach is similar to divide and conquer in breaking down the
problem into smaller and yet smaller possible sub-problems. But unlike, divide and
conquer, these sub-problems are not solved independently. Rather, results of these
smaller sub-problems are remembered and used for similar or overlapping sub-
problems.
 Dynamic Programming Example

Let's find the Fibonacci sequence up to 5th term. A Fibonacci series is the sequence of
numbers in which each number is the sum of the two preceding ones. For example, 0, 1,
1, 2, 3. Here, each number is the sum of the two preceding numbers.
Algorithm

Let n be the number of terms.

1. If n <= 1, return 1.

2. Else, return the sum of two preceding numbers.

We are calculating the Fibonacci sequence up to the 5th term.

1. The first term is 0.

2. The second term is 1.

3. The third term is sum of 0 (from step 1) and 1(from step 2), which is 1.

4. The fourth term is the sum of the third term (from step 3) and second term (from step 2)
i.e. 1 + 1 = 2.
5. The fifth term is the sum of the fourth term (from step 4) and third term (from step 3)
i.e. 2 + 1 = 3.
Hence, we have the sequence 0, 1, 1, 2, 3. Here, we have used the results of the previous
steps as shown below. This is called a dynamic programming approach.

F(0) = 0

F(1) = 1

F(2) = F(1) + F(0)

F(3) = F(2) + F(1)

F(4) = F(3) + F(2)

Advantages

 It is very easy to understand and implement.

 It solves the sub problems only when it is required.
 It is easy to debug.

Disadvantages

 It uses the recursion technique that occupies more memory in the call stack.
Sometimes when the recursion is too deep, the stack overflow condition will
occur.
 It occupies more memory that degrades the overall performance.

***Q-23. Write the difference between Greedy Method and Dynamic Programming?

Solution:

Feature
Greedy method Dynamic programming

In Dynamic Programming we
In a greedy Algorithm, we make decision at each step
make whatever choice seems considering current problem
best at the moment in the hope and solution to previously
that it will lead to global solved sub problem to calculate
Feasibility optimal solution. optimal solution .

It is guaranteed that Dynamic

Programming will generate an
In Greedy Method, sometimes optimal solution as it generally
there is no such guarantee of considers all possible cases and
Optimality getting Optimal Solution. then choose the best.

A Dynamic programming is an
A greedy method follows the algorithmic technique which is
problem solving heuristic of usually based on a recurrent
making the locally optimal formula that uses some
Recursion choice at each stage. previously calculated states.

It requires Dynamic
Memoization It is more efficient in terms of Programming table for
memory as it never look back Memoization and it increases
or revise previous choices it’s memory complexity.
 Feature
Greedy method Dynamic programming

Greedy methods are generally Dynamic Programming is

Time faster. For example, Dijkstra’s generally slower. For
complexity shortest path algorithm takes example, Bellman Ford
O(ELogV + VLogV) time. algorithm takes O(VE) time.

The greedy method computes Dynamic programming

its solution by making its computes its solution bottom
choices in a serial forward up or top down by synthesizing
fashion, never looking back or them from smaller optimal sub
Fashion revising previous choices. solutions.

Fractional knapsack .
Example 0/1 knapsack problem