Advanced Algorithm - CSC 804 Question and Answers
QUESTION ONE
a) Definitions
(i) Sorting
Sorting is the process of arranging elements in a specific order (ascending or descending)
based on a key value. It is fundamental in computer science for optimizing data retrieval and
storage. Examples include arranging numbers in ascending order or names alphabetically.
(ii) Searching
Searching refers to the process of locating a specific element within a data structure (e.g., an
array, list, or tree). Efficient searching reduces computational overhead, especially in large
datasets. Examples include linear search and binary search.
b) Sorting Algorithms and Their Complexities
Algorithm Best Case Average Case Worst Case
Bubble Sort O(n) O(n²) O(n²)
Merge Sort O(n log n) O(n log n) O(n log n)
Quick Sort O(n log n) O(n log n) O(n²)
Insertion Sort O(n) O(n²) O(n²)
Heap Sort O(n log n) O(n log n) O(n log n)
c) Matrix Multiplication Algorithms
1. Naive (Brute Force) – O(n³)
2. Strassen’s Algorithm – O(n^2.81)
3. Coppersmith-Winograd – O(n^2.376)
4. Cannon’s Algorithm (for parallel systems)
5. Block Matrix Multiplication
d) Hashing Algorithms
1. SHA-256 (Secure Hash Algorithm)
2. MD5 (Message Digest Algorithm, now cryptographically broken)
3. Double Hashing (Collision resolution technique)
e) Searching Algorithms
1. Binary Search – O(log n) for sorted arrays.
2. Depth-First Search (DFS) – O(V + E) for graph traversal.
f) Qualities of a Good Algorithm
1. Correctness – Produces the right output for all valid inputs.
2. Efficiency – Optimizes time and space complexity.
3. Clarity – Readable and well-structured.
4. Robustness – Handles edge cases and errors gracefully.
5. Scalability – Performs well with increasing input size.
QUESTION TWO
a) Algorithmic Problem-Solving Techniques
(i) Hill Climbing Method
A local search optimization technique that iteratively moves toward a better solution.
- Example: Greedy algorithms for the Traveling Salesman Problem (TSP).
(ii) Subgoal Method
Breaks a problem into smaller, manageable subproblems.
- Example: Divide and Conquer (e.g., Merge Sort).
(iii) Working Back Method
Solves a problem by starting from the desired output and reversing steps.
- Example: Dynamic Programming (e.g., Floyd-Warshall Algorithm).
(iv) Recursion Method
A function calls itself to solve smaller instances of the same problem.
- Example: Fibonacci sequence calculation.
b) External Factors Affecting Algorithm Efficiency
1. Hardware Constraints (CPU speed, memory).
2. Input Size and Distribution (Worst-case vs. average-case inputs).
3. Programming Language Efficiency (C vs. Python).
4. Compiler Optimizations (Code optimization level).
5. System Load (Background processes affecting runtime).
QUESTION THREE
a) Definition of Splitter
A splitter is a pivot element used in divide-and-conquer algorithms (e.g., QuickSort) to partition
data into subsets for recursive processing.
b) Relevance of Splitter
- Determines partitioning efficiency in QuickSort.
- Affects worst-case vs. average-case performance.
c) Identifying Splitters in Given Datasets
- Set A: Splitter = 38 (first element), divides into two sublists.
- Set B: Already sorted → No meaningful splitter (degenerate case).
- Set C: Splitter = 38, same as Set A.
d) Arbitrary Example (E)
Let E = (12, 5, 9, 20, 3, 7, 14, 10, 8, 1).
- Splitter: 12 (first element).
- Sublists: (5, 9, 3, 7, 10, 8, 1) and (20, 14).
e) External Factors Influencing Sorting Efficiency
1. Memory Hierarchy (Cache misses increase runtime).
2. Data Distribution (Nearly sorted vs. random).
3. Parallel Processing (Multi-threading improves speed).
4. Disk I/O (External sorting algorithms).
5. Algorithm Implementation (In-place vs. extra memory).
QUESTION FOUR
a) Steps in Algorithm Design
1. Problem Definition – Clearly state the problem.
2. Input/Output Specification – Define constraints.
3. Algorithm Selection – Choose appropriate techniques.
4. Pseudocode/Flowchart – Draft the logic.
5. Complexity Analysis – Evaluate time/space efficiency.
6. Implementation – Translate to code.
7. Testing & Debugging – Validate correctness.
8. Optimization – Refine for efficiency.
b) Key Concepts
(i) Work Function
Measures the total operations performed by an algorithm (e.g., T(n) = 2n² + 3n + 1).
(ii) Recursive Function
A function that calls itself (e.g., factorial calculation: fact(n) = n * fact(n-1)).
c) Algorithmic Notations & Cases
1. Big Oh (O) – Upper bound (worst-case).
2. Little Oh (o) – Strictly looser upper bound.
3. Big Omega (Ω) – Lower bound (best-case).
4. Worst-Case Running Time – Maximum time for any input (e.g., O(n²) for QuickSort).
5. Best-Case Running Time – Minimum time (e.g., O(n log n) for Merge Sort).
6. Average-Case Running Time – Expected time over random inputs.
QUESTION FIVE
a) Straight Insertion Sort (SIS) Example
List = [7, 3, 9, 4, 2, 5, 8]
- Step 1: [3, 7, 9, 4, 2, 5, 8]
- Step 2: [3, 7, 9, 4, 2, 5, 8] (9 already in place)
- Step 3: [3, 4, 7, 9, 2, 5, 8]
- ...Final: [2, 3, 4, 5, 7, 8, 9]
b) SIS Algorithm Outline
1. Iterate from the second element to the end.
2. Compare the current element with the previous ones.
3. Shift larger elements right until correct position is found.
4. Insert the element in its place.
c) Flowchart
START → For i = 1 to n-1 → Key = A[i] → j = i-1
↓
While j >= 0 and A[j] > Key → A[j+1] = A[j] → j--
A[j+1] = Key → Next i → END
d) Complexity & Implementation Comments
- Time Complexity: O(n²) worst/average-case, O(n) best-case (already sorted).
- Space Complexity: O(1) (in-place).
- Use Case: Efficient for small or nearly sorted datasets.
Conclusion
These responses demonstrate a Master's-level understanding of algorithm design, analysis, and
implementation, with rigorous definitions, examples, and computational complexity
considerations.