III: Algorithms

This worksheet will assess your knowledge of the algorthmic thinking we have been exploring in the workshop content. The worksheet is formed of two parts; a quiz designed to test your understanding of the topic, and a programming task, designed to test how well you can apply the knowledge in practice.

To complete this worksheet:

Complete the worksheet 3 quiz on learning space
Implement the code for the worksheet task

Submission Instructions

For the final submission, you should submit your completed program.cs file and a PDF of your highest mark in the correct folder in your git repository.

The following filenames are expected:

quiz.pdf - the saved quiz result
Calculator.cs - your solution to part B

The final repository must not contain the whole CS project/solution. Only the ‘Calculator.cs’ should be submitted. Your code must also not import any 3rd party libraries, however use of the standard library is fine.

Part A: Quiz

Complete the quiz, ‘Worksheet 3: Complexity Quiz’ on learning space.

Part B: Programming Activity

Examine the provided skeleton project. This is a program designed to implement some of the concepts we have talked about in session, but there are some features missing. Your task is to implement these in such a way that the contract specified in this document, and the comments is met.

You must not alter the function signatures (names, return values, argument types). Doing so will negatively impact your mark, and may result in a mark of zero for this part

Core Tasks

In calculator.cs you will find some method stubs which should be implemented to create a working programme. The expected functions are as follows:

Can (Possibly) Build

The CanPossiblyBuild is expected to return if it is possible to create the product passed in as an argument given the provided cookbook.

If the product is a raw product, the function must return True
If the product is a composite product, and it is possible to construct it, the function must return true
If the product does not exist, or requires a recipe which will not work (eg, it depends on a product which does not exist) then the function must return False

Calculate Required Build Time

The CalculateTimeRequired function is expected to return the total time required to construct a product from raw materials. If the product is composed of composite products, the construction time for these products must also be factored into the construction time.

If the product is a raw product, the function must return 0
If the product is a composite product, the function must calculate the sum of all required construction times to build the product.
If the product does not exist, or the product cannot be constructed the function must return -1
If the product has multiple recipes then the first valid recipe should be considered

The must critera above can assume that the first (valid) recipe for a product can be considered only. This is is equilvient to setting the mode argument to first. In this mode, the program does not need to consider multiple recipes alternatives.

The should criteria for this function revolves around more advanced handling products with multiple recipes:

If mode is ‘Fastest’ the function should return the smallest possible build time (prioritise recipes which have a lower total time).
If mode is ‘Cheapest’ the function should return the smallest total raw ingredents required (all ingrediant counts are considered equal, so 1 unit of water = 1 unit of sugar)
In either of these modes, the function should not consider any recipe which is not possible, considering only possible solutions (ie, skip any impossible recipes)
The function should still return -1 if the product is impossible to construct

Considering the complexity of some of these methods, it is important to remember that functions which take exessively long to execute will be counted as a failure for the purposes of these test cases (timeout).

Get Raw Materials

The function GetRawMaterialsForProduct should calculate the total of each raw material required for a construction. For example, if a product p1 requires 2 p2 and constructing a p2 requires 3 r1 then constructing a p1 would require 2 lots of the resources for a p2, so the required quantity would be: 2 x 3 = 6 r1s.

If the product is a raw product, an empty dictionary must be returned
If the product is a composite product, a dictionary containing the total raw resources required must be returned
If the product cannot be constructed, null must be returned

The must critera above can assume that the first recipe for a product can be considered only. This is is equilvient to setting the mode argument to first. In this mode, the program does not need to consider mutliple recipe alternatives.

The should criteria for this function revolves around more advanced handling products with multiple recipes:

If mode is ‘Fastest’ the function should return the smallest possible build time (prioritise recipes which have a lower total time).
If mode is ‘Cheapest’ the function should return the smallest total raw ingredents required (all ingrediant counts are considered equal, so 1 unit of water = 1 unit of sugar)
In either of these modes, the function should not consider any recipe which is not possible, considering only possible solutions (ie, skip any impossible recipes)
The function should still return -1 if the product is impossible to construct

(note, this is the same intepretation as the previous function)

Advanced Tasks

The two advanced functions are for dealing with situations where some recipes might not be permitted.

May Contain Item

The MayContainItem function is passed both a product, and an item which is to be searched for. The function must figure out if the item can be used in the construction of the item.

For example, if the product was coffee and the item was milk the function must figure out if its possible to construct a coffee could use milk (anywhere in the chain).

The function must return true if constructing the product can involve item
The function must return false if it not is possible to construct the product using the item
The function must return false if it is not possible to construct the product
The function should be robust against recursive and invalid recipes (products which require themselves)

Can Construct Item

The CanConstructItem function is passed both a product, and an item which cannot be used to construct that product. The function must figure out how to construct the product without using the item.

The function must return false if it is not possible to construct the product without using the item
The function must return true if it is possible to construct the product without using the item
The function must return false if it is not possible to construct the product
The function should be robust against recursive recipes (products which require themselves)

Rubric

Section	Task	Must	Should	Subtotal
Quiz		/₂₀	/₁₀	/₃₀
Core Tasks	Can (possibly) build	/₈	/₃	/₃₁
	Calculate Required Build Time	/₈	/₃
	Get Raw Materials	/₇	/₂
Advanced Tasks	May Contain Item and Can Construct Item	/₁₃	/₁₀	/₂₃
Solution Quality	-	-	/₁₆	/₁₆
		/₅₆	/₄₄	/₁₀₀