# Week 2 - Dynamic Arrays
just some note:
## Team
>Members:
>
- William 530785
- Nghi Nguyen 532297
>
> Date: 3/6/2023
## Activities
Make sure to have the activities signed off regularly to ensure progress is tracked.
Before you start, download the project from Blackboard and explore the code contained in it.
### Activity 1: Random access
Rewrite the code by replacing **all** expressions in which pointers are dereferenced with equivalent ones that use the *array index operator* ("[..]").
````c
#include <stdio.h>
#define COUNT (50)
void fill_fibonacci(unsigned long long * storage, int count) {
*storage = 0;
*(storage + 1) = 1;
for (int i = 2; i < count; i++) {
*(storage + i) = *(storage + i - 1) + *(storage + i - 2);
}
}
int main(void) {
unsigned long long array[COUNT];
fill_fibonacci(array, COUNT);
for (int i = 1; i < COUNT; i++) {
printf("f(%d) = %llu\n", i, array[i]);
}
}
````
Fixed:
```c
#include <stdio.h>
#define COUNT 50
void fill_fibonacci(unsigned long long * storage, int count) {
storage[0] = 0;
storage[1] = 1;
for (int i = 2; i < count; i++) {
storage[i] = storage[i - 1] + storage[i - 2];
}
}
int main(void) {
unsigned long long array[COUNT];
fill_fibonacci(array, COUNT);
for (int i = 1; i < COUNT; i++) {
printf("f(%d) = %llu\n", i, array[i]);
}
}
```
### Activity 2: Array definition
Explain what each of the three fields of the `array_t` structure listed below is used for.
Find out, for your system, what the maximum number of elements is that can be stored in the array.
```C
typedef struct array {
size_t capacity;
size_t count;
float *data;
} array_t;
```
Answer:
`Capacity` is the maximum amount of elements the array can hold.
`Count` is the current amount of elements the array is holding.
`Data` is the pointer to access the array values.
For my compute, the maxmium of the size_t is 4611686018427387903 bytes. This number divides by 8 gives the maximum number of capacity.
### Activity 3: Correct initialization
Answer:
Version 1 is incorrect because it is returning the pointer of a local variable, which can result in undefined behavior. Also, it is not allocating memory on the heap so it is not creating a dynamic array. To fix this, we can use the malloc function to allocate some memory to make a actual dynamic array just like in version 2.
```C
array_t* array_init(array_t *p_array, size_t capacity) { // version 2
if (p_array != NULL) {
p_array->data = malloc(sizeof(float[capacity]));
p_array->count = 0;
p_array->capacity = p_array->data != NULL ? capacity : 0;
}
return p_array;
}
```
### Activity 4: Cleaning up
Program 1 is correct. On program 2, the variable array didn't allocate any memory unlike program 1, it's freeing the first element of the automatic lifetime variable array which would result in undefined behavaior.
```c
//program 1
int main(void) {
array_t *array = (array_t *) malloc(sizeof(array_t));
array_init(array, 10);
// .... do some work ...
// finally, clean up
array_destroy(array);
free(array);
}
// program 2
int main(void) {
array_t array;
array_init(&array, 10);
// .... do some work ...
// finally, clean up
array_destroy(&array);
free(&array);
}
```
### Activity 5: Resizing an array
void array_reserve(array_t *p_array, size_t min_capacity) {
size_t capacity = p_array->capacity;
while (capacity < min_capacity) {
capacity = (capacity + 1) * 1.5;
}
if (capacity != p_array->capacity) {
p_array->data = realloc(p_array, capacity);
}
}
Answer:
Google Search: 1.5 is ideal growth rate. The source: https://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array
Code:
#define ARRAY_GROWTH_RATE 1.5
void array_reserve(array_t *p_array, size_t min_capacity) {
size_t capacity = p_array->capacity;
while (capacity < min_capacity) {
capacity = (capacity + 1) * ARRAY_GROWTH_RATE;
}
if (capacity != p_array->capacity) {
p_array->data = realloc(p_array->data, (sizeof(float) * capacity));
if (p_array != NULL){ // check if allocation worked
p_array->capacity = capacity;
}
else{
p_array->capacity = 0;
}
}
}
```
###Activity 6: Appending values
Record your function definition here.
```c
void array_append(array * arr, float value);
```
Answer:
void array_append(array_t * arr, float value){
//check if there's enough space and extend the space if not
if (arr->capacity == arr->count){
array_reserve(arr, arr->capacity + 1); //we are just adding one new element
}
arr->data[arr->count] = value;
arr->count++;
}
### Activity 7: Inserting values
Record your function definition here.
```c
void array_insert(array * arr, size_t index, float value);
```
Make sure to test your function using the `test_array_insert` function.
Your code is correct if all the `assert` statements in the test function pass.
Answer:
void array_insert(array_t * arr, size_t index, float value) {
if (index <= arr->capacity) //must be a valid index
{
array_append(arr, 0); //since we are inserting, we need extra slot for the old values
for (size_t i = 0; i < (arr->count - index); i++){
arr->data[arr->count - i] = arr->data[(arr->count - i) - 1]; //make the 'next' element value to be the 'previous' element value
}
arr->data[index] = value;
}
}
### Activity 8: Removing by index
Record your function definition here.
```c
void array_remove(array * arr, size_t index);
```
Make sure to test your function using the `test_array_remove` function.
Your code is correct if all the `assert` statements in the test function pass.
answer:
void array_remove(array_t * arr, size_t index) {
for (size_t i = index; i < arr->capacity + 1; i++) {
arr->data[i] = arr->data[i + 1];
}
arr->count--;
}
### Activity 9: Constant time complexity
Consant time complexity means the program takes the same time to run no matter what the input size is.
### Activity 10: Worst-case time complexity
| Operation | Worst-case time complexity |
| --------------- | -------------------------- |
| Insert | Add value to the first index O(n) |
| Remove | Remove the first index value O(n) |
| Lookup / access | Since it's random access, so O(1) |
At both the worst-case of `Insert` and `Remove` operations, all elements of the array needs to be shifted, so it's O(n), it scales with the size of the array as it's shifting n amount of elements.
### Activity 11: Complexity of *append*
The average time complexity should be O(1) because you are just inserting a new element. When you don't have enough array size and you need to allocate new size, you will just allocate a bigger capacity with realloc and the array doesn't need a new address.
### Activity 12: Storing grades in a dynamically growing array
// keep asking the user to enter a grade, stop when user enters 0
void input_grades(array_t * grades){
float userInput;
int studentNumber = 1;
printf("Enter student %d's grade: \n", studentNumber);
scanf("%f", &userInput);
array_append(grades, userInput);
while (userInput != 0){
studentNumber++;
printf("Enter student %d's grade: \n", studentNumber);
scanf("%f", &userInput);
array_append(grades, userInput);
}
}
// computes and returns the average grade
float average(const array_t * grades){
float gradeSum = 0;
for (int i = 0; i < (grades->count - 1); i++){
gradeSum = gradeSum + grades->data[i];
}
return (float) gradeSum / (grades->count - 1);
}
// counts and returns the number of grades that are at least the threshold
int num_passed(const array_t * grades, float threshold){
int numPassedAmount = 0;
for (int i = 0; i < (grades->count - 1); i++){
if(grades->data[i] >= threshold){
numPassedAmount++;
}
}
return numPassedAmount;
}
int main() {
array_t grades;
array_init(&grades, 0);
input_grades(&grades);
float averageNum = average(&grades);
int passed = num_passed(&grades, 5.5f);
printf("Average grade: %.2f\n", averageNum);
printf("%d out of %zu students passed\n", passed, grades.count - 1);
array_destroy(&grades);
}
## Looking back
### What we've learnt
-Big O notation
### What were the surprises
The ideal growth rate is 1.5
### What problems we've encountered
no problems
### What was or still is unclear
Even i hve looked up th einternet, I still not sure why the ideal growth rate is spefically 1.5.
### How did the group perform?
This week wasn't as hard as the first 1.But still very chellging
Sign in with Wallet
Connect another wallet