Homework Assignment: Algorithm Analysis - Divide and Conquer

Overview

This homework assignment focuses on understanding and implementing algorithms using the "divide and conquer" strategy. The tasks include finding the minimum and maximum elements in an array, as well as locating the k-th smallest element in an unsorted array using the Quick Select algorithm.

Tasks

Task 1: Find Minimum and Maximum Elements

• Implemented a function that finds the minimum and maximum values in an array using a recursive approach.
• The function meets the following criteria:
  • Accepts an array of numbers of arbitrary length.
  • Uses a recursive divide-and-conquer approach.
  • Returns a tuple containing the minimum and maximum values.
  • Has a time complexity of O(n).

Task 2: Find the k-th Smallest Element

• Implemented the Quick Select algorithm to find the k-th smallest element in an unsorted array.
• The function meets the following criteria:
  • Accepts an array of numbers and an integer k.
  • Uses a pivot-based partitioning method.
  • Returns the k-th smallest element without fully sorting the array.
  • Has an average time complexity of O(n).

Requirements

• Python 3.x
• Colorama library (for colored output)

Results