Problem Solving in IT (COMP1001) and Computational Thinking and Problem Solving (COMP 1002)
Class Project
(Final version, may have minor bug fix) (Due at noon on 8 December 2019)
Rocky K. C. Chang 13 November 2019
Objective:
You will have experienced the entire problem-solving process through designing and implementing a program to solve a relatively complex river-crossing puzzle. In particular, you will learn
• How to model a river-crossing problem as a graph problem;
• How to analyze the state space and classify them into different kinds of states;
• How to apply a shortest-path algorithm to solve the problem;
• How to modularize the entire program into smaller functions with well-defined signatures;
• How to implement graph based on adjacency list using Python dictionary;
• How to implement each function using Python accurately and with clear documentation; and
• How to write a quality report to describe each step of the problem-solving process.
A Red-Sea-Crossing Problem:
Moses is bringing seven other people with him from Egypt to Israel which are separated by Red Sea. Besides Moses, there are Pharaoh and two families: (1) Ahab (husband), Jezebel (wife) and a servant and (2) Ananias (husband), Sapphira (wife) and a servant. Further details below:
• They ride on a boat that accommodates only two people traveling between Egypt and Israel.
• Only Moses, Pharaoh, Ahab, and Ananias can operate the boat.
• If Moses is not present, Pharaoh will beat up all others with him.
• If Ahab is absent from his wife and servant, Ananias will beat them up.
• If Ananias is absent from his wife and servant, Ahab will beat them up.
The problem is to bring them from Egypt to Israel without having anyone beaten up in a minimum number of trips.
1
The Project:
In this project you will design and implement a program to solve this problem. You must apply and document the three-step process: data abstraction, algorithm design and coding. For the last step, you must modularize your code by identifying the functions that you need and their signatures.
Some important notes:
1. Follow the exact format of the expected output except of the number of empty lines separating different parts of the outputs. The states should also be printed in a sorted order
2. Section A: According to the problem, the boat can be operated only by men. Therefore, a more subtle constraint is to have boat with at least one man. That is, the states that violate this constraint will be considered illegal.
3. Section B: The final graph must include the nodes that are part of at least one shortest path. Draw the graph in a separate page. To obtain this final graph, you need to write another function to prune away the nodes that are not part of any shortest path.
4. Section C : You just need to print any one of the solutions.
Deliverables:
1. A report documenting the process of solving the problem
a. Three pages maximum. One inch on all margins and Times New Roman font with 11pt and single space. You may use an additional page just for the graph. Your file must be in pdf format named “your student ID”_report.pdf.
b. The report must contain the following content and sections. There is no need to include the code, because it is already in the .py file. i. Your name, student ID and program name
ii. A problem description
iii. Data abstraction (including a description of the states, a graph as a result of the data abstraction, the data types required, …) iv. The algorithm needed to solve the graph problem
v. A modular design of the program
vi. A Python implementation of the data types
2. A well-documented Python program in a single .py file. Name your .py file by “your student ID”_program.py. a. You must use docstring to describe each function.
b. By using appropriate comments and variable names, your program must be easy to follow and understand. c. Give proper reference to the source of the code that you adopt for your program.
d. The expected outputs of your program are given in the next page.
3. Submission instructions (failing to follow these instructions will result in at most 20% deduction in the project marks):
a. Create a folder named Project_”Your Student ID”_”Your Name”. Please do not leave any space in the folder’s name. For example, Project_18912346_ChangKowChuen. Put the files in (1) and (2) into this folder.
b. Compress this folder as rar or zip file and name it Project_”YourStudent ID”_”Your Name”.rar/zip.
c. Submit the rar/zip file to Blackboard. You can upload it an unlimited number of times, but only the last one will be graded.
2
Expected outputs from your program
SECTION A: THE STATE SPACE
(The set of legal states: (108)
EEEEEEEEE EEEEEEEEW EEEEEEEWE EEEEEEEWW EEEEEEWWW EEEEEWEEE EEEEEWEEW EEEEEWEWE EEEEEWEWW EEEEWEEEE EEEEWEEEW EEEEWEEWE EEEEWEEWW EEEEWWEEE EEEEWWEEW EEEEWWEWE EEEEWWEWW EEEWEEWEE EEEWEEWEW EEEWEEWWE EEEWEEWWW EEEWEWWEE EEEWEWWEW EEEWEWWWE EEEWEWWWW EEEWWEWEE EEEWWEWEW EEEWWEWWE EEEWWEWWW EEEWWWEEE EEEWWWWEE EEEWWWWEW EEEWWWWWE EEEWWWWWW EEWEEEEEE EWEWWWWWW EWWEEEEEE EWWEEEEEW EWWEEEEWE EWWEEEEWW EWWEEEWWW EWWEEWEEE EWWEEWEEW EWWEEWEWE EWWEEWEWW EWWEWEEEE EWWEWEEEW EWWEWEEWE EWWEWEEWW EWWEWWEEE EWWEWWEEW EWWEWWEWE EWWEWWEWW EWWWWWEEE WEEEEEWWW WEEWEEWEE WEEWEEWEW WEEWEEWWE WEEWEEWWW WEEWEWWEE WEEWEWWEW WEEWEWWWE WEEWEWWWW WEEWWEWEE WEEWWEWEW WEEWWEWWE WEEWWEWWW WEEWWWEEE WEEWWWWEE WEEWWWWEW WEEWWWWWE WEEWWWWWW WEWEEEEEE WWEWWWWWW WWWEEEEEE WWWEEEEEW WWWEEEEWE WWWEEEEWW WWWEEEWWW WWWEEWEEE WWWEEWEEW WWWEEWEWE WWWEEWEWW WWWEWEEEE WWWEWEEEW WWWEWEEWE WWWEWEEWW WWWEWWEEE WWWEWWEEW WWWEWWEWE WWWEWWEWW WWWWEEWEE WWWWEEWEW WWWWEEWWE WWWWEEWWW WWWWEWWEE WWWWEWWEW WWWWEWWWE WWWWEWWWW WWWWWEWEE WWWWWEWEW WWWWWEWWE WWWWWEWWW WWWWWWEEE WWWWWWWEE WWWWWWWEW WWWWWWWWE WWWWWWWWW
(C1)::) The set of illegal states that violates the constraint of having the boat with at least a man: (32)
EWWWEEWEE EWWWEEWEW
EWWWEWWWE EWWWEWWWW
EWWWWWWEE EWWWWWWEW
WEEEEEEWE WEEEEEEWW
WEEEWEEEE WEEEWEEEW
WEEEWWEWE WEEEWWEWW
EWWWEEWWE EWWWEEWWW EWWWEWWEE EWWWEWWEW EWWWWEWEE EWWWWEWEW EWWWWEWWE EWWWWEWWW EWWWWWWWE EWWWWWWWW WEEEEEEEE WEEEEEEEW WEEEEWEEE WEEEEWEEW WEEEEWEWE WEEEEWEWW WEEEWEEWE WEEEWEEWW WEEEWWEEE WEEEWWEEW
(C2)::) The set of illegal states that violates the constraint of preventing Moses Pharaoh from beating others: (252)
EEWEEEEEW EEWEEEEWE EEWEEEEWW EEWEEEWEE EEWEEEWEW EEWEEEWWE EEWEEEWWW EEWEEWEEE EEWEEWEEW EEWEEWEWE EEWEEWEWW EEWEEWWEE EEWEEWWEW EEWEEWWWE EEWEEWWWW EEWEWEEEE EEWEWEEEW EEWEWEEWE EEWEWEEWW EEWEWEWEE EEWEWEWEW EEWEWEWWE EEWEWEWWW EEWEWWEEE EEWEWWEEW EEWEWWEWE EEWEWWEWW EEWEWWWEE EEWEWWWEW EEWEWWWWE EEWEWWWWW EEWWEEEEE EEWWEEEEW EEWWEEEWE EEWWEEEWW EEWWEEWEE
3
EEWWEEWEW EEWWEEWWE EEWWEEWWW EEWWEWEEE EEWWEWEEW EEWWEWEWE EEWWEWEWW EEWWEWWEE EEWWEWWEW EEWWEWWWE EEWWEWWWW EEWWWEEEE EEWWWEEEW EEWWWEEWE EEWWWEEWW EEWWWEWEE EEWWWEWEW EEWWWEWWE EEWWWEWWW EEWWWWEEE EEWWWWEEW EEWWWWEWE EEWWWWEWW EEWWWWWEE EEWWWWWEW EEWWWWWWE EEWWWWWWW EWEEEEEEE EWEEEEEEW EWEEEEEWE EWEEEEEWW EWEEEEWEE EWEEEEWEW EWEEEEWWE EWEEEEWWW EWEEEWEEE EWEEEWEEW EWEEEWEWE EWEEEWEWW EWEEEWWEE EWEEEWWEW EWEEEWWWE EWEEEWWWW EWEEWEEEE EWEEWEEEW EWEEWEEWE EWEEWEEWW EWEEWEWEE EWEEWEWEW EWEEWEWWE EWEEWEWWW EWEEWWEEE EWEEWWEEW EWEEWWEWE EWEEWWEWW EWEEWWWEE EWEEWWWEW EWEEWWWWE EWEEWWWWW EWEWEEEEE EWEWEEEEW EWEWEEEWE EWEWEEEWW EWEWEEWEE EWEWEEWEW EWEWEEWWE EWEWEEWWW EWEWEWEEE EWEWEWEEW EWEWEWEWE EWEWEWEWW EWEWEWWEE EWEWEWWEW EWEWEWWWE EWEWEWWWW EWEWWEEEE EWEWWEEEW EWEWWEEWE EWEWWEEWW EWEWWEWEE EWEWWEWEW EWEWWEWWE EWEWWEWWW EWEWWWEEE EWEWWWEEW EWEWWWEWE EWEWWWEWW EWEWWWWEE EWEWWWWEW EWEWWWWWE WEWEEEEEW WEWEEEEWE WEWEEEEWW WEWEEEWEE WEWEEEWEW WEWEEEWWE WEWEEEWWW WEWEEWEEE WEWEEWEEW WEWEEWEWE WEWEEWEWW WEWEEWWEE WEWEEWWEW WEWEEWWWE WEWEEWWWW WEWEWEEEE WEWEWEEEW WEWEWEEWE WEWEWEEWW WEWEWEWEE WEWEWEWEW WEWEWEWWE WEWEWEWWW WEWEWWEEE WEWEWWEEW WEWEWWEWE WEWEWWEWW WEWEWWWEE WEWEWWWEW WEWEWWWWE WEWEWWWWW WEWWEEEEE WEWWEEEEW WEWWEEEWE WEWWEEEWW WEWWEEWEE WEWWEEWEW WEWWEEWWE WEWWEEWWW WEWWEWEEE WEWWEWEEW WEWWEWEWE WEWWEWEWW WEWWEWWEE WEWWEWWEW WEWWEWWWE WEWWEWWWW WEWWWEEEE WEWWWEEEW WEWWWEEWE WEWWWEEWW WEWWWEWEE WEWWWEWEW WEWWWEWWE WEWWWEWWW WEWWWWEEE WEWWWWEEW WEWWWWEWE WEWWWWEWW WEWWWWWEE WEWWWWWEW WEWWWWWWE WEWWWWWWW WWEEEEEEE WWEEEEEEW WWEEEEEWE WWEEEEEWW WWEEEEWEE WWEEEEWEW WWEEEEWWE WWEEEEWWW WWEEEWEEE WWEEEWEEW WWEEEWEWE WWEEEWEWW WWEEEWWEE WWEEEWWEW WWEEEWWWE WWEEEWWWW WWEEWEEEE WWEEWEEEW WWEEWEEWE WWEEWEEWW WWEEWEWEE WWEEWEWEW WWEEWEWWE WWEEWEWWW WWEEWWEEE WWEEWWEEW WWEEWWEWE WWEEWWEWW WWEEWWWEE WWEEWWWEW WWEEWWWWE WWEEWWWWW WWEWEEEEE WWEWEEEEW WWEWEEEWE WWEWEEEWW WWEWEEWEE WWEWEEWEW WWEWEEWWE WWEWEEWWW WWEWEWEEE WWEWEWEEW WWEWEWEWE WWEWEWEWW WWEWEWWEE WWEWEWWEW WWEWEWWWE WWEWEWWWW WWEWWEEEE WWEWWEEEW WWEWWEEWE WWEWWEEWW WWEWWEWEE WWEWWEWEW WWEWWEWWE WWEWWEWWW WWEWWWEEE WWEWWWEEW WWEWWWEWE WWEWWWEWW WWEWWWWEE WWEWWWWEW WWEWWWWWE
(C3): The set of illegal states that violates the constraint of preventing Ananias from beating Ahab’s household: (192) EEEEEWWEE EEEEEWWEW EEEEEWWWE EEEEEWWWW EEEEWEWEE EEEEWEWEW EEEEWEWWE EEEEWEWWW EEEEWWWEE EEEEWWWEW EEEEWWWWE EEEEWWWWW
4
EEEWEEEEE EEEWEEEEW EEEWEEEWE EEEWEEEWW EEEWEWEEE EEEWEWEEW EEEWEWEWE EEEWEWEWW EEEWWEEEE EEEWWEEEW EEEWWEEWE EEEWWEEWW EEWEEWWEE EEWEEWWEW EEWEEWWWE EEWEEWWWW EEWEWEWEE EEWEWEWEW EEWEWEWWE EEWEWEWWW EEWEWWWEE EEWEWWWEW EEWEWWWWE EEWEWWWWW EEWWEEEEE EEWWEEEEW EEWWEEEWE EEWWEEEWW EEWWEWEEE EEWWEWEEW EEWWEWEWE EEWWEWEWW EEWWWEEEE EEWWWEEEW EEWWWEEWE EEWWWEEWW EWEEEWWEE EWEEEWWEW EWEEEWWWE EWEEEWWWW EWEEWEWEE EWEEWEWEW EWEEWEWWE EWEEWEWWW EWEEWWWEE EWEEWWWEW EWEEWWWWE EWEEWWWWW EWEWEEEEE EWEWEEEEW EWEWEEEWE EWEWEEEWW EWEWEWEEE EWEWEWEEW EWEWEWEWE EWEWEWEWW EWEWWEEEE EWEWWEEEW EWEWWEEWE EWEWWEEWW EWWEEWWEE EWWEEWWEW EWWEEWWWE EWWEEWWWW EWWEWEWEE EWWEWEWEW EWWEWEWWE EWWEWEWWW EWWEWWWEE EWWEWWWEW EWWEWWWWE EWWEWWWWW EWWWEEEEE EWWWEEEEW EWWWEEEWE EWWWEEEWW EWWWEWEEE EWWWEWEEW EWWWEWEWE EWWWEWEWW EWWWWEEEE EWWWWEEEW EWWWWEEWE EWWWWEEWW WEEEEWWEE WEEEEWWEW WEEEEWWWE WEEEEWWWW WEEEWEWEE WEEEWEWEW WEEEWEWWE WEEEWEWWW WEEEWWWEE WEEEWWWEW WEEEWWWWE WEEEWWWWW WEEWEEEEE WEEWEEEEW WEEWEEEWE WEEWEEEWW WEEWEWEEE WEEWEWEEW WEEWEWEWE WEEWEWEWW WEEWWEEEE WEEWWEEEW WEEWWEEWE WEEWWEEWW WEWEEWWEE WEWEEWWEW WEWEEWWWE WEWEEWWWW WEWEWEWEE WEWEWEWEW WEWEWEWWE WEWEWEWWW WEWEWWWEE WEWEWWWEW WEWEWWWWE WEWEWWWWW WEWWEEEEE WEWWEEEEW WEWWEEEWE WEWWEEEWW WEWWEWEEE WEWWEWEEW WEWWEWEWE WEWWEWEWW WEWWWEEEE WEWWWEEEW WEWWWEEWE WEWWWEEWW WWEEEWWEE WWEEEWWEW WWEEEWWWE WWEEEWWWW WWEEWEWEE WWEEWEWEW WWEEWEWWE WWEEWEWWW WWEEWWWEE WWEEWWWEW WWEEWWWWE WWEEWWWWW WWEWEEEEE WWEWEEEEW WWEWEEEWE WWEWEEEWW WWEWEWEEE WWEWEWEEW WWEWEWEWE WWEWEWEWW WWEWWEEEE WWEWWEEEW WWEWWEEWE WWEWWEEWW WWWEEWWEE WWWEEWWEW WWWEEWWWE WWWEEWWWW WWWEWEWEE WWWEWEWEW WWWEWEWWE WWWEWEWWW WWWEWWWEE WWWEWWWEW WWWEWWWWE WWWEWWWWW WWWWEEEEE WWWWEEEEW WWWWEEEWE WWWWEEEWW WWWWEWEEE WWWWEWEEW WWWWEWEWE WWWWEWEWW WWWWWEEEE WWWWWEEEW WWWWWEEWE WWWWWEEWW
(C4)::) The set of illegal states that violates the constraint of preventing Ahab from beating Ananias’s household: (192)
EEEEEEWEE EEEEEEWEW EEEEEEWWE EEEEEWWEE EEEEEWWEW EEEEEWWWE EEEEWEWEE EEEEWEWEW EEEEWEWWE EEEEWWWEE EEEEWWWEW EEEEWWWWE EEEWEEEEW EEEWEEEWE EEEWEEEWW EEEWEWEEW EEEWEWEWE EEEWEWEWW EEEWWEEEW EEEWWEEWE EEEWWEEWW EEEWWWEEW EEEWWWEWE EEEWWWEWW EEWEEEWEE EEWEEEWEW EEWEEEWWE EEWEEWWEE EEWEEWWEW EEWEEWWWE EEWEWEWEE EEWEWEWEW EEWEWEWWE EEWEWWWEE EEWEWWWEW EEWEWWWWE EEWWEEEEW EEWWEEEWE EEWWEEEWW EEWWEWEEW EEWWEWEWE EEWWEWEWW EEWWWEEEW EEWWWEEWE EEWWWEEWW EEWWWWEEW EEWWWWEWE EEWWWWEWW
5
EWEEEEWEE EWEEEEWEW EWEEEEWWE EWEEEWWEE EWEEEWWEW EWEEEWWWE EWEEWEWEE EWEEWEWEW EWEEWEWWE EWEEWWWEE EWEEWWWEW EWEEWWWWE EWEWEEEEW EWEWEEEWE EWEWEEEWW EWEWEWEEW EWEWEWEWE EWEWEWEWW EWEWWEEEW EWEWWEEWE EWEWWEEWW EWEWWWEEW EWEWWWEWE EWEWWWEWW EWWEEEWEE EWWEEEWEW EWWEEEWWE EWWEEWWEE EWWEEWWEW EWWEEWWWE EWWEWEWEE EWWEWEWEW EWWEWEWWE EWWEWWWEE EWWEWWWEW EWWEWWWWE EWWWEEEEW EWWWEEEWE EWWWEEEWW EWWWEWEEW EWWWEWEWE EWWWEWEWW EWWWWEEEW EWWWWEEWE EWWWWEEWW EWWWWWEEW EWWWWWEWE EWWWWWEWW WEEEEEWEE WEEEEEWEW WEEEEEWWE WEEEEWWEE WEEEEWWEW WEEEEWWWE WEEEWEWEE WEEEWEWEW WEEEWEWWE WEEEWWWEE WEEEWWWEW WEEEWWWWE WEEWEEEEW WEEWEEEWE WEEWEEEWW WEEWEWEEW WEEWEWEWE WEEWEWEWW WEEWWEEEW WEEWWEEWE WEEWWEEWW WEEWWWEEW WEEWWWEWE WEEWWWEWW WEWEEEWEE WEWEEEWEW WEWEEEWWE WEWEEWWEE WEWEEWWEW WEWEEWWWE WEWEWEWEE WEWEWEWEW WEWEWEWWE WEWEWWWEE WEWEWWWEW WEWEWWWWE WEWWEEEEW WEWWEEEWE WEWWEEEWW WEWWEWEEW WEWWEWEWE WEWWEWEWW WEWWWEEEW WEWWWEEWE WEWWWEEWW WEWWWWEEW WEWWWWEWE WEWWWWEWW WWEEEEWEE WWEEEEWEW WWEEEEWWE WWEEEWWEE WWEEEWWEW WWEEEWWWE WWEEWEWEE WWEEWEWEW WWEEWEWWE WWEEWWWEE WWEEWWWEW WWEEWWWWE WWEWEEEEW WWEWEEEWE WWEWEEEWW WWEWEWEEW WWEWEWEWE WWEWEWEWW WWEWWEEEW WWEWWEEWE WWEWWEEWW WWEWWWEEW WWEWWWEWE WWEWWWEWW WWWEEEWEE WWWEEEWEW WWWEEEWWE WWWEEWWEE WWWEEWWEW WWWEEWWWE WWWEWEWEE WWWEWEWEW WWWEWEWWE WWWEWWWEE WWWEWWWEW WWWEWWWWE WWWWEEEEW WWWWEEEWE WWWWEEEWW WWWWEWEEW WWWWEWEWE WWWWEWEWW WWWWWEEEW WWWWWEEWE WWWWWEEWW WWWWWWEEW WWWWWWEWE WWWWWWEWW
The set of illegal states the that violate both C2 and C3: (96) EEWEEWWEE EEWEEWWEW EEWEEWWWE EEWEEWWWW EEWEWEWEE EEWEWEWEW EEWEWEWWE EEWEWEWWW EEWEWWWEE EEWEWWWEW EEWEWWWWE EEWEWWWWW EEWWEEEEE EEWWEEEEW EEWWEEEWE EEWWEEEWW EEWWEWEEE EEWWEWEEW EEWWEWEWE EEWWEWEWW EEWWWEEEE EEWWWEEEW EEWWWEEWE EEWWWEEWW EWEEEWWEE EWEEEWWEW EWEEEWWWE EWEEEWWWW EWEEWEWEE EWEEWEWEW EWEEWEWWE EWEEWEWWW EWEEWWWEE EWEEWWWEW EWEEWWWWE EWEEWWWWW EWEWEEEEE EWEWEEEEW EWEWEEEWE EWEWEEEWW EWEWEWEEE EWEWEWEEW EWEWEWEWE EWEWEWEWW EWEWWEEEE EWEWWEEEW EWEWWEEWE EWEWWEEWW WEWEEWWEE WEWEEWWEW WEWEEWWWE WEWEEWWWW WEWEWEWEE WEWEWEWEW WEWEWEWWE WEWEWEWWW WEWEWWWEE WEWEWWWEW WEWEWWWWE WEWEWWWWW WEWWEEEEE WEWWEEEEW WEWWEEEWE WEWWEEEWW WEWWEWEEE WEWWEWEEW WEWWEWEWE WEWWEWEWW WEWWWEEEE WEWWWEEEW WEWWWEEWE WEWWWEEWW WWEEEWWEE WWEEEWWEW WWEEEWWWE WWEEEWWWW WWEEWEWEE WWEEWEWEW WWEEWEWWE WWEEWEWWW WWEEWWWEE WWEEWWWEW WWEEWWWWE WWEEWWWWW WWEWEEEEE WWEWEEEEW WWEWEEEWE WWEWEEEWW WWEWEWEEE WWEWEWEEW
6
WWEWEWEWE WWEWEWEWW WWEWWEEEE WWEWWEEEW WWEWWEEWE WWEWWEEWW
The set of illegal states the that violate both C2 and C4: (96) EEWEEEWEE EEWEEEWEW EEWEEEWWE EEWEEWWEE EEWEEWWEW EEWEEWWWE EEWEWEWEE EEWEWEWEW EEWEWEWWE EEWEWWWEE EEWEWWWEW EEWEWWWWE EEWWEEEEW EEWWEEEWE EEWWEEEWW EEWWEWEEW EEWWEWEWE EEWWEWEWW EEWWWEEEW EEWWWEEWE EEWWWEEWW EEWWWWEEW EEWWWWEWE EEWWWWEWW EWEEEEWEE EWEEEEWEW EWEEEEWWE EWEEEWWEE EWEEEWWEW EWEEEWWWE EWEEWEWEE EWEEWEWEW EWEEWEWWE EWEEWWWEE EWEEWWWEW EWEEWWWWE EWEWEEEEW EWEWEEEWE EWEWEEEWW EWEWEWEEW EWEWEWEWE EWEWEWEWW EWEWWEEEW EWEWWEEWE EWEWWEEWW EWEWWWEEW EWEWWWEWE EWEWWWEWW WEWEEEWEE WEWEEEWEW WEWEEEWWE WEWEEWWEE WEWEEWWEW WEWEEWWWE WEWEWEWEE WEWEWEWEW WEWEWEWWE WEWEWWWEE WEWEWWWEW WEWEWWWWE WEWWEEEEW WEWWEEEWE WEWWEEEWW WEWWEWEEW WEWWEWEWE WEWWEWEWW WEWWWEEEW WEWWWEEWE WEWWWEEWW WEWWWWEEW WEWWWWEWE WEWWWWEWW WWEEEEWEE WWEEEEWEW WWEEEEWWE WWEEEWWEE WWEEEWWEW WWEEEWWWE WWEEWEWEE WWEEWEWEW WWEEWEWWE WWEEWWWEE WWEEWWWEW WWEEWWWWE WWEWEEEEW WWEWEEEWE WWEWEEEWW WWEWEWEEW WWEWEWEWE WWEWEWEWW WWEWWEEEW WWEWWEEWE WWEWWEEWW WWEWWWEEW WWEWWWEWE WWEWWWEWW
The set of illegal states the that violate both C3 and C4: (144) EEEEEWWEE EEEEEWWEW EEEEEWWWE EEEEWEWEE EEEEWEWEW EEEEWEWWE EEEEWWWEE EEEEWWWEW EEEEWWWWE EEEWEEEEW EEEWEEEWE EEEWEEEWW EEEWEWEEW EEEWEWEWE EEEWEWEWW EEEWWEEEW EEEWWEEWE EEEWWEEWW EEWEEWWEE EEWEEWWEW EEWEEWWWE EEWEWEWEE EEWEWEWEW EEWEWEWWE EEWEWWWEE EEWEWWWEW EEWEWWWWE EEWWEEEEW EEWWEEEWE EEWWEEEWW EEWWEWEEW EEWWEWEWE EEWWEWEWW EEWWWEEEW EEWWWEEWE EEWWWEEWW EWEEEWWEE EWEEEWWEW EWEEEWWWE EWEEWEWEE EWEEWEWEW EWEEWEWWE EWEEWWWEE EWEEWWWEW EWEEWWWWE EWEWEEEEW EWEWEEEWE EWEWEEEWW EWEWEWEEW EWEWEWEWE EWEWEWEWW EWEWWEEEW EWEWWEEWE EWEWWEEWW EWWEEWWEE EWWEEWWEW EWWEEWWWE EWWEWEWEE EWWEWEWEW EWWEWEWWE EWWEWWWEE EWWEWWWEW EWWEWWWWE EWWWEEEEW EWWWEEEWE EWWWEEEWW EWWWEWEEW EWWWEWEWE EWWWEWEWW EWWWWEEEW EWWWWEEWE EWWWWEEWW WEEEEWWEE WEEEEWWEW WEEEEWWWE WEEEWEWEE WEEEWEWEW WEEEWEWWE WEEEWWWEE WEEEWWWEW WEEEWWWWE WEEWEEEEW WEEWEEEWE WEEWEEEWW WEEWEWEEW WEEWEWEWE WEEWEWEWW WEEWWEEEW WEEWWEEWE WEEWWEEWW WEWEEWWEE WEWEEWWEW WEWEEWWWE WEWEWEWEE WEWEWEWEW WEWEWEWWE WEWEWWWEE WEWEWWWEW WEWEWWWWE WEWWEEEEW WEWWEEEWE WEWWEEEWW WEWWEWEEW WEWWEWEWE WEWWEWEWW WEWWWEEEW WEWWWEEWE WEWWWEEWW WWEEEWWEE WWEEEWWEW WWEEEWWWE WWEEWEWEE WWEEWEWEW WWEEWEWWE
7
WWEEWWWEE WWEEWWWEW WWEEWWWWE WWEWEEEEW WWEWEEEWE WWEWEEEWW WWEWEWEEW WWEWEWEWE WWEWEWEWW WWEWWEEEW WWEWWEEWE WWEWWEEWW WWWEEWWEE WWWEEWWEW WWWEEWWWE WWWEWEWEE WWWEWEWEW WWWEWEWWE WWWEWWWEE WWWEWWWEW WWWEWWWWE WWWWEEEEW WWWWEEEWE WWWWEEEWW WWWWEWEEW WWWWEWEWE WWWWEWEWW WWWWWEEEW WWWWWEEWE WWWWWEEWW
The set of illegal states the that violate C2, C3 and C4: (72) EEWEEWWEE EEWEEWWEW EEWEEWWWE EEWEWEWEE EEWEWEWEW EEWEWEWWE EEWEWWWEE EEWEWWWEW EEWEWWWWE EEWWEEEEW EEWWEEEWE EEWWEEEWW EEWWEWEEW EEWWEWEWE EEWWEWEWW EEWWWEEEW EEWWWEEWE EEWWWEEWW EWEEEWWEE EWEEEWWEW EWEEEWWWE EWEEWEWEE EWEEWEWEW EWEEWEWWE EWEEWWWEE EWEEWWWEW EWEEWWWWE EWEWEEEEW EWEWEEEWE EWEWEEEWW EWEWEWEEW EWEWEWEWE EWEWEWEWW EWEWWEEEW EWEWWEEWE EWEWWEEWW WEWEEWWEE WEWEEWWEW WEWEEWWWE WEWEWEWEE WEWEWEWEW WEWEWEWWE WEWEWWWEE WEWEWWWEW WEWEWWWWE WEWWEEEEW WEWWEEEWE WEWWEEEWW WEWWEWEEW WEWWEWEWE WEWWEWEWW WEWWWEEEW WEWWWEEWE WEWWWEEWW WWEEEWWEE WWEEEWWEW WWEEEWWWE WWEEWEWEE WWEEWEWEW WWEEWEWWE WWEEWWWEE WWEEWWWEW WWEEWWWWE WWEWEEEEW WWEWEEEWE WWEWEEEWW WWEWEWEEW WWEWEWEWE WWEWEWEWW WWEWWEEEW WWEWWEEWE WWEWWEEWW
The set of illegal states the that violate only C2: (132) EEWEEEEEW EEWEEEEWE EEWEEEEWW EEWEEEWWW EEWEEWEEE EEWEEWEEW EEWEEWEWE EEWEEWEWW EEWEWEEEE EEWEWEEEW EEWEWEEWE EEWEWEEWW EEWEWWEEE EEWEWWEEW EEWEWWEWE EEWEWWEWW EEWWEEWEE EEWWEEWEW EEWWEEWWE EEWWEEWWW EEWWEWWEE EEWWEWWEW EEWWEWWWE EEWWEWWWW EEWWWEWEE EEWWWEWEW EEWWWEWWE EEWWWEWWW EEWWWWEEE EEWWWWWEE EEWWWWWEW EEWWWWWWE EEWWWWWWW EWEEEEEEE EWEEEEEEW EWEEEEEWE EWEEEEEWW EWEEEEWWW EWEEEWEEE EWEEEWEEW EWEEEWEWE EWEEEWEWW EWEEWEEEE EWEEWEEEW EWEEWEEWE EWEEWEEWW EWEEWWEEE EWEEWWEEW EWEEWWEWE EWEEWWEWW EWEWEEWEE EWEWEEWEW EWEWEEWWE EWEWEEWWW EWEWEWWEE EWEWEWWEW EWEWEWWWE EWEWEWWWW EWEWWEWEE EWEWWEWEW EWEWWEWWE EWEWWEWWW EWEWWWEEE EWEWWWWEE EWEWWWWEW EWEWWWWWE WEWEEEEEW WEWEEEEWE WEWEEEEWW WEWEEEWWW WEWEEWEEE WEWEEWEEW WEWEEWEWE WEWEEWEWW WEWEWEEEE WEWEWEEEW WEWEWEEWE WEWEWEEWW WEWEWWEEE WEWEWWEEW WEWEWWEWE WEWEWWEWW WEWWEEWEE WEWWEEWEW WEWWEEWWE WEWWEEWWW WEWWEWWEE WEWWEWWEW WEWWEWWWE WEWWEWWWW WEWWWEWEE WEWWWEWEW WEWWWEWWE WEWWWEWWW WEWWWWEEE WEWWWWWEE WEWWWWWEW WEWWWWWWE WEWWWWWWW WWEEEEEEE WWEEEEEEW WWEEEEEWE WWEEEEEWW WWEEEEWWW WWEEEWEEE WWEEEWEEW WWEEEWEWE WWEEEWEWW WWEEWEEEE WWEEWEEEW WWEEWEEWE WWEEWEEWW WWEEWWEEE WWEEWWEEW
8
WWEEWWEWE WWEEWWEWW WWEWEEWEE WWEWEEWEW WWEWEEWWE WWEWEEWWW WWEWEWWEE WWEWEWWEW WWEWEWWWE WWEWEWWWW WWEWWEWEE WWEWWEWEW WWEWWEWWE WWEWWEWWW WWEWWWEEE WWEWWWWEE WWEWWWWEW WWEWWWWWE
The set of illegal states the that violate only C3: (24) EEEEEWWWW EEEEWEWWW EEEEWWWWW EEEWEEEEE EEEWEWEEE EEEWWEEEE EWWEEWWWW EWWEWEWWW EWWEWWWWW EWWWEEEEE EWWWEWEEE EWWWWEEEE WEEEEWWWW WEEEWEWWW WEEEWWWWW WEEWEEEEE WEEWEWEEE WEEWWEEEE WWWEEWWWW WWWEWEWWW WWWEWWWWW WWWWEEEEE WWWWEWEEE WWWWWEEEE
The set of illegal states the that violate only C4: (24) EEEEEEWEE EEEEEEWEW EEEEEEWWE EEEWWWEEW EEEWWWEWE EEEWWWEWW EWWEEEWEE EWWEEEWEW EWWEEEWWE EWWWWWEEW EWWWWWEWE EWWWWWEWW WEEEEEWEE WEEEEEWEW WEEEEEWWE WEEWWWEEW WEEWWWEWE WEEWWWEWW WWWEEEWEE WWWEEEWEW WWWEEEWWE WWWWWWEEW WWWWWWEWE WWWWWWEWW
SECTION B: FORMING A GRAPH
There are 38 legal states that are part of at least one shortest path. EEEEEEEEE [‘WWWEEEEEE’]
EEEEEEEEW [‘WEEEEEWWW’, ‘WWWEEEEEW’]
EEEEEEEWE [‘WEEEEEWWW’, ‘WWWEEEEWE’]
EEEEEEEWW [‘WEEEEEWWW’, ‘WEEWEEWWW’] EEEEEEWWW [‘WEEWEEWWW’, ‘WWWEEEWWW’] EEEEEWEEE [‘WEEWWWEEE’, ‘WWWEEWEEE’] EEEEWEEEE [‘WEEWWWEEE’, ‘WWWEWEEEE’] EEEEWWEEE [‘WEEWWWEEE’, ‘WEEWWWWEE’] EEEWEWWWW [‘WWEWWWWWW’, ‘WWWWEWWWW’] EEEWWEWWW [‘WWEWWWWWW’, ‘WWWWWEWWW’] EEEWWWEEE [‘WEEWWWWEE’, ‘WWWWWWEEE’] EEEWWWWEW [‘WWEWWWWWW’, ‘WWWWWWWEW’] EEEWWWWWE [‘WWEWWWWWW’, ‘WWWWWWWWE’] EEEWWWWWW [‘WWEWWWWWW’, ‘WWWWWWWWW’] EEWEEEEEE [‘WWWEEEEEE’, ‘WWWEEEEEW’, EWWEEEEWW [‘WWWEEEWWW’, ‘WWWWEEWWW’] EWWEEEWWW [‘WWWWEEWWW’, ‘WWWWEWWWW’, EWWEWWEEE [‘WWWWWWEEE’, ‘WWWWWWWEE’] EWWWWWEEE [‘WWWWWWWEE’, ‘WWWWWWWEW’, WEEEEEWWW [‘EEEEEEEEW’, ‘EEEEEEEWE’,
‘WWWEEEEWE’,
‘WWWWWEWWW’]
‘WWWWWWWWE’]
‘EEEEEEEWW’]
‘WWWEEWEEE’, ‘WWWEWEEEE’]
9
WEEWEEWWW [‘EEEEEEEWW’, ‘EEEEEEWWW’]
WEEWWWEEE [‘EEEEEWEEE’,
WEEWWWWEE [‘EEEEWWEEE’,
WWEWWWWWW [‘EEEWEWWWW’,
WWWEEEEEE [‘EEEEEEEEE’, ‘EEWEEEEEE’] WWWEEEEEW [‘EEEEEEEEW’, ‘EEWEEEEEE’] WWWEEEEWE [‘EEEEEEEWE’, ‘EEWEEEEEE’] WWWEEEWWW [‘EEEEEEWWW’, ‘EWWEEEEWW’] WWWEEWEEE [‘EEEEEWEEE’, ‘EEWEEEEEE’] WWWEWEEEE [‘EEEEWEEEE’, ‘EEWEEEEEE’] WWWWEEWWW [‘EWWEEEEWW’, ‘EWWEEEWWW’] WWWWEWWWW [‘EEEWEWWWW’, ‘EWWEEEWWW’] WWWWWEWWW [‘EEEWWEWWW’, ‘EWWEEEWWW’] WWWWWWEEE [‘EEEWWWEEE’, ‘EWWEWWEEE’] WWWWWWWEE [‘EWWEWWEEE’, ‘EWWWWWEEE’] WWWWWWWEW [‘EEEWWWWEW’, ‘EWWWWWEEE’] WWWWWWWWE [‘EEEWWWWWE’, ‘EWWWWWEEE’] WWWWWWWWW [‘EEEWWWWWW’]
‘EEEEWWEEE’]
‘EEEWWWWEW’, ‘EEEWWWWWE’, ‘EEEWWWWWW’]
‘EEEEWEEEE’,
‘EEEWWWEEE’]
‘EEEWWEWWW’,
There are 70 legal states that are NOT part of any shortest
path.
EEEEEWEEW EEEEEWEWE EEEEEWEWW EEEEWEEEW EEEEWWEEW EEEEWWEWE EEEEWWEWW EEEWEEWEE EEEWEEWWW EEEWEWWEE EEEWEWWEW EEEWEWWWE EEEWWEWWE EEEWWWWEE EWEWWWWWW EWWEEEEEE EWWEEWEEE EWWEEWEEW EWWEEWEWE EWWEEWEWW EWWEWEEWE EWWEWEEWW EWWEWWEEW EWWEWWEWE WEEWEEWEW WEEWEEWWE WEEWEWWEE WEEWEWWEW WEEWWEWEE WEEWWEWEW WEEWWEWWE WEEWWEWWW WEEWWWWWW WEWEEEEEE WWWEEEEWW WWWEEWEEW WWWEWEEEW WWWEWEEWE WWWEWEEWW WWWEWWEEE WWWEWWEWW WWWWEEWEE WWWWEEWEW WWWWEEWWE WWWWEWWWE WWWWWEWEE WWWWWEWEW WWWWWEWWE
SECTION C: SHORTEST PATHS
EEEEWEEWE EEEEWEEWW
EEEWEEWEW EEEWEEWWE
EEEWWEWEE EEEWWEWEW
EWWEEEEEW EWWEEEEWE
EWWEWEEEE EWWEWEEEW
EWWEWWEWW WEEWEEWEE
WEEWEWWWE WEEWEWWWW
WEEWWWWEW WEEWWWWWE
WWWEEWEWE WWWEEWEWW
WWWEWWEEW WWWEWWEWE
WWWWEWWEE WWWWEWWEW
East: [‘Ahab’, ‘Ananias’, ‘Jezebel’, ‘Moses’, ‘Pharaoh’, ‘Sapphira’, ‘servant of Ahab’, ‘servant of Ananias’] West: []
(1) Moses and Pharaoh go from the east to the west.
East: [‘Ahab’, ‘Ananias’, ‘Jezebel’, ‘Sapphira’, ‘servant of Ahab’, ‘servant of Ananias’] West: [‘Moses’, ‘Pharaoh’]
(2) Moses goes from the west to the east.
10
East: [‘Ahab’, ‘Ananias’, ‘Jezebel’, ‘Moses’, ‘Sapphira’, ‘servant of Ahab’, ‘servant of Ananias’] West: [‘Pharaoh’]
(3)
East:
West:
(4)
Moses and servant of Ananias go from the east to the west.
[‘Ahab’, ‘Ananias’, ‘Jezebel’, ‘Sapphira’, ‘servant of Ahab’] [‘Moses’, ‘Pharaoh’, ‘servant of Ananias’]
Moses and Pharaoh go from the west to the east.
[‘Ahab’, ‘Ananias’, ‘Jezebel’, ‘Moses’, ‘Pharaoh’, ‘Sapphira’, ‘servant of Ahab’] Ananias and Sapphira go from the east to the west.
[‘Ahab’, ‘Jezebel’, ‘Moses’, ‘Pharaoh’, ‘servant of Ahab’] [‘Ananias’, ‘Sapphira’, ‘servant of Ananias’]
Ananias goes from the west to the east.
East:
West: [‘servant of Ananias’]
(5)
East:
West:
(6)
[‘Ahab’, ‘Ananias’, ‘Jezebel’, ‘Moses’, ‘Pharaoh’, ‘servant of Ahab’] Ahab and Ananias go from the east to the west.
[‘Jezebel’, ‘Moses’, ‘Pharaoh’, ‘servant of Ahab’] [‘Ahab’, ‘Ananias’, ‘Sapphira’, ‘servant of Ananias’] Ahab goes from the west to the east.
[‘Ahab’, ‘Jezebel’, ‘Moses’, ‘Pharaoh’, ‘servant of Ahab’] [‘Ananias’, ‘Sapphira’, ‘servant of Ananias’]
Moses and Pharaoh go from the east to the west.
East:
West: [‘Sapphira’, ‘servant of Ananias’]
(7)
East:
West:
(8)
East:
West:
(9)
East:
West:
(10)Ananias goes from the west to the east.
[‘Ahab’, ‘Jezebel’, ‘servant of Ahab’]
[‘Ananias’, ‘Moses’, ‘Pharaoh’, ‘Sapphira’, ‘servant of Ananias’]
East: [‘Ahab’, ‘Ananias’, ‘Jezebel’, ‘servant of Ahab’] West: [‘Moses’, ‘Pharaoh’, ‘Sapphira’, ‘servant of Ananias’] (11) Ahab and Ananias go from the east to the west.
East: [‘Jezebel’, ‘servant of Ahab’]
West: [‘Ahab’, ‘Ananias’, ‘Moses’, ‘Pharaoh’, ‘Sapphira’, ‘servant of Ananias’] (12) Ahab goes from the west to the east.
East: [‘Ahab’, ‘Jezebel’, ‘servant of Ahab’]
11
West: [‘Ananias’, ‘Moses’, ‘Pharaoh’, ‘Sapphira’, ‘servant of Ananias’] (13) Ahab and servant of Ahab go from the east to the west.
East: [‘Jezebel’]
West: [‘Ahab’, ‘Ananias’, ‘Moses’, ‘Pharaoh’, ‘Sapphira’, ‘servant of Ahab’, ‘servant of Ananias’] (14) Moses and Pharaoh go from the west to the east.
East: [‘Jezebel’, ‘Moses’, ‘Pharaoh’]
West: [‘Ahab’, ‘Ananias’, ‘Sapphira’, ‘servant of Ahab’, ‘servant of Ananias’] (15) Moses and Jezebel go from the east to the west.
East: [‘Pharaoh’]
West: [‘Ahab’, ‘Ananias’, ‘Jezebel’, ‘Moses’, ‘Sapphira’, ‘servant of Ahab’, ‘servant of Ananias’] (16) Moses goes from the west to the east.
East: [‘Moses’, ‘Pharaoh’]
West: [‘Ahab’, ‘Ananias’, ‘Jezebel’, ‘Sapphira’, ‘servant of Ahab’, ‘servant of Ananias’] (17) Moses and Pharaoh go from the east to the west.
12
Marking scheme:
1. Program correctness: 40% (see the rubrics table below)
a. Section A: 16%
i. C1: 2% ii. C2: 2% iii. C3: 2% iv. C4: 2%
v. C2 and C3: 2% vi. C2 and C4: 2% vii. C3 and C4: 2%
viii. C2 and C3 and C4: 2%
b. Section B: 9%
i. Adjacency list: 5% ii. 70 legal states: 4%
c. Section C (shortest path): 15%
2. Code readability: 10% (see the rubrics table below)
3. Report: 50% (see the rubrics table below)
a. Problem statement: 2%
b. State modelling: 2%
c. Types of states: 6%
d. The graph drawing: 5%
e. Abstracted to a graph problem: 2%
f. Identification of abstract data types needed: 3%
g. Applying a shortest-path algorithm for solving the problem: 2% h. Modularization of the program: 5%
i. Completeness of the function signatures: 5%
j. Implementation of the abstract data types (mainly graph) using Python: 3% k. Quality of the writing: 15%
13
Rubrics for program correctness, code readability and documentation, and content of the report
Expectations fully met (4)
Expectations mostly met (3)
Expectations somewhat met (2)
Expectations largely not met (1)
Expectations not met at all (0)
Program Correctness (40%)
The program runs correctly according to the specification for all cases.
The program runs correctly according to the specification almost for all cases.
The program runs correctly according to the specification only for the major cases.
The program runs correctly according to the specification only for a small number of cases.
The program does not run correctly for all cases.
Code readability and documentation (10%)
The code is very well organized and very easy to understand. The documentation is very clear and accurate.
The code is generally well organized and easy to understand. The documentation is generally clear and accurate.
The code is adequately organized and needs some effort to understand. The documentation is adequately prepared.
The code is poorly organized and is difficult to understand. The documentation lends very little help.
No effort to organize the code for understanding. There is no/very little documentation.
Content of the report (50%)
The report documents all the main steps of problem solving very clearly, logically and comprehensively.
The report documents most of the main steps of problem solving clearly, logically and comprehensively.
The report meets just the basic requirements in terms of clarity, logical presentation and comprehensiveness.
Lacking important details and clarity, the report offers limited help in understanding the problem-solving process.
The report is largely incomprehensible. It offers no help in understanding the problem-solving process.
14
Reviews
There are no reviews yet.