1

BSDS3003 – Data Structure & Algorithm
Individual Assignment 1 – Critical Path Method (weighting: 40%)

Problem Description
One of the key project management tools is concerned about project scheduling. The critical path
method (CPM) is used to identify overall project duration and critical activities, which form critical
path(s), in a network of inter-dependent tasks/activities of a project. Four types of dependencies
may exist between a pair of tasks. This assignment only focuses on the end-to-start dependency, i.e. a
task can only starts after the completion of its predecessor task(s). In this assignment, you may
assume only end-to-start relationship is supported. An illustration of the basic concepts of CPM can
be found at https://www.youtube.com/watch?v=4oDLMs11Exs and
https://milestonetask.com/critical-path-analysis-steps-example/.



In this assignment, you are required to prepare a Python program that take a network of task/activity
nodes as input. The network and task nodes are to be represented as a Python ADTs. Each node
ADT should store the following data:
• Node number
• Brief task/deliverable description
• Duration required to complete the task (0 for deliverables)
• Earliest start time
• Earliest finish time
• Latest start time
• Latest finish time
• Slack (= Latest start time - Earliest start time)
• List of predecessor(s)
• List of successor(s)

Commented [LCSP1]: Finish to start is fine
2

You need to decide how to store the network of nodes, e.g. in an array, a list, or some other data
structures. For simplicity, you may define the network in your program instead of retrieving task
details from a database.

Test Data
You are required to test your Python program with the following task network:


Run your program and show its outputs to answer the following questions:
1. What is the project duration?
2. List all the tasks in the critical path.
3. If task F takes 10 weeks instead of 9 weeks to finish, how would it affect your answers to
questions 1 and 2?

Submission Requirements

Submit your Python program (in .py extension) which should be properly documented with
comments, and a brief report that details the justification of your choice of data structures, test
results, and answers to the above questions to Moodle no later than Monday, 1 June 2020. The
Python code should be included in the appendix of the report. An analysis of time and space
complexities of your program is also needed (<10%).

This assignment amounts to 40% of the course grade. Grading will be based on solution correctness
(50%), completeness (25%), and efficiency of the submitted solution including choice of appropriate
data structures (15%), as well as the quality of the documentation (10%).

3



中間是 slack time
4


Critical path


Add print screen in the appendix

Can use network to identify the shortest path, but expect to do is from scrash (edge?)