Master of Data Science
CSC 821 : Design and Analysis of Algorithms
(Group 1 ASSIGNMENT)
👥 Group Members
1. Miriam Mutisya
2. Jennifer Maiyo
3. Samuel Ouma Othieno
4. Kevin Ochieng
5. Paul Omari
6. Evans Obonyo
7. Elijah Nyakundi
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 1
GROUP ASSIGNMENT
Module 2: Designing and
Analysing Algorithms
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 2
INTRODUCTION
Designing the Algorithm
Design Strategies
Brute Force
Greedy algorithm
Divide and Conquer
Dynamic programming (DP)
Algorithm Analysis
Time complexity
Space complexity
Big O notation
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 3
Designing the Algorithm
This is the core step where the actual algorithm is developed. The key considerations
include:
Choosing the Right Approach: Based on the problem type, decide on an approach (e.g., divide
and conquer, dynamic programming, greedy algorithms).
Step-by-Step Breakdown: Break down the problem into smaller, manageable tasks and outline
the steps needed to solve each.
Pseudocode: Write the algorithm in pseudocode, which is a high-level description of the steps in a
format that is independent of any specific programming language. Alternatively, you can use a
flowchart to represent the algorithm
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 4
Pseudocode to find the maximum number in a list:
FUNCTION FindMaximum(numbers)
// Step 4: Return the maximum
// Step 1: Validate input
RETURN max
IF numbers is empty THEN
END FUNCTION
RETURN "Error: List is empty"
// Example usage
END IF
INPUT numbers
// Step 2: Initialize maximum
OUTPUT FindMaximum(numbers)
SET max = numbers[0]
// Step 3: Iterate through the list
FOR each number IN numbers DO
IF number > max THEN
max = number
END IF
END FOR
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 5
Design Principles
To design effective algorithms, certain strategies can help break down complex problems
into manageable parts.
Common problem-solving strategies include:
Divide and Conquer: Dividing the problem into smaller, similar sub-problems, Solving each sub-
problem recursively and Combining the solutions of sub-problems into a final solution.
Greedy Algorithms: Greedy strategies make the locally optimal choice at each step with the hope
of finding a global optimum.
Dynamic Programming (DP): Dynamic Programming is useful when a problem involves
overlapping sub-problems and optimal substructure.
Brute force: Examines every possible solution to a problem.
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 6
Design Strategies - Brute Force Algorithms:
Approach: Examines every possible solution to a problem.
Implementation: Typically straightforward to implement, but computationally
expensive.
Time Complexity: Often proportional to the size of the search space, which can grow
exponentially with the input.
Guaranteed Solution: If a solution exists, a brute force algorithm will eventually find
it.
Example: Finding the maximum element in an array by comparing all elements.
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 7
Design Strategies - Greedy Algorithms
Approach:
Makes locally optimal choices at each step, hoping to find a globally optimal solution.
Implementation:
Can be faster than brute force algorithms, especially for certain problems.
Time Complexity:
Varies depending on the problem, but often has a lower time complexity than brute
force.
Guaranteed Solution:
Not always guaranteed to find the optimal solution for all problems.
Example:
Making change with the fewest coins by always choosing the largest denomination
possible.
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 8
Design Strategies - Divide and
Conquer
Key Steps:
1.1. Divide:
The algorithm first divides the original problem into
smaller, non-overlapping subproblems.
2.2. Conquer:
Each subproblem is then solved recursively, or if small
enough, solved directly.
3.3. Combine:
Finally, the solutions to the subproblems are combined to
produce the solution to the original problem.
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 9
Design Strategies - Dynamic Programming (DP)
Dynamic Programming is useful when a problem involves overlapping sub-problems
and optimal substructure.
How It Works:
Break the problem into overlapping sub-problems.
Solve each sub-problem once and store its result.
Reuse stored results instead of recalculating.
Real-World Example: Calculating Fibonacci numbers using stored results.
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 10
Fibonacci sequence -
Example
Fibonacci sequence is a series of numbers where each number is the sum
of the two before it:
1. Manual Calculation Example
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 11
Algorithm Analysis
This involves evaluating the performance and efficiency of an algorithm.
It helps to understand how the algorithm scales with input size in terms of
time and space resources.
In the analysis of algorithms, key concepts include
Time complexity: how fast it runs
Space complexity: how much memory it needs
Big O notation: mathematical tool to describe upper bounds of
growth
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 12
Time Complexity
Time complexity measures how the running time of an algorithm changes with the size of the input.
It helps to estimate how long an algorithm takes to complete based on the input size.
Time complexity is often expressed as a function of the input size n .
For example, if an algorithm takes 2n +3 steps for input size , its time complexity is O(n).
Example: Finding the maximum value in an unsorted array.
def find_max(arr):
max_value = arr[0]
for i in range(1, len(arr)):
if arr[i] > max_value:
max_value = arr[i]
return max_value
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 13
Linear Search Time complexity
examples
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 14
Space Complexity
Space complexity measures how the amount of memory an algorithm uses
changes with the size of the input.
It includes memory for variables and any extra data structures used.
Example 3: Creating a List of Integers
def create_list(n):
lst = []
for i in range(n):
[Link](i)
return lst
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 15
Big O Notation and Its Significance
Big O notation describes the upper bound of an algorithm’s time or space complexity.
It represents the worst-case scenario, helping to compare algorithm efficiency.
It allows comparison between different algorithms.
Helps predict how an algorithm scales with large inputs.
Indicates the maximum resources (time or space) required.
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 16
Big O Notation Example;
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 17
Big O Notation Example Cont’d;
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 18
Quick Comparison Table
Algorithm Strategy Time Complexity Space Applications
Complexity
Linear Search Brute Force O(n) O(1) Small data
Binary Search Divide & Conquer O(log n) O(1) Sorted data
Merge Sort Divide & Conquer O(n log n) O(n) Sorting
Quick Sort Divide & Conquer O(n log n) avg, O(n²) worst O(log n) Sorting
Dijkstra’s Greedy O(V²) / O(E log V) O(V) Shortest path
Algorithm
Fibonacci (DP) Dynamic O(n) O(n) Optimization
Programming
N-Queens Backtracking O(n!) O(n²) Puzzles
Randomized Randomized O(n log n) O(log n) Sorting
QuickSort
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 19
9/22/2025 THE OPEN UNIVERSITY OF KENYA (OUK) -2025 20