Added all school stuff

12 files changed, 611 insertions, 0 deletions

diff --git a/sem1/algo/.gitignore b/sem1/algo/.gitignore
new file mode 100644
index 0000000..38aee6d
--- /dev/null
+++ b/sem1/algo/.gitignore
@@ -0,0 +1,2 @@
+**/a.out
+**/build
diff --git a/sem1/algo/lek1/merge.c b/sem1/algo/lek1/merge.c
new file mode 100644
index 0000000..997bcb8
--- /dev/null
+++ b/sem1/algo/lek1/merge.c
@@ -0,0 +1,115 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <stdint.h>
+
+#define DO_PRINT 0
+
+void printArr(int *arr, size_t len) {
+	printf("{");
+	for(int i = 0; i < len; i++) {
+		printf(" %d%s", arr[i], i+1 == len ? " " : ",");
+	}
+	printf("}\n");
+}
+
+int *genArr(size_t len, int div) {
+	/* Make array */
+	int *arr = (int *) malloc(len * sizeof(int));
+
+	if( arr == NULL) {
+		return NULL;
+	}
+
+	/* Fill it with random */
+	while( len-- ) {
+		arr[len] = div - (rand() % (div*2));
+	}
+
+	return arr;
+
+}
+
+int mergeSort(int *arr, size_t len) {
+	/* Check if len is one(then it's sorted */
+	if (len <= 1) {
+		return 0;
+	}
+	/* Calculate array sizes */
+	size_t q = len/2;
+	size_t rl = len-q;
+
+	/* Make arrays */
+	int *left = (int *) malloc(q * sizeof(int));
+	if( left == NULL ) {
+		return 1;
+	}
+	int *right = (int *) malloc(rl * sizeof(int));
+	if( right == NULL ) {
+		return 1;
+	}
+
+	/* Copy data */
+	memcpy(left, arr, q * sizeof(int));
+	memcpy(right, arr + q, rl * sizeof(int));
+
+	/* Sort each */
+	mergeSort(left, q);
+	mergeSort(right, rl);
+
+	/* Merge them into arr */
+	for(int i=0, j=0, k = 0; k < len; k++) {
+		if( i < q && ( j == rl || left[i] <= right[j] ) ) {
+			arr[k] = left[ i++ ];
+		} else {
+			arr[k] = right[ j++ ];
+		}
+	}
+
+	/* Free the pointers */
+	free(left);
+	free(right);
+
+	return 0;
+}
+
+void test(size_t len) {
+
+	int *a = genArr(len, len);
+
+#if DO_PRINT == 1
+	printArr(a, len);
+	printf("\n\n");
+#endif
+
+	clock_t begin = clock();
+	mergeSort(a, len);
+	clock_t end = clock();
+
+#if DO_PRINT == 1
+	printArr(a, len);
+#endif
+
+	clock_t diff = end - begin;
+	printf("Sorting %d long array took %d : %f s\n", len, diff, (double)diff/CLOCKS_PER_SEC);
+
+	free(a);
+}
+
+void bench() {
+
+	size_t len = SIZE_MAX;
+
+	srand((unsigned) time(NULL));
+	for (int i = 1; i < len; i *= 2) {
+		test(i);
+	}
+}
+
+int main(void) {
+
+	bench();
+
+	return 0;
+}
diff --git a/sem1/algo/mm2/linked/Makefile b/sem1/algo/mm2/linked/Makefile
new file mode 100644
index 0000000..881143c
--- /dev/null
+++ b/sem1/algo/mm2/linked/Makefile
@@ -0,0 +1,31 @@
+CC = gcc
+# Enable gdb and pull include files from current dir
+CFLAGS = -ggdb -I.
+LDFLAGS = 
+
+BINARY = linked
+BUILD_DIR = build
+
+# Capture c files 
+c_files = $(wildcard *.c)
+
+# Convert c names to corrosponding o names
+OBJ = $(patsubst %.c, $(BUILD_DIR)/%.o, $(c_files))
+
+# $@ is the %.o file and $^ is the %.c file
+$(BUILD_DIR)/%.o: %.c
+	mkdir -p $(dir $@)
+	$(CC) -c -o $@ $^ $(CFLAGS)
+
+# $@ becomes left part thus linked
+$(BINARY): $(OBJ)
+	$(CC) -o $@ $^ $(LDFLAGS)
+
+.PHONY: clean run
+
+run: $(BINARY)
+	./$(BINARY)
+
+clean:
+	rm -f $(OBJ) $(BINARY)
+	rmdir $(BUILD_DIR)
diff --git a/sem1/algo/mm2/linked/Readme.md b/sem1/algo/mm2/linked/Readme.md
new file mode 100644
index 0000000..679dcf3
--- /dev/null
+++ b/sem1/algo/mm2/linked/Readme.md
@@ -0,0 +1,22 @@
+# Linked list assignment
+
+The linked list stuff is in node.c and higher level list functions in llist.c.
+
+Build with make:
+
+```
+make
+```
+
+To build and run
+
+```
+make run
+```
+
+To clean up when we are done.
+
+```
+make clean
+```
+
diff --git a/sem1/algo/mm2/linked/llist.c b/sem1/algo/mm2/linked/llist.c
new file mode 100644
index 0000000..41ab892
--- /dev/null
+++ b/sem1/algo/mm2/linked/llist.c
@@ -0,0 +1,89 @@
+#include "llist.h"
+
+#include <string.h>
+#include <stdio.h>
+
+
+#define OUT_OFF_BOUNDS 2
+
+void llist_init(llist_t *list) {
+	/* Zero out structure */
+	list->head = list->root = NULL;
+
+	list->len = 0;
+
+}
+
+void llist_append(llist_t *list, int val) {
+	/* Insert node after HEAD */
+	list->head = node_insert(list->head, val);
+
+	/* Check if was list is empty */
+	if( list->len == 0 ) {
+		/* Set root */
+		list->root = list->head;
+	}
+
+	/* Increase count */
+	list->len++;
+}
+
+node_t *llist_get_node(llist_t *list, unsigned int index) {
+	/* Check if we have it */
+	if( index >= list->len ) {
+		return NULL;
+	}
+
+	/* Find the best way to go down the list */
+	int direc = index > (list->len / 2) ? -1 : 1;
+
+	/* Setup start location */
+	int pos = direc > 0 ? 0 : list->len-1;
+	node_t *node = direc > 0 ? list->root : list->head;
+	
+	/* Go to index */
+	while( pos != index ) {
+		/* TODO kinda risky, we trust our math and len */
+		node = direc > 0 ? node->next : node->prev;
+
+		pos += direc;
+	}
+
+	return node;
+}
+
+int llist_get(llist_t *list, unsigned int index) {
+	/* Get node */
+	node_t *node = llist_get_node(list, index);
+	if( node == NULL ) {
+		/* Yes i know this is stupid */
+		return -1;
+	}
+
+	/* Return value */
+	return node->val;
+}
+
+
+int llist_pop(llist_t *list, unsigned int index) {
+	/* Get node */
+	node_t *node = llist_get_node(list, index);
+	if( node == NULL ) {
+		/* Yes i know this is stupid */
+		return -1;
+	}
+
+	/* Update root and head if we delete it */
+	if( node == list->root ) {
+		list->root = node->next;
+	}
+	if( node == list->head ) {
+		list->head = node->prev;
+	}
+	
+	/* Keep len up to date */
+	list->len--;
+
+	/* Delete stuff */
+	return node_pop(node);
+}
diff --git a/sem1/algo/mm2/linked/llist.h b/sem1/algo/mm2/linked/llist.h
new file mode 100644
index 0000000..e52be89
--- /dev/null
+++ b/sem1/algo/mm2/linked/llist.h
@@ -0,0 +1,22 @@
+#ifndef LIST_H
+#define LIST_H
+
+#include "node.h"
+
+typedef struct {
+	node_t *root;
+	node_t *head;
+	unsigned int len;
+} llist_t;
+
+void llist_init(llist_t *list);
+
+void llist_append(llist_t *list, int val);
+
+node_t *llist_get_node(llist_t *list, unsigned int index);
+
+int llist_get(llist_t *list, unsigned int index);
+
+int llist_pop(llist_t *list, unsigned int index);
+
+#endif 
diff --git a/sem1/algo/mm2/linked/main.c b/sem1/algo/mm2/linked/main.c
new file mode 100644
index 0000000..72b62cc
--- /dev/null
+++ b/sem1/algo/mm2/linked/main.c
@@ -0,0 +1,45 @@
+#include <stdio.h>
+#include "node.h"
+#include "llist.h"
+
+void list_print(node_t *root) {
+	int index = 0;
+	/* Loop through notes and print them */
+	while( root != NULL ) {
+		/* Print a value */
+		printf("%d: %d\n", index++, root->val);
+
+		/* Next value */
+		root = root->next;
+	}
+}
+
+/* Remove node */
+int main() {
+	
+	/* Do some stuff */
+	llist_t list;
+	llist_init(&list);
+
+	llist_append(&list, 11); // 0
+	llist_append(&list, 22); // 1
+	llist_append(&list, 33); // 2
+	llist_append(&list, 44); // 3
+	llist_append(&list, 89); // 4
+	llist_append(&list, 12); // 5
+	llist_append(&list, 2);  // 6
+	llist_append(&list, 1);  // 7
+	llist_append(&list, 7);  // 8
+	llist_append(&list, 232);// 9
+
+	list_print(list.root);
+	printf("%d\n", llist_get(&list, 5));
+	llist_pop(&list, 9);
+	printf("%d\n", llist_get(&list, 7));
+
+	list_print(list.root);
+
+	while( list.len ) {
+		printf("Popped %d\n", llist_pop(&list, 0));
+	}
+}
diff --git a/sem1/algo/mm2/linked/node.c b/sem1/algo/mm2/linked/node.c
new file mode 100644
index 0000000..cce1be0
--- /dev/null
+++ b/sem1/algo/mm2/linked/node.c
@@ -0,0 +1,57 @@
+#include "node.h"
+
+#include <string.h>
+#include <stdlib.h>
+
+/* Insert after node */
+node_t *node_insert(node_t *node, int val) {
+	/* Create new node */
+	node_t *newNode = (node_t *) malloc( sizeof(node_t) );
+	if( newNode == NULL ) {
+		return NULL;
+	}
+
+
+	newNode->val = val;
+	newNode->prev = node;
+
+	/* Check if there is node before */
+	if( node == NULL ) {
+		/* If not then there is no after */
+		newNode->next = NULL;
+		return newNode;
+	}
+
+	/* Set next node */
+	newNode->next = node->next;
+	node->next = newNode;
+
+	/* Check node after */
+	if( newNode->next != NULL ) {
+		/* Backlink next node */
+		newNode->next->prev = newNode;
+	}
+
+	return newNode;
+}
+
+/* Pop node */
+int node_pop(node_t *node) {
+	int val = node->val;
+
+	/* Check prev */
+	if( node->prev != NULL ) {
+		/* Point last node to next node */
+		node->prev->next = node->next;
+	}
+
+	/* Check next */
+	if( node->next != NULL ) {
+		node->next->prev = node->prev;
+	}
+
+	/* Free memory */
+	free(node);
+
+	return val;
+}
diff --git a/sem1/algo/mm2/linked/node.h b/sem1/algo/mm2/linked/node.h
new file mode 100644
index 0000000..027926b
--- /dev/null
+++ b/sem1/algo/mm2/linked/node.h
@@ -0,0 +1,23 @@
+#ifndef NODE_H
+#define NODE_H
+
+typedef struct node_struct {
+	int val;
+	struct node_struct *next;
+	struct node_struct *prev;
+} node_t;
+
+/** @brief Create a new node after specified node 
+ *  
+ *  @param node Pointer to node where new node should be inserted, can also be NULL
+ *  @param val Value to add to new node
+ */
+node_t *node_insert(node_t *node, int val);
+
+/** @brief Pop node from chain and free's the resource
+ *  
+ *  @return Value in node
+ */
+int node_pop(node_t *node);
+
+#endif 
diff --git a/sem1/algo/mm2/queue.c b/sem1/algo/mm2/queue.c
new file mode 100644
index 0000000..a93f76a
--- /dev/null
+++ b/sem1/algo/mm2/queue.c
@@ -0,0 +1,100 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#define EFULL 2
+#define EMPTY 3
+
+/* Queue stuff */
+typedef struct {
+	int head;
+	int tail;
+	int len;
+	int cap;
+	int *buff;
+} queue_t;
+
+/* Queue functions */
+int queue_init(queue_t *q, size_t cap) {
+	/* Make the struct and set i to zero */
+	memset(q, 0, sizeof(queue_t));
+
+	/* Allocate the buffer */
+	q->buff = (int *) malloc(cap * sizeof(int));
+	if( q->buff == NULL ) {
+		return 1;
+	}
+
+	/* Set capacity, the rest should be zero form memset */
+	q->cap = cap;
+	return 0;
+}
+
+void queue_free(queue_t *q) {
+	/* Free the heap buffer */
+	free(q->buff);
+}
+
+int queue_place(queue_t *q, int val) {
+	/* Check if full */
+	printf("len: %d\n", q->len);
+	if( q->len >= q->cap) {
+		printf("ERR: Full\n");
+		return EFULL;
+	}
+
+	/* Add to queue */
+	q->buff[q->head] = val;
+	
+	/* Increase values */
+	q->head = (q->head+1) % q->cap;
+	q->len++;
+
+	return 0;
+}
+
+int queue_get(queue_t *q, int *val) {
+	/* Check if empty */
+	if( !q->len ) {
+		printf("ERR: Empty\n");
+		return EMPTY;
+	}
+
+	/* Read value */
+	if( val != NULL ){
+		*val = q->buff[q->tail];
+	}
+
+	/* Decrease values */
+	q->tail = (q->tail+1) % q->cap;
+	q->len--;
+
+	return 0;
+}
+
+int main(void) {
+	int in;
+	char com;
+
+	queue_t q;
+	queue_init(&q, 16);
+
+	for(;;) {
+		/* Read a command */
+		scanf("%c", &com);
+
+		if( com == 'w') {
+			printf("> ");
+			scanf("%d", &in);
+			queue_place(&q, in);
+		} else if( com == 'r' ) {
+			queue_get(&q, &in);
+			printf("%d\n", in);
+		} else if( com == 'q' ) {
+			break;
+		}
+	}
+
+	queue_free(&q);
+	
+}
diff --git a/sem1/algo/mm3/multiply.c b/sem1/algo/mm3/multiply.c
new file mode 100644
index 0000000..e454de3
--- /dev/null
+++ b/sem1/algo/mm3/multiply.c
@@ -0,0 +1,56 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <time.h>
+
+uint64_t mult(uint64_t x, uint64_t y, unsigned int bits) {
+	/* Check if they expect more than 64 bits. */
+	if( bits > 64 ) {
+		printf("Sorry we cant handle higher than 64 bits\n");
+		exit(1);
+	} else if(bits <= 1) {
+		return x && y;
+	}
+
+	unsigned int newBits = bits >> 1;
+
+#if DO_PRINT == 1
+	printf("\n\n bits: %u, New bits: %u\n", bits, newBits);
+#endif 
+
+	/* Split up into to */
+	uint32_t halvMask = ((uint64_t)1 << newBits) - 1;
+#if DO_PRINT == 1
+	printf("Using mask 0x%08X\n", halvMask);
+#endif 
+	uint32_t a = (x >> (newBits)) & halvMask;
+	uint32_t b = x & halvMask;
+	uint32_t c = (y >> (newBits)) & halvMask;
+	uint32_t d = y & halvMask;
+
+#if DO_PRINT == 1
+	printf("A: 0x%08X, B: 0x%08X, C: 0x%08X, D: 0x%08X\n", a, b, c, d);
+#endif 
+
+	return (mult(a, c, newBits) << bits) + ((mult(a, d, newBits) + mult(b, c, newBits)) << newBits) + mult(b, d, newBits);
+
+}
+
+
+int main(void) {
+
+	uint32_t a = 0xFFFFFF;
+	uint8_t  b = 55;
+	uint64_t res;
+
+	clock_t begin = clock();
+	res = mult(a, b, 64);
+	clock_t end = clock();
+
+	printf("Result: %lld\n", res);
+
+	clock_t diff = end - begin;
+	printf("Took %d which is %f s\n", diff, (double)diff/CLOCKS_PER_SEC);
+	
+	return 0;
+}
diff --git a/sem1/algo/mm3/opgaver.md b/sem1/algo/mm3/opgaver.md
new file mode 100644
index 0000000..a6e560c
--- /dev/null
+++ b/sem1/algo/mm3/opgaver.md
@@ -0,0 +1,49 @@
+# Opgave 1
+
+## Exercise 9.2
+
+**T(n) = 3T(n/2) + n**
+
+a = 3
+b = 2
+d(n) = n
+
+a ? d(b) -> 3 > 2
+
+Svaret er derfor O(n^log2(3)) = O(n^1.59)
+
+**T(n) = 3T(n/2) + n^2**
+
+3 ? 2^2 -> 3 < 4
+
+d(n) = n^2 hvilket betyder at O(n^2)
+
+**T(n) = 8T(n/2) + n^2**
+
+8 ? 2^3 -> 8 = 8
+
+d(n) = n^3 hvilket betyder at O(n^3 log2(n))
+
+## Evercise 9.3
+
+**T(n) = 4T(n/3) + n**
+
+a = 4
+b = 3
+d(n) = n
+
+4 ? 3 -> 4 > 3
+
+Derfor er svaret O(n^log3(4)) = O(n^1.26)
+
+**T(n) = 4T(n/3) + n^2**
+
+4 ? 3^2 -> 4 < 9
+
+d(n) = n^2 hvilket betyder at O(n^2)
+
+**T(n) = 9T(n/3) + n^2**
+
+9 ? 3^2 -> 9 = 9
+
+d(n) = n^2 hvilket betyder at O(n^2 log2(n))