WGU C950 NHP3 Task 1: PS Routing Program
Planning | Passed on First Attempt |Latest
Update with Complete Solution
Bachelor of Science, Computer Science
Data Structures and Algorithms II –
Filipe Araujo
Student ID: xxxxxxxxx
A. Identify a named self-adjusting algorithm (e.g., nearest neighbor
algorithm, greedy algorithm) that could be used to create your
program to deliver the packages.
For the WGUPS routing program, I used the Nearest Neighbor Algorithm as
an appropriate self-adjusting algorithm to create the delivery routing
solution. The Nearest Neighbor Algorithm is a greedy algorithm that selects
the closest unvisited location from the current position and moves to that
location. This process repeats until all places have been visited.
B. Identify a self-adjusting data structure, such as a hash table, that
could be used with the algorithm identified in part A to store the
package data.
I used a Hash Table as an appropriate self-adjusting data structure with the
Nearest Neighbor Algorithm to efficiently store and manage the package
data. A hash table is a data structure that uses a hash function to associate
keys with values, enabling fast insertion, deletion, and lookup operations.
, B1. Explain how your data structure accounts for the relationship
between the data components you are storing.
The hash table supports the relationships between stored data in the
following ways:
1. Key-Value Mapping: Each package is stored with its unique ID as
the key, enabling O(1) average-case lookup time. This is critical for
fast access during route planning and status updates.
2. Data Organization: The value associated with each key will be a
Package object containing all relevant package information, including
delivery address, deadline, city, zip code, weight, and delivery status.
This organization allows for efficient storage and retrieval of all
package attributes.
3. Relationship Preservation: The hash table maintains the
relationship between packages and their attributes while allowing
quick access to specific packages by their ID. This is essential for
tracking package status and updating information (such as the
address correction for package #9 from 300 State St to 410 S State St
at 10:20 a.m.).
4. Dynamic Updates: The hash table supports efficient updates to
package information, which is necessary for handling the address
correction for package #9 at 10:20 a.m. and updating delivery status
as packages are delivered.
5. Flexible Querying: While the primary key is the package ID, the
implementation can include methods to query packages based on
other attributes such as delivery deadline or address, facilitating the
grouping of packages for efficient routing (e.g., packages 14, 15, and
19 that must be delivered together).
Because of its constant-time access and update capabilities, the hash table
pairs well with the Nearest Neighbor Algorithm, which depends on frequent
lookups and updates during route optimization.
C. Write an overview of your program in which you do the following:
C1. Explain the algorithm’s logic using pseudocode.
This pseudocode outlines the core logic of the delivery algorithm,
incorporating the Nearest Neighbor approach while accounting for the
specific constraints of the WGUPS scenarios, such as delivery deadlines,
special notes, truck restrictions, and the address correction for package #9.
Planning | Passed on First Attempt |Latest
Update with Complete Solution
Bachelor of Science, Computer Science
Data Structures and Algorithms II –
Filipe Araujo
Student ID: xxxxxxxxx
A. Identify a named self-adjusting algorithm (e.g., nearest neighbor
algorithm, greedy algorithm) that could be used to create your
program to deliver the packages.
For the WGUPS routing program, I used the Nearest Neighbor Algorithm as
an appropriate self-adjusting algorithm to create the delivery routing
solution. The Nearest Neighbor Algorithm is a greedy algorithm that selects
the closest unvisited location from the current position and moves to that
location. This process repeats until all places have been visited.
B. Identify a self-adjusting data structure, such as a hash table, that
could be used with the algorithm identified in part A to store the
package data.
I used a Hash Table as an appropriate self-adjusting data structure with the
Nearest Neighbor Algorithm to efficiently store and manage the package
data. A hash table is a data structure that uses a hash function to associate
keys with values, enabling fast insertion, deletion, and lookup operations.
, B1. Explain how your data structure accounts for the relationship
between the data components you are storing.
The hash table supports the relationships between stored data in the
following ways:
1. Key-Value Mapping: Each package is stored with its unique ID as
the key, enabling O(1) average-case lookup time. This is critical for
fast access during route planning and status updates.
2. Data Organization: The value associated with each key will be a
Package object containing all relevant package information, including
delivery address, deadline, city, zip code, weight, and delivery status.
This organization allows for efficient storage and retrieval of all
package attributes.
3. Relationship Preservation: The hash table maintains the
relationship between packages and their attributes while allowing
quick access to specific packages by their ID. This is essential for
tracking package status and updating information (such as the
address correction for package #9 from 300 State St to 410 S State St
at 10:20 a.m.).
4. Dynamic Updates: The hash table supports efficient updates to
package information, which is necessary for handling the address
correction for package #9 at 10:20 a.m. and updating delivery status
as packages are delivered.
5. Flexible Querying: While the primary key is the package ID, the
implementation can include methods to query packages based on
other attributes such as delivery deadline or address, facilitating the
grouping of packages for efficient routing (e.g., packages 14, 15, and
19 that must be delivered together).
Because of its constant-time access and update capabilities, the hash table
pairs well with the Nearest Neighbor Algorithm, which depends on frequent
lookups and updates during route optimization.
C. Write an overview of your program in which you do the following:
C1. Explain the algorithm’s logic using pseudocode.
This pseudocode outlines the core logic of the delivery algorithm,
incorporating the Nearest Neighbor approach while accounting for the
specific constraints of the WGUPS scenarios, such as delivery deadlines,
special notes, truck restrictions, and the address correction for package #9.
