User Tools

Site Tools


Sidebar

projects

wcp1 (due 20240124)
pct0 (bonus; due 20240125)
pct1 (bonus; due 20240125)
abc0 (due 20240131)
btt0 (due 20240131)
pct2 (due 20240131)
wcp2 (due 20240131)
mpg0 (due 20240207)
pct3 (bonus; due 20240207)
wcp3 (due 20240207)
mpg1 (due 20240214)
pct4 (due 20240214)
wcp4 (due 20240214)
bwp1 (bonus; due 20240228)
mpg2 (due 20240228)
pct5 (bonus; due 20240228)
wcp5 (due 20240228)
cgf0 (due 20240306)
gfo0 (due 20240306)
pct6 (due 20240306)
wcp6 (due 20240306)
cgf1 (due 20240313)
pct7 (bonus; due 20240313)
wcp7 (due 20240313)
cgf2 (due 20240320)
pct8 (due 20240320)
wcp8 (due 20240320)
pct9 (bonus; due 20240327)
wcp9 (due 20240327)
bwp2 (bonus; due 20240410)
cgf3 (due 20240410)
gfo1 (due 20240410)
pctA (due 20240410)
wcpA (due 20240410)
pctB (bonus; due 20240417)
waq0 (due 20240417)
wcpB (due 20240417)
pctC (due 20240424)
waq1 (due 20240424)
wcpC (due 20240424)
pctD (bonus; due 20240501)
wcpD (bonus; due 20240501)
gfo2 (due 20240508)
pctE (bonus; due 20240508)
wcpE (bonus; due 20240508)
EoCE (due 20240516)
haas:spring2024:data:projects:sll3

Corning Community College

CSCS2320 Data Structures

PROJECT: Singly-Linked List of Nodes (SLL3)

OBJECTIVE

To continue 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.

OVERVIEW

Now with our singly-linked list implementation complete, we will perform a baseline tweak for use with the group data structure in sll4 (a group of lists). That particular tweak is the incorporation of a quantity element, so each and every transaction upon the list needs to maintain the accuracy of the node count.

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-sll3

EDIT

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

FIXES

If you are getting unexplainable build errors on your own system when you run 'make default' after already running 'make clean', it can be one of two things.

Firstly, it can be because your using the wrong version of gcc, the sll3 project files can only compile with version 9 of gcc. You can use the same version of gcc as 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

If that does not fix the problem then you need to edit one of the Makefiles in the sll3 project directory. The offending Makefile is in the /src/list/ directory. Run the following command to edit that file:

USER@SYSTEM:$ nano ~/src/SEMESTER/DESIG/sll3/src/list/Makefile

remove the following line of code (after the line that says lib:)

@date +'%Y%m%d%H%M%S' >> /var/public/$(SEMESTER)/$(DESIG)/$(PROJ)/.updates/.metrics/${USER}

You might have to change the semester to fall2022 instead of having it check for the semester by checking the directory. You can delete what SEMESTER is set to and insert fall2022 instead.

Note that if you are working on your pi there may be no semester file to begin with, so to create it simply use cd /usr/local/etc/ to go to the relevant location, use sudo su to gain root access, create a file named “semester”, and insert “fall2022” into it. Then use can exit root with the “exit” command to decrease the likelihood of doing something you shouldn't.

Then try building the project again.

BACKGROUND

There are no new files or functions to work on this week. Instead, we will be going back to some of the core list-processing functions we've developed in the previous weeks, and enhance their functionality to expand our linked-list data structure. Once you upgrade to SLL3, you will see a couple of new properties on the 'list' struct, contained in the list.h file.
These two new properties are:

  • qty: An 'unsigned long int,' that indicates the number of nodes contained within the 'list.'
  • next: A 'list' pointer that points to another 'list,' this way we will link one list to another.

Do not overthink these properties. To get a better understanding of what they are, think back to the functionality of our nodes. Our Node structs have 2 properties, 'info' and 'right.' The info variable holds data within the node. The 'right' pointer links the current node to another node. With that in mind, qty and next will work in a similar way.

Going up in a level of abstraction, lists are the new nodes! Linking lists does not mean merging nodes. A list pointing to another means that they are only linked together, each list will conserve its own nodes and pointers.

SPECIFICATIONS

Therefore, it is our task to modify our core node-list-processing functions to modify the qty value when necessary. When does the qty value change? When you add or remove nodes from the list! And to have a 'next' pointer ready to point to a linked list. For sll3, we will not focus much on 'next,' next will be part of sll4.

Depending on how you coded your functions, these are functions you might be looking to modify:

  • mk(): Implement the new functionality of 'qty' and the next 'list'
  • insert(): Add new functionality related to 'qty'
  • append(): Same as insert
  • obtain(): Opposite of insert() & append()
  • cp(): Make sure to copy the new properties of the struct 'list'
  • perhaps even clear().

Remember, these are list functions.

*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

Inside list.h, the included header file given to you when you upgraded, and that you've had for the past few iterations of this project was updated with additional variables. Two new variables were added to the list struct.

Those are qty and next.

  • [next] is a pointer to the next list, we are now dealing with groups of linked lists. (myList → next)
  • [qty] contains the amount of nodes in the list. (myList → qty)

Other than that, nothing has changed inside the list.h file given to you. This project should take minimal time, don't be surprised if it seems too easy, that's why sll3 and sll4 are due both the week after break week. More detailed information about the types of qty and the next pointer are specified above in the specifications section.

Remember- with the new quantity property, you only want to change it's value if you are adding/removing nodes to the list (Only in insert, append, and obtain). Also, be sure you check that you are not incrementing the quantity if inserting NULL to the list, or else your quantity will be incorrect (qty 1 number off on insert unit test). This should be checked for each function that inserts/removes nodes from the list.

OUTPUT SPECIFICATIONS

Nothing has changed in terms of output from your original five functions. Only add functionality of the new variables to the previously made functions.

UNIT TESTS

Unit Tests are again located inside bin/ after you compile. To compile, from the base sll3 directory, make clean(should be done every time but first time is not necessary) then make. An errors file will be created after running make, this may be helpful if things aren't compiling correctly. Unit Tests will have more tests in each than previous, these tests are for your next and qty variables.

DEBUGGING

Useful tools for debugging issues are gdb and examining the test files themselves. to utilize gdb, run the test program with the gdb command (not make check), with a command that might look like “gdb ./bin/unit-lobtain”. Once in gdb the “run” command with start the program, and “break (line number)” will cause the program to stop at the specified line number. Once you have hit the breakpoint you can use “display (variable name)” to see the value of a variable at every step, “n” to step to the next line, and “continue” to continue running the program until the next breakpoint. Note that if you encounter a seg fault the program will tell the where the seg fault occurs, and you can use “run” again to restart the program.

 

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:sll3:final tally of results (78/78)
*:sll3:obtained project by the Sunday prior to duedate [13/13]
*:sll3:clean compile, no compiler messages [13/13]
*:sll3:implementation passes unit tests [13/13]
*:sll3:adequate modifications to code from template [13/13]
*:sll3:program operations conform to project specifications [13/13]
*:sll3: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/spring2024/data/projects/sll3.txt · Last modified: 2022/09/26 14:38 by 127.0.0.1