Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

COMS10016 | Week 05-07 | Summative Coursework 01:

This is your first assignment in imperative programming. This coursework runs over approximately the next two weeks (Blackboard submission deadline Thursday 31st October 2024, well before 1pm) and counts 20% towardsyour credit for the COMS10016 unit. Start the coursework as soon as possible and make sure you read the entire task first. Its main purpose is to show us what you have learned regarding fundamental aspects of C so far, that is writing basic syntactically and semantically correct programs with no memory leaks using pointers, strings, and bit operations. Our weekly lectures and sample code, labs and optional exercises with sample solutions built up to this point. This time you MUST work individually and not collaborate with anyone or any AI. All code you submit must be your own, no part should be developed with someone or be taken from somewhere else. Use our MS Teams channel or the 3h lab on the 30th October 2024 to ask questions. Mastering the coursework yourself will enable you to progress in your learning, show what you have learned so far, and provide a foundation for many future assessments and vivas.

Ask your questions on our MS Teams channel only. Do not share or paste code snippets or solution details in the MS Teams channel or anywhere else with anyone. We will answer your questions in the MS Teams channel and help you along if there are questions re the assignment. Our 3h lab in Week 07 in MVB2.11/1.15 will provide in-person help with submissions and so far unanswered queries - the vast majority of the coursework should be done by this point. For someone new to C in this unit achieving an average result in this coursework may take between 5 and 15 hours if you are up-to-date in your learning, sometimes more. Since the coursework covers basics, a professional programmer may pass the coursework in well under one hour. However, to allow for inclusive assessment for students at all skill levels at this point, we have Consolidation Week upcoming for revising lectures and formative programs, and for taking as much time as needed for recap and getting up to speed with your programming and this coursework.

Again, do not copy or otherwise accept any code parts from peers or other sources and do not publish or make accessible parts of your own code anywhere. Do the right thing for yourself. The programs we may use for checking against the web, your peers and other sources are advanced. Unethical conduct and plagiarism are unprofessional and may result in 0 marks for a coursework, the entire unit, may lead to repeating a year or in repeated cases the forced end to your studies.

Use only standard libraries as given in the skeleton code for this task, so your code compiles and runs without linking any other libraries. Your task comes in two parts: a closed task worth the first 50% of your mark that comes with all tests so you can self-check progress and get feedback at any time, and anopen- ended task. Backup your work regularly. Do not attempt the open-ended task before successfully and fully finishing the closed task.

Step 1: Understand Doubly-linked Lists

Before you start on this task make sure you watched and understood all lectures up to Lecture 15. You should have compiled, run, and understood all the code provided for pointers, dynamic data, stacks, and lists. In particular, be sure you have run, compiled and understood in detail the program linkedlist.c from Lecture 15 and maybe looked at the preparatory optional exercises on Bits and Pointers.

Your task will evolve around doubly-linked lists with a sentinel node. Thus, let us understand and visualise this concept first. One way of producing a list or sequence of variable elements is to form a node by attaching a pointer to each element, one that points to the next node and so forth. In essence, a doubly linked list is made up of a sequence of nodes where neighbouring nodes pointto each other. Each node is a structure that has a payload x (e.g. just an int)  and two pointers: back and next. The back pointer always points to thepredecessor node and the next pointer always points to the successor node. Two neighbouring nodes in a doubly-linked list can therefore be pictured like this:

This emphasizes that a node structure contains three fields. However, for most purposes you can simplify the visualisation by depicting the above two nodes like this:

In this simplified visualisation, a pointer from the left end of a node represents its back pointer, and a pointer from the right end is its next pointer. A pointer toanywhere on a node's rectangle means a pointer to the start of the node.

The Sentinel Node. It used to be a standard solution to implement doubly-linked lists by keeping track of the first and last node of the list (like the 3 node and 7 node in the picture above), where the first node would point backward to NULL, and the last node would point forward to NULL. However, it turns out that adding an extra node, called a sentinel node, simplifies list implementations and makes the code much more readable. For a circular, doubly-linked list our sentinel node (pictured with no payload x) is linked in between the first and last payload in the list:

Here both the back and next pointers of the sentinel node simply point to the sentinel node itself.

The Structure list. To represent a list in a list data structure we need two node pointers: one fixed pointer to the sentinel node (called none) to access both list ends in constant time, and one current pointer that points to a current node in the list allowing for traversals:

In the above image the current position is the node that holds 7, so payload 7 is selected. If the current pointer in a list points to none then we will interpret this as 'no payload is selected':

Picturing List Manipulations. To visualize what a function does to a list, draw a picture of the situation before the function call, and another of thesituation  after the call. For instance, consider the function after. If a payload is selected it moves the current pointer one element forward. When applying the function to our list with the payload 3 selected, it would have the simple effect of moving the current pointer one step forward to payload 7:

Applying the after function to our list when the payload 7 is selected moves the current pointer one step forward to the sentinel node, meaning 'no item' is selected after the call:

Step 2: Understand the Closed Task

The header file list.h forms an API, which you should read carefully because the comments describe what the functions you will have to implement in list.c have to do. The list.c file has just two data structures node and list which you must use, and a lot of tests. The program as given to you will not compile initially. So, our first task is to produce a compiling skeleton by studying the signatures of the 14 missing procedures and accordingly defining some initial dummy functions.

For a start, download all above files into a folder of your development machine that only you have access to. After that, your first task is to turn list.c into a full skeleton program that compiles. You can do this without understanding all of the technicalities of the assignment.

Two Key Data Structures. In the file list.c a structure for the nodes which make up the list is defined, and a structure for the list itself. The node structure struct node is not visible to the user of the module. Each node is used to hold a payload x and pointers to the two neighbouring nodes (next and back) which define the list ordering. The overall list structure struct list represents a list and is essential so that your newList function can return something to theuser  which is well defined. This structure holds two pointers: one to the sentinel node of the list and one to the currently selected node. Read the code comments about the list structure carefully. You will have to use the two data structures exactly as described to comply with the tests.

Pay attention to use the exact line for compilation, including that the parameter -Dtest_list must be used to run the tests.

There is a separate test function for each of the 14 list functions you need to implement, except for freeList which can't be tested directly. The tests specify each function using before and after pictograms compressed into strings.

Function Descriptions. What does each function do? There is a detailed comment for each function in the list.h header which gives a summary. For each function, there is a test function with some assert calls. These show precisely what the function does on the empty list "|" and a list with two items in at least each of the three cases "|37" and "3|7" and "37|". That should be enough for you to work out what the function does in every possible case.

Details on Support Functions. The functions build, destroy and match form the heart of the testing and are implemented 'brute force'. The build function is used to build a list from the 'before' picture of a test, the function being tested is applied to the list, match is used to check that the result list matches the 'after'picture, and destroy frees up the list. Each of the functions uses an array of

But that is not a technique you are supposed to be using in the list functions, because all of your 14 functions, apart from freeing your list, must take

Step 5: Write the 14 Functions One by One

Develop freeList. For all the functions, the compiler options test things that the tests themselves can't. In the case of freeList, there is no explicit testing that can be done. Therefore the only testing is that memory leak detection does not give any messages. Your freeList procedure should first free all nodes of the list including the sentinel node and finally free the list structure itself.

The trouble is, this is very error-prone. The code may be written with a mental picture of where the nodes were at the start of the function, but one or more of the pointers used in the expression may have been changed already by the time this line is executed. Trouble can arise particularly when shuffling lines of code around. A line of code that used to work may suddenly no longer work.

And it is possible to 'lose' a node altogether, because there are no pointers left pointing to it, and therefore no way to reach it.

Use Robust Strategies. In this assignment, the insert and delete functions are the most difficult ones. They involve handling three nodes, either a new 'middle' node being inserted between (up to) two existing ones, or one existing node being deleted and its (up to) two neighbours being linked up together to close the gap in the circular list. A good strategy is to set up three local pointer variables (e.g. p, q and r or whatever you like) for these three nodes at the beginning of a function, so that you can keep track of them no matter what changes are made to the pointers between them. Each line of code after that can then be written simply using only one arrow, and the order in which the lines of code are executed doen't matter, making the code much more robust.

A List of Items. The header is set up to store payload values in lists. In the header payload is defined as int to provide an example case. However, payload must be used as a synonym for int everywhere in your code, so that there is only one place in the header file where a change would need to be made to store some other type of items. This means the module can be used with different payload types in different programs. For those who are interested, note that even this it is not truly generic since the setup cannot be used multiple times for different payload types in the same program. There is no really satisfying way of making fully generic modules in C. It is recommended, as a last test before submitting, that you change the payload type to double, to check that you haven't inadvertently assumed int anywhere. (The numbers used in the tests should still work as doubles.)

The claim of constant time doesn't cover the vagueness in the time taken by malloc and free calls but, conventionally, memory management costs are considered separately from the 'logic' costs of operations. The function names use the camelCase convention, where capitals make the letters go up anddown  like the humps on a Bactrian camel. I should point out, for those who are interested, that including a current position in a list structure itself is not thread safe. A more thread-safe approach is to create a separate iterator object each time the list is traversed. However, that approach can still easily lead to 'concurrent modification' problems where the list structure is changed by one thread while another is traversing it. It is much safer to make sure that a list is owned by a single thread. You will also have noticed that we have to compile our list.c program with the -Dtest_list flag to enable the tests. As you will learn in later lectures, if we don't use this flag then, in our case, we compile our program as a module without a main function and the tests. The program then seizes to be a stand-alone program, but instead can become part of another program that just uses its functionality.

Only if your program passes all tests in the above closed task and you have time left, then you can do some extra open-ended work towards a mark above 50% in your own program called visualise.c on the following problem: Usingonly standard libraries, if any, write a program in C11 (do not use binary printing with %b as offered in C Version 23) that visualises the bit structure of data types in C in binary when entered in decimal form. The program must take 1) a type, and 2) particular data of this type in decimal notation as command line arguments. It should check for input errors (and print the exact string "Input error." in this case, any other output will cost you marks). If there are no input errors, it should print the bit structure of the data in groups of a nibble and no other output before or after that. Make sure you take your input as command line parameters and not via the scanf function. The below examples show exact program runs with the correct output - make sure any error messages are also exactly "Input error." printed to stdout - nothing different from that. Example runs are:

We recommend to keep things relatively simple at first, for instance, by starting with investigating just char. The knowledge you already gained in computer architecture may be handy. Most importantly for this unit, your program should contain detailed unit tests for all functions. These functions should be run if no command line parameters are provided, i.e.:

If you have time left, follow up with visualising the bit structure of int, long, unsigned char, unsigned int and double exactly in this development sequence.

You may need to do some research into interpreting the bit structure of floating point representations if you attempt to look into double. If you still have time left after that, extend your program (keeping all previous functionality intact) so that it shows the decimal value of data types in C when entered in binary form in groups of nibbles. The following examples show again the exact program runs and output expected:

Use the exact development sequence as before, starting with binary to char, binary to int etc. Note that it is always clear from the structure of your input if you are converting to decimal or to binary since binary input has leading zeros and comes in chunks of a nibble. You can extend your program further (keeping all previous functionality intact) by allowing for structured input using semicolon separated and {} enclosed types such as:

Whenever you have reached a well working version, take a copy of your work, so you can revert back to it at any point. Rather submit something simple that works bug-free and is well tested than something that contains bugs - you will not get many marks for buggy code at all. Be careful not to over spend on

A mark out of 50% for the extra work will be awarded by swiftly reading the summary, checking whether your program matches what you claim, judging the sophistication and extent of what has been done, and checking whether the program follows the conventions and advice given in the unit. In particular,writing  tests as part of the program, in the same way as the skeletons we provide, is very much recommended. Also recommended is working in very small steps, one test at a time, keeping your program in a working state.

Step 8: Submit

Submit your work via 'Upload Files' in Blackboard under the submission point "List" for the 2024/25 unit COMS10016. A link to the submission point will be made available on the Blackboard Unit Website in Week 7. It will be linked on the unit website directly as well. You are responsible for early submission, thus submit AT LEAST an hour before the deadline (deadline is 01:00pm UK time on 31 October 2024) to make sure there are no upload problems. As youknow,  the university systems will automatically apply quite severe penalties if the coursework is late only by one second. You must submit ALL individual files (list.c, and if completed visualise.c and readme.txt) as different file attachments in a SINGLE submission, do not zip or compress your work. If you decide to resubmit you MUST submit ALL FILES AGAIN - only the files present in your last submission will be marked. If your last submission is late you will receive the associated mark penalty in any case.

Open-ended Task: If you attempted the open-ended part, then also submit your extra program visualise.c and a readme.txt file with any comments you might want to make (absolute maximum of 100 words). Again, make sure your program compiles without warnings, runs without errors or leaks, and doesn't still contain debugging print statements.