11 Questions with Answers For Algorithm Exam

#1. .Look up the words algorithm and algorithm in your dictionary and write down their
meanings?
 Algorithm: A step-by-step set of instructions to solve a problem or perform a task.

#2. What is an Algorithm?

An Algorithm is a finite sequence of instructions, which has a clear meaning and can be
performed with a finite amount of effort in a finite length of time.

#3. Characteristics of an Algorithm

1) Must take an input.
2) Must give some output.
3) Definiteness: each instruction is clear and unambiguous.
4) Finiteness: algorithm terminates after finite number of steps.
5) Effectiveness: every instruction must be basic.

#4. Performance of a Program with two examples: The performance of a program is the
amount of the computer memory and time that a program needs to run means how much
time and memory it needs to run.
They are measured as:
Examples

1. Time Complexity: How the runtime of the program changes as the input size grows

 Linear Search: time complexity is O(n) The time it takes to search grows directly with the
number of items in the list. If there are 10 items, it checks up to 10 times; if 100 items, up to 100
checks.

 Binary Search: time complexity is O(logn) The time grows much slower because it repeatedly
halves the number of items to search. If there are 16 items, it takes about 4 checks; for 32 items,
about 5 checks.

2. Space Complexity: How much extra memory the program uses.

 Bubble Sort: Space complexity: O(1) it sorts the list using the same memory without needing
extra memory.

 Merge Sort: space complexity is O(n) it uses additional memory when create temporary arrays
during the sorting process

#5. What are the Algorithm Design Goals?

The three basic design goals that one should strive for in a program are as below.
1) Time Efficiency (Try to save time): Optimize the algorithm to run as fast as possible,
minimizing the time complexity.
2) Space Efficiency (Try to save space): Optimize the algorithm to use the least amount of
memory or space, minimizing the space complexity.
3) Simplicity: Design algorithms that are easy to understand, implement, and debug.
4) Scalability: Ensure that the algorithm performs well as the size of input data increases.

#6. Classification of Algorithms

1. Based on Functionality:

 Sorting Algorithms: Used to arrange data in a specific order (e.g., smallest to largest).
Examples: Bubble Sort, Merge Sort.
 Searching Algorithms: Help find specific data in a collection.
Examples: Linear Search, Binary Search.
 Graph Algorithms: Solve problems related to graphs (nodes and edges).
Examples: Dijkstra's Algorithm, BFS, DFS.

2. Based on Design Approach:

 Divide and Conquer: Break the problem into smaller parts, solve them, and combine the results.
Example: Merge Sort.
 Greedy: Make the best decision at each step, hoping it leads to the best overall solution.
Example: Kruskal’s Algorithm.
 Dynamic Programming: Solve smaller sub problems, save their results, and reuse them.
Example: Fibonacci Series.
 Backtracking: Try all possibilities, undoing choices when necessary.
Example: Solving a maze.
 Brute Force: Check every possible solution to find the correct one.
Example: Password cracking by trying all combinations.
3. Based on Input Data Structure:

 Array-based Algorithms: Work with arrays.

Example: Quick Sort.
 Graph-based Algorithms: Solve problems on graph structures.
Example: Bellman-Ford Algorithm.
 Tree-based Algorithms: Deal with hierarchical data.
Example: Binary Search Tree Traversal.

4. Based on Output:

 Decision Problems: Answer is "yes" or "no."

Example: Is the number prime?
 Optimization Problems: Find the best solution.
Example: Shortest path in a network.

5. Based on Execution:

 Recursive Algorithms: Call themselves repeatedly until a condition is met.

Example: Factorial Calculation.
 Iterative Algorithms: Use loops to repeat steps until a condition is met.
Example: Calculating the sum of numbers.

6. Based on Complexity:

 Time-efficient Algorithms: Focus on solving problems quickly.

 Space-efficient Algorithms: Use less memory during execution.

#7.What is difference between Algorithm, Pseudocode & Program?

Algorithm: Algorithm is systematic logical approach of solving a problem and can written in
natural language
Pseudocode: It’s a simple version of the programming code that does not require any strict
programming language.
-Program: It’s is the actual code in any particular programming language such as C, C++, Java

#8. Explain Pseudocode with two examples

Pseudocode: It’s a simple version of the programming code that does not require any strict
programming language.

Example 1: Finding the maximum number in a list.

Function FindMax(list)
max = list[0]
For each item in list
If item > max then
max = item
Return max
End Function
```

Example 2: Calculating the factorial of a number.

Function Factorial(n)
If n == 0 then
Return 1
Else
Return n * Factorial(n - 1)
End If
End Function

Comments and Code Structure

Comments

 Explain what the code does for better understanding.

 Use // for single-line comments or inline explanations.
Example:

// Initialize x to 5
int x = 5;

Blocks
 Use {} to group statements, often for loops, functions, or conditionals.
Example:

if (x > 0) {
print("Positive");
}

Identifiers

 Names for variables, functions, etc. (start with a letter or _, followed by letters, digits, or _).
 Example of simple data type:

int count; // 'count' is an integer identifier

 Example of compound data type:

node = record {
datatype data1;
datatype data2;
link next; // Points to the next node
}

#9. Recursive Algorithms

A recursive algorithm is the one that calls itself in order to solve smaller instances of the same
problem.

Examples of Recursive Algorithms

1. Factorial Calculation

 Problem: Find the factorial of a number n (n! = n × (n-1) × (n-2) × ... × 1).
 Recursive Explanation: If you want to calculate n!, you multiply n by the factorial of n-1, and so on, until
you reach 0!, which equals 1.

Function Factorial(n)
If n == 0 then
Return 1 // Base case
Else
Return n * Factorial(n - 1) // Recursive case
End Function

2. Fibonacci Sequence

 Problem: Find the nth number in the Fibonacci sequence, where each number is the sum of the two
preceding ones: 0, 1, 1, 2, 3, 5, 8, ...
 Recursive Explanation: To find the nth Fibonacci number, add the (n-1)th and (n-2)th Fibonacci numbers.
Function Fibonacci(n)

If n == 0 then
Return 0 // Base case
Else if n == 1 then
Return 1 // Base case
Else
Return Fibonacci(n - 1) + Fibonacci(n - 2) // Recursive case
End Function

3. Sum of an Array

 Problem: Find the sum of all elements in an array.

 Recursive Explanation: Add the first element to the sum of the rest of the array until the array is empty.

Function SumArray(arr)
If arr is empty then
Return 0 // Base case
Else
Return arr[0] + SumArray(arr[1...n-1]) // Recursive case
End Function

4. Factorial of a Number (Using Tail Recursion)

 Problem: Calculate the factorial of n using tail recursion, which is a more efficient version of recursion.
 Recursive Explanation: Keep track of the result as you go along.

Function TailFactorial(n, accumulator)

If n == 0 then
Return accumulator // Base case
Else
Return TailFactorial(n - 1, n * accumulator) // Recursive case
End Function

#11. Write down short notes about space complexity and time complexity

Space Complexity

 Definition: Space complexity refers to the amount of memory an algorithm needs to run,
depending on the input size. It tells us how the memory usage grows as the problem size
increases

Time Complexity

 Definition: Time complexity describes how the running time of an algorithm increases with the
size of the input.

Time Complexity and Space Complexity Examples:

1. **Linear Search**:
- Time Complexity: O(n)
- Space Complexity: O(1) (in-place search)

2. **Binary Search**:
- Time Complexity: O(log n)
- Space Complexity: O(1) (in-place search)

3. **Bubble Sort**:
- Time Complexity: O(n^2)
- Space Complexity: O(1) (in-place sorting)

4. **Merge Sort**:
- Time Complexity: O(n log n)
- Space Complexity: O(n) (requires additional space for merging)