User Tools

Site Tools


Sidebar

projects

wcp1 (due 20220824)
ntr0 (due 20220831)
pct1 (bonus; due 20220831)
uom0 (due 20220831)
wcp2 (due 20220831)
pct2 (due 20220907)
pct3 (bonus; due 20220907)
rle0 (due 20220907)
wcp3 (due 20220907)
bdb0 (due 20220914)
wcp4 (due 20220914)
pct4 (due 20220915)
cnv0 (due 20220921)
wcp5 (due 20220921)
pct5 (bonus; due 20220922)
gfo0 (due 20220928)
lmr0 (due 20220928)
wcp6 (due 20220928)
pct6 (due 20220929)
pct7 (bonus; due 20221005)
rle1 (due 20221005)
wcp7 (due 20221005)
bwp1 (bonus; due 20221019)
pct8 (due 20221019)
wcp8 (due 20221019)
cnv1 (due 20221020)
pct9 (bonus; due 20221026)
wcp9 (due 20221026)
lmr1 (due 20221027)
gfo1 (due 20221102)
pctA (due 20221102)
wcpA (due 20221102)
rle2 (due 20221104)
pctB (bonus; due 20221109)
wcpB (due 20221109)
cnv2 (due 20221110)
pctC (due 20221116)
wcpC (due 20221116)
lmr2 (due 20221117)
bwp2 (bonus; due 20221201)
pctD (bonus; due 20221201)
wcpD (bonus; due 20221201)
pctE (bonus; due 20221207)
wcpE (bonus; due 20221207)
gfo2 (due 20221208)
EoCE (due 20221219)
haas:fall2022:discrete:projects:cnv1

Corning Community College

CSCS2330 Discrete Structures

PROJECT: Computing N-ary Values (CNV1)

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.

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, the aim here is to explore various algorithmic optimizations, and compare processing runtimes against that baseline.

EDIT

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

BACKGROUND

CNV1 is an introduction to program and algorithm optimization. We will be revisiting our cnv0 program, and we will make it harder, better, faster, and stronger.

OPTIMIZATIONS

There are 5 levels of optimization that could potentially be called upon simultaneously, with some exceptions.

  • 0 none
  • 1 break
  • 2 odds
  • 4 map
  • 8 sqrt
  • 16 approx sqrt

The numbers on the left represent binary positions.

Recall binary numbers and their position values.

0   0  0  0  0 0 0 0
128 64 32 16 8 4 2 1

You may take “optimizations” as a program argument or use an environment variable with getenv.

The optimizations should be a single argument or environment variable, for example the optimization argument of 19 would equal the following optimizations: 16 goes into 19, so approx sqrt would be activated & 2 goes into 19 - 16, so odds would be enabled & finally, 1 goes into 19 - 16 - 2, so the break optimization would be enabled.

Explanation:

  • Break→Stop checking once you have determined that the value is not of the correct n-ary value
  • Odds→Since all prime numbers beyond 2 are odd, there is no need to check whether or not the evens are prime
  • Map→Only check numbers that lay upon the (6n±1) equation
  • Sqrt→You only need to check up to and including the square root of the value being checked to discover half of all possible factor pairs
  • Approx sqrt→Same as sqrt, but without the sqrt function from the math library. Instead run a rough sqrt point that grows as the value checked does.

* 6n±1: This formula defines all prime numbers above 3. Every prime number follows the 6n±1 equation where n is any integer, 1 or greater. All prime numbers follow this pattern, although the resulting number will not necessarily be a prime number.

GENERAL: SQUARE ROOT POINT

For the approximate square root functionality you will have a “square root point”, this point is the approximation of the square root for the number you're checking.

Start with this point equal to 2. The point will increase when ( number to check > point * point ).

For example, when the number to check is 10, the point will be 3 (10 > 3*3), and therefore the approximate square root of 10 is 3.

The starting value of 2 should be used as the approximation for numbers 2-8 however when the number to check reaches 9, (9 > 2*2), so the point will increase to 3.

Examples:

  • sqrt of 2-8 is 2
  • sqrt of 9-15 is 3
  • sqrt of 16-24 is 4
  • sqrt of 25-35 is 5
  • sqrt of 36-48 is 6
  • etc…

GENERAL: MAP

With map, you are pretty much only doing the calculations if the valueToCheck is equal to the value given from the equation 6n(+/-)1, where n is a number > 1. If it is not equal to this, then go to the next value rather than doing the calulations.

GENERAL: Break

With break, you are aiming to reduce the program run time by breaking out of the check when the total factors of the current number exceeds that of the given nary value. This will drastically reduce the time, especially if you are checking larger numbers with a small nary value.

N-ARY(1) SPECIFIC

Odds and Map are only to be used during nary 1 (when dealing with prime numbers).

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

Program should output the same as cnv0. The only difference is using the optimizations, your optimized version should be for the most part, faster than the cnv0 or zero optimization equivalent of the same operation.

OUTPUT SPECIFICATIONS

VERIFICATION

Similar to cnv0, there is no makefile. However, output doesn't change for this program, only the time. To verify, make sure your times when using optimizations are less than the times without optimizations.

 

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:

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