C950 Task-1 FAQ

C950 Task-1 FAQ

(Task-1: The planning phase of the WGUPS Routing Program)

C950 Data Structures and Algorithms II

Page 1 of 10
 C950 Task-1 FAQ

Introduction
Mainly elaborate on the project and how you approach to implement it.

You should come up with your own solution. You can see an example here:
C950 WGUPS Project Implementation Steps - Example

A. Algorithm Identification

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.

You must identify the self-adjusting part of your algorithm by name. Though
you may have written your own algorithm using a variety of approaches,
you should be able to connect or generalize part of your algorithm to a
commonly recognizable method, e.g., a greedy algorithm, farthest neighbor
algorithm, etc.

The identified (also called chosen or core) algorithm must be self-adjusting

(inferred from the scenario). Non self-adjusting methods can also be used
to find a solution, but there must be at least one part that uses a self-
adjusting algorithm.

B. Data Structure Identification

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.

Page 2 of 10
 C950 Task-1 FAQ

This is where you want to elaborate what data is being hold, in what data
structure and why you made that decision. Also how the data components
are related to each other.

B1. Explanation of Data Structure

1. Explain how your data structure accounts for the relationship between
the data components you are storing.

See above

C1. Algorithm’s Logic

Write an overview of your program in which you do the following:

1. Explain the algorithm’s logic using pseudocode.

Note: You may refer to the attached “Sample Core Algorithm Overview” to
complete part C1.

Answer all the questions above with 4-5 sentences.

Provide a “what, how, and why“ summary explanation of how your code
finds a solution, i.e., explain how your core algorithm works. You can see
more on Pseudocode here: C950 Guide to [Link].

C2. Development Environment

2. Describe the programming environment you will use to create the
Python application, including both the software and hardware you will use.

See above.

Page 3 of 10
 C950 Task-1 FAQ

C3. Space and Time complexity using Big-O notation

3. Evaluate the space-time complexity of each major segment of the
program and the entire program using big-O notation.

See above.

Big-O cheat sheet; [Link]

Introduction to Big-O: [Link]

C4. Scalability and Adaptability

4. Explain the capability of your solution to scale and adapt to a growing
number of packages.

See above.

The identified (chosen) algorithm from Part A must be self-adjusting. Hence

it will have at least one scalable element. This discussion can also include
shortcomings, e.g., “X will not scale well because…”

C5. Software Efficiency and Maintainability

5. Discuss why the software design would be efficient and easy to
maintain.

See above.

By “efficiency”, they mean the Big-O time complexity of your entire

program. Your program must run in polynomial time or better to be efficient.

By “maintainability”, they mean how the entire program can be easily

understood, repaired, and enhanced by developers other than the author.

Page 4 of 10
 C950 Task-1 FAQ

C6. Self-Adjusting Data Structures

6. Describe both the strengths and weaknesses of the self-adjusting data
structure (e.g., the hash table).

See above.

At least self-adjusting one data structure needs to be discussed. The hash

table discussed above can fulfill this requirement.

C7. Data Key

7. Justify the choice of a key for efficient delivery management from the
following components:

• delivery address

• delivery deadline

• delivery city

• delivery zip code

• package ID

• package weight

• delivery status (i.e., at the hub, en route, or delivered), including the

delivery time

See above.

Elaborate on how you approach choosing data key (ex. PackageID), and
why you chose that specific key.

D. Sources
Acknowledge sources, using in-text citations and references, for content
that is quoted, paraphrased, or summarized.

Page 5 of 10
 C950 Task-1 FAQ

An example:

Lysecky, R., & Vahid, F. (2018, June). C950: Data Structures and
Algorithms II. zyBooks.

Retrieved March 22, 2021, from

[Link]

E. Professional Communication
Demonstrate professional communication in the content and presentation
of your submission.

The submitted document should be grammatically correct and easy to read.

Make use of one of the many freely available grammar checkers and/or the
writing center. You can run your document through
[Link]

Here are additional questions you may be wondering about:

Do I have to use Python?

Yes. The project requires that you use a version compatible with the latest
version of Python 3.

Am I required to use a specific IDE?

We recommend the free community version of PyCharm.

Do all packages have to be delivered on time?

Page 6 of 10
 C950 Task-1 FAQ

Yes. Packages must be delivered on or before their delivery time.

Packages with an "EOD" deadline must be delivered before the "End Of
Day." "EOD" is not specified, but it's reasonable to assume that it's 5:00
pm. However, solutions are almost always completed before 3:00 pm.

Why are there three trucks?

Only two drivers are available, and trucks have unlimited gas and load
instantly. Perhaps, a third truck makes instantaneous load times realistic
(truck 3 can be loaded while the others are out). However, it is no required
to use truck 3 (or truck 1).

What is the maximum total mileage allowed for trucks?

Less than 140 miles. This is what the official task directions mean by
"optimal." Both heuristics and optimizing algorithms are important to get a
good solution.

Does the solution have to be absolutely optimal?

The delivery problem is a variation of the traveling salesperson problem

(TSP), which is known to be NP-Hard. So even if you found the optimal
solution, we couldn't verify it without checking every possible route (and we
don't have enough time for that!). Furthermore, the task requires your
algorithm to be "efficient," meaning it must run in polynomial time. If you
find a polynomial-time algorithm for solving the TSP, please let us know as
this would answer the P versus NP problem -a millennium problem with a

Page 7 of 10
 C950 Task-1 FAQ

one million dollar prize. Therefore, you should use an algorithm that finds a
solution that performs sufficient optimization. For this, there are many
approaches resulting in far less than 145 miles.

Do I need to use any algorithms not covered in the learning

materials?

No, but you certainly can. However, a program using only the covered
algorithms (plus some heuristics) can find an adequately optimal solution.

Can I use external third-party libraries?

No. Only submit code that you've written yourself or from the standard built-
in Python library. Evaluators will need to run your code on their machines
without installing additional resources.

Can I use the built-in Python dictionary construct for my hash table?

No. Your hash table can use lists, sets, or tuples. You can use dictionaries
elsewhere in your project.

Does my program have to parse the excel data straight from excel?

No. You can export the data from excel to text or CSV file. Include these
files with your submitted project. You can clean up the file manually,
making it easier to import, e.g., removing headers.

Page 8 of 10
 C950 Task-1 FAQ

The Excel mileage matrix only has the lower half filled in, so it only
has mileage entries in one direction, for example from point A to point
B, but not from point B to point A. Does that mean a truck has to find
an alternate route?

No. The distance table is bi-directional, i.e., the distance from A to B equals
the distance from B to A. Furthermore, the distance table is a fully
connected graph, i.e., it provides a direct path between every address. So
using a graph data structure is not necessary.

However, the triangle inequality does not hold. Meaning the provided
distance from A to B mileage might not always be the shortest path! For
example, from the distance table: hub-->Taylorsville is 11.0, but hub-->
Valley Regional--> Taylorsville is 6.4+0.6 =7 miles. You can optimize the
distance table via a pathfinding algorithm, such as Dijkstra's. However, this
step is not necessary to find a solution under 145 miles.

Does my program need to have an interactive external user interface?

Yes. See Part G above. The 'user' needs to conveniently be able to check
the status of any package at any time. For example, the user should be
able to look up package #19 at 10:43 am and check the info and status.
Having the user provide a time and printing the info and status of all the
packages will meet this requirement. We recommend a simple command-
line interface.

Does the user need to be able to update the package's address?

Page 9 of 10
 C950 Task-1 FAQ

There is no requirement for this, and the code should be able to complete
the delivery simulation using only the provided data.

How do we handle the package with the wrong address (#9)?

The wrong delivery address for package #9, Third District Juvenile Court,
will be corrected at 10:20 a.m. The correct address is “410 S State St., Salt
Lake City, UT 84111”. There is no specification for how you handle this
situation other than package #9 cannot be delivered to the correct address
before 10:20 a.m. It is acceptable to assume WGUPS knows the address is
incorrect and when it will be corrected. Hence effectively treating package
#9 like a delayed package.

Page 10 of 10