Understanding Algorithms and Flowcharts

What is an Algorithm?

• An algorithm constitutes a step-by-step procedure designed to perform a specific task or solve a particular problem.
• It requires defined inputs and outputs.
• It needs a finite number of unambiguous steps.
• Effectiveness in achieving the desired outcome is essential.

Characteristics of Good Algorithms

• Correctness requires generating the correct output for any valid input.
• Efficiency involves using resources like time and memory efficiently.
• Finiteness means it should terminate after a finite number of steps.
• Clarity requires being easy to understand and implement.
• Input/Output Specification needs inputs and outputs to be well-defined.

Algorithm Example

• Step 1: Start
• Step 2: Declare variables num1, num2, and sum.
• Step 3: Read values for num1 and num2.
• Step 4: Add num1 and num2, assigning the result to the variable sum.
• Step 5: Display sum.
• Step 6: Stop.

What is a Flowchart?

• A flowchart is a graphical representation of a process or algorithm.
• It employs different shapes and lines to show the steps.
• It provides a visual way to understand the flow and logic of a system.
• Facilitates easier analysis and improvement.

Definition of Pseudocode

• Pseudocode is a high-level description of an algorithm or a computer program.
• It utilizes a combination of natural language.
• Includes some programming language-like constructs.
• It is not tied to any specific programming language syntax.
• It outlines the logic of a program without being overly concerned with implementation details.

Efficiency of an Algorithm

• Time Complexity measures the amount of time an algorithm requires to complete its task as a function of the input size.
• Space Complexity evaluates the amount of memory or storage required by an algorithm related to the input size.

Worst, Best, and Average Case Efficiencies

• Worst-case efficiency refers to the maximum amount of time or resources an algorithm requires for any input of a given size.
• Best-case efficiency refers to the minimum amount of time or resources an algorithm requires for any input of a given size.
• Average-case efficiency is the measure of an algorithm's performance across all possible inputs.
• Considers the probability distribution of inputs.

Algorithm of Sequential Search

• function sequentialSearch(list, target):
  • This defines a function named sequentialSearch that takes a list and a target value as input.
• for i = 0 to length(list) - 1:
• This starts a loop that iterates through each element in the list.
• The loop variable i starts at 0 and goes up to the last index of the list.
• if list[i] equals target:
• This checks if the current element of the list (list[i]) is equal to the target value.
• return i:
• If the current element is equal to the target, this statement returns the index i of the found element and exits the function.
• return -1:
• If the loop completes without finding the target in the list, this statement returns -1, indicating that the target was not found.
• Worst case: Cworst(n) = n
• Best case: Cbest(n) = 1
• Average case: Cavg(n) = (n+1)/2, for a successful search
• Average case: Cavg(n) = n, for an unsuccessful search

Asymptotic Notations

• Big-O Notation represents the upper bound of the running time of an algorithm and gives the worst-case complexity.
• A function t(n) is in O(g(n)) if t(n) ≤ c * g(n) for all n ≥ n0.
• Big-Ω Notation represents the lower bound of the running time of an algorithm, providing the best-case complexity.
• t(n) ≥ c * g(n) for all n ≥ n0.
• Big-Θ Notation represents both the upper and lower bounds of the running time.
• It’s used for analyzing the average-case complexity.
• c₂ * g(n) ≤ t(n) ≤ c₁ * g(n) for all n ≥ n0.

General Plan for Analyzing Efficiency of a Non-Recursive Algorithm

• Decide on parameter n indicating input size.
• Identify the algorithm’s basic operation.
• Check whether the number of times the basic operation is executed depends only on the size of an input.
• If it also depends on some additional property, determine worst, average, and best cases for input of size n.
• Set up a sum for the number of times the basic operation is executed.
• Simplify the sum using standard formulas and rules.

Example 1: Maximum Element

• function findMax(arr):
  • The function findMax takes an array arr as input.
• maxElement = arr[0]:
  • Initializes maxElement to the first element of the array.
• for i = 1 to length(arr) - 1:
  • A loop iterates through the rest of the array.
• if arr[i] > maxElement:
  • Checks if the current element arr[i] is greater than maxElement.
• maxElement = arr[i]:
  • If it is, maxElement is updated to the current element.
• return maxElement:
  • After iterating through the array, the function returns the maximum element.
• T(n) = Θ(n) comparisons

Example 2: Matrix Multiplication

• function matrixMultiplication(matrixA, matrixB):
  • This defines a function called matrixMultiplication that takes two matrices, matrixA and matrixB, as input.
• for i = 0 to rows(matrixA) - 1:
  • This starts a loop that iterates through each row of matrixA.
• for j = 0 to columns(matrixB) - 1:
  • Nested inside the first loop, this loop iterates through each column of matrixB.
• resultMatrix[i][j] = 0:
  • Inside the nested loops, this line initializes each element of the resultMatrix to 0.
• for k = 0 to columns(matrixA) - 1:
  • This innermost loop iterates over the columns of matrixA.
• resultMatrix[i][j] += matrixA[i][k] * matrixB[k][j]:
  • This line calculates the dot product of the i-th row of matrixA and the j-th column of matrixB and adds it to resultMatrix[i][j].
• return resultMatrix:
  • After all calculations, this line returns the computed resultMatrix.
• T(n) = Θ(n^3) multiplications

Example 3: Element Uniqueness Problem

• function areElementsUnique(arr):
• Defines a function that takes an array arr as input.
• n = length(arr):
• Assigns the length of the array to the variable n.
• for i from 0 to n - 1:
• Outer loop that iterates through each element of the array.
• for j from i + 1 to n - 1:
• Inner loop that iterates through the remaining elements of the array.
• if arr[i] equals arr[j]:
• Checks if the current element arr[i] is equal to any of the remaining elements arr[j].
• return false:
• If a duplicate is found, the function immediately returns false.
• return true:
• If the function iterates through all pairs of elements without finding a duplicate, it returns true.
• T(n) = Θ(n^2) comparisons

General Plan for Analyzing Efficiency of a Recursive Algorithm

• Decide on parameter n indicating input size.
• Identify the algorithm’s basic operation.
• Check whether the number of times the basic operation is executed depends only on the size of an input.
• If it also depends on some additional property, determine worst, average, and best cases for input of size n.
• Set up a recurrence relation for the number of times the basic operation is executed.
• Solve the recurrence by backward substitutions or another method.

Solving the Recurrence for M(n)

• Demonstrates solving a recurrence relation M(n) = M(n-1) + 1 with M(0) = 0 using backward substitution.
• Expands M(n-1), M(n-2), and so on to find a pattern.
• Generalizes the pattern to M(n) = M(n-i) + i.
• Substitutes M(0) = 0 to get M(n) = n.
• The method used is backward substitution.

The Tower of Hanoi: Algorithm

• Algorithm hanoi(n,from,to,temp):
• This defines the hanoi algorithm, which takes n (number of disks), from (source peg), to (destination peg), and temp (temporary peg) as inputs.
• If(n>c):
• There seems to be a typo here as the condition (n>c) is unclear. Assuming c should be 1, the condition checks if the number of disks n is greater than 1.
• hanoi(n-1,from,temp,to):
• Recursively calls the hanoi function to move the top n-1 disks from the source peg to the temporary peg, using the destination peg as the auxiliary peg.
• move disk n:
• Moves the largest disk (disk n) from the source peg to the destination peg.
• hanoi(n-1,temp,to,from):
• Recursively calls the hanoi function again to move the n-1 disks from the temporary peg to the destination peg, using the source peg as the auxiliary peg.
• Recurrence relation: M(n) = M(n-1) + 1 + M(n-1) for n > 1
• This defines the number of moves M(n) needed to solve the Tower of Hanoi problem with n disks, which equals to moving n-1 disks to the temporary peg, moving the nth disk and, moving the discs from the temporary to the destination peg.
• = 2 M(n-1) + 1:
• Simplify recurrence relation.
• M(1) = 1 (one disk):
• This is the base case for the recurrence relation, stating that it takes 1 move to move 1 disk from the source peg to the destination peg.

The Tower of Hanoi: Analysis

• Provides a manual step-by-step analysis of Tower of Hanoi.
• Calculates M(n) = 2^(n-1).