Algorithm Introduction Topics: Study Guide

Let’s break down the key introductory topics in algorithms as described in your class notes (DAA
Unit 1):

1. What is an Algorithm?
Definition:
An algorithm is a finite set of clear instructions to solve a problem or perform a particular task.
It must have:
Input: Zero or more values provided before running.
Output: At least one result produced after completion.
Definiteness: Each step must be precisely defined and unambiguous.
Finiteness: Must terminate after a limited number of steps.
Effectiveness: Operations must be basic enough to perform by hand if needed.
Quick Check:
Can you list these five characteristics from memory?

2. Areas to Study an Algorithm

The process involves:
1. Devise: Designing the step-by-step solution.
2. Validate: Ensuring it gives the correct output for all valid inputs.
3. Analyze: Measuring efficiency, especially time and space required.
4. Test: Running the algorithm on actual data sets to check and improve.
Design Techniques:
Divide and Conquer
Greedy Method
Dynamic Programming
Backtracking
Branch and Bound
3. Expressing Algorithms: Pseudo Code
Pseudo code uses plain language plus programming rules—helpful for expressing logic
before actual coding.
Flowcharts: Diagrams to visualize steps.
Commenting, assignment, conditions, and loops are all part of pseudo code standards.

4. Performance Analysis

Time Complexity
Definition: Number of essential operations performed as input size ($ n $) increases.
Methods to Determine:
Table Method: Count each statement’s steps and frequency of execution.
Count Variable: Use a variable to increment with every operation.
Example:
If a for-loop runs from $ 1 $ to $ n $, a single instruction inside will run $ n $ times.
Try:
If "for i := 1 to n do" includes two assignments and a sum, how many total steps for $ n = 4 $?

Space Complexity
Definition: Amount of memory needed, including variables, constants, arrays, and recursion
stack.
Formula:
$ S(P) = C + S_P(Input Characteristics) $

5. Cases in Complexity Analysis

Best Case: Minimum operations (ideal scenario)
Worst Case: Maximum operations (hardest scenario)
Average Case: Expected operations averaged over all possible inputs
Can you think of an example where the best case differs from the worst case? Try with Linear
Search.

6. Asymptotic Notation
Used to describe general behavior as $ n $ grows:
Big O ($ O $): Upper bound; worst-case scenario.
Omega ($ \Omega $): Lower bound; best-case scenario.
 Theta ($ \Theta $): Tight bound; both upper and lower.
Little o and Little omega: Stricter versions for loose bounds.
Order (from fastest to slowest):
$ O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) $
Practice:
How would you describe the complexity of sorting an already sorted array using Bubble Sort?

Mini-Review / Mnemonic
“FIDOE” helps remember algorithm properties:
Finiteness
Input
Definiteness
Output
Effectiveness

Want to Go Deeper?
If you tell me your course or grade level, I can make this even more tailored—like focusing on
pseudocode syntax, more on recursion, or going into real problem examples. Ready to try a
practice problem, or do you want clarification on any topic above?
Your Turn:
Pick any piece above and restate it, or ask for a quiz question on that section!
⁂

Understanding Pseudocode
Let’s break down the basics of pseudocode so you can easily express and design algorithms
before actual coding.

What Is Pseudocode?
Definition:
Pseudocode is a step-by-step description of an algorithm using plain English structured
like code, but without strict syntax rules. It focuses on logic, not language specifics. [2] [3] [4]
Purpose:
Plans out a solution before coding.
Helps communicate ideas between programmers or students.
Easy to adapt into any programming language.
Quick Check:
Why is pseudocode more readable than regular code?

Common Pseudocode Constructs

Here are some typical elements and their roles: [3] [4] [5]

Construct Role in Pseudocode Example (in pseudocode)

INPUT Get input from the user INPUT number

OUTPUT/DISPLAY Show result to user OUTPUT result

SET/ASSIGN Assign values to variables SET sum TO 0

IF–THEN–ELSE Decision/branching IF score > 50 THEN ...

FOR/WHILE Loops/repeat steps FOR i FROM 1 TO n DO ...

REPEAT–UNTIL Exit-controlled loop REPEAT ... UNTIL found = true

Tip: Indent instructions inside loops or decisions for clarity.

Simple Example
Let’s write pseudocode to add two numbers and display the result: [4] [3]

START
INPUT number_1
INPUT number_2
SET sum TO number_1 + number_2
OUTPUT sum
END

Now, can you rephrase this for multiplying two numbers instead?

Best Practices for Writing Pseudocode

Use clear sequence: start with BEGIN/START, end with END.
Keep statements concise.
Use standard keywords (IF, FOR, SET, OUTPUT, INPUT).
Indent where hierarchy or logic changes.
Avoid specific programming syntax—focus on logic. [6] [4]
Mini-Review
Here’s a mnemonic:
IS SOLID
Indent for hierarchy
Standard keywords
Simple statements
Order: BEGIN...END
Logic, not syntax
Input/Output clear
Describe steps in detail

Your Turn
Would you like to practice writing pseudocode for a basic task? Or want a sample illustrating
loops or decisions?
Also, if you tell me your course or grade, I can further tailor examples and practice!
⁂

Specifications of Pseudocode
Let’s break down the main standards, rules, and best practices when writing pseudocode. This
will help make your algorithm designs clear, complete, and readable for anyone with basic
programming knowledge.

1. Main Constructs (Core Building Blocks)

Pseudocode typically uses these six structured programming constructs (always in uppercase
for clarity): [11] [12]
SEQUENCE: List actions one after another.
IF–THEN–ELSE: Conditional branching.
WHILE: Loop with a condition at the top.
REPEAT–UNTIL: Loop with a condition at the bottom.
FOR: Counting loop (repeat a fixed number of times).
CASE: Multibranch selection (choose from several named options).
Each construct can be nested inside others to handle complex logic. [12] [11]
2. Writing Standards & Syntax
General Style Guidelines: [13] [12]
Capitalize the initial word (keyword) of each line.
One statement per line for clarity.
Indent to show hierarchy/nesting.
Always mark the end of blocks with END keywords (ENDIF, ENDWHILE, etc.).
Programming language independent — focus on logic, not on syntax.
Use the problem’s domain vocabulary, not programming terms (e.g., “Append item to list”
rather than “[Link](item)”).
Keep it complete: Every step needed for implementation should be described.

Example Format

BEGIN
SET total TO 0
FOR i FROM 1 TO n DO
IF i MOD 2 == 0 THEN
INCREMENT total
ENDIF
ENDFOR
OUTPUT total
END

Quick Check:
Why is indentation and END keyword important when writing nested structures?

3. Keyword Summary
Pseudocode Keyword Usage

SET / ASSIGN Variable assignment (SET x TO 5)

INPUT Get user input (INPUT number)

OUTPUT / DISPLAY Show results (OUTPUT total)

IF–THEN–ELSE Decision-making (IF x > 0 THEN ... ELSE ...)

WHILE / ENDWHILE Loop while a condition is true

FOR / ENDFOR Fixed repetition

CASE / ENDCASE Multiple choices

4. Completeness & Clarity
Avoid abstraction: Lay out every step that will occur.
Avoid technical details: Use plain English.
Make it readable: Even a non-programmer should get the basic logic. [14]

Mnemonic: "SIMPLE"
Structured constructs
Indentation for hierarchy
Main keywords capitalized
Plain-English statements
Label ends of blocks
Each step clear, complete

Check & Practice

Can you write pseudocode for finding the maximum value in a list, following these standards?
If you want an example, or want to explore complex constructs (like sub-procedures or CASE
statements), let me know your course/grade and I’ll tailor it!
Ready for a practice round, or do you want to go deeper on a specific keyword or construct?
⁂

Recursive Algorithms: Introduction and Key

Concepts
Let’s break down recursive algorithms step-by-step for clarity and retention.

What Is a Recursive Algorithm?

A recursive algorithm is a method where a function calls itself to solve smaller instances of the
same problem, repeatedly breaking a complex task down until it reaches a simple base case it
can solve directly. [20] [21] [22] [23]
Recursive algorithms involve two key parts: a base case and a recursive step.
Main Components of Recursion
1. Base Case
Definition: The simplest, smallest version of the problem that can be solved directly.
Purpose: Stops further recursive calls and begins the unwinding process. [21] [22] [23] [20]
Example (for factorial):
If $ n = 1 $, return 1 (since $ 1! = 1 $).
2. Recursive Case
Definition: The portion where the function calls itself with a smaller/simpler input.
Purpose: Breaks the problem into smaller chunks. [22] [23] [20] [21]
Example (for factorial):
For $ n > 1 $, return $ n \times $ factorial($ n-1 $).
Quick Check:
Why is the base case important? What happens if it’s missing?

Types of Recursion
Direct Recursion: Function calls itself directly.
Indirect Recursion: Two or more functions call each other in a circular pattern.
Head Recursion: Recursive call occurs first, before other calculations.
Tail Recursion: Recursive call is the last operation—can be optimized for speed.
Non-Tail Recursion: Recursive call is followed by further processing after it returns. [20] [21]
[22]

Practice:
Can you identify whether the following pseudocode is direct or indirect recursion?

Common Applications of Recursion

Tree/Graph Traversal (e.g., Depth-First Search)
Divide-and-Conquer Techniques (e.g., Merge Sort, Quick Sort)
Backtracking Problems (e.g., finding all solutions for puzzles)
Combinatorics (e.g., generating permutations and combinations)
Dynamic Programming (e.g., with memoization/fibonacci). [22] [20]
Memory Use and Efficiency
Every recursive call uses stack memory: stores parameters, local variables, and return
address. [21]
Excessive recursion may cause a stack overflow if the base case isn’t reached or input is
too large.
Tail recursion can be optimized to use less memory.

Mini-Review / Mnemonic
BRR for recursive algorithms:
Base case
Recursive case
Reduce problem size each call

Your Turn
Restate what a base case is in your own words, or write sample pseudocode for a recursive
function like factorial, including a clear base case and recursive case.
If you let me know your grade or course, I can tailor examples and practice problems to your
comfort level! Ready to try a sample, or need clarification on any recursion type?
⁂

sequence
Sequencing in algorithms (and pseudocode) means executing instructions one after another in a
strictly defined order, from top to bottom, without skipping or repeating any step unless control
structures change the flow. It is one of the three basic building blocks of algorithms, along with
selection (choices) and iteration (loops). [29] [30] [31] [32]

What is sequence?
Sequence is a linear progression of steps: “do step 1, then step 2, then step 3,” where each
step runs exactly once in the specified order. [31] [33]
The output of one step is often used as the input to the next, so changing the order can
make the algorithm incorrect even if all steps are present. [30] [29]
Sequence in pseudocode
In pseudocode, sequence is represented by writing one statement per line, all at the same
indentation level, executed from the first line to the last. [34] [35]
Example patterns include: INPUT data, then PROCESS data, then OUTPUT result, with no
conditions or loops altering the order. [36] [37]

Why sequence is important

Correct sequencing ensures the algorithm’s logic matches the real-world process (for
example, putting toothpaste on a brush before brushing teeth). [32] [30]
Because computers follow instructions exactly in the order given, a wrong sequence can
produce wrong results even if each individual instruction is valid. [38] [39]
If you tell what your teacher asked under “sequence” (only definition, or examples in
pseudocode/flowchart), a short exam-ready answer can be prepared for you.
⁂

Explain sequence in algorithms with simple

examples
Sequence in algorithms means doing steps in a fixed, logical order: first step 1, then step 2, then
step 3, and so on, each exactly once, unless a condition or loop changes the flow. It is the
simplest control structure and is always present, even inside more complex algorithms. [49] [50]
[51] [52]

Simple definition
A sequence is a set of instructions executed one after another, from top to bottom. [51] [53]
The order matters: if you change the order, you may get a wrong result even though the
individual steps are correct. [50] [49]

Example 1: Add two numbers

Algorithm (sequence only, no conditions or loops):
1. Read two numbers
2. Add them
3. Print the result
Pseudocode-style:
INPUT A
INPUT B
SET SUM = A + B
OUTPUT SUM
Here, each step runs once and strictly in order.

Example 2: Find area of a rectangle

1. Read length
2. Read breadth
3. Compute area = length × breadth
4. Display area
Again, these instructions form a pure sequence: no branching, no repetition, just one step after
another.

Example 3: Convert Celsius to Fahrenheit

1. Read temperature in Celsius (C)
2. Compute F = (9/5) × C + 32
3. Print F
All three examples show the same idea: a sequence is a straight-line flow of control, where each
statement is executed exactly once in the written order.
⁂

and?
Great, you’ve brought in sequence, selection, and iteration. Nice connection.
First, quick check on you:
What’s your level (school/college)?
What are your goals with algorithms (exam, coding, viva)?
Here’s our short lesson plan (5 steps total):
Step 1: Sequence (we’ve started this)
Step 2: Selection (if / if-else / case)
Step 3: Iteration (loops)
Step 4: Put all three together in a small algorithm
Step 5: Quick review / quiz
Now, about your query “and?”:
Sequence is just one control structure. The other two are:
Selection: making choices (IF / ELSE)
Iteration: repeating steps (loops)
To continue the lesson plan:
In your own words, how would you define “selection” in algorithms?
 ⁂

in detail about
Great, you’re clearly working through control structures. Nice.
First, quick check:
What’s your level (school/college)?
Are you preparing for an exam on “Algorithms / C / DAA” or just for understanding?
Here’s our updated lesson plan (5 steps, focused on your goal of understanding control
structures in algorithms):
Step 1: Sequence (done)
Step 2: Selection – in detail (we start this now)
Step 3: Iteration
Step 4: Combine all three in one algorithm
Step 5: Short review/quiz
We’ll now do Step 2: selection in detail, one concept at a time.
1. Basic idea of selection
Selection (also called decision or branching) is a control structure that lets an algorithm choose
between two or more possible paths based on a condition (true/false). After the chosen path
finishes, control joins back and continues with the rest of the algorithm.
Very short definition you can write in exams:
“Selection is a control structure that chooses which statement or block to execute from two
or more alternatives, based on a condition.”
2. Why do we need selection?
Without selection, algorithms would always do the same steps in the same order. With selection,
an algorithm can:
react to input
handle different cases (e.g., pass/fail, positive/negative, menu options)
implement logic like “if this happens, do X, otherwise do Y”.
3. Types of selection
Conceptually, there are three main kinds:
Single-way selection:
Only do something if the condition is true; otherwise, do nothing.
Example idea: “If marks ≥ 50, print Pass.”
Two-way selection:
 Choose between exactly two paths: one if condition is true, another if it is false.
Example idea: “If marks ≥ 50, print Pass else print Fail.”
Multi-way selection:
Choose between more than two possible paths (e.g., grade A/B/C/D, menu options
1/2/3/4).
Often implemented as:
nested if-else
if–else-if ladder
switch-case
4. Single-way selection (if)
General pseudocode:
IF condition THEN
statements
ENDIF
Example (pass message only):
INPUT mark
IF mark ≥ 50 THEN
OUTPUT "You have passed the exam"
ENDIF
OUTPUT "Program ends"
If condition is false, the IF block is skipped; the rest continues.
5. Two-way selection (if–else)
General pseudocode:
IF condition THEN
statements_if_true
ELSE
statements_if_false
ENDIF
Example (pass/fail):
INPUT mark
IF mark ≥ 50 THEN
OUTPUT "Pass"
ELSE
OUTPUT "Fail"
ENDIF
Exactly one of the two blocks runs.
 6. Multi-way selection (if–else-if, nested if, switch)
a) If–else-if ladder:
IF condition1 THEN
block1
ELSE IF condition2 THEN
block2
ELSE IF condition3 THEN
block3
ELSE
default_block
ENDIF
Example (grading):
INPUT marks
IF marks ≥ 90 THEN
OUTPUT "Grade A"
ELSE IF marks ≥ 80 THEN
OUTPUT "Grade B"
ELSE IF marks ≥ 70 THEN
OUTPUT "Grade C"
ELSE
OUTPUT "Fail"
ENDIF
b) Nested if:
One if (or else) contains another if inside.
Used when decisions depend on previous decisions.
c) Switch-case (multi-way by value):
Used when one variable is compared with many constant values (e.g., 1,2,3,4).
Pseudocode:
SWITCH choice
CASE 1: statements_for_1
CASE 2: statements_for_2
CASE 3: statements_for_3
DEFAULT: default_statements
ENDSWITCH
7. Flow idea (important for viva/theory)
In a selection structure:
There is usually a decision point (condition).
Based on true/false, control flows along one branch.
 All branches eventually meet again, so the algorithm can continue.
8. Short exam-style explanation (summary)
If you need a compact “in detail” paragraph answer:
“Selection is a control structure used in algorithms and programming to choose between
alternative actions based on conditions. A Boolean condition (true/false) is evaluated; depending
on the result, one of the alternative paths is executed while the others are skipped. There are
three main types of selection: single-way selection (simple if), two-way selection (if–else), and
multi-way selection (nested if–else, if–else-if ladder, and switch-case). In all cases, the branches
join again after the selection, and execution continues with the next statement.”
We’re now well into Step 2 of the lesson plan (selection in detail), which directly supports your
goal of understanding control structures in algorithms.
Your turn (understanding check):
Can you, in your own words, write a 1–2 line definition of “selection” as you would for an exam?
⁂

psudo
Great, you’re asking about “psudo” (pseudocode). Let’s tighten what we’ve done and go one
clear step further.
First, quick check:
What course/level are you in (school/degree + subject)?
Are you mainly preparing for an exam/viva in Algorithms/DAA?
We’re in Step 1–2 of our lesson plan (pseudocode basics + control structures), which supports
your goal of understanding algorithm fundamentals.
Very short, exam-style core points about pseudocode:
Pseudocode is a plain-English, language-independent way to write an algorithm, shaped like
code but without strict syntax.
It focuses on logic, not on details like data types or library functions.
It usually uses six main constructs: SEQUENCE, IF–THEN–ELSE, WHILE, REPEAT–UNTIL,
FOR, CASE. [72]
The flow in sequence logic is from top to bottom, one instruction after another. [73] [74]
Purpose: easier for humans to understand and then convert into any programming
language. [75] [73]
Tiny example (pure sequence pseudocode):
BEGIN
INPUT number
SET result TO number * 50
OUTPUT result
END
Your turn (understanding check):
If you had to give a 1–2 line definition of “pseudocode” in your own words for an exam, how
would you write it?
⁂

1. [Link]
2. [Link]
3. [Link]
4. [Link]
5. [Link]
6. [Link]
ssing-algorithms/
7. [Link]
8. [Link]
9. [Link]
10. [Link]
11. [Link]
12. [Link]
13. [Link]
14. [Link]
15. [Link]
16. [Link]
17. [Link]
18. [Link]
19. [Link]
20. [Link]
21. [Link]
22. [Link]
23. [Link]
ies-of-recursive-algorithms
24. [Link]
25. [Link]
26. [Link]
27. [Link]
re_and_Algorithms_(Njoroge)/02:_Recursion/2.01:Activity_1-_Recursive_Algorithm
28. [Link]
29. [Link]
orithms/a/the-building-blocks-of-algorithms
30. [Link]
31. [Link]
32. [Link]
33. [Link]
34. [Link]
35. [Link]
[Link]
36. [Link]
37. [Link]
ls/Programming_Fundamentals_-
A_Modular_Structured_Approach_using_C(Busbee)/11:_Introduction_to_Structured_Programming/11.02:_
Pseudocode_Examples_for_Control_Structures
38. [Link]
39. [Link]
40. [Link]
41. [Link]
42. [Link]
43. [Link]
44. [Link]
45. [Link]
46. [Link]
47. [Link]
48. [Link]
49. [Link]
orithms/a/the-building-blocks-of-algorithms
50. [Link]
51. [Link]
52. [Link]
53. [Link]
54. [Link]
55. [Link]
56. [Link]
orithms/a/the-building-blocks-of-algorithms
57. [Link]
58. [Link]
59. [Link]
60. [Link]
61. [Link]
62. [Link]
63. [Link]
64. [Link]
65. [Link]
66. [Link] [Link]
67. [Link]
68. [Link]
69. [Link] Engineering/2434/crs-14158/Files/Chapter [Link]
70. [Link]
71. [Link]
72. [Link]
73. [Link]
74. [Link]
[Link]
75. [Link]
76. [Link]
harts-1
77. [Link]
78. [Link]
79. [Link]