User Tools

Site Tools


Sidebar

projects

pct0 (bonus; due 20230823)
wcp1 (due 20230823)
abc0 (due 20230830)
btt0 (due 20230830)
pct1 (bonus; due 20230830)
pct2 (due 20230830)
wcp2 (due 20230830)
mpg0 (due 20230906)
pct3 (bonus; due 20230906)
wcp3 (due 20230906)
pct4 (due 20230913)
ttb0 (due 20230913)
wcp4 (due 20230913)
pct5 (bonus; due 20230920)
ttb1 (due 20230920)
wcp5 (due 20230920)
dap0 (due 20230927)
gfo0 (due 20230927)
pct6 (due 20230927)
wcp6 (due 20230927)
cgf0 (due 20231004)
pct7 (bonus; due 20231004)
wcp7 (due 20231004)
bwp1 (bonus; due 20231018)
cgf1 (due 20231018)
pct8 (due 20231018)
wcp8 (due 20231018)
cgf2 (due 20231025)
pct9 (bonus; due 20231025)
wcp9 (due 20231025)
cgf3 (due 20231101)
gfo1 (due 20231101)
pctA (due 20231101)
wcpA (due 20231101)
pctB (bonus; due 20231108)
waq0 (due 20231108)
wcpB (due 20231108)
pctC (due 20231115)
waq1 (due 20231115)
wcpC (due 20231115)
bwp2 (bonus; due 20231129)
pctD (bonus; due 20231129)
wcpD (bonus; due 20231129)
gfo2 (due 20231206)
pctE (bonus; due 20231206)
wcpE (bonus; due 20231206)
EoCE (due 20231214)
haas:fall2023:data:projects:sll0

Corning Community College

CSCS2320 Data Structures

PROJECT: Singly-Linked List of Nodes (SLL0)

OBJECTIVE

To enhance our ability to explore various algorithmic and computing realms through the exploration and cultivation of debugging and troubleshooting skills, and collaboratively authoring and documenting the project and its specifications.

UPGRADING

To assist with consistency across all implementations, project files for use with this project, along with the integration of the work you did on the last project, is made possible via a special recipe in the Makefile.

Simply go into the project base directory, and run:

lab46:~/src/SEMESTER/DESIG/prevPROJECT$ make upgrade-sll0

OVERVIEW

Your task is to implement the first set of the core list library functions (which utilizes the node library) and make sure that they conform to specifications.

Contributing to project documentation is also a core part of this project. If from reading the existing documentation or through your own exploring, you find something lacking, unclear, or outright missing, that is an opportunity to potentially contribute content.

You want the project documentation to provide you (as if coming in with no awareness of the project) with sufficient information so as to allow you to proceed. Asking questions on the discord is a great way of getting more information that you can use to add content.

EDIT

You will want to go here to edit and fill in the various sections of the document:

BACKGROUND

As we are slowly building onto our code library, this week we will be moving forward to list manipulating functions, lists containing nodes; at this point, we should now have fully functional node processing functions as the foundation.

If you remember from our pseudocode from sln0, one of the processes we implemented to include new nodes into a list was to insert them. That is what we will be focusing on…

First and foremost, after upgrading your project folder, as explained further down below, you will find a new header file inside the inc directory called 'list.h'. This header declares a new type of struct called List, with two pointer properties lead and last, and five new functions:

  • mklist()
  • setpos()
  • getpos()
  • insert()
  • displays()

It is recommended to work on them in that order. If you choose to work on them in that order, know that the unit tests call on display so you will need to comment out the display call inside the unit tests of setpos, getpos, and insert. However, mklist works fine and should be the first one completed.

You will now have a new directory as well called 'list', /sll0/src/list/.
Here you will find four new .c files containing their corresponding functions:

  • mk.c
  • pos.c
  • insert.c
  • displayf.c

SPECIFICATIONS

Our goal is to implement five functions in four files. The files are located in the /src/list directories along with a makefile. The functions are themed on the use of lists.

To get the project files:

cd /sln1
make upgrade-sll0
cd ../sll0/

* this will upgrade sln1 → sll0

NOTICE: To easily compile your files, from the base directory you can run make clean followed by make default afterwards you can run make check or inside the bin folder run the desired unit test if you want more specific information of what went wrong.

Another thing to note is that the sll0 project files can only compile with version 9 of gcc. If you are not on lab46 and the project fails to build the library or unit tests, this may be because you are using a newer or older version of gcc.

You can use an older version of gcc off of lab46 by using the following commands (assuming you are using a Raspberry Pi with it's default OS) in this link: https://gist.github.com/sol-prog/95e4e7e3674ac819179acf33172de8a9

*Our task is to ask questions on Discord or in class and document our findings on this wiki page collaboratively, regarding the functionality of this project.

*For anybody interested in editing the wiki page, here is the dokuwiki user guide: https://www.dokuwiki.org/wiki:syntax#basic_text_formatting -Ash

PROGRAM

There are four programs that you will need to complete. The first consists of creating the initial list (mklist). The pos.c program has two functions you will need to complete. The first being getpos() and the second setpos() as seen below. Finally, we need to have a displayf(). Information on these functions can be found below.

mklist() should make a new list containing a lead and last node. These nodes point to the start and end of the list. Is very similar to mknode().For Errors: On error, return NULL. getpos() should get the position of the node passed into the function. It should look at the node passed in → info and find that node inside the list. If that node isn't found inside the list it should return the appropriate error specified inside pos.c. Start a temp node at the beginning of the list and go through each node until the given node is reached, using some form of a counter to obtain that positions value. For Errors: If Null/Undefined list or node is given, return a negative one(-1). If out-out-bounds condition, return a negative two.(-2) setpos() should set a new Node* to a position specified by a number passed into the function, think of setting a tmp variable and looping to get to that position as done in sln0. For Errors: If Null/Undefined list or node is given, return a negative one(-1). If out-out-bounds condition, return a negative two.(-2) insert() should put a new node containing a value passed into the function before the specified place. This place will be passed into the function as will the new node. For optimization of your program these should utilize the setpos() and getpos() functions to set new nodes to maintain the list. The list should be able to insert before the start and anywhere else. Remember that if the node is one after the start, you will have to set the lead's right to the new node.

displayf() should display the list in a forward orientation (start→end node). There are two modes for display. The first is to display the list without the position of each value i.e 4 → 13 → -1 → NULL.

The second mode is to display the index along with the values of the list. i.e 4[0] → 10[1] → …. → NULL

DEBUGGING ADVICE

One tool that can be utilised for debugging is the gdb and make debug commands. Use the command make with the argument debug (typed as “make debug”), then run the gdb command with the executable you are debugging (“gdb ./executable”), then from the use “run {any arguments}” and it will show where your error has occured. Furthermore, with regards to debugging a specific unit test, you can make use of the tests in sll0/unit/list/(unit test to debug). Here you will be able to compare your results with the expected results. (Unit tests are very useful!)

An “errors” file is also made after running make default. Checking through this may be helpful in figuring out what's going wrong if things aren't working.
After running “make” your c code will be compiled, if errors are present the errors file as mentioned will prompt with a message after the compile looking like “* There were warnings or errors during compile! Type: 'cat errors' at the prompt to view.”. If you see this message, you can cat the file errors that is only available in the base sll0 directory, this file will display every error present while compiling all of the c files. You need to be careful because it shows every compile error so if many errors are present, it might be multiple files not just one, meaning there is most likely less errors than you think for the given file you are working on.
=====OUTPUT SPECIFICATIONS===== The only program that will be displaying output is the display function, with it possessing a standard mode and an indexed mode. The standard will simply show the values one after another, such as “0 → 3 → 7 → 9 → 19 → NULL”. The indexed mode will show the list address (starting at 0) along with the index location, such that “[0] 0 → [1] 3 → [2] 7 →[3] 9 → NULL”. Note that the NULL is not accompanied by a list address. =====UNIT TESTS===== When running
make check there will be 43 total match checks, when the functions are setup correctly, all 43 should match the output of the unit tests. You may receive an error that looks something like this: <cli> YOURNAME@lab46:~/YOURDIR/sll0$ make check ====================================================== = Verifying Singly-Linked List Functionality = ====================================================== [mklist] Total: 5, Matches: 5, Mismatches: 0 [insert] Total: 11, Matches: 11, Mismatches: 0 [displayf] Total: 10, Matches: 10, Mismatches: 0 [getpos] Total: 8, Matches: 8, Mismatches: 0 [setpos] * NOT CURRENTLY OPERATIONAL * ====================================================== [RESULTS] Total: 34, Matches: 34, Mismatches: 9 ====================================================== </cli> This does not mean the verify script is broken, you likely have a segmentation fault.
To analyze further, navigate to
sll0/unit/list and run the unit test for the function giving you problems. In this example: <cli> YOURNAME@lab46:~/YOURDIR$ cd unit/list/ YOURNAME@lab46:~/YOURDIR/unit/list$ ./unit-setpos UNIT TEST: list library setpos() function ========================================= Test 0: Running setpos() on NULL list … Segmentation fault (core dumped) </cli> Indeed, a segmentation fault. You'll also receive this error if you haven't yet implemented displayf**.

 

SUBMISSION

To be successful in this project, the following criteria (or their equivalent) must be met:

  • Project must be submit on time, by the deadline.
    • Late submissions will lose 33% credit per day, with the submission window closing on the 3rd day following the deadline.
  • All code must compile cleanly (no warnings or errors)
    • Compile with the -Wall and –std=gnu18 compiler flags
    • all requested functionality must conform to stated requirements (either on this document or in a comment banner in source code files themselves).
  • Executed programs must display in a manner similar to provided output
    • output formatted, where applicable, must match that of project requirements
  • Processing must be correct based on input given and output requested
  • Output, if applicable, must be correct based on values input
  • Code must be nicely and consistently indented
  • Code must be consistently written, to strive for readability from having a consistent style throughout
  • Code must be commented
    • Any “to be implemented” comments MUST be removed
      • these “to be implemented” comments, if still present at evaluation time, will result in points being deducted.
      • Sufficient comments explaining the point of provided logic MUST be present
  • No global variables (without instructor approval), no goto statements, no calling of main()!
  • Track/version the source code in your lab46 semester repository
  • Submit a copy of your source code to me using the submit tool (make submit on lab46 will do this) by the deadline.

Submit Tool Usage

Let's say you have completed work on the project, and are ready to submit, you would do the following (assuming you have a program called uom0.c):

lab46:~/src/SEMESTER/DESIG/PROJECT$ make submit

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.

RUBRIC

I'll be evaluating the project based on the following criteria:

78:sll0:final tally of results (78/78)
*:sll0:obtained project by the Sunday prior to duedate [13/13]
*:sll0:clean compile, no compiler messages [13/13]
*:sll0:implementation passes unit tests [13/13]
*:sll0:adequate modifications to code from template [13/13]
*:sll0:program operations conform to project specifications [13/13]
*:sll0:code tracked in lab46 semester repo [13/13]

Pertaining to the collaborative authoring of project documentation

  • each class member is to participate in the contribution of relevant information and formatting of the documentation
    • minimal member contributions consist of:
      • near the class average edits (a value of at least four productive edits)
      • near the average class content change average (a value of at least 256 bytes (absolute value of data content change))
      • near the class content contribution average (a value of at least 1kiB)
      • no adding in one commit then later removing in its entirety for the sake of satisfying edit requirements
    • adding and formatting data in an organized fashion, aiming to create an informative and readable document that anyone in the class can reference
    • content contributions will be factored into a documentation coefficient, a value multiplied against your actual project submission to influence the end result:
      • no contributions, co-efficient is 0.50
      • less than minimum contributions is 0.75
      • met minimum contribution threshold is 1.00

Additionally

  • Solutions not abiding by spirit of project will be subject to a 50% overall deduction
  • Solutions not utilizing descriptive why and how comments will be subject to a 25% overall deduction
  • Solutions not utilizing indentation to promote scope and clarity or otherwise maintaining consistency in code style and presentation will be subject to a 25% overall deduction
  • Solutions not organized and easy to read (assume a terminal at least 90 characters wide, 40 characters tall) are subject to a 25% overall deduction
haas/fall2023/data/projects/sll0.txt · Last modified: 2022/09/15 11:26 by 127.0.0.1