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)
pct8 (due 20231018)
wcp8 (due 20231018)
yol0 (due 20231018)
bjm0 (due 20231025)
pct9 (bonus; due 20231025)
wcp9 (due 20231025)
bjm1 (due 20231101)
gfo1 (due 20231101)
pctA (due 20231101)
wcpA (due 20231101)
pctB (bonus; due 20231108)
set0 (due 20231108)
wcpB (due 20231108)
mor0 (due 20231115)
pctC (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:discrete:projects:cnv2

Corning Community College

CSCS2330 Discrete Structures

PROJECT: Computing N-ary Values (CNV2)

OBJECTIVE

To continue our exploration of algorithms, their implementation, their optimization, their efficiency, and collaboratively authoring and documenting the project and its specifications.

GRABIT

To assist with consistency across all implementations, data files for use with this project are available on lab46 via the grabit tool. Be sure to obtain it and ensure your implementation properly works with the provided data.

lab46:~/src/SEMESTER/DESIG$ grabit DESIG PROJECT

OVERVIEW

Your task is to implement a program that determines, within provided command-line constraints, the matching N-ary values. This project in particular with focus exclusively on N-ary(1) values.

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.

Having done the baseline implementation in discrete/cnv0, and explored various algorithmic optimizations in discrete/cnv1, the aim here is to explore the impact that space can have on performance, instead of just focusing on tweaks to time complexity.

There are 2 variants you are producing for this project:

  • array-based lookup: store all your discovered primes in an array, and use that array in your factor testing (ie only check prime factors).
  • sieve of eratosthenes (this is the big important one: here we take an entirely different approach to calculating primes, what I like to call the “third grade math approach) that should blow all your other approaches out of the water.

EDIT

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

BACKGROUND

APPROACHES

ARRAY-BASED PRIME FACTOR

For the array optimisation, we will be using an array to aid us in the finding of primes. For the size of the array, it is recommended to reserve space equivalent to 1/3 of the range (assume that we are operating on range rather than quantity). The way this works is that when we find a prime number, we will store it in the array, and then when testing a value for being prime we will test it against our array contents rather than an incrementing value. If the value is not divisible by any of the values in our array, then it must be prime. For initialisation, it is recommended to put 2 in the array from the get-go (assume we are starting at 2). Note that while it is possible and recommended that the array optimisation coexist with the other optimisations, it is acceptable to have array as a standalone optimisation.

SIEVE OF ERATOSTHENES

The sieve only works with prime numbers, you might find it easier just to create a separate file that contains the code for your sieve of eratosthenes. If you do, add your filename to the end of “BIN = $(PROJ)” inside of the makefile. Example: if you have a file named sieve.c, your new Makefile should read “BIN = $(PROJ) sieve”. You can test if you did it right by running make and it will show sieve.c as well as your cnv2.c file.

NOTE: Your implementation of the Sieve of Eratosthenes will likely involve the usage of exponents, likely squares. Keep in mind that the ^ operator in C does not mean exponent / power. ^ is a bitwise XOR operator. Either use the pow() function that math.h provides, or simple multiply the same variable by itself multiple times.

Prime numbers only.

You have a populated array starting from your checking value to your upper bound. You will cross out all other numbers that are divisible by the number you are checking (for example if you start with 2, it will cross off 4, 4+2, 6+2, 8+2…(n+2), where (n+2) < = max. Also, one way you can “cross off” the numbers is by creating and initializing a second bool array…This is a helpful way to only display values in your array that are prime numbers. This will reduce the numbers you will be checking. Afterwards, move to the your checking number to the next number that is not a crossed out number, and test if that is a prime. If it is, remove that number from the list of available numbers, until you reach the upper bound. Repeat this process until either your quantity or upper bound is reached.

Here is a nice gif:

\*\*I will fix these notes later - Ash

SPECIFICATIONS

*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

If you create a second source file for your sieve, you can include it in the makefile by adding the following line:

BIN = $(PROJ) <name of sieve file, without the .c>

Add it below the line that says:

BIN = $(PROJ)

For example, if your file is named sieve.c:

BIN = $(PROJ)
BIN = $(PROJ) sieve

OUTPUT SPECIFICATIONS

New functions should output prime numbers, separated by newline characters. This will largely follow the format of the previous iterations of cnv (cnv0, cnv1).

VERIFICATION

Similar to the other cnvX projects, there is no verification script, or unit test for you to test against. However, cnv2 only deals with prime numbers, so you can test the output against a list of prime numbers. Also, your new optimization, the array, should be consistently faster than the non-optimized version of the same parameters. The sieve should blow the times out of the water and be extremely quick.

 

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:

156:cnv2:final tally of results (156/156)
*:cnv2:used grabit to obtain project by the Sunday prior to duedate [13/13]
*:cnv2:clean compile, no compiler messages [13/13]
*:cnv2:implementation passes verification tests [39/39]
*:cnv2:adequate modifications to code from template [39/39]
*:cnv2:program operations conform to project specifications [39/39]
*:cnv2: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/discrete/projects/cnv2.txt · Last modified: 2022/10/30 15:39 by 127.0.0.1