Algorithm Design
Uploaded by
tatendajairosmazanaAlgorithm Design
Uploaded by
tatendajairosmazanaAlgorithm Design & Data Structures — What you need to be
able to do
1) Analyse algorithms for a given situation
You should be able to:
Understand what the algorithm must accomplish (inputs, outputs, constraints).
Determine the time complexity (e.g., O(n)O(n)O(n), O(nlogn)O(n\log n)O(nlogn),
O(n2)O(n^2)O(n2)).
Determine the space complexity (extra memory used).
Use Big-O reasoning such as:
o Best / average / worst case
o Loops (linear vs nested)
o Recursion patterns
Explain performance clearly (why it’s O(n2)O(n^2)O(n2), etc.).
2) Design algorithms for a given situation
You should be able to:
Choose an appropriate approach (brute force, greedy, divide-and-conquer, dynamic
programming).
Write an algorithm in steps (often pseudocode).
Ensure it works correctly (correctness reasoning).
Improve efficiency when possible.
Handle edge cases (empty input, one element, duplicates, etc.).
3) Demonstrate familiarity with standard algorithms
You should be able to recognize/use and explain common algorithms such as:
Searching: Linear search, Binary search
Sorting: Bubble, Selection, Insertion, Merge, Quick, Heap sort
Graph algorithms: BFS, DFS, Dijkstra (shortest path), MST (Prim/Kruskal)
Greedy / DP examples: coin change, knapsack (DP), scheduling problems (greedy)
(Your teacher/exam may specify which ones are required—tell me and I’ll tailor a study list.)
4) Distinguish between dynamic and static data structures
This is a key concept.
Static data structures
Size is fixed at the time of creation.
Cannot easily grow/shrink during execution.
Example: Array (in languages with fixed-size arrays)
Characteristics:
Less overhead for managing memory
But can waste space or overflow if the size is underestimated
Dynamic data structures
Size can change during execution.
Memory is allocated/deallocated as needed.
Example: Linked list, dynamic arrays (e.g., vector/list), trees built with nodes
Characteristics:
More flexible
Usually more overhead than arrays (extra pointers / memory management)
(a) Describe an algorithm for using the tree to read the names in alphabetic order
To read the names stored in a tree in alphabetical order, we use an in-order traversal of the tree.
First, we start from the root node and recursively visit the left subtree, because in a binary
search tree all names in the left subtree are alphabetically smaller than the current node’s name.
After finishing the left subtree, we output (print) the name stored in the current node. Then we
recursively visit the right subtree, where all names are alphabetically greater than the current
node. By repeating this process for every node, the names are visited and printed from smallest
to largest, which means they appear in alphabetical order.
(b) write an algorithm, in pseudocode, of a program that accepts any 200 positive numbers
and displays their sum.
SUM-200-POSITIVE()
sum ← 0
FOR i ← 1 TO 200 DO
REPEAT
READ x
UNTIL x > 0
sum ← sum + x
END FOR
PRINT sum
END
sum ← 0
This sets up a variable sum to store the running total. It starts at 0.
FOR i ← 1 TO 200 DO
This loop runs exactly 200 times. Each time through the loop, we will read one positive number.
REPEAT … UNTIL x > 0
This part keeps asking the user for input until the input x is positive.
It reads x using READ x.
After each read, it checks the condition x > 0.
If x is not greater than 0 (so it’s 0 or negative), it repeats and reads again.
This guarantees that the program only accepts positive numbers into the sum.
sum ← sum + x
Once a valid positive number x is entered, it adds x to the running total sum.
END FOR
The loop finishes after 200 valid positive numbers have been added.
PRINT sum
Finally, the program outputs the total sum of those 200 positive numbers.
END
Marks the end of the algorithm.
(c) Explain why database design is important
Database design is important because it determines how efficiently and correctly data is
stored, organized, and accessed.
Accuracy & fewer errors: A good design reduces duplication and prevents inconsistent
data (for example, the same person’s details being entered differently in different places).
Efficient storage: It uses space better by structuring tables and relationships properly, so
the database doesn’t waste memory.
Fast queries and retrieval: Well-designed data makes it quicker to search, sort, and
generate reports—because data is stored in a logical way.
Data security and control: Good design supports proper user access (e.g., which
tables/records users can view or change) and helps protect sensitive information.
Consistency and reliability: Clear relationships (like primary keys and foreign keys)
ensure data stays linked correctly, even as the database grows.
Scalability and maintainability: With a strong design, it’s easier to update the system,
add new features, and handle more data without major rewriting.
(d) Explain the following:
Step-by-Step Dry Run
1. Initialization
o Read N=5
o Set M=1, F=1
2. Iteration 1
o Add 1 to M: M=2
o Update F=F×M=1×2=2
o Check: M=N? → 2≠5 → Loop continues
3. Iteration 2
o Add 1 to M: M=3
o Update F=2×3=6
o Check: M=N? → 3≠5 → Loop continues
4. Iteration 3
o Add 1 to M: M=4
o Update F=6×4=24
o Check: M=N? → 4≠5 → Loop continues
5. Iteration 4
o Add 1 to M: M=5
o Update F=24×5=120
o Check: M=N? → 5=5 → YES → Print F=120 → Stop
Completed Trace Table
NM F M = N? Output
51 1 No -
52 2 No -
53 6 No -
5 4 24 No -
N M F M = N? Output
5 5 120 Yes 120
✅ Final Answer: When N=5, the algorithm outputs 120, which is 5!.
Sub Main()
Dim rand As New Random
Dim face As Integer
Dim count As Integer
For i = 1 To 20
face = [Link](1, 7)
If face = 4 Then
count += 1
End If
Next
[Link]("4 appeared {0} times", count)
[Link]()
End Sub