- Data Structures and Algorithms Final Project
This project involves a series of tasks aimed at demonstrating proficiency in various data structures and algorithms, including linked lists, recursion, graph algorithms, and more. Each task is implemented in Python and includes visualizations and analyses to support the solutions.
The project consists of the following tasks:
- Task 1: Implement and manipulate singly linked lists, including reversing, sorting, and merging.
- Task 2: Use recursion to create and visualize the Pythagorean tree fractal.
- Task 3: Implement Dijkstra's algorithm using a binary heap for finding the shortest paths in a weighted graph.
- Task 4: Visualize a binary tree using the provided Python code.
- Task 5: Implement and visualize tree traversal algorithms (DFS and BFS) using stack and queue.
- Task 6: Solve a food selection problem using greedy and dynamic programming approaches.
- Task 7: Simulate dice rolls using the Monte Carlo method and compare results with analytical probabilities.
Three operations on singly linked lists:
- Reversing a Singly Linked List: Develop a function that reverses the order of nodes in a singly linked list by changing the links between nodes.
- Sorting a Singly Linked List: Implement a sorting algorithm (e.g., merge sort) for singly linked lists. This requires functions to split the list, merge sorted sublists, and recursively sort the sublists.
- Merging Two Sorted Singly Linked Lists: Create a function that merges two sorted singly linked lists into a single sorted list. This will involve comparing nodes from both lists and linking them in the correct order.
- Implement Recursion for Fractal Generation: Write a recursive function to create the Pythagorean tree fractal. The function should draw each branch and recursively call itself to draw the smaller branches.
- Visualize the Fractal: Use a plotting library (e.g., Matplotlib) to visualize the fractal. The user should be able to specify the recursion depth to see different levels of the fractal.
- Implement Dijkstra's Algorithm: Develop the algorithm to find the shortest paths from a starting vertex to all other vertices in a weighted graph using a priority queue (heapq).
- Graph Representation: Represent the graph using a dictionary where keys are vertices and values are dictionaries of neighbors and edge weights.
- Calculate Distances: Calculate and return the shortest distances from the starting vertex to all other vertices.
- Build a Binary Tree: Write a function to construct a binary tree up to a specified depth.
- Visualize the Tree: Use the provided code to visualize the binary tree. Each node should be represented with a unique identifier and visually arranged to reflect the tree structure.
- Implement DFS and BFS Traversals: Write functions to perform depth-first search (DFS) and breadth-first search (BFS) on the binary tree. Use a stack for DFS and a queue for BFS.
- Color Nodes Based on Traversal Order: Assign a unique color to each node based on its position in the traversal order. Use a gradient of colors to represent the traversal sequence from start to finish.
- Visualize Traversals: Modify the tree visualization to show the nodes with their assigned colors, reflecting the traversal order.
- Solve the Food Selection Problem Using a Greedy Algorithm: Implement a greedy algorithm that selects food items to maximize the calorie-to-cost ratio without exceeding the budget.
- Solve the Same Problem Using Dynamic Programming: Develop a dynamic programming solution to find the optimal set of food items that maximizes the total calories within the given budget.
- Compare Results: Compare the solutions obtained from the greedy algorithm and the dynamic programming approach.
- Simulate Dice Rolls: Write a program to simulate rolling two dice a large number of times. Record the sum of the numbers rolled.
- Calculate Probabilities: Determine the probability of each possible sum (from 2 to 12) based on the simulation results.
- Compare with Analytical Probabilities: Compare the simulated probabilities with the analytical probabilities provided. Visualize the results using a plot to show how closely the simulation matches the theoretical values.
The results include:
- Correct implementation of linked list operations.
- Visualization of the Pythagorean tree fractal at different recursion depths.
- Successful calculation of shortest paths using Dijkstra's algorithm.
- Visualization of the binary tree and traversal orders.
- Comparison of solutions from greedy and dynamic programming algorithms for the food selection problem.
- Probability distribution of dice roll sums from the Monte Carlo simulation compared with analytical probabilities.
| Sum | Analytical P (%) | Simulation P (%) | Difference |
|---|---|---|---|
| 2 | 2.78 | 2.885 | 0.105 |
| 3 | 5.56 | 5.601 | 0.041 |
| 4 | 8.33 | 8.297 | -0.033 |
| 5 | 11.11 | 11.121 | 0.011 |
| 6 | 13.89 | 13.949 | 0.059 |
| 7 | 16.67 | 16.533 | -0.137 |
| 8 | 13.89 | 13.876 | -0.014 |
| 9 | 11.11 | 11.107 | -0.003 |
| 10 | 8.33 | 8.371 | 0.041 |
| 11 | 5.56 | 5.519 | -0.041 |
| 12 | 2.78 | 2.741 | -0.039 |
This project demonstrates various data structures and algorithms, including their implementation, visualization, and analysis. Each task provides a practical application of these concepts, showcasing their utility and performance in different scenarios.
This project demonstrates various data structures and algorithms, including their implementation, visualization, and analysis. Each task provides a practical application of these concepts, showcasing their utility and performance in different scenarios.