Module 1: Introduction to Algorithms

Important Problem Types, Asymptotic Notations and Its Properties, Basic Efficiency Classes,
Mathematical Analysis for Recursive and Non-Recursive Algorithms.

Priority 1 (Must Prepare)

1. Define an algorithm. Explain the characteristics/properties of a good algorithm.
2. Differentiate between Algorithm, Pseudocode, and Flowchart.
3. Explain important problem types in algorithm design with suitable examples.
4. Explain Big-O, Big-Ω, and Big-Θ notations with examples.
5. Discuss the properties of asymptotic notations.
6. Explain basic efficiency classes and arrange them according to their growth rates.
7. Analyze the time complexity of:
o A single loop
o A nested loop
o A logarithmic loop
8. Explain best-case, average-case, and worst-case analysis with examples.
9. Solve the recurrence relations:
o T(n)=T(n−1)+1T(n)=T(n-1)+1T(n)=T(n−1)+1
o T(n)=T(n/2)+1T(n)=T(n/2)+1T(n)=T(n/2)+1
o T(n)=2T(n/2)+nT(n)=2T(n/2)+nT(n)=2T(n/2)+n
10. Explain and apply the Master Theorem with suitable examples.

Priority 2 (Important)
11. Prove that 3n2+5n+7=O(n2)3n^2+5n+7 = O(n^2)3n2+5n+7=O(n2).
12. Show that 2n2+n=Θ(n2)2n^2+n = \Theta(n^2)2n2+n=Θ(n2).
13. Compare recursive and non-recursive algorithm analysis.
14. Write an algorithm (or pseudocode) for Linear Search and analyze its complexity.
15. Write an algorithm (or pseudocode) for Binary Search and analyze its complexity.
16. Write an algorithm to find the factorial of a number.
17. Write an algorithm to generate Fibonacci numbers.
18. Compare the growth rates of O(1)O(1)O(1), O(log⁡n)O(\log n)O(logn), O(n)O(n)O(n),
O(nlog⁡n)O(n\log n)O(nlogn), O(n2)O(n^2)O(n2), and O(2n)O(2^n)O(2n).

Priority 3 (Short Questions)

19. What is an algorithm?
20. What are the characteristics of an algorithm?
21. What is pseudocode?
22. What is a flowchart?
23. What is time complexity?
24. What is space complexity?
25. What is a recurrence relation?
 26. Define Big-O notation.
27. Define Big-Ω notation.
28. Define Big-Θ notation.
29. What is worst-case analysis?
30. What is average-case analysis?
31. What is best-case analysis?
32. What is a polynomial-time algorithm?
33. What is an exponential-time algorithm?
34. What is a sorting problem?
35. What is a searching problem?
36. What is a graph problem?
37. What is a string processing problem?
38. What is a combinatorial problem?
39. What is a geometric problem?

Answers
Part 1: Questions 1–3 (Introduction + Problem Types)

1. Define an Algorithm. Explain the

Characteristics/Properties of a Good
Algorithm.
Definition

An algorithm is a finite sequence of well-defined instructions used to solve a problem or

perform a computation. It takes some input, processes it through a series of steps, and
produces the desired output.

Example: Algorithm to find the sum of two numbers.

Step 1: Start
Step 2: Read A and B
Step 3: Compute Sum = A + B
Step 4: Display Sum
Step 5: Stop

Characteristics of a Good Algorithm

1. Input

An algorithm should have zero or more inputs supplied externally.

Example: Numbers A and B in an addition algorithm.

2. Output

An algorithm should produce at least one output.

Example: Sum of A and B.

3. Definiteness

Every step must be clear and unambiguous.

Correct: Add A and B.

Incorrect: Process the numbers somehow.

4. Finiteness

The algorithm must terminate after a finite number of steps.

Example: A loop running from 1 to n terminates after n iterations.

5. Effectiveness

Each operation should be basic and executable within finite time.

Example: Addition, subtraction, comparison.

6. Correctness

The algorithm should produce correct results for all valid inputs.

7. Generality

The algorithm should solve a class of problems rather than a specific instance.

Example: Finding the maximum of any list of numbers.

8. Efficiency

The algorithm should use minimum time and memory.

Diagram: Algorithm Development Process

Problem Definition
↓
Algorithm Design
↓
Analysis
↓
Implementation
↓
Testing
↓
Output

Advantages of Algorithms

1. Easy to understand.
2. Language independent.
3. Helps in program development.
4. Simplifies debugging.
5. Improves efficiency.

Conclusion

An algorithm is the foundation of problem solving in computer science. A good algorithm

must be finite, definite, correct, effective, efficient, and capable of producing the desired
output.

2. Differentiate Between Algorithm,

Pseudocode, and Flowchart
Introduction

Algorithms, pseudocode, and flowcharts are tools used for designing solutions before actual
programming.

Algorithm

An algorithm is a step-by-step procedure for solving a problem.

Example

1. Start
2. Read A and B
3. Sum = A + B
4. Print Sum
5. Stop
Pseudocode

Pseudocode is an informal programming-like representation of an algorithm.

Example

BEGIN

INPUT A, B

SUM ← A + B

PRINT SUM

END

Flowchart

A flowchart is a graphical representation of an algorithm using standard symbols.

Flowchart Symbols

Oval → Start/Stop

Rectangle → Process

Parallelogram → Input/Output

Diamond → Decision

Arrow → Flow of control

Flowchart Example
┌───────┐
│ Start │
└───┬───┘
│

┌──────▼──────┐
│ Read A, B │
└──────┬──────┘
│
┌──────▼──────┐
│ Sum=A+B │
└──────┬──────┘
│
┌──────▼──────┐
│ Print Sum │
└──────┬──────┘
│
┌───▼───┐
│ Stop │
└───────┘

Comparison Table
Feature Algorithm Pseudocode Flowchart

Representation Step-by-step text Program-like text Graphical

Ease of Writing Easy Very Easy Time-consuming

Understanding Moderate Easy Very Easy

Modification Easy Easy Difficult

Programming Relation Indirect Very close Indirect

Conclusion

Algorithms provide logical steps, pseudocode provides a programming-oriented description,

and flowcharts provide a visual representation of the solution.

3. Explain Important Problem Types in

Algorithm Design with Suitable Examples
Introduction

Algorithm design focuses on solving different categories of computational problems.

Understanding these problem types helps in selecting appropriate algorithms.

1. Sorting Problems

Sorting arranges data in a particular order.

Example

Input: 8, 3, 6, 1

Output: 1, 3, 6, 8
Common Algorithms

• Bubble Sort

• Merge Sort

• Quick Sort

Applications

Database management, searching, reporting.

2. Searching Problems

Searching locates a specific element within a collection.

Example

Find 25 in:

10, 15, 20, 25, 30

Common Algorithms

• Linear Search

• Binary Search

Applications

Student records, library systems, search engines.

3. String Processing Problems

These deal with text manipulation and pattern matching.

Example

Finding the word "algorithm" in a document.

Applications

Text editors, spell checkers, search engines.

4. Graph Problems

A graph consists of vertices and edges.

Diagram
A
/ \
B---C
\ /
D
Examples

• Shortest Path

• Minimum Spanning Tree

• Network Routing

Applications

Google Maps, communication networks.

5. Combinatorial Problems

Finding the best arrangement from many possibilities.

Examples

• Travelling Salesman Problem

• Knapsack Problem

• Scheduling

Applications

Transportation, resource allocation.

6. Geometric Problems

Problems involving points, lines, and shapes.

Example

Finding the closest pair of points.

Applications

Computer graphics, GIS systems, robotics.

Summary Table
Problem Type Example

Sorting Arrange numbers

Searching Find an element

String Processing Pattern matching

Graph Shortest path

Combinatorial Knapsack

Geometric Closest pair of points

Conclusion

Sorting, searching, string processing, graph, combinatorial, and geometric problems form the
major categories of algorithmic problems and have wide practical applications.

Reply "continue" and I'll provide detailed exam-ready answers for Questions 4–7
(Asymptotic Notations, Properties, Efficiency Classes, and Loop Analysis).