Understand the steps.
Measure the work.

DAA · UNIT 1 · 01

What is an algorithm?

SOURCE DEFINITION · PDF PAGE 1

Algorithm

It is a finite steps to solve a problem.

SOURCE DEFINITION · PDF PAGE 1

Algorithm (alternative definition)

An algorithm is a step-by-step procedure or set of well-defined instructions for solving a specific problem or performing a particular task.

SOURCE DEFINITION · PDF PAGE 1

Well-defined

Algorithms have precise, unambiguous instructions that define how to perform a task. Each steps must be clear and understandable.

SOURCE DEFINITION · PDF PAGE 1

Finiteness

An algorithm must eventually terminate after a finite number of steps.

SOURCE DEFINITION · PDF PAGE 2

Effectiveness

Algorithms are practical and can be implemented using a finite amount of time and memory.

SOURCE DEFINITION · PDF PAGE 2

Input

Algorithms take input values as their starting point and produce output based on these inputs.

SOURCE DEFINITION · PDF PAGE 2

Output

Algorithms should generate at least one output or it may be more output.

A counterexample: “Keep trying until it works” lacks a precise step and a termination condition. It is not a sufficient algorithm specification.

DAA · UNIT 1 · 02

From a problem to a correct program.

The supplied notes show six connected stages. Correctness checks and efficiency analysis can send us back to our decisions or design.

Maximum(A[0…n−1])  // n ≥ 1
    max ← A[0]
    for i ← 1 to n−1
        if A[i] > max
            max ← A[i]
    return max

Worked trace: [7, 2, 9, 4] → start max = 7 → compare 2 (keep 7) → compare 9 (update to 9) → compare 4 (keep 9). The answer is 9 after three comparisons.

Correctness invariant: after each iteration, max is the largest element in the inspected prefix. It holds initially for the first element, is preserved by the update, and gives the required maximum when the entire array has been inspected. A finite loop over n−1 remaining elements establishes termination.

DAA · UNIT 1 · 03

Make the assumptions explicit.

SOURCE DEFINITION · PDF PAGE 3

Sequential algorithms

In Random-access Machine, instructions are executed one after another. Algorithms designed to be executed on these machines are called sequential algorithms.

SOURCE DEFINITION · PDF PAGE 3

Parallel algorithms

In some newer computers, operations are executed concurrently, i.e. in parallel. Algorithms that take advantage of this capability are called parallel algorithms

SOURCE DEFINITION · PDF PAGE 4

Exact algorithm

An algorithm used to solve the problem exactly and produce correct result is called an exact algorithm

SOURCE DEFINITION · PDF PAGE 4

Approximation algorithm

If the problem is so complex and able to get exact solution, then we have to choose an algorithm called approximation algorithm.

DAA · UNIT 1 · 04

Describe the steps before coding.

SOURCE DEFINITION · PDF PAGE 5

Natural language

It is very simple and easy to specify an algorithm using natural language.

SOURCE DEFINITION · PDF PAGE 6

Psuedo code

Psuedo code is a mixture of a natural language constructs.

SOURCE DEFINITION · PDF PAGE 6

Flowchart

Flowchart is a graphical representation of an algorithm.

SOURCE DEFINITION · PDF PAGE 6

Flowchart (description)

It is a method of expressing an algorithm by a collection of connected geometric shapes containing descriptions of the algorithm's steps.

Sum(a, b)
    c ← a + b
    return c

Natural-language steps: read the first number; read the second number; add them and store the sum; display the sum. For a = 7 and b = 5, the output is 12. The selected basic operation, addition, executes once.

a, b = map(int, input().split())
print("Sum =", a + b)
print("Additions =", 1)

DAA · UNIT 1 · 05

Choose a strategy that fits the problem.

SOURCE DEFINITION · PDF PAGE 4

Algorithmic strategy

Algorithmic strategy are a general approach by which many problems can be solved algorithmically

One problem, several possible approaches

To find a key in an unsorted array, a direct scan is a suitable baseline. If the array is already sorted and supports indexed access, binary search can repeatedly reduce the remaining interval. If many searches are required, an index or hash table may justify preprocessing and additional memory. Include that preparation cost in the comparison.

Why a greedy choice needs proof

For coins {1, 3, 4} and amount 6, taking the largest coin first gives 4 + 1 + 1 (three coins). The optimum is 3 + 3 (two coins). A locally attractive choice can miss the global optimum.

Dynamic programming avoids repeated work

Naive recursive F(5) requests F(3) more than once. A table computes F(0) = 0, F(1) = 1, then F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5 once each. Under a unit-cost arithmetic model, tabulation takes Θ(n) time; retaining only the previous two values reduces extra storage to Θ(1). The size of large Fibonacci integers adds a separate bit-cost concern.

DAA · UNIT 1 · 06

Recognize a limitation. Measure an improvement.

The source suggests reducing time and space, selecting suitable data structures such as hashes, heaps, graphs and tries, simplifying logic, choosing a better design paradigm, and testing with dry runs. These are choices to justify for the specific problem; each has costs.

LoopSum(n)
    sum ← 0
    for i ← 1 to n
        sum ← sum + i
    return sum

FormulaSum(n)
    return n × (n + 1) / 2

Worked example: n = 5 gives 1 + 2 + 3 + 4 + 5 = 15. The formula 5 × 6 / 2 also gives 15. The loop performs five additions; the formula uses a constant number of arithmetic operations. This shortcut applies to consecutive integers 1…n, not an arbitrary array of five values.

Constant factor versus growth class: reducing 3n² + 2n + 7 operations to n² improves the count, but both have Θ(n²) growth. Replacing the consecutive-sum loop with the formula changes Θ(n) to Θ(1) in this unit-cost model. Fixed-width overflow and the cost of large-integer arithmetic must still be considered.

n = int(input())
if n < 0:
    raise ValueError("n must be nonnegative")
total = 0
for i in range(1, n + 1):
    total += i
print("Loop sum =", total)
print("Formula sum =", n * (n + 1) // 2)
print("Loop additions =", n)

DAA · UNIT 1 · 07

State what n means and what you count.

SOURCE DEFINITION · PDF PAGE 8

Time efficiency

how fast the algorithm runs.

SOURCE DEFINITION · PDF PAGE 8

Space efficiency

how much extra memory it uses.

SOURCE DEFINITION · PDF PAGE 14

Input size

An algorithm's efficiency is defined as a function of some parameter 'n' indicating the algorithm's input size.

SOURCE DEFINITION · PDF PAGE 15

Basic operation

It is the most significant operation in an algorithm that contributes the most to its running time.

Efficiency analysis relates resource use to input size. State five things: the input-size parameter, computation model, selected basic operation, case being analyzed and resulting count or growth class.

A numeric value N takes approximately ⌊log₂ N⌋ + 1 bits when N ≥ 1. A loop up to the numeric value N is not linear in its bit-length b. Choose the size parameter before labelling growth.

Why clock time alone is insufficient

Seconds and milliseconds depend on CPU, compiler, implementation quality and operating conditions. Counting operations provides a machine-independent model. If C(n) is the count and t is an approximate cost per operation, T(n) ≈ tC(n). The source highlights basic operations in inner loops, such as key comparisons. Not every problem has the same basic operation.

Time and extra space are separate

Scanning n elements can take Θ(n) time while keeping only a constant number of extra variables. An algorithm that stores an n-entry helper table uses Θ(n) additional space. Report auxiliary space separately from memory already occupied by the input; recursion stack frames count as extra storage.

DAA · UNIT 1 · 08

Count the operations you can see.

SequentialSearch(A[0…n−1], K)
    i ← 0
    while i < n and A[i] ≠ K
        i ← i + 1
    if i < n return i
    else return −1

One binary-search probe can involve both equality and order comparisons. Counting probes is useful, but it is not identical to counting every primitive comparison. Binary search has Θ(log n) worst-case search time on an already sorted random-access array. Sorting and input validation are separate work; the sample Python program reads and validates the input first, so the complete program includes Θ(n) preparation.

def sequential_search(values, key):
    comparisons = 0
    for i in range(len(values)):
        comparisons += 1
        if values[i] == key:
            return i, comparisons
    return -1, comparisons

values = list(map(int, input().split()))
key = int(input())
index, comparisons = sequential_search(values, key)
print("Index =", index)
print("Comparisons =", comparisons)

def binary_search(values, key):
    low, high, probes = 0, len(values) - 1, 0
    while low <= high:
        mid = (low + high) // 2
        probes += 1
        if values[mid] == key:
            return mid, probes
        if values[mid] < key:
            low = mid + 1
        else:
            high = mid - 1
    return -1, probes

values = list(map(int, input().split()))
if any(values[i] > values[i + 1] for i in range(len(values) - 1)):
    raise ValueError("Binary search requires sorted data")
key = int(input())
index, probes = binary_search(values, key)
print("Index =", index)
print("Midpoint probes =", probes)

DAA · UNIT 1 · 09

Keep input size fixed. Change the input.

SOURCE DEFINITION · PDF PAGE 19

Worst-case efficiency

Worst-case efficiency of an algorithm is its efficiency for the worst-case input of size n.

SOURCE DEFINITION · PDF PAGE 19

Best-case efficiency

Best-case efficiency of an algorithm is its efficiency for the best case input size n

SOURCE DEFINITION · PDF PAGE 19

Average-case efficiency

Average-case efficiency lies b/w best-case and worst-case.

For n = 8: the best count is 1 and the worst count is 8. If every successful first-match position is equally likely and the key is always present, the average is (1 + 2 + … + 8)/8 = 4.5. A single execution still performs an integer number of comparisons.

DAA · UNIT 1 · 10

Weight each possible outcome.

Probability of first match at position i = p/n
Comparisons for that outcome = i
Probability of failure = 1 − p
Comparisons on failure = n

Cavg(n) = (p/n) Σ(i = 1…n) i + n(1−p)
        = p(n+1)/2 + n(1−p)

If positions are not equally likely, replace p/n with their actual probabilities and sum probability × cost for each outcome. Duplicates also affect the distribution of the first matching position. An average claim without these assumptions is incomplete.

DAA · UNIT 1 · 11

Watch growth change with input size.

SOURCE DEFINITION · PDF PAGE 16

Order of growth

The order of growth describes how the running time increases as the input size 'n' grows.

The source table lists quicksort with n log n. Its average time is Θ(n log n) under suitable pivot/input assumptions, while its worst case is Θ(n²). Merge sort has Θ(n log n) worst-case time in the usual comparison model. The Tower of Hanoi needs exactly 2ⁿ − 1 moves, giving Θ(2ⁿ) growth.

DAA · UNIT 1 · 12

Separate an exact count from a growth class.

An exact expression such as 3n² + 2n + 7 counts selected operations in a model. Asymptotic notation describes how that expression behaves for sufficiently large n.

These definitions are added explanations, not quotations from the supplied PDF. For n ≥ 1, 3n² ≤ 3n² + 2n + 7 ≤ 12n², demonstrating a tight quadratic bound. Constants and lower-order terms do not change this class.

Case and notation are different ideas: “worst case” specifies which inputs are considered; O or Θ specifies a bound on the resulting cost function. O does not inherently mean worst case. A best-case function can also have an asymptotic bound.

Sequential blocks: n + n² operations have Θ(n²) growth. Nested blocks: if each of n outer iterations performs n inner operations, the total is n × n = n². Do not multiply counts just because two loops appear in the same program.

DAA · UNIT 1 · 13

Derive the count from the loop bounds.

Single loop:               Square nested loops:
for i ← 1 to n             for i ← 1 to n
    basic operation            for j ← 1 to n
                                   basic operation

Triangular nested loops:   Repeated halving:
for i ← 1 to n             value ← n
    for j ← 1 to i         while value > 1
        basic operation       value ← floor(value / 2)

Count the chosen body operation first; loop-condition checks and increments are additional operations. The source programs deliberately print body counts. At n = 1, the halving loop performs zero divisions. The triangular loop saves about half the body work of the square loop for large n, while both remain quadratic.

n = int(input())
if not 1 <= n <= 1000:
    raise ValueError("Choose n from 1 to 1000")
linear = square = triangular = halving = 0
for i in range(n):
    linear += 1
for i in range(n):
    for j in range(n):
        square += 1
for i in range(n):
    for j in range(i + 1):
        triangular += 1
i = n
while i > 1:
    halving += 1
    i //= 2
print("Linear =", linear)
print("Square =", square)
print("Triangular =", triangular)
print("Halving =", halving)

DAA · UNIT 1 · 14

Preserve the GCD. Reduce the numbers.

SOURCE DEFINITION · PDF PAGE 20

Euclid's algorithm

Euclid's algorithm is a simple and efficient method for finding the greatest common divisor GCD of two numbers.

Euclid(a, b)  // positive integers
    while b ≠ 0
        r ← a mod b
        a ← b
        b ← r
    return a

Why it works

Write a = qb + r. A common divisor of a and b divides a − qb = r. Conversely, a common divisor of b and r divides qb + r = a. Both pairs therefore have the same common divisors and the same greatest common divisor. When b becomes 0, GCD(a,0) = a.

Why it terminates and how to analyze it

Every nonzero remainder satisfies 0 ≤ r < b. The divisor decreases until a zero remainder appears. Count one remainder operation per iteration. For positive integers, the number of iterations is O(log min(a,b)) as the smaller input grows, with a constant initial allowance. This is a count of arithmetic steps; it does not assert that remainder operations on arbitrarily large integers cost constant time. Consecutive Fibonacci numbers produce many Euclidean steps.

a, b = map(int, input().split())
if a < 0 or b < 0 or (a == 0 and b == 0):
    raise ValueError("Use nonnegative inputs, not both zero")
remainders = 0
while b:
    a, b = b, a % b
    remainders += 1
print("GCD =", a)
print("Remainders =", remainders)

DAA · UNIT 1 · 15

Turn the trace into a real Python program.

Choose an example and load it into the embedded Python interpreter. Select I/O inside the compiler, check the sample STDIN, and press Run. Change the input or edit the source to explore a different case.

3 7 11 16 22 29 35 42
42

Index = 7
Comparisons = 8

def sequential_search(values, key):
    comparisons = 0
    for i in range(len(values)):
        comparisons += 1
        if values[i] == key:
            return i, comparisons
    return -1, comparisons

values = list(map(int, input().split()))
key = int(input())
index, comparisons = sequential_search(values, key)
print("Index =", index)
print("Comparisons =", comparisons)

All six programs use Python 3. Search input is one line of space-separated values, then the key on the next line. Addition and GCD read two integers on one line. Loop and summation examples read n. Python integers grow as needed: operation-count analysis here uses a unit-cost arithmetic model, while large-number arithmetic has additional bit costs. Copy a program to your own Python interpreter if you prefer.

DAA · UNIT 1 · 16

Revise. Explain. Check your understanding.

These model answers are added study material. Use the source definitions above when your question asks for the wording of a definition.

Check the key ideas