6 files changed, 327 insertions, 0 deletions

diff --git a/usth/ICT2.1/labwork/2/Ex1.c b/usth/ICT2.1/labwork/2/Ex1.c
new file mode 100644
index 0000000..b4d5836
--- /dev/null
+++ b/usth/ICT2.1/labwork/2/Ex1.c
@@ -0,0 +1,100 @@
+/*
+ * Train represented using linked list by lisp-like constructs.
+ * This is free and unencumbered software released into the public domain.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "construct.h"
+
+#define N 7
+#define LEN_MAX 42
+#define PSNGR_MAX 5	/* this raises the chance of empty vehicle */
+
+struct vehicle {
+	int passengers;
+	char *name;
+};
+
+void free_vehicle(struct vehicle *v)
+{
+	free(v->name);
+	free(v);
+}
+
+struct vehicle *mkvehicle(int passengers, char *name)
+{
+	struct vehicle *v = malloc(sizeof(struct vehicle));
+	v->passengers = passengers;
+	v->name = name;
+	return v;
+}
+
+struct vehicle *rand_vehicle()
+{
+	int len = rand() % LEN_MAX + 2;	/* avoid empty name */
+	char *name = malloc(len--);
+	for (int j = 0; j < len; ++j)
+		name[j] = 'a' + rand() % 26;
+	name[len] = 0;
+	return mkvehicle(rand() % PSNGR_MAX, name);
+}
+
+void print_vehicle(struct vehicle *v)
+{
+	printf("%s (%d passengers)\n", v->name, v->passengers);
+}
+
+void print_train(construct *train)
+{
+	if (train == NULL)
+		return;
+	print_vehicle(car(train));
+	print_train(cdr(train));
+}
+
+/* Remove empty vehicles */
+construct *optimize_train(construct *train)
+{
+	if (train == NULL)
+		return NULL;
+	struct vehicle *first = car(train);
+	construct *rest = cdr(train);
+	free(train);
+
+	if (first->passengers)
+		return cons(first, optimize_train(rest));
+	free_vehicle(first);
+	return optimize_train(rest);
+}
+
+int main()
+{
+	construct *train = NULL;
+
+	srand(time(NULL));
+	for (int i = 0; i < N; ++i)
+		train = cons(rand_vehicle(), train);
+	puts("Initial train:");
+	print_train(train);
+	putchar(10);
+
+	train = optimize_train(train);
+	puts("Optimized train:");
+	print_train(train);
+	putchar(10);
+
+	int index = rand() % length(train);
+	struct vehicle *v = rand_vehicle();
+	while (!v->passengers) {
+		free(v);
+		v = rand_vehicle();
+	}
+	train = insert(v, train, index);
+	printf("Train after inserting a new one at index %d:\n", index);
+	print_train(train);
+
+	return 0;
+}
diff --git a/usth/ICT2.1/labwork/2/Ex2.c b/usth/ICT2.1/labwork/2/Ex2.c
new file mode 100644
index 0000000..8f32134
--- /dev/null
+++ b/usth/ICT2.1/labwork/2/Ex2.c
@@ -0,0 +1,104 @@
+/*
+ * Polynomial represented using linked list, with free coefficient at last.
+ * This is free and unencumbered software released into the public domain.
+ */
+
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "construct.h"
+
+#define COEFF_MOD 42
+
+/*
+ * Add addition to the coefficient of power n of poly if it already exists.
+ * Return the mutated polynomial on success and NULL otherwise.
+ */
+construct *add_term(construct *poly, double addition, size_t n)
+{
+	double *term = nth(poly, length(poly) - n - 1);
+	if (term == NULL)
+		return NULL;
+	*term += addition;
+	return poly;
+}
+
+/* Remove the nth term and return the mutated polynomial. */
+construct *remove_term(construct *poly, size_t n)
+{
+	if (poly == NULL)
+		return NULL;
+	size_t len = length(poly);
+	if (++n == len) {
+		construct *rest = cdr(poly);
+		free(car(poly));
+		free(poly);
+		return rest;
+	}
+
+	double *term = nth(poly, len - n);
+	if (term == NULL)
+		return poly;
+	*term = 0;
+	return poly;
+}
+
+/*  Evaluate the polynomial poly of the length len at the specified value. */
+double polyval(construct *poly, double value, size_t len)
+{
+	if (!len--)
+		return 0;
+	double coeff = *(double *) car(poly);
+	return pow(value, len) * coeff + polyval(cdr(poly), value, len);
+}
+
+/* Print the polynomial poly of the length len using the specified varname. */
+void polyprint(construct *poly, char *varname, size_t len)
+{
+	if (len--) {
+		printf(len ? "%g%s^%zu + " : "%g",
+		       *(double *) car(poly), varname, len);
+		polyprint(cdr(poly), varname, len);
+	} else {
+		putchar(10);
+	}
+}
+
+int main()
+{
+	construct *polynomial = NULL;
+	srand(time(NULL));
+	int len = rand() % 4 + 3;
+
+	for (int i = 0; i < len; ++i) {
+		double *coeff = malloc(sizeof(double));
+		*coeff = rand() % COEFF_MOD;
+		polynomial = cons(coeff, polynomial);
+	}
+
+	puts("Initial polynomial:");
+	polyprint(polynomial, "x", len);
+
+	double x = rand() % COEFF_MOD;
+	int n = rand() % len;
+	polynomial = add_term(polynomial, x, n);
+	printf("The polynomial after adding %g to the number %d term:\n", x, n);
+	polyprint(polynomial, "x", len);
+
+	polynomial = remove_term(polynomial, --len);
+	printf("The polynomial after removing the number %d term:\n", len);
+	polyprint(polynomial, "x", len);
+
+	n = rand() % (len - 1);
+	polynomial = remove_term(polynomial, n);
+	printf("The polynomial after removing the number %d term:\n", n);
+	polyprint(polynomial, "x", len);
+
+	puts("Evaluation of the polynomial using x from stdin:");
+	scanf("%lf", &x);
+	printf("%g\n", polyval(polynomial, x, len));
+
+	return 0;
+}
diff --git a/usth/ICT2.1/labwork/2/README.md b/usth/ICT2.1/labwork/2/README.md
new file mode 100644
index 0000000..25b43c4
--- /dev/null
+++ b/usth/ICT2.1/labwork/2/README.md
@@ -0,0 +1,49 @@
+# Algorithms and Data Structures: Tutorial 2
+
+This package contains the following files:
+
+* construct.h
+* construct.c
+* Ex1.c
+* Ex2.c
+
+Where construct is an minimal implementation of Lisp construct with
+`cons`, `car`, `cdr`, `length`, `nth` and `insert`.  It eases and simplifies
+the implementation of linked lists (and trees and and graphs if we study them
+later on).  All source files are as licensed under the Unlicense which states
+
+> This is free and unencumbered software released into the public domain.
+>
+> Anyone is free to copy, modify, publish, use, compile, sell, or
+> distribute this software, either in source code form or as a compiled
+> binary, for any purpose, commercial or non-commercial, and by any
+> means.
+>
+> In jurisdictions that recognize copyright laws, the author or authors
+> of this software dedicate any and all copyright interest in the
+> software to the public domain. We make this dedication for the benefit
+> of the public at large and to the detriment of our heirs and
+> successors. We intend this dedication to be an overt act of
+> relinquishment in perpetuity of all present and future rights to this
+> software under copyright law.
+>
+> THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+> EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+> MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+> IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+> OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+> ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+> OTHER DEALINGS IN THE SOFTWARE.
+>
+> For more information, please refer to <http://unlicense.org/>
+
+The solution of the second exercise uses the math library and thus
+it needs to by linked during compilation.  Both uses the `construct` library:
+
+    cc construct.c Ex1.c -o Ex1
+    cc construct.c Ex2.c -lm -o Ex2
+
+Additionally, `Ex2` requires a value of `x` to be entered from stdin:
+
+    ./Ex1
+    echo 7 | ./Ex2
diff --git a/usth/ICT2.1/labwork/2/TT2.pdf b/usth/ICT2.1/labwork/2/TT2.pdf
new file mode 100644
index 0000000..c373df5
--- /dev/null
+++ b/usth/ICT2.1/labwork/2/TT2.pdf
Binary files differdiff --git a/usth/ICT2.1/labwork/2/construct.c b/usth/ICT2.1/labwork/2/construct.c
new file mode 100644
index 0000000..db32d8a
--- /dev/null
+++ b/usth/ICT2.1/labwork/2/construct.c
@@ -0,0 +1,57 @@
+/*
+ * Lisp construct implementation.
+ * This is free and unencumbered software released into the public domain.
+ */
+
+#include <stdlib.h>
+
+#include "construct.h"
+
+construct *cons(void *first, construct *rest)
+{
+	construct *list = malloc(sizeof(construct));
+	list->car = first;
+	list->cdr = rest;
+	return list;
+}
+
+void *car(construct *list)
+{
+	return list->car;
+}
+
+construct *cdr(construct *list)
+{
+	return list->cdr;
+}
+
+size_t length(construct *list)
+{
+	if (list == NULL)
+		return 0;
+	return length(cdr(list)) + 1;
+}
+
+void *nth(construct *list, size_t n)
+{
+	if (list == NULL)
+		return NULL;
+	return n ? nth(cdr(list), n - 1) : car(list);
+}
+
+/*
+ * Try to insert x before item of index i and return the new construct.
+ * Return NULL on invalid index.
+ */
+construct *insert(void *x, construct *list, size_t i)
+{
+	if (!i)
+		return cons(x, list);
+	if (list == NULL)
+		return NULL;
+
+	void *first = car(list);
+	construct *rest = cdr(list);
+	free(list);
+	return cons(first, insert(x, rest, i - 1));
+}
diff --git a/usth/ICT2.1/labwork/2/construct.h b/usth/ICT2.1/labwork/2/construct.h
new file mode 100644
index 0000000..2d1c840
--- /dev/null
+++ b/usth/ICT2.1/labwork/2/construct.h
@@ -0,0 +1,17 @@
+/*
+ * Lisp construct header.
+ * This is free and unencumbered software released into the public domain.
+ */
+
+typedef struct list construct;
+struct list {
+	void *car;
+        construct *cdr;
+};
+
+construct *cons(void *, construct *);
+void *car(construct *);
+construct *cdr(construct *);
+size_t length(construct *);
+void *nth(construct *, size_t);
+construct *insert(void *, construct *, size_t);