F#代写 | CAB402 Programming Paradigms Assignment 1

CAB402 Programming Paradigms

Assignment 1

The purpose of this assignment is to develop your functional programming skills by developing a non-trivial application using F#.

The principal focus will be on learning to program in a “pure” functional style – i.e. without making use of any mutable state. In
order to contrast this pure functional style of programming with the more traditional imperative (impure) and object-oriented
paradigms, you will develop two separate implementations:

1. A pure functional implementation using F#

2. An object-oriented C# implementation

Required Software

1. Visual Studio 2019 (with .NET desktop development and .NET Core 3.1 SDK)
QUT Study Planner

Undergraduate courses within the QUT Science and Engineering Faculty require students to complete:

• A common set of first year units
• A first major (such as Computer Science)
• 2 minors consisting of 4 units per minor, or a second major consisting of 8 units.
Students therefore have choice regarding which major and minors they take. Within each of those study areas there is often
further choice regarding which optional units to study. Students are also free to enrol in units in whatever order they desire,
provided only that they meet the unit prerequisites and the unit is offered in that semester. Given all this choice, it can be difficult
to decide which units to take and when to take them. It is very possible that the order in which you take units may result in it
taking longer to graduate then is strictly necessary. This app is designed to assist QUT students in selecting which units to study
and more importantly, determining the optimal order in which to take them to graduate as soon as possible.

The app takes as input several csv files that provide information about the units and courses at QUT. These files are embedded as
resources within the CourseData project which is part of the skeleton solution provided. The units.csv file lists the code, title
and number of credit points for each unit along with the semesters that it is offered and its prerequisites. The Parser.fs file
provided as part of the skeleton solution contains a parser created using FParseC, an F# Parser Combinator library
(https://www.quanttec.com/fparsec/). The parser can be used to convert the string based prerequisite descriptions in
the csv file into a hierarchical representation. For example, the prerequisite: (CAB201 or ITD121) and (MZB151 or 12cp)
would be converted into the following data structure:

Some units, such as CAB402 are offered only once each year, while others such as CAB202 are offered in both Semester 1 and
Semester 2 each year. Some units at QUT are also offered in the Summer semester.

And Prereq
Or Prereq Or Prereq
Unit Prereq
Unit Prereq
Unit Prereq
CP Prereq
Before we can attempt to determine the optimal order in which to take units, we must start by deciding which study areas and
which units we wish to study. We do this by browsing through the available study areas listed in the tabs on the right side of the
app. You can change courses (IN01 or EN01) using the drop-down list in the top left corner of the window.
We select units from the study areas on the right and drag and drop them onto our study plan on the left. Units highlighted in
green are units that are not yet in our study plan and we meet their prerequisites based on units already in our study plan. Units
highlighted in grey are not currently enrollable as we haven’t met their prerequisites yet. Units with other colours are already in
our study plan. Those units that are already in our study plan are colour coded based on the study area that they were chosen
from. Note, it is possible for the same unit to exist in more than one study area, so when we add it to our study plan it is important
to remember the study area to which it belongs. A UnitInPlan record (defined in Types.fs of the provided skeleton solution)
therefore consists of a unit code, a study area code and a semester of study (which includes both the year and the semester of
offer). A StudyPlan (also defined in Types.fs) is a collection of such UnitInPlan records(order within this collection is not relevant).
Only the enrollable green units can be dragged from the study areas. Units already in the study plan can also be dragged and
dropped, either into a different semester or back into the study area window (to remove them from the study plan). When we
pick up a unit, the semesters within our study plan that we can legally schedule that unit are highlighted in green. Attempting to
drop a unit into any of the other semesters will fail.
Note that the blue lines in the study areas depict prerequisite relationships between units. When we move our mouse over a unit
the title and prerequisites for that unit are displayed at the top middle of the study area window.
Scheduling Wizard

Once we have selected all the units that we wish to study and dragged them onto the study plan we can then use the scheduling
wizard to optimize the plan, i.e. try to complete the chosen units in fewer semesters. Note, we assume that you can study no more
than 4 units per semester and that study commences in 2020 semester 1. We press the Optimize button at the top of the screen
(either the F# version or the C# version) in order to ask the system to search for a better plan. This search may take some time,
especially if our search algorithm in not efficiently implemented. A progress window is displayed while the search is progressing
and automatically closes once the best possible schedule has been found. The following shows a before and after example for
study plan optimization:

Before Optimization:

After Optimization:

MVVM (Model-View-ViewModel)
The GUI app uses the Model-View-ViewModel (MVVM) architectural pattern. See:
• https://en.wikipedia.org/wiki/Model-view-viewmodel,
• https://docs.microsoft.com/en-us/windows/uwp/data-binding/data-binding-and-mvvm,
• https://docs.microsoft.com/en-us/xamarin/xamarin-forms/enterprise-application-patterns/mvvm,
• https://blogs.msdn.microsoft.com/msgulfcommunity/2013/03/13/understanding-the-basics-of-mvvm-design-pattern/)
The GUI app is split into 3 components: The Model, The View and the ViewModel. The model provides data structures for
representing objects in the domain as well as basic “business logic” for the application domain. The View is the part of the
application that determines what the user sees on the screen and what user interactions (clicks, keyboard, gestures, etc) are
allowed. The ViewModel acts as a bridge between the View and the Model:
The View and the ViewModel have been completely implemented for you in the provided skeleton solution, so you need only
implement the Model (an F# version and a C# version).
Skeleton Solution
You have been provided with a skeleton solution that you are required to use. It consists of one Visual Studio Solution that contains
six (6) separate Visual Studio projects:
CourseData Project
A class library containing just csv files embedded as resources. Units.csv contains information about all units, while EN01.csv and
IN01.csv contains information about the study areas and units that make up those courses.
FSharpModel Project
An F# class library that implements the Model component of the MVVM application. This is where most of your work will be done.
It includes:
• Types.fs: A collection of typesrelated to study plans (these types have been provided for you and should not be changed).
• Parser.fs: A set of functions for parsing csv files and prerequisites (these functions have been provided for you).
• Model.fs: A set of skeleton functions that you need to implement. Replace the “Fix me” comments with F# code.
• BoundOptimizer.fs: A set of functions to improve the efficiency of the wizard search (a naïve implementation is provided).
• FSharpSchedulingWizard.fs: The F# version of the scheduling wizard.
CSharpWizard Project
A C# class library that provides an alternative (imperative and object-oriented) implementation of the scheduling wizard. You need
to add code to this project.
ModelUnitTests Project
An extensive set of unit tests for the FSharpModel and CSharpWizard. Use the Test Explorer within Visual Studio to run these unit
tests. These tests have been provided for you. Please do not modify this project.
ViewModel Project
A C# class library that implements the ViewModel of the MVVM application. Please explore, but do not modify this project.
WPFView Project
A C# Windows Presentation Foundation application that implements the View part of the MVVM application. Please explore, but
do not modify this project. This should be your “StartUp Project” when running the GUI app within Visual Studio.
In implementing the functions in FSharpModel, please do not modify the names or signature of the existing functions, but feel
free to create additional helper functions to assist in the implementation of the required functions.
For the CSharpWizard module, the minimum that you need to implement is the TryToImproveSchedule function. You can make
use of types and functions from FSharpModel, including from the CSharpSchedulingWizard – except the
TryToImproveSchedule function. The goal here is to contrast the pure functional style used in the FSharpModel with the
imperative object-oriented style used in CSharpSchedulingWizard. Be sure to follow object-oriented programming and design
best practice when implementing the C# module. You should discuss in your report whether the imperative style with mutable
state lead to better execution performance than the pure function version. You should also compare the two implementations
from the perspective of ease of development, clarity, succinctness, understandability and maintainable. Remember that
regardless of which language or style you are using, readability is mostly determined by good choice of function and variable
names and appropriate use of whitespace.
The Optimization Algorithm
We start with an initial study plan that we aim to improve. From the initial plan we can determine the semester in which we will
complete. Our aim is to try to complete in an earlier semester. Rather than directly trying to find the best possible schedule we
instead try to improve the current plan in an incremental manner. We take whatever is the last semester in the study plan and try
to create a schedule that completes at least one semester earlier. If we succeed at that goal, then we try to further improve the
schedule by aiming for one semester earlier than the schedule that we just found. We continue until we can find not better
schedule. The algorithm actually generates a sequence of successively better study plans – so that the GUI can present the user
with the best plan found so far while waiting for the optimization search to complete. All study is assumed to commence in 2020
semester 1. Once we know the total number of units in the plan, assuming that we can take no more than 4 units per semester
and assuming that all SEF units are only offered in Semester 1 or Semester 2, we can determine the minimum number of semesters
required to complete and therefore the best possible graduation date (based on a 2020 semester 1 start). If we reach this best
possible graduation date, we need not waste time searching for a better schedule.
So, when searching for a study plan, we have a set of units to schedule and a target completion semester. We create the optimized
study plan incrementally, adding one unit to the plan at each stage. At any given stage we have a set of planned units that have
already been assigned a specific semester and a set of units that are yet to be scheduled. Once the set of units remaining to be
scheduled becomes empty, we have a compete schedule. At each step of constructing the study plan we start by selecting one of
the remaining units that is schedulable, i.e. there exists a semester between the first semester (2020/1) and the target completion
semester such that the unit is offered and all of its prerequisites are met based on units already planned in earlier semesters. Once
we’re found such a schedulable unit, we try successively to place it into each of the possible semester between the first semester
and the target completion semester. As soon as we find a semester where than unit can be legally scheduled and it is possible to
successfully schedule the other remaining units, then we have succeeded and stop searching further (at least for the current target
semester). If none of the possible semesters leads to a complete schedule, then we have failed and stop searching further.
Bounds Tightening (Challenge Exercise!)
This search algorithm is guaranteed to eventually find the optimal study plan; however, it has exponential complexity and may
therefore take a very long time to execute for study plans containing large numbers of units. To try to improve the search time we
need to restrict the number of combinations explored by making the algorithm smarter. If the first semester is 2020/1 and the
last semester is 2024/2 then for every unit, we have 15 possible semesters to try. However, by considering prerequisite
relationships between units within the study plan we can reduce the set of possible semesters to try.
For example, if the study plan included IFB104, CAB203 and CAB402 and the target last semester was 2022/2, the latest that
CAB402 could be taken would be 2022/1 (since it is not offered in semester 2). CAB203 must be taken before CAB402, therefore
the latest that CAB203 could be taken would be 2021/1 (since it is not offered in semester 2). IFB104 must be taken before CAB203,
therefore the latest that IFB104 could be taken would be 2020/2. We similarly compute the earliest semester that each unit could
be taken considering the semesters they are offered and mandatory dependencies between units. Once we have the earliest and
latest possible semesters in which each unit could be taken, we can then generate a tighter sequence of all possible semesters in
between in which it might be taken (provided it is offered in those semesters). This information is stored in PlannedUnit record
(provided in Types.fs) and passed as part of a BoundPlan from the TryToImproveSchedule function to the
scheduleRemaining function.
But how can we determine that IFB104 must be taken before CAB203? If our plan contains say IFB104 and CAB203 then we can’t
necessarily assume that IFB104 must be taken before CAB203 because the prerequisite for CAB203 is:
EGD126 or IFB104 or ITD104 or MZB126
so, the prerequisite might be achieved by one of those other units which would therefore allow CAB203 to be taken before ITF104.
However, if none of those other units are in the plan, then IFB104 must be taken before CAB203. So, to determine mandatory
dependencies, we consider not only the prerequisites, but also the other units in the plan. Let’s assume we have a plan involving
units X and Y that is legal. If we find that removing X from the plan make Y no longer enrollable (in any semester), then we can
conclude that X must be taken before Y.
In the skeleton solution a naïve implementation of the boundUnitsInPlan function is provided within the BoundsOptimizer
module. This naïve implementation simply returns the sequence of all semesters from the first semester to the target semester
for all remaining units. It will work, but the resulting optimization search will be very slow for study plans with larger number of
units. For those students aiming to merely pass CAB402 you can simply use that provided implementation. For those students
seeking a challenge and aiming for a grade of 6 or 7 in CAB402 you should replace that implementation with the algorithm
described above. Note: the unit tests assume that the unitDependenciesWithinPlan and boundUnitsInPlan functions have
been implemented as above so you should expect those unit tests to fail unless you have changed the algorithm.
Useful F# Functions and Constructs to Know
F# Function/Construct Number of occurrences in my sample solution
let 120
|> 50
lambda functions 42
Seq.map 14
match … with … 11
Seq.filter 7
seq { … } 5
Seq.forall 4
Seq.exists 3
Seq.isEmpty 3
yield 3
yield! 3
Option.None 2
Seq.append 2
Seq.concat 2
Seq.empty 2
Seq.length 2
Seq.max 2
Seq.toList 2
Seq.tryFind 2
IsNone 1
IsSome 1
List.filter 1
Map.find 1
Option.flatten 1
Option.isSome 1
Seq.min 1
Seq.sum 1
Set.contains 1
Set.map 1
Set.toSeq 1
String.concat 1
What to Submit
1. A 1-2 page PDF report discussing your experience and comparing the two approaches (F# pure functional and C# objectoriented imperative). Your comparison should include a discussion on the efficiency and effectiveness of the two
approaches. You should discuss which was easier to program, which code is easier to read, understand and maintain,
which is more concise and which produces more efficient code. Provide measures were applicable to support your claims.
2. A zip file containing your entire Visual Studio Solution folder.
You should work with the skeleton visual studio solution provided and make changes only to the following projects:
• FSharpModel
• CSharpWizard
• All occurrences of // TODO: Fixme comment should be replaced by an actual implementation.
• Extra helper functions and methods should be added as needed. Complex functions and methods should be
broken down into simpler functions. Ensure you use meaningful names for all functions, methods, parameters
and variables.
• Ideally, all 21412 unit tests should pass.
To reduce file size when submitting you should remove the following:
• .vs folder
• packages folder
• bin folders
• obj folders
• Visual Studio solution files except for CAB402StudyPlanner.sln
Everything remaining should be added to a compressed zip file with a name of the form n1234567.zip
Note: this must be a zip file, not a tar file, not a rar file, not an iso file, etc.
When we mark your assignment we will:
1. Unzip your zip file
2. Double click on CAB402StudyPlanner.sln to open your solution in Visual Studio 2019
3. Perform a Rebuild Solution (this should cause any required packages to download as necessary).
4. Run all the unit tests via the Test Explorer Window
5. Start your WPFView application and test that it behaves as expected, trying both the Optimize (F#) and Optimize
(C#) commands for various study plans.
6. We will then browse your source code and assess it against the assessment criteria.