Engineering Computation Workshop 11
===
###### tags: `comp20005` `workshop` `c`
---
## Last Workshop
- Dynamic memory allocation
- Review
- Poker Hands & Physics
- Design a more efficient method for max-subarray problem
---
### Dynamic Memory Allocation
**Situation:** You want to create an array but you are unsure how large it is going to be at compile time, you also don't like wasting resources.
---
### Dynamic Memory Allocation
**Situation:** I want to decompose my functions better, so I want to create my structs/arrays in another function and return them instead of doing it all in main.
---
### Dynamic Memory Allocation
Normally we would just make a large enough array and hope for the best or throw back an error:
```cpp
int large_array[10000];
```
---
### Dynamic Memory Allocation
**Constraints:** If we wish to return an array and return it from a function not in main, or we don't know how large it is at compile time - the program needs to find out how many elements are stored inside during run-time otherwise we will inevitably get an index out of bounds error.
---
### Dynamic Memory Allocation
**Solution:** Allocate memory dynamically using `stdlib.h` functions `calloc`, `malloc`, `alloc`.
---
### Dynamic Memory Allocation
**malloc**: allocates memory to the requested pointer and returns it.
**declaration**
```cpp
void *malloc(size_t size)
```
**parameters**: `size` the size of the memory block in bytes
**return value**: `void*` pointer to the allocated memory or `NULL` if request fails
---
### Dynamic Memory Allocation
**example**
```cpp
int main(){
int new_array* = make_array(n)
}
int* make_array(int n){
int* new_array = (int*) malloc(n * sizeof(int));
assert (new_array != NULL);
return new_array;
}
```
---
### Dynamic Memory Allocation
It is a lot more useful however to have everything in a struct so lets do that, it will make sense later.
```cpp
struct {
int* A;
int size;
int capacity;
} typedef array_t;
```
---
### Dynamic Memory Allocation
**calloc**: allocates memory to the requested pointer and returns it. Also sets all the memory values to zero before returning.
**declaration**
```cpp
void *calloc(size_t nitems, size_t size)
```
**parameters**: `size` the size of the elements, `nitems` the number of elemments to be allocated
**return value**: `void*` pointer to the allocated memory or `NULL` if request fails
---
### Dynamic Memory Allocation
```cpp
array_t* make_array(int n){
int* A = (int*) calloc(n, size_of(int));
array_t* new_array = (*array_t) malloc(sizeof(array_t));
assert (new_array != NULL && A != NULL);
new_array -> A = A;
new_array.size = n;
new_array.capacity = n;
return new_array;
}
```
---
### Dynamic Memory Allocation
**realloc**: attempts to reize the memory block pointed to by `ptr` that was previously allocated with malloc or calloc.
**declaration**
```cpp
void *realloc(void *ptr, size_t size)
```
**parameters**: `*ptr` pointer to the previous memory block, `size` the size of the new memory block in bytes
**return value**: `void*` pointer to the newly allocated memory or `NULL` if request fails
---
### Dynamic Memory Allocation
```cpp
void resize_array(array_t *array){
if (array -> size == capacity){
array -> A = realloc(array -> A, sizeof(int) * array.capacity * 2);
assert(array -> A != NULL);
new_array -> capacity = 2*n;
}
}
```
---
## Review by Exam Questions
- reverseArray
- insertionSort
- myStrCat
- isPalindrome
- intersectingStructs
- numerical
- printPerms
---
### ReverseArray
> Write a function `void reverse_array(int A[], int n)` that takes an array of integers and reverses them inplace
---
### ReverseArray
```cpp
void swap(int A[], int a, int b){
int tmp = A[a];
A[a] = b;
A[b] = tmp;
}
void reverse_array(int A[], int n) {
int l = 0;
int r = n-1;
while (l < r) {
swap(&A[l], &A[r]);
l++;
r--;
}
}
```
---
### insertionSort
> Write a recursive function `void ins_sort(int* A, int n)` that takes an array of integers and sorts the numbers in place
---
### insertionSort
```cpp
void ins_sort(int* A, int n) {
if (n < 2) return;
ins_sort(A, n-1);
int key = A[n-1];
int j;
for (j = n-2; j >= 0 && A[j] > key; j--)
A[j+1] = A[j];
A[j+1] = key;
}
```
---
### StrCat
> Write a fucntion `my_str_cat(char* dst, char* src)` that appends src to the end of dst (assume there is enough memory in dst)
---
### StrCat
```cpp
int find_null_byte(char* string) {
int i =0;
while (string[i] != '\0') ++i;
return i;
}
void my_str_cat(char *src, char *dst) {
int src_index = find_null_byte(src);
int dst_index = find_null_byte(dst);
for (int i = 0; i <= src_index; ++i)
dst[i+dst_index] = src[i];
}
```
---
### isPalindrome
> Write a function `is_palindrome(char* s)` that returns 1 if the string is a palindrome else 0
---
### isPalindrome
```cpp
int is_palindrome(char* s) {
int r = find_null_byte(s);
return p_recur(s, 0, r-1);
}
int p_recur(char* s, int l , int r){
if (l >= r) return 1;
if (s[l] != s[r]) return 0;
return p_recur(s, ++l, --r);
}
```
---
### IntersectingStructs
A rectangle is represented by its lower and upper bounds in the x-dimension and the lower and upper bounds in the y-dimension, denoted by lx, ux, ly, uy, respectively. These bounds should be stored by double variables.
> Write the definition of a struct type named rectangle_t that represents the rectangle following the description above.
---
### IntersectingStructs
```cpp
typedef struct {
double x,y;
} point_t;
typedef struct {
point_t u, l;
} rectangle_t;
```
---
### IntersectingStructs
> Write a function `int intersect(rectangle_t rect1, rectangle_t rect2)` that returns 1 if the two rectangles intersect else 0.
---
### IntersectingStructs
```cpp
int vertical(rectangle_t rect1, rectangle_t rect2){
return rect1.l.y <= rect2.u.y || rect2.l.y <= rect1.u.y;
}
int horizontal(rectangle_t rect1, rectangle_t rect2){
return rect1.l.x <= rect2.u.x || rect2.l.x <= rect1.u.x;
}
int intersect(rectangle_t rect1, rectangle_t rect2) {
return horizontal(rect1,rect2) && vertical(rect1,rect2);
}
```
---
### IntersectingStructs
> Write a function `int countIntersect(rectangle_t rects1[], int n1, rectangle_t rects2[], int n2)` that returns the count of pairs of rectangles that intersect between 1 and 2
---
### IntersectingStructs
```cpp
int countIntersect(rectangle_t* rects1, int n1, rectangle_t* rects2, int n2) {
int count = 0;
for (int i = 0; i < n1; ++i){
for (int j = 0; j < n2; ++j)
count += intersect(rects1[i], rects2[i]);
}
return count;
}
```
---
### Numerical
> In a 16 bit twos compliment number representation for integers, what bit pattern represents the number 123 and -123
---
### Numerical
```
0000000001111011
1111111110000101
```
---
### Numerical
> In a 32 bit floating point number system with a 23 bit mantissa, 8 bit exponent and 1 bit sign how are the following numbers represented 0.0625, 23.725
---
### Numerical
```
00111101100000000000000000000000
01000001101111011100110011001101
```
---
### Numerical
> In general, to fit n arbitary points, a polynomial function of degree x is needed. Here what would be a possible value of x?
---
### Numerical
```
n-1
```
---
### PrintPerms
> Write a function `void print_perms(int n)` that prints out every permutation of the numbers from 1 to n, one per line. e.g.
`print_perms(3)`
```
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
```
---
### PrintPerms
```cpp
void print_perms(int n){
int A[n];
for (int i=1; i <= n; ++i)
A[i-1] = i;
perms(A, n, 0, n-1);
}
void perms(int *A, int n, int l, int r){
if (l == r){
print_array(A, n);
return;
}
for (int i = l; i <= r; ++i){
swap(a[l], a[i]);
perms(a, l+1, r);
swap(a[l], a[i]);
}
}
```
---
### Card Game -> Onto Grok!
Semester Slides:
https://hackmd.io/@kvoli/BJnR0242U
{"metaMigratedAt":"2023-06-15T04:32:41.904Z","metaMigratedFrom":"Content","title":"Engineering Computation Workshop 11","breaks":true,"contributors":"[{\"id\":\"097a8b2e-1817-41aa-b11f-65c49c54dbaf\",\"add\":8345,\"del\":338}]"}