Description
Programming Language : C
- INTRODUCTION / AIM
In this experiment, you are expected to gain knowledge on C language including read-write files, arrays, matrices, recursion and dynamic memory allocation. Prior knowledge on basic C syntax is assumed.
- BACKGROUND INFORMATION
- C LANGUAGE
- is an imperative procedural language. It was designed to be compiled using a relatively straightforward compiler, to provide low-level access to memory, to provide language constructs that map efficiently to machine instructions, and to require minimal run-time support.
Despite its low-level capabilities, the language was designed to encourage cross-platform programming. A standards-compliant and portably written C program can be compiled for a very wide variety of computer platforms and operating systems with few changes to its source code.
The language has become available on a very wide range of platforms, from embedded microcontrollers to supercomputers.
- ARRAYS
Array types in C are traditionally of a fixed, static size specified at compile time. However, it is also possible to allocate a block of memory at run-time, using the standard library’s malloc function. C’s unification of arrays and pointers means that declared arrays and these dynamically allocated simulated arrays are virtually interchangeable.
| Static | Dynamic |
Since arrays are always accessed via pointers, array accesses are typically not checked against the underlying array size. Array bounds violations are therefore possible and rather common in carelessly written code, and can lead to various repercussions, including illegal memory accesses, corruption of data, buffer overruns, and run-time exceptions. If bounds checking is desired, it must be done manually.
- MULTI-DIMENSIONAL ARRAYS
- does not have a special provision for declaring multi-dimensional arrays, but rather relies on recursion within the type system to declare arrays of arrays, which effectively accomplishes the same thing. The index values of the resulting “multidimensional array” can be thought of as increasing in row-major order.
Multi-dimensional arrays are commonly used in numerical algorithms to store matrices. The structure of the C array is well suited to this particular task. However, since arrays are passed merely as pointers, the bounds of the array must be known fixed values or else explicitly passed to any subroutine that requires them, and dynamically sized arrays of arrays cannot be accessed using double indexing. (A workaround for this is to allocate the array with an additional “row vector” of pointers to the columns.).
- DYNAMIC MEMORY ALLOCATION
The task of fulfilling an allocation request consists of locating a block of unused memory of sufficient size. Memory requests are satisfied by allocating portions from a large pool of memory called the heap or free store. At any given time, some parts of the heap are in use, while some are “free” (unused) and thus available for future allocations.
The C dynamic memory allocation functions are defined in stdlib.h header.
| Function | Description |
| malloc | allocates the specified number of bytes |
| realloc | increases or decreases the size of the specified block of memory. Reallocates it if needed |
| calloc | allocates the specified number of bytes and initializes them to zero |
| free | releases the specified block of memory back to the system |
- RECURSION
Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function. The C programming language supports recursion, i.e., a function to call itself. But while using recursion, programmers need to be careful to define an exit condition from the function, otherwise it will go into an infinite loop.
- MEMORY LEAK
A memory leak is a type of resource leak that occurs when a computer program incorrectly manages memory allocations in such a way that memory which is no longer needed is not released. A memory leak may also happen when an object is stored in memory but cannot be accessed by the running code. You can use Valgrind to check for Memory Leak in your program.
- ONLINE RESOURCES
- Wikipedia C Entry: https://en.wikipedia.org/wiki/C_(programming_language)
- C Tutorial : https://www.tutorialspoint.com/cprogramming
- Valgrind : http://valgrind.org/info/about.html
- EXPERIMENT
In this experiment, it is aimed to write a program that can perform vector and matrix manipulation operations.
For this purpose, the vector, matrix data and the command list must be read from the file. Each line in the command list represents a manipulation process to be performed.
You should use your vector and matrix structure to implement all these operations in the C programming language. To store the vectors and matrices, you must use dynamic memory allocation.
Input files are consist of integer numbers separated by spaces and new lines. Vector files “.vec” and matrix files have “.mat” file extension. You can determine the type of an input file by looking at the file extensions.
Command types
- Initialization o veczeros [name] [length]: Creates a new vector of given length and name, filled with zeros.
Parameters: “name”: name of created vector, “length”: length of vector
Return: vector
Output: created vector [name] [length]
[elements of vector]
- matzeros [name] [x] [y]: Creates a new matrix of given x, y and name, filled with zeros.
Parameters: “name”: name of created matrix, shape=“x”,“y”
Return: matrix
Output: created matrix [name] [x] [y]
[elements of matrix]
- vecread [filename]: Reads the vector from the file with the given filename
Parameters: “filename”: path of the vector file to read
Return: vector
Output: read vector [name] [length]
[elements of vector]
- matread [filename]: Reads the matrix from the file with the given filename
Parameters: “filename”: path of the sparse matrix file to read
Return: matrix
Output: read matrix [name] [x] [y]
[elements of matrix]
- Concatenation o vecstack [vector1] [vector2] [direction] [name]: Combines “vector1” and “vector2” and creates a matrix.
Parameters: Function takes the names of the vectors and the form of assembly as parameter. The “direction” parameter can be “row” or “column”. The new matrix name is given with the “name” parameter.
Return: matrix
Output: vectors concatenated [name] [x] [y] [newline]
[elements of new matrix]
- matstack [matrix1] [matrix2] [where]: Combines “matrix1” and
“matrix2”.
Parameters: Function takes the names of the matrices and the form of assembly as parameter. The “where” parameter can be “r” for right and
“d” for down.
Return: matrix
Output: matrices concatenated [matrix1] [x] [y] [newline]
[elements of matrix1]
- mvstack [matrix] [vector] [where]: Combines “matrix” and “vector”. Parameters: Function takes name of the matrix, name of vector. The
“where” parameter can be “r” for right and “d” for down.
Return: matrix
Output: matrix and vector concatenated [matrix] [x] [y] [newline]
[elements of matrix]
- Padding
o pad [matrix] [x] [y] [mode]: Enlarges the size of the matrix and sets the values of the new elements.
Parameters: Function takes name of the matrix, x, y and the “mode” as parameter. The mode parameter can be “maximum” or “minimum”.
- “maximum“: Pads with the maximum value of all or part of the vector along each axis.
- “minimum“: Pads with the minimum value of all or part of the vector along each axis.
Return: matrix
Output: matrix paded [matrix] [x] [y] [newline]
[elements of matrix]
o padval [matrix] [x] [y] [val]: Enlarges the size of the matrix and sets the values of the new elements.
Parameters: Function takes name of the matrix, x, y and the “val” as parameter. Return: matrix
Output: matrix paded [matrix] [x] [y] [newline]
[elements of matrix]
- Slicing o vecslice [vector] [start] [stop] [name]: Takes a part from the given vector.
Parameters: Function takes “vector name”, “start”, “stop” and “name” as parameters. “start” is the start index and “stop” is the end index. The taken slice name is given with the “name” parameter.
Return: vector
Output: vector sliced [name] [elements]
[elements of vector]
- matslicecol [matrix] [index] [start] [stop] [name]: Takes a part of vector from the given matrix.
Parameters: Function takes “matrix name”, “index”, “start”, “stop” and “name” as parameters. “index” is the column index, “start” is the start index and “stop” is the end index. The taken slice name is given with the “name” parameter.
Return: vector
Output: vector sliced [name] [elements]
[elements of vector]
- matslicerow [matrix] [index] [start] [stop] [name]: Takes a part of vector from the given matrix.
Parameters: Function takes “matrix name”, “index”, “start”, “stop” and
“name” as parameters. “index” is the row index, “start” is the start index and “stop” is the end index. The taken slice name is given with the “name” parameter. Return: vector
Output: vector sliced [name] [elements]
[elements of vector]
- matslice [matrix] [x1] [x2] [y1] [y2] [name]: Takes a part of matrix from the given matrix.
Parameters: Function takes “matrix name”, “x1”, “x2”, “y1”, “y2” and
“name” as parameters. “x1” is the start column index, “x2” is the end column index, “y1” is the start row index, “y2” is the end row index. The taken matrix name is given with the “name” parameter.
Return: matrix
Output: matrix sliced [name] [x] [y] [newline]
[elements of matrix]
- Math
- add [matrix1] [matrix2]: calculates the element-wise sum of two matrices and overwrites matrix1
Parameters: Function takes the names of the matrices.
Return: matrix
Output: add [matrix1] [matrix2] [newline]
[elements of matrix1]
- multiply [matrix1] [matrix2]: calculates the element-wise product of two matrices and overwrites matrix1
Parameters: Function takes the names of the matrices.
Return: matrix
Output: multiply [matrix1] [matrix2] [newline]
[elements of matrix1]
- subtract [matrix1] [matrix2]: calculates the element-wise subtraction of two matrices and overwrites matrix1
Parameters: Function takes the names of the matrices.
Return: matrix
Output: subtract [matrix1] [matrix2] [newline]
[elements of matrix1]
3.1. EXECUTION
The name of the compiled executable program should be “matrixman”. Your program should read input/output file names from the command line, so it will be executed as follows:
matrixman [folder_of_input_files] [command_list_file_name] [output file name]
e.g.: ./matrixman inputs commands.cmd output.out
You can see sample input and output in piazza page. The program must run on DEV (dev.cs.hacettepe.edu.tr) UNIX machines. So make sure that it compiles and runs in one of the UNIX lab. If we are unable to compile or run, the project risks getting zero point. It is recommended that you test the program using the same mechanism on the sample files (provided) and your own inputs. You must compare your own output and sample output. If your output is different from the sample, the project risks getting zero point, too.
3.2. INPUT/OUTPUT FORMAT
In the commands file, the numbers are separated by spaces and newlines. You do need to check the input for errors. An example commands file can be given as follows:
matread m3.mat matread m4.mat subtract m3 m4 matslice m4 5 9 0 3 m8 matslicerow m4 1 2 6 v7 mvstack m8 v7 d subtract m3 m8
Sample matrix and vector files:
v1.vec
7 1 9 4 6 8 1 9 1 9
m1.mat
1 1 1
1 2 1
1 1 1
m3.mat
1 2 3 4
4 5 6 7
7 8 9 9
1 1 1 1
Your program should write outputs to the output file, so that each line in the output file will contain the result of multiplication. If the above input file is given, the output file should be as below:
| read matrix m3.mat 4 4
1 2 3 4 4 5 6 7 7 8 9 9 1 1 1 1 read matrix m4.mat 3 9 8 7 6 5 8 4 1 5 4 5 2 8 7 3 1 4 1 2 2 3 6 4 7 9 2 1 4 error matrix sliced m8 3 4 4 1 5 4 1 4 1 2 9 2 1 4 vector sliced v7 4 8 7 3 1 matrix and vector concatenated m8 4 4 4 1 5 4 1 4 1 2 9 2 1 4 8 7 3 1 subtract m3 m8 -3 1 -2 0 3 1 5 5 -2 6 8 5 -7 -6 -2 0 |
3.3. DESIGN EXPECTATIONS
You must use dynamic memory allocation for your solution. Writing spaghetti, or static arrays could render your entire assignment “unacceptable” and make it subject to huge (if not complete) grade loss.
3.4. VALID PLATFORMS
Your code will be compiled against gcc. You should not assume the availability of any other non-standard libraries/features. If you use a different compiler, it is your responsibility to ensure that your code has no compilation issues with the version of gcc in dev server.
- EVALUATION
- REQUIRED FILES
You should create and submit a ZIP archive in the following structure for evaluation. An invalid structured archive will cause you partial or full score loss.
You are required to submit a Makefile[1], which will be used to compile your program to generate the matrixman executable.
| Directory | Files | Description |
| Source | *.c, *.h, Makefile | Program source/header files and Makefile |
| Report | Your report (Only pdf format is accepted) |
- REPORTS
You must write a report which is related to your program. The topics that should be included in the report are:
- Problem definition
- Methods and solution
- Functions implemented and not implemented
[1] Make file example http://mrbook.org/tutorials/make/
REFERENCES
