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?)
