XJCO 1921辅导、辅导C++语言编程
- 首页 >> Algorithm 算法 XJCO 1921- Programming Project - Coursework 2
This work is the second coursework for this module. It corresponds to 70% of the overall assessment for
this module.
This work has two submission deadlines:
Submission Deadlines:
1. Planning Report (20 marks): 12 PM BST on Friday 29 April 2022 via Minerva
2. Project implementation (50 marks): 12 PM BST on Wednesday 11 May 2021; via Minerva
Project Implementation [50 marks]
You are asked to implement one of the topics described below using the C programming language. Use a
git repository host like GitHub or Gitlab for version control throughout the project life cycle.
Important notes:
You should create a new git repository for this coursework.
There is code online for the project topics, some in C, some in other languages. If you choose to
use some other code or libraries as a starting point, you must include the reference to this code in
your planning report. Make sure you attribute any publicly available code that you use to its proper
sources.
You must also be clear what the code you have written and what code you found online during lab
marking (e.g., by commenting on the source code).
You are expected to apply the modular and testing programming techniques taught in the module. A
good implementation should have a dedicated (regression) test suite.
Makefile: You should also submit a Makefile with at least two targets: all and clean. "make all"
compiles your code to generate an executable binary, while "make clean" removes all object files
(.o), all executables, and any temporary files created during your run.
Version control: We will check the commit logs of your git repository. We expect to see steady
progress towards completion, as revealed in the pattern of git commits. One of the implications of
this is that we will be penalising any student who develops their code without git, then dumps it all
into git at the last minute.
Project Topics
Project 1 – Route finding
This project asks you to compute the best path between 2 points on a map.
You are given a large data set (to be downloaded from Minerva) that represents all the footpaths on the
Leeds University Campus that you can use to test your application
What does it involve?
Data input from a file - the data file is quite complex, and you have to read it in
Data structures - you have to decide how to store the data; there are suggestions below
Algorithms - you have to create a function to find a path between 2 points; there are standard algorithms for
this that you read about
2
More information
Given a data set in the form of a set of locations (Nodes) and paths connecting them (Links), you should
implement an algorithm to compute the best route between 2 given locations.
"Best" could, for example, be the shortest route, but you may wish to consider other measures.
The data set is attached in the file 'Final_Map.map' and represents footpaths on campus. A jpeg image,
also attached, shows what the path network looks like.
The following requirements are essential:
1. You should create a suitable data structure for the problem - a suitable candidate would be an Adjacency
List which stores a list of points in the data, and for every point, a list of points that are connected to it with
edges.
https://www.khanacademy.org/computing/computer-science/algorithms/graphrepresentation/a/representing-graphs
2. You should consider importing the data into your data structure.
3. You should consider a suitable visualisation of the data - see attached jpeg. A good (1st)
implementation would require you to visualise the map and the path found.
4. You should implement at least one algorithm that finds a path between 2 given points.
Notes
The data file contains several lists of different types of data.
The most basic is the "node" which is a point in space with coordinates defined by (lat,lon) - you can use
them as (x,y). Each node has a defined "id".
The next is the "link" which is a line defined by 2 node id's.
Those 2 data types are enough to define the map of the network. i.e. you can plot each link to get the
picture I attach above.
There is extra data in that file that you can use or ignore.
There are several ways to read the data file. One way is to use fgets() and sscanf().
Project 2 – The Game of Life
In this project, you will build the famous and fascinating system known as "Conway's Game of Life". Life is
a "cellular automaton" - a system of cells that live on a grid, where they live, die and evolve according to the
rules that govern their world. Life is simple - elegant rules give rise to astonishingly complex emergent
behaviour.
The Game is played on a 2-D grid, divided into "cells". Each cell is either "dead" or "alive" at a given
"generation." The Game consists of a set of rules that describe how the cells evolve from generation to
generation.
These rules calculate the state of a cell in the next generation as a function of the states of its neighbouring
cells in the current generation. In a 2-D world, a cell's neighbours are those 8 cells vertically,
horizontally, or diagonally adjacent to that cell.
Conway's set of rules is summarised as:
1. Any live cell with 0 or 1 live neighbour becomes dead because of underpopulation
2. Any live cell with 2 or 3 live neighbours stays alive because its neighbourhood is just right
3. Any live cell with more than 3 live neighbours becomes dead because of overpopulation
3
4. Any dead cell with exactly 3 live neighbours becomes alive by reproduction
Example (the so-called "glider" ):
What does it involve?
In this project, you are asked to implement Conway's Game of Life, with the minor restriction that our 2-D
world is finite. The neighbours of a cell on the edge of the world that would be beyond the edge are
assumed dead.
The initial state of the world should be read from a file, and the final state should be output to a file. You will
need to decide the format of the file.
The size of the world should be configurable and is defined in the initial state file.
The number of steps could be taken from the user at the beginning of the program, or the program keeps
evolving until it is terminate (hence no predefined numbers of steps).
The final state of your program should be saved into the state file so that it can be restored during the next
run.
You will need to decide how to present the world and the evolutionary process.
A good (1st) implementation would require you to visualise the Game graphically and display the
animations of each evolution step. The delay used for animations could be predefined in the initial
state file.
Resources: Graphics library
The SDL library could be a good choice for graphic rendering, but you can use other graphic libraries (e.g.,
QT for Project 1) too.
SDL - the Simple DirectMedia Layer
SDL is a high-level library giving access to the multimedia hardware on your device.
A Tutorial of SDL can be found at https://wiki.libsdl.org/Tutorials
There are many existing applications online that use SDL - if you choose to base your code on one, you
must be able to clearly distinguish your work from the original code.
Note that many SDL applications use C++; this course requires a C implementation.
Installing SDL yourself
For Linux and Mac, it is easy to install SDL from source and compile on your machine.
It is described on the wiki and is quite simple.
Download the C source code and extract.
4
Run './configure','./make','./make install' (as root) and it should work.
Some extensions, e.g. SDL_image, have to be downloaded and built separately.
Building code with SDL:
They can be compiled directly into your code using the standard approach for libraries, as required
ie. -lSDL2 -lSDL2_image -lSDL2_ttf
Example: An example of SDL is provided on Minerva.
5
Planning Report [20 marks]
As part of the project submission, you are required to submit a planning plan. Due to the limited time frame,
plan your project carefully. The report submission deadline is designed to force you to consider the scope
and design of the project carefully before implementing the project.
Specifically, you should write a design and test plan for your chosen project with the following structure:
Title
A chosen title for your project, your name, and your student number
Summary
A short description of your project. Which project choice it is? What your project will do?
List of the key modules and a single sentence describing their purpose (~300 words) .
Test plan
A clear statement of testing methodology, and how will you test your application? (~200 words).
What are the tests you can design for each iteration of your project? What are the tests for each
module?
List of all the tests with description. There are a number of ways for documenting tests. An
example of the expected description is shown in the appendix at the end of this document.
Schedule (~ 0.5 page)
It is important that you have a realistic plan for how much time you will spend on the project and
on each iteration of the design.
Write a plan (in tabular form) for what will you do each week until the project is submitted. This
should include time off required for revision and exams and your holidays.
For each week, write 1-2 sentences describing what you will do.
Notes:
The report should be written in the style of a technical report. Please be concise. I have indicated advisory
page counts though these are not strict.
You do not need to include your code as part of the report. Snippets may be used if appropriate, but only if
illustrating a specific point.
6
Submissions
There are two submissions for this coursework:
The planning report is due at 12 PM BST on Friday, 29 April 2022.
The project implementation is due at 12 PM BST on Wednesday, 11 May 2022.
You should follow the instructions below on how to prepare your submission. No late submission will be
accepted unless this was agreed in advance.
Planning Report
You need to submit two copies of your report. Submit a hard copy to the SWJTU lecturer/TA/teaching
office and an electronic copy of your report as a single PDF file to the Turnitin submission portal on
Minerva. You need to submit both copies by 12 PM BST on Friday, 29 April 2022. Checks for
plagiarism and collusion will be carried on for the report.
Project Implementation
Submit your entire git repository (containing your code, regression test suite, and a Makefile or
CMakeList.txt for building the program), along with a ReadMe.txt file containing (1) the URL of your git
repository, (2) a screenshot of your git commit history and (3) instructions on how to run your program,
all in in a single zip (.zip or .gz) file through Minerva.
Important notes on the submission:
• Write the program in standard C. If you write your code in any other language, it will not be
assessed, and you will get a zero mark.
• This is an individual project, and you are not supposed to work in groups or pairs
with other students.
• Be aware that plagiarism in your code will earn you a zero mark and will have very serious
consequences. If two (or more) students have large portions of their files nearly identical, they
will be accused of plagiarism or collusion. If found guilty, all parties involved will incur the
penalty, regardless of who was the author of the code. For this reason, never show or give
access to your code to anyone. Do not help a colleague by sharing your code, or you will both
be found guilty of collusion.
• It is your responsibility to make sure that nobody has access to your code. Lock the session
if you leave your computer unattended.
• Make sure to download and check your submission. Corrupted files, binary files, wrong
versions, copies of your project (over the years, we have seen it all), or anything other than
what is requested in this document will be considered an invalid submission.
• We will not accept submissions other than through Minerva.
7
Project Demonstration
• The project implementation will be marked during a lab session after the submission
deadline.
• The projects will be evaluated on the correctness of code and ingenuity.
• During marking, you will be asked to reflect on your project development. What challenges
you faced and how you addressed them and what you learned from this exercise?
• You will be asked to demonstrate your work from your Minerva submission.
• You need to demonstrate your work to a member of the course team, failing to do so will
result in 0 marks.
• You need to come to the marking session with your exercise completed. We will not be
able to provide support for this exercise during marking.
• You should be able to explain what you have done clearly, to show that you understand the
concepts introduced.
• Checks for plagiarism and collusion will be carried out on all work.
8
Appendix
Example test case description
Using Coursework 1 as an example
Function: int load_books (FILE *file, BookArray* a);
Expected behaviour:
result == 0
Loads the database of books from file and into an array in the program
Assertions:
The file pointer "file" is not NULL
The Bookarry buffer is not NULL
Test cases:
C1:
Input:
A normal file handler and a benign BookList pointer,
Expected results:
Stored the data into BookArray buffer, return 0
C2:
Input:
A NULL file handler and a benign BookList pointer,
Expected results:
Display an error message and return -1
C3:
Input:
A NULL BookList pointer and a benign file handler
Expected results:
Display an error message and return -1
C4:
Input:
A NULL BookList pointer and a NULL file handler
Expected results:
Display an error message and return -1
This work is the second coursework for this module. It corresponds to 70% of the overall assessment for
this module.
This work has two submission deadlines:
Submission Deadlines:
1. Planning Report (20 marks): 12 PM BST on Friday 29 April 2022 via Minerva
2. Project implementation (50 marks): 12 PM BST on Wednesday 11 May 2021; via Minerva
Project Implementation [50 marks]
You are asked to implement one of the topics described below using the C programming language. Use a
git repository host like GitHub or Gitlab for version control throughout the project life cycle.
Important notes:
You should create a new git repository for this coursework.
There is code online for the project topics, some in C, some in other languages. If you choose to
use some other code or libraries as a starting point, you must include the reference to this code in
your planning report. Make sure you attribute any publicly available code that you use to its proper
sources.
You must also be clear what the code you have written and what code you found online during lab
marking (e.g., by commenting on the source code).
You are expected to apply the modular and testing programming techniques taught in the module. A
good implementation should have a dedicated (regression) test suite.
Makefile: You should also submit a Makefile with at least two targets: all and clean. "make all"
compiles your code to generate an executable binary, while "make clean" removes all object files
(.o), all executables, and any temporary files created during your run.
Version control: We will check the commit logs of your git repository. We expect to see steady
progress towards completion, as revealed in the pattern of git commits. One of the implications of
this is that we will be penalising any student who develops their code without git, then dumps it all
into git at the last minute.
Project Topics
Project 1 – Route finding
This project asks you to compute the best path between 2 points on a map.
You are given a large data set (to be downloaded from Minerva) that represents all the footpaths on the
Leeds University Campus that you can use to test your application
What does it involve?
Data input from a file - the data file is quite complex, and you have to read it in
Data structures - you have to decide how to store the data; there are suggestions below
Algorithms - you have to create a function to find a path between 2 points; there are standard algorithms for
this that you read about
2
More information
Given a data set in the form of a set of locations (Nodes) and paths connecting them (Links), you should
implement an algorithm to compute the best route between 2 given locations.
"Best" could, for example, be the shortest route, but you may wish to consider other measures.
The data set is attached in the file 'Final_Map.map' and represents footpaths on campus. A jpeg image,
also attached, shows what the path network looks like.
The following requirements are essential:
1. You should create a suitable data structure for the problem - a suitable candidate would be an Adjacency
List which stores a list of points in the data, and for every point, a list of points that are connected to it with
edges.
https://www.khanacademy.org/computing/computer-science/algorithms/graphrepresentation/a/representing-graphs
2. You should consider importing the data into your data structure.
3. You should consider a suitable visualisation of the data - see attached jpeg. A good (1st)
implementation would require you to visualise the map and the path found.
4. You should implement at least one algorithm that finds a path between 2 given points.
Notes
The data file contains several lists of different types of data.
The most basic is the "node" which is a point in space with coordinates defined by (lat,lon) - you can use
them as (x,y). Each node has a defined "id".
The next is the "link" which is a line defined by 2 node id's.
Those 2 data types are enough to define the map of the network. i.e. you can plot each link to get the
picture I attach above.
There is extra data in that file that you can use or ignore.
There are several ways to read the data file. One way is to use fgets() and sscanf().
Project 2 – The Game of Life
In this project, you will build the famous and fascinating system known as "Conway's Game of Life". Life is
a "cellular automaton" - a system of cells that live on a grid, where they live, die and evolve according to the
rules that govern their world. Life is simple - elegant rules give rise to astonishingly complex emergent
behaviour.
The Game is played on a 2-D grid, divided into "cells". Each cell is either "dead" or "alive" at a given
"generation." The Game consists of a set of rules that describe how the cells evolve from generation to
generation.
These rules calculate the state of a cell in the next generation as a function of the states of its neighbouring
cells in the current generation. In a 2-D world, a cell's neighbours are those 8 cells vertically,
horizontally, or diagonally adjacent to that cell.
Conway's set of rules is summarised as:
1. Any live cell with 0 or 1 live neighbour becomes dead because of underpopulation
2. Any live cell with 2 or 3 live neighbours stays alive because its neighbourhood is just right
3. Any live cell with more than 3 live neighbours becomes dead because of overpopulation
3
4. Any dead cell with exactly 3 live neighbours becomes alive by reproduction
Example (the so-called "glider" ):
What does it involve?
In this project, you are asked to implement Conway's Game of Life, with the minor restriction that our 2-D
world is finite. The neighbours of a cell on the edge of the world that would be beyond the edge are
assumed dead.
The initial state of the world should be read from a file, and the final state should be output to a file. You will
need to decide the format of the file.
The size of the world should be configurable and is defined in the initial state file.
The number of steps could be taken from the user at the beginning of the program, or the program keeps
evolving until it is terminate (hence no predefined numbers of steps).
The final state of your program should be saved into the state file so that it can be restored during the next
run.
You will need to decide how to present the world and the evolutionary process.
A good (1st) implementation would require you to visualise the Game graphically and display the
animations of each evolution step. The delay used for animations could be predefined in the initial
state file.
Resources: Graphics library
The SDL library could be a good choice for graphic rendering, but you can use other graphic libraries (e.g.,
QT for Project 1) too.
SDL - the Simple DirectMedia Layer
SDL is a high-level library giving access to the multimedia hardware on your device.
A Tutorial of SDL can be found at https://wiki.libsdl.org/Tutorials
There are many existing applications online that use SDL - if you choose to base your code on one, you
must be able to clearly distinguish your work from the original code.
Note that many SDL applications use C++; this course requires a C implementation.
Installing SDL yourself
For Linux and Mac, it is easy to install SDL from source and compile on your machine.
It is described on the wiki and is quite simple.
Download the C source code and extract.
4
Run './configure','./make','./make install' (as root) and it should work.
Some extensions, e.g. SDL_image, have to be downloaded and built separately.
Building code with SDL:
They can be compiled directly into your code using the standard approach for libraries, as required
ie. -lSDL2 -lSDL2_image -lSDL2_ttf
Example: An example of SDL is provided on Minerva.
5
Planning Report [20 marks]
As part of the project submission, you are required to submit a planning plan. Due to the limited time frame,
plan your project carefully. The report submission deadline is designed to force you to consider the scope
and design of the project carefully before implementing the project.
Specifically, you should write a design and test plan for your chosen project with the following structure:
Title
A chosen title for your project, your name, and your student number
Summary
A short description of your project. Which project choice it is? What your project will do?
List of the key modules and a single sentence describing their purpose (~300 words) .
Test plan
A clear statement of testing methodology, and how will you test your application? (~200 words).
What are the tests you can design for each iteration of your project? What are the tests for each
module?
List of all the tests with description. There are a number of ways for documenting tests. An
example of the expected description is shown in the appendix at the end of this document.
Schedule (~ 0.5 page)
It is important that you have a realistic plan for how much time you will spend on the project and
on each iteration of the design.
Write a plan (in tabular form) for what will you do each week until the project is submitted. This
should include time off required for revision and exams and your holidays.
For each week, write 1-2 sentences describing what you will do.
Notes:
The report should be written in the style of a technical report. Please be concise. I have indicated advisory
page counts though these are not strict.
You do not need to include your code as part of the report. Snippets may be used if appropriate, but only if
illustrating a specific point.
6
Submissions
There are two submissions for this coursework:
The planning report is due at 12 PM BST on Friday, 29 April 2022.
The project implementation is due at 12 PM BST on Wednesday, 11 May 2022.
You should follow the instructions below on how to prepare your submission. No late submission will be
accepted unless this was agreed in advance.
Planning Report
You need to submit two copies of your report. Submit a hard copy to the SWJTU lecturer/TA/teaching
office and an electronic copy of your report as a single PDF file to the Turnitin submission portal on
Minerva. You need to submit both copies by 12 PM BST on Friday, 29 April 2022. Checks for
plagiarism and collusion will be carried on for the report.
Project Implementation
Submit your entire git repository (containing your code, regression test suite, and a Makefile or
CMakeList.txt for building the program), along with a ReadMe.txt file containing (1) the URL of your git
repository, (2) a screenshot of your git commit history and (3) instructions on how to run your program,
all in in a single zip (.zip or .gz) file through Minerva.
Important notes on the submission:
• Write the program in standard C. If you write your code in any other language, it will not be
assessed, and you will get a zero mark.
• This is an individual project, and you are not supposed to work in groups or pairs
with other students.
• Be aware that plagiarism in your code will earn you a zero mark and will have very serious
consequences. If two (or more) students have large portions of their files nearly identical, they
will be accused of plagiarism or collusion. If found guilty, all parties involved will incur the
penalty, regardless of who was the author of the code. For this reason, never show or give
access to your code to anyone. Do not help a colleague by sharing your code, or you will both
be found guilty of collusion.
• It is your responsibility to make sure that nobody has access to your code. Lock the session
if you leave your computer unattended.
• Make sure to download and check your submission. Corrupted files, binary files, wrong
versions, copies of your project (over the years, we have seen it all), or anything other than
what is requested in this document will be considered an invalid submission.
• We will not accept submissions other than through Minerva.
7
Project Demonstration
• The project implementation will be marked during a lab session after the submission
deadline.
• The projects will be evaluated on the correctness of code and ingenuity.
• During marking, you will be asked to reflect on your project development. What challenges
you faced and how you addressed them and what you learned from this exercise?
• You will be asked to demonstrate your work from your Minerva submission.
• You need to demonstrate your work to a member of the course team, failing to do so will
result in 0 marks.
• You need to come to the marking session with your exercise completed. We will not be
able to provide support for this exercise during marking.
• You should be able to explain what you have done clearly, to show that you understand the
concepts introduced.
• Checks for plagiarism and collusion will be carried out on all work.
8
Appendix
Example test case description
Using Coursework 1 as an example
Function: int load_books (FILE *file, BookArray* a);
Expected behaviour:
result == 0
Loads the database of books from file and into an array in the program
Assertions:
The file pointer "file" is not NULL
The Bookarry buffer is not NULL
Test cases:
C1:
Input:
A normal file handler and a benign BookList pointer,
Expected results:
Stored the data into BookArray buffer, return 0
C2:
Input:
A NULL file handler and a benign BookList pointer,
Expected results:
Display an error message and return -1
C3:
Input:
A NULL BookList pointer and a benign file handler
Expected results:
Display an error message and return -1
C4:
Input:
A NULL BookList pointer and a NULL file handler
Expected results:
Display an error message and return -1