Welcome to the final section of the course! In this module, you will apply the knowledge and skills you have acquired throughout the course to complete comprehensive projects. These projects are designed to challenge your understanding of algorithm analysis and design, and to help you gain practical experience in solving complex problems.

Objective: Compare the performance of different sorting algorithms on various datasets.

Requirements:

1. Implement the following sorting algorithms:
   • Insertion Sort
   • Merge Sort
   • Quick Sort
2. Generate datasets of different sizes and characteristics (e.g., sorted, reverse sorted, random).
3. Measure and compare the time complexity and space complexity of each algorithm on these datasets.
4. Visualize the results using graphs or tables.

Steps:

1. Implement Sorting Algorithms:

   def insertion_sort(arr):
       for i in range(1, len(arr)):
           key = arr[i]
           j = i - 1
           while j >= 0 and key < arr[j]:
               arr[j + 1] = arr[j]
               j -= 1
           arr[j + 1] = key
       return arr
   
   def merge_sort(arr):
       if len(arr) > 1:
           mid = len(arr) // 2
           L = arr[:mid]
           R = arr[mid:]
   
           merge_sort(L)
           merge_sort(R)
   
           i = j = k = 0
           while i < len(L) and j < len(R):
               if L[i] < R[j]:
                   arr[k] = L[i]
                   i += 1
               else:
                   arr[k] = R[j]
                   j += 1
               k += 1
   
           while i < len(L):
               arr[k] = L[i]
               i += 1
               k += 1
   
           while j < len(R):
               arr[k] = R[j]
               j += 1
               k += 1
       return arr
   
   def quick_sort(arr):
       if len(arr) <= 1:
           return arr
       else:
           pivot = arr[len(arr) // 2]
           left = [x for x in arr if x < pivot]
           middle = [x for x in arr if x == pivot]
           right = [x for x in arr if x > pivot]
           return quick_sort(left) + middle + quick_sort(right)
   

2. Generate Datasets:

   import random
   
   def generate_datasets():
       sizes = [10, 100, 1000, 10000]
       datasets = {
           'sorted': [list(range(size)) for size in sizes],
           'reverse_sorted': [list(range(size, 0, -1)) for size in sizes],
           'random': [random.sample(range(size), size) for size in sizes]
       }
       return datasets
   

3. Measure Performance:

   import time
   
   def measure_performance():
       datasets = generate_datasets()
       results = {}
   
       for key, data in datasets.items():
           results[key] = {}
           for arr in data:
               start_time = time.time()
               insertion_sort(arr.copy())
               results[key]['insertion_sort'] = time.time() - start_time
   
               start_time = time.time()
               merge_sort(arr.copy())
               results[key]['merge_sort'] = time.time() - start_time
   
               start_time = time.time()
               quick_sort(arr.copy())
               results[key]['quick_sort'] = time.time() - start_time
   
       return results
   

4. Visualize Results:

   import matplotlib.pyplot as plt
   
   def visualize_results(results):
       for key, data in results.items():
           plt.figure(figsize=(10, 5))
           plt.title(f'Performance of Sorting Algorithms on {key} Data')
           plt.xlabel('Dataset Size')
           plt.ylabel('Time (seconds)')
           for alg, times in data.items():
               plt.plot([10, 100, 1000, 10000], times, label=alg)
           plt.legend()
           plt.show()
   
   results = measure_performance()
   visualize_results(results)
   

Objective: Implement and compare Dijkstra's and Floyd-Warshall algorithms to find the shortest path in a graph.

Requirements:

1. Implement Dijkstra's algorithm.
2. Implement Floyd-Warshall algorithm.
3. Create a graph with weighted edges.
4. Compare the performance and correctness of both algorithms.

Steps:

1. Implement Dijkstra's Algorithm:

   import heapq
   
   def dijkstra(graph, start):
       queue = []
       heapq.heappush(queue, (0, start))
       distances = {vertex: float('infinity') for vertex in graph}
       distances[start] = 0
   
       while queue:
           current_distance, current_vertex = heapq.heappop(queue)
   
           if current_distance > distances[current_vertex]:
               continue
   
           for neighbor, weight in graph[current_vertex].items():
               distance = current_distance + weight
   
               if distance < distances[neighbor]:
                   distances[neighbor] = distance
                   heapq.heappush(queue, (distance, neighbor))
   
       return distances
   

2. Implement Floyd-Warshall Algorithm:

   def floyd_warshall(graph):
       distance = {i: {j: float('infinity') for j in graph} for i in graph}
       for vertex in graph:
           distance[vertex][vertex] = 0
           for neighbor, weight in graph[vertex].items():
               distance[vertex][neighbor] = weight
   
       for k in graph:
           for i in graph:
               for j in graph:
                   if distance[i][j] > distance[i][k] + distance[k][j]:
                       distance[i][j] = distance[i][k] + distance[k][j]
   
       return distance
   

3. Create a Graph:

   graph = {
       'A': {'B': 1, 'C': 4},
       'B': {'A': 1, 'C': 2, 'D': 5},
       'C': {'A': 4, 'B': 2, 'D': 1},
       'D': {'B': 5, 'C': 1}
   }
   

4. Compare Performance and Correctness:

   import time
   
   def compare_algorithms(graph):
       start_time = time.time()
       dijkstra_result = dijkstra(graph, 'A')
       dijkstra_time = time.time() - start_time
   
       start_time = time.time()
       floyd_warshall_result = floyd_warshall(graph)
       floyd_warshall_time = time.time() - start_time
   
       print("Dijkstra's Algorithm Result:", dijkstra_result)
       print("Dijkstra's Algorithm Time:", dijkstra_time)
       print("Floyd-Warshall Algorithm Result:", floyd_warshall_result)
       print("Floyd-Warshall Algorithm Time:", floyd_warshall_time)
   
   compare_algorithms(graph)
   

Objective: Solve a complex problem using dynamic programming.

Requirements:

1. Choose a problem that can be solved using dynamic programming (e.g., Knapsack problem, Longest Common Subsequence).
2. Implement the solution using dynamic programming.
3. Analyze the time and space complexity of the solution.

Steps:

1. Choose a Problem: Let's choose the Longest Common Subsequence (LCS) problem.

2. Implement the Solution:

   def lcs(X, Y):
       m = len(X)
       n = len(Y)
       L = [[None]*(n+1) for i in range(m+1)]
   
       for i in range(m+1):
           for j in range(n+1):
               if i == 0 or j == 0:
                   L[i][j] = 0
               elif X[i-1] == Y[j-1]:
                   L[i][j] = L[i-1][j-1] + 1
               else:
                   L[i][j] = max(L[i-1][j], L[i][j-1])
   
       return L[m][n]
   
   X = "AGGTAB"
   Y = "GXTXAYB"
   print("Length of LCS is", lcs(X, Y))
   

3. Analyze Complexity:

   • Time Complexity: O(m*n), where m and n are the lengths of the two sequences.
   • Space Complexity: O(m*n) for the table used to store the lengths of LCS.

Congratulations on completing the final projects! These projects have provided you with hands-on experience in implementing, analyzing, and comparing different algorithms. You have also learned how to visualize and interpret the performance of algorithms, which is a crucial skill in algorithm analysis and design.

By completing these projects, you have demonstrated your ability to apply theoretical concepts to practical problems, which is essential for any professional working with algorithms. Keep practicing and exploring new problems to further enhance your skills and knowledge in this field. Good luck!