[SOLVED] CS algorithm Java CS 2505 Computer Organization I C01: Array Accesses in C

CS 2505 Computer Organization I C01: Array Accesses in C
C Programming Struct Types and Simple Array Processing
This assignment focuses on array read accesses, using a simple struct data type, and computational logic. The assignment centers on the concept of a mesa, and makes use of the following data type:
/**Represents a mesa, defined as a contiguous sequence of array cells,
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/
storing the same value, which must be at least MIN_MESA_HEIGHT, and
including at least MIN_MESA_LENGTH such cells.The mass of such
a sequence is defined as the sum of the values in the sequence.
A Mesa object is said to be proper if each of the following
conditions holds:
height and length satisfy the minimum requirement
end > begin >= 0
mass = sum of the values in the sequence
valid = true
or if each of the following conditions hold:
height = begin = end = mass = 0
valid = false
#define MIN_MESA_HEIGHT 200 // minimum height to be a mesa #define MIN_MESA_LENGTH 9 // minimum length to be a mesa
struct _Mesa { uint16_t height; uint16_t begin; uint16_t end; uint32_t mass;
For example, the array below contains two valid mesas:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 70 827 376 376 376 376 376 376 376 376 376 376 376 376 245 245 245 245 387 387 387 387 387 387 387 387 387 387 458 458 949 949
The first one starts at index 2, ends at index 13, and its mass is 4512. The second begins at index 18, ends at index 27, and its mass is 3870. So, the first mesa is the biggest one.
You should ponder designing an efficient algorithm to determine the largest mesa, if any, in a given array. Its not particularly difficult, as problems go, but its easy to get it wrong if you dont think about it correctly.
How do you decide youve reached the end of a run of identical values? How do you keep track of whether the run was long enough? How do you remember whether youve found the first mesa, and what its attributes are? How do you adjust if you find a larger mesa? How do you avoid going beyond the end of the array?
And, what important questions have I not asked myself yet?
And, be warned, when we test your solution, we may use different values for the minimum mesa height and minimum mesa length, so dont hard-code numeric values (which is, in almost all cases, poor design anyway).
bool valid;
typedef struct _Mesa Mesa;
};
// the height of the mesa
// the first index included in the mesa
// the last index included in the mesa
// the product of the mesas height and length
// true iff a valid Mesa was found
Version 2.00 This is a purely individual assignment! 1

CS 2505 Computer Organization I C01: Array Accesses in C
For this assignment, you will implement the following C function:
/**
*Given an array of nonnegative integers, a mesa is a sequence of at
*least MIN_MESA_LENGTH identical values.The length of a mesa is the
*number of values in the sequence, and the mass of a mesa is the sum
*of the values in the sequence.
*
*bigMesa() determines the mesa of maximum mass in the array that is
*passed into it.bigMesa() reports its results by setting three extern
*variables:mesaStart, mesaEnd and mesaMass.
*
* Pre:A[0:A_Size 1] are nonnegative integers.
*
* Returns: a proper Mesa object, consistent with the definition of a
* * * * * * */
proper Mesa object given earlier
Restrictions:
uses only its parameters and local automatic variables
does not read input or write output
does not use a second array.
Mesa bigMesa(const uint16_t A[], uint16_t A_Size);
The function will traverse a given array of integers, and create a proper Mesa object, representing the most massive mesa
found, if that is possible, but must also detect the case where a given array does not contain any valid mesas.
Supplied Implementation Code
Download the supplied tar file, c01Files.tar, for this assignment and unpack it in a CentOS directory. You will find the following files:
c01driver.c
bigMesa.h*
bigMesa.c
Mesa.h*
Mesa.o
checkAnswer.h*
checkAnswer.o
Generator.h*
Generator.o
C test driver (read the comments!)
header file for assigned function (do not modify!)
shell file for implementing your solution
header file for Mesa type (do not modify!)
64-bit implementation of Mesa support functions
header file for grading code (do not modify!)
64-bit implementation of grading code
header for test case generator
64-bit implementation of test case generator
Do not modify the files marked with an asterisk (*), because you will not be submitting those files. You may modify the driver file during your testing, but we will use the original version when grading. Compile the code with the command:
centos > gcc -o c01 -std=c11 -Wall -W -ggdb3 c01driver.c bigMesa.c Mesa.o Generator.o checkAnswer.o
The supplied C file bigMesa.c includes a trivial implementation for the required function. Although the given code will compile correctly, the resulting program will not satisfy the requirements of the assignment, since the supplied implementation of the required function doesnt do anything useful. So, you must correctly complete the implementation of the bigMesa() function.
You may need to add include directives to the bigMesa.c file, as needed for any C Standard Library features you use. You may write secondary helper functions if you like; if so, those must be defined and declared within the supplied bigMesa.c file. Such functions should be declared as static.
The testing code in driver.c creates a large buffer around the array that bigMesa() will analyze. The code for that involves dynamic allocation and pointers, which you cannot use in your implementation of bigMesa(). One purpose of the buffer is to protect from possible segfault violations if your implementation of bigMesa() wanders slightly outside
Version 2.00 This is a purely individual assignment! 2

CS 2505 Computer Organization I C01: Array Accesses in C
the boundaries of the array. Another purpose of the buffer is to confuse your solution if you wander outside the boundaries of the array.
What to Submit
You will submit your modified version of the file bigMesa.c to the Curator, via the collection point c01. That file must include any helper functions you have written and called from your version of bigMesa(); any such functions must be declared (as static) in the file you submit. You must not include any extraneous code (such as an implementation of main() in that file).
If you make multiple submissions of your solution to the Curator, we will grade your last submission. If your last submission is made after the posted due date, a penalty of 10% per day will be applied.
The Student Guide and other pertinent information, such as the link to the proper submit page, can be found at: http://www.cs.vt.edu/curator/
Pledge:
Each of your program submissions must be pledged to conform to the Honor Code requirements for this course. Specifically, you must include the following pledge statement in the submitted C source file:
//On my honor:
//
// I have not discussed the C language code in my program with
//anyone other than my instructor or the teaching assistants
//assigned to this course.
//
// I have not used C language code obtained from another student,
//the Internet, or any other unauthorized source, either modified
//or unmodified.
//
// If any C language code or documentation used in my program
//was obtained from an authorized source, such as a text book or
//course notes, that has been clearly noted with a proper citation
//in the comments of my program.
//
// I have not designed this program in such a way as to defeat or
//interfere with the normal operation of the Curator System.
//
//
//
We reserve the option of assigning a score of zero to any submission that is undocumented or does not contain this statement.
Change Log
Version Posted 2.00 Jan 19
Pg Change
Base document.
Version 2.00
This is a purely individual assignment! 3

CS 2505 Computer Organization I C01: Array Accesses in C
Appendix: Quick Introduction to struct Types The struct mechanism in C has many similarities to the class mechanism in Java:
Bundling of a collection of data values (fields) as a unit; data values are referenced by name.
Can be passed as parameters or used as return values from functions.
Can be assigned; values of corresponding data members are copied from source to target.
Deep content (i.e., dynamically-allocated members) is not copied on assignment.
There are also important differences:
All fields are public; there is no access control.
Functions cannot be members of a struct variable.
May be accessed by name or by pointer; Java objects can only be accessed by reference.
Can be created by static declarations or by dynamic allocation (not used in this assignment).
Heres a common use for a struct type in C: struct _Rational {
int64_t top;
int64_t bottom; };
typedef struct _Rational Rational;
We could create a Rational object statically (sufficient for this assignment):
Rational R;
In both cases, the fields in the new Rational object are (logically) uninitialized. For now, we will only consider the first
case, in which the object was created by a static allocation (so its stored on the stack).
When we create a struct variable statically, we can also initialize it (but only in the variable declaration):
Rational R = {37, 63};
We can implement functions to carry out operations on Rational objects (they just cant be member functions). For
example:
Rational Rational_Add(const Rational Left, const Rational Right) { Rational Sum; // create object to hold the result
// initialize that object
Sum.Top= Left.Top * Right.Bottom + Left.Bottom * Right.Top;
Sum.Bottom = Left.Bottom * Right.Bottom;
// return (a copy of) it to the caller
return Sum; }
Note how the fields of a Rational object are accessed here; we use the name of the object, followed by the field-selector operator (.), followed by the name of the field: Sum.Top
Version 2.00 This is a purely individual assignment! 4