Assignment #1 For Algorithms

Task 1: Fibonacci Series

• Implement the Fibonacci series using recursion.
• Implement the Fibonacci series using divide and conquer (matrix multiplication) .
• Implement the Fibonacci series using dynamic programming

Task 2: Search Algorithms

• Sequential Search:
• Recursive Sequential Search
• Binary Search
• Recursive Binary Search

Task 3: Heap, Priority Queue and Heap Sort

1. Implement a Heap:
   • Define a class/structure for the heap.
   • Implement methods for inserting an element and maintaining the heap property (heapify).
   • Implement methods to extract the maximum and minimum from the heap.
2. Implement a Priority Queue:
   • Use the heap implementation (from step 1) to build a priority queue.
   • Define methods for inserting an element with a priority and extracting the highest priority element.
   • Ensure the insertion maintains the heap property.
3. Implement Heap Sort:
   • Utilize your heap implementation to sort an array.
   • Build a max heap from the array and repeatedly extract the max element from the heap and rebuild it until the array is sorted