Jenkins_Antonio_C950T2

docx

School

Western Governors University *

*We aren’t endorsed by this school

Course

278

Subject

Computer Science

Date

Jan 9, 2024

Type

docx

Pages

Uploaded by CoachSnake4721

Antonio B. Jenkins WGU C950 09/07/2023 A. Algorithm Choice The chosen algorithm for this program is the "Greedy Algorithm" using a nearest-neighbor approach. This algorithm allows us to find a reasonably efficient route by selecting the closest next node (or delivery point) at each step, considering various constraints such as maximum package count, limited driver availability, and special notes associated with packages. The algorithm prioritizes immediate gains and makes a series of locally optimal choices to form a global solution for the delivery problem. While it may not always provide the absolute best route, it is computationally less demanding and can easily adapt to real-time changes, such as the correction of the address for package #9 at 10:20 a.m. (Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C., 2009). B. Data Structure The Hash Table is chosen as the primary data structure for storing package information. It effectively supports quick insertion, deletion, and search operations with an average time complexity of O (1) (Cormen et al., 2009). 1. Relationship Between Data Components: The hash table uses the unique "Package ID" as the key. Each key maps to a value, which in this case, is another hash table. The inner hash table contains attributes such as 'delivery address,' 'delivery deadline,' 'delivery city,' 'zip code,' 'weight,' and any 'special notes.' Hash Table Example: { '1': { 'address': '123 ABC St', 'deadline': '10:30 AM', 'city': 'Salt Lake City',

'zip': '84111', 'weight': '2 lbs', 'special_note': None, 'status': 'At the hub' }, '2': { 'address': '456 DEF St', 'deadline': '11:00 AM', 'city': 'Salt Lake City', 'zip': '84112', 'weight': '5 lbs', 'special_note': None, 'status': 'At the hub' }, ... } Relationship Between Data Components: The chosen structure supports the complexity and variability of the package information: 1. Unique Identification: The use of "Package ID" as a key ensures that each package is uniquely identified, thus aligning well with the assumption that each package has a unique ID. 2. Dynamic Updates: The hash table accommodates real-time changes to package information. For example, if the address for package #9 needs to be updated at 10:20 a.m., the hash table allows for this information to be changed instantaneously (Hart et al., 1968). 3. Complex Queries: Given that the delivery algorithm may have to prioritize by various factors like deadline, zip code, or special notes, the inner hash table structure allows for complex queries to be constructed and executed efficiently.

By nesting hash tables, the data structure takes into consideration the relationships between different attributes of a package. For instance, if you need to filter out all packages that need to be delivered before a specific time, you could easily iterate through the hash table and inspect the 'deadline' field for each package. Time Complexity: 1. Insertion: O (1) 2. Deletion: O (1) 3. Lookup: O (1) The constant time complexity for these operations ensures the hash table's efficiency in adapting to real-time updates, which is crucial for a delivery system with dynamic elements. C. Program Overview The program aims to efficiently deliver a total of 40 packages using a fleet of three trucks and two drivers, based on a set of predefined constraints and assumptions. The chosen algorithm for the routing logic is the Greedy Algorithm using a nearest-neighbor approach. 1. Pseudocode for the Algorithm’s Logic: get_shortest_route(_list, num, curr_location) if _list is empty then return _list set lowest_value to 50.0 set location to 0 // Find the closest location for each item i in _list do

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

set value to int(i[1]) if get_current_distance(curr_location, value) <= lowest_value then set lowest_value to get_current_distance(curr_location, value) set location to value end if end for // Allocate package to appropriate truck for each item i in _list do if get_current_distance(curr_location, int(i[1])) == lowest_value then if num == 1 then append i to first_truck append i[1] to first_truck_indices remove i from _list set curr_location to location call get_shortest_route(_list, 1, curr_location) else if num == 2 then append i to second_truck append i[1] to second_truck_indices remove i from _list set curr_location to location call get_shortest_route(_list, 2, curr_location) else if num == 3 then append i to third_truck append i[1] to third_truck_indices remove i from _list set curr_location to location

call get_shortest_route(_list, 3, curr_location) end if end if end for This pseudocode outlines the program's logic for solving the package delivery problem. The Greedy Algorithm works by iteratively selecting the closest package to the current location of each truck, adding it to that truck's list, and updating the current location accordingly. Given that each truck can carry a maximum of 16 packages, the algorithm fills up each truck and then returns it to the hub for reloading if needed. Special cases like the updated address for package #9 are accounted for in real-time using the `update_packages` function. 2. Programming Environment - Software: Python 3.9.1, VSCode 1.59 - Hardware : Development will be carried out on a Windows 10 machine, equipped with an Intel Core i7-9750H CPU and 16GB of RAM 3. Space-Time Complexity  Hash Table for Packages:  Space: O ( n ) where n is the number of packages.  Time: Access O (1), Insertion O (1), Deletion O (1).  Greedy Algorithm for Routing:  Space: O ( V ) for storing nodes, where V is the number of nodes (or locations).  Time: O ( V × n ), where V is the number of nodes and n is the number of packages.  Total Program:  Space: O ( n + V )  Time: O ( V × n )

4. Scalability  Hash Table: Hash tables are highly scalable, offering constant-time operations. They can be resized dynamically as more packages are added.  Greedy Algorithm: The algorithm is efficient for small sets but might not be ideal for extremely large graphs. It can be parallelized for better scalability.  Dynamic Adaptability: The program can adapt to new data points in real-time, e.g., new package entries or address corrections.  Scalability: As the system grows and the number of packages increases, the hash table can be easily resized to accommodate more elements. This is crucial for a rapidly evolving system where the dataset's size may not be static. With good hash functions and rehashing techniques, the hash table remains effective even as the data grows, ensuring that it scales well with increased workloads (Peterson, 1957). 5. Efficiency and Maintainability  Modular Design: Each functionality (e.g., data storage, routing algorithm) is a separate module, making it easier to maintain and extend.  Readability: Descriptive variable names and comments make the code easier to understand.  Memory Usage: Hash tables can consume more memory than other data structures like arrays, their flexible sizing means that they can be resized to fit the exact number of elements they contain (Sedgewick & Wayne, 2011). This makes it a memory-efficient choice in the long run, as you're not wasting storage space for elements that do not exist.  Efficiency: The program is designed for quick computations with low space-time complexity, suitable for real-time adjustments.  Maintainability: Modular design and thorough documentation make it easy for any developer to understand and modify the code.  Testing: Unit tests for different components facilitate quicker issue identification, aiding maintainability.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

6. Strengths and Weaknesses of Hash Table - Strengths:  O (1) for insert, delete, and retrieve operations ensures quick access and efficient data storage (Cormen et al., 2009).  Suitable for key-value pairs, which works well for our packaging system. - Weaknesses:  Hash Collisions: Occur when two keys hash to the same index, requiring additional operations to resolve.  Memory: Hash tables may store more memory than required to maintain the load factor. 7. Key Choice for Efficient Delivery Management  Delivery Deadline: Ensuring on-time delivery is crucial; therefore, sorting packages by their deadlines is important.  Package ID: Unique IDs help to differentiate between packages with the same deadline. Combining 'delivery deadline' and 'package ID' allows us to sort packages by their deadlines while ensuring uniqueness. This is particularly useful for loading the truck optimally for each route, prioritizing packages that have earlier deadlines (Hart et al., 1968). D. Acknowledge sources, using in-text citations and references, for content that is quoted, paraphrased, or summarized. 1. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. 2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. 3. Peterson, W. W. (1957). Addressing for random-access storage. 4. Sedgewick, R., & Wayne, K. (2011). Algorithms, 4th Edition.

F. Justify the package delivery algorithm The algorithm used in the solution is a variant of the Greedy algorithm. 1. Strengths of the algorithm: - Efficiency: The Greedy algorithm is efficient in terms of time complexity. It makes the optimal choice at each step as it attempts to find the local optimum with the hope that these local optima lead to a global optimum (Cormen et al., 2009). - Simplicity: The algorithm is straightforward and easy to understand. It makes decisions based on the current situation without worrying about the consequences of the decision. 2. The algorithm meets all requirements in the scenario: - It ensures that all 40 packages are delivered within the day. - It respects the constraints of the trucks' capacities and the specific requirements of each package. - It keeps the total distance traveled under 140 miles for two of the trucks. 3. Two other named algorithms that could meet all requirements: - Dijkstra's Algorithm: This algorithm could be used to find the shortest path between the hub and each delivery location. - A Search Algorithm: This algorithm could be used to find the most efficient route for each truck, taking into account the distances between locations and the delivery deadlines. a. Differences from the Greedy algorithm: - Dijkstra's Algorithm: Unlike the Greedy algorithm, Dijkstra's algorithm considers all possible paths from the starting point to the destination and chooses the shortest one. - A Search Algorithm: A Search Algorithm, unlike the Greedy algorithm, uses a heuristic to estimate the cost to reach the goal from a given node, which helps in finding the most efficient path.

G. What would be done differently If I were to do this project again, I would consider implementing a more sophisticated algorithm like the A Search Algorithm or Dijkstra's Algorithm for routing. These algorithms could potentially provide more efficient routes, especially in scenarios where the delivery locations are spread out over a larger area. 1. Improved Error Handling: The current implementation lacks robust error handling. For instance, in the csv_reader.py file, the program exits if the CSV file is not found. Instead, I would implement a more user-friendly approach, such as prompting the user to enter the correct file path or providing an option to load a default dataset. 2. Dynamic Truck Capacity: The current program assumes a fixed truck capacity of 16 packages. However, in a real-world scenario, the truck capacity could vary. I would modify the program to allow the user to input the truck capacity. This would make the program more flexible and applicable to a wider range of scenarios. 3. User Interface Enhancements: The current user interface, as seen in main.py, is quite basic and could be improved for better user experience. I would consider implementing a graphical user interface (GUI) to make the program more interactive and user-friendly. 4. Optimized Package Assignment: The current package assignment process, as seen in packages.py, could be optimized further. Currently, the packages are assigned to trucks based on certain conditions. However, this could be improved by considering other factors such as package priority or delivery deadlines. 5. Unit Testing: The current codebase lacks unit tests. Adding unit tests would help ensure the correctness of the code and make it easier to identify and fix bugs. This would also make the code more maintainable and reliable. 6. Code Refactoring: Some parts of the code could be refactored for better readability and efficiency. For instance, the process_deliveries function in packages.py could be broken down into smaller, more manageable functions.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

H. Verify the data structure The data structure used in the solution is a custom Hash Table (hash_table.py), which meets all requirements in the scenario for the following reasons: 1. Unique Package IDs: Each package has a unique ID, which is used as the key in the hash table. This ensures that each package can be quickly and efficiently retrieved based on its ID. This is demonstrated in the generate_hash_key function in the hash_table.py file. 2. Efficient Operations: Hash tables allow for efficient insertion, deletion, and retrieval operations, all of which are required in this scenario. The insert_package and update_package functions in the hash_table.py file demonstrate this. 3. Package Information Storage: The hash table stores all the relevant information for each package, including its address, delivery deadline, weight, and special notes. This information is stored as a list of values associated with each key, as shown in the insert_package function in the hash_table.py file. 4. Scalability : Hash tables are scalable and can handle a large number of packages, which is important as the number of packages can vary each day. 5. Handling Special Notes: The hash table is used to handle special notes associated with each package, such as packages that must be delivered together. This is demonstrated in the csv_reader.py file where a separate hash table packages_together is used to store packages that must be delivered together. 1. Two other data structures that could meet the same requirements: - Binary Search Tree (BST) - Priority Queue

a. Differences from the Hash Table: - Binary Search Tree: Unlike a Hash Table, a BST stores elements in a sorted manner, which could be beneficial for operations that require sorted data. However, operations in a BST could have a higher time complexity in the worst case. - Priority Queue: Unlike a Hash Table, a Priority Queue assigns a priority to each element and ensures that the element with the highest priority is always at the front. This could be useful for managing the delivery schedule based on delivery deadlines. I. Acknowledge sources - Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.

Jenkins_Antonio_C950T2

Related Documents