乐趣区

关于算法:XJCO-1921路由计划

XJCO 1921- Programming Project
Coursework 2 – Route Planning
Deadline: 12 PM BST on Monday, 15 May 2023
This work is the second coursework for this module. It corresponds to 60% of the overall assessment for
this module. Submissions should be made via Gradescope.
Course Specification
Create a software program in C to compute the best path between 2 points on a map according to the
specification below. Use Github (link via Minerva) for version control throughout the project.

  1. Coursework Specification:
    You are given a large data set (to be downloaded from the GitHub Classroom) that represents all the
    footpaths on the Leeds University Campus that you can use to test your application
  2. Your program should read a map from a file. The data file is quite complex, and you have to decide
    how to store the data. A suitable data structure 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.
    You should also find a suitable data structure to store the map attributes, potentially by extending
    the Adjacency List. Care should be taken to maximise memory access efficiency while minimising
    your program’s memory footprint.
  3. You will need to implement an algorithm to compute the best route between two locations.
    Like a real-life route navigation system, the “best” route can be:
    a. The shortest route (by considering the distance between two points)
    b. The quickest route (by considering the speed limit of roads)
    c. The shortest route that meets some constraints, e.g., must pass a given location or POI (point of
    interest)
    A good implementation (1st) should flexibly support all these routing options.
  4. You should consider a suitable way to visualise the data – for example, a basic requirement would
    be plotting routes and edges in Gnuplot. However, A 1st mark would require using a graphical library
    to visualise the data as part of your program in real time.
  5. Your program should allow editing the map attributes by adding new routes and adding or changing
    road attributes like speed limits. The edited map should be saved and can be reloaded by your
    program.
    Data file:
    • 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.
    • There is extra data in that file that you can use, and your program should be able to extend the
    attributes if needed.
    • There are several ways to read the data file. One way is to use fgets() and sscanf().
    Notes:
    • Your program must have more than one module (C file).
    • The program should provide adequate error handling, i.e., display meaningful messages if an
    error occurs and handle common errors. We will be running our own test cases to mark the
    assignments and doing our best to devise creative ways to break your code! You should
    therefore develop your test cases to beat us to it.
    • Your code should not make hard code any relative paths. All file names should be specified by
    command-line arguments. This will allow us to test any file location for input and output.
  6. Good Programming Practice:
    You should follow good software development practices. For this exercise, you are asked to:
    • Follow modular development by making sure the code is modular and well structured; code with
    proper comments
    • Use Makefile for code compilation;
    • Use a git repository for version control
    Notes:
  7. 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.
  8. Modular design: We will check the commit logs of your git repository. By the end of Week 9, you
    should commit a text file called “modules.txt” describing your proposed modules and their purpose.
    Each module should have 1 paragraph of no more than 500 characters describing the module and
    its purpose.
  9. Test plan: By the end of Week 10, you should also commit a text file called “testplan.txt” with no
    more than 2 paragraphs, each of no more than 500 characters, describing your test plan.
  10. 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 and then dumps it
    all into git at the last minute.
    Assessment/marking criteria grid
  11. at 5 if static arrays are used)

  12. specification

  13. the overall mark will be capped at 30 / 60 if the student gets less than 50% in this category
    Submission
    Your work should be submitted to the submission portal on Gradescope.
    Your submission should be in a directory in the root of your git repository called “cw2” and contain
    files that conform to the assignment specification. Your submission should contain all the relevant
    source code and header files, a brief README file explaining how to run your submission and a
    Makefile which builds all of the executables.
    It is your responsibility to ensure that your submission compiles and executes on the lab machine.
    Your git commit and push must be made prior to the submission deadline.
    You should also include a test script called “test.sh” to automatically execute your test cases and any
    test files you rely on.
    In summary, your hand-in should include:

  14. All necessary .c and .h files
  15. A makefile as described above
  16. A test script “test.sh”
  17. A readme file called “readme.txt”
  18. A test plan file called “testplan.txt”
  19. A file called “modules.txt”
  20. Any test data files which you use for your test script.
    With the exception of the test files, all of these files must be in the cw2 directory. You may place the
    test data files in a subdirectory if you wish.
    Submit all your files in a single zip (.zip or .gz) file through Gradescope. If there are ANY other files
    (e.g., object files or executable binary) or subdirectories in the directory when it has been handed in,
    you will lose marks (from the programming practices category). This includes any hidden file (prefixed
    with .), except for .git and .gitignore.
    You should follow the instructions below on how to prepare your submission. Late submissions are
    accepted up to 7 days late. Each day, or part of a day, will incur a 5% penalty.
    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
    ifyou 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 invalid submissions.
    • We will not accept submissions other than through Gradescope.
    Marking and Demonstration
    • This exercise will be marked during a lab session after the submission deadline.
    • You will be asked to demonstrate your work from your Gradescope 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 completed exercise. 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.
退出移动版