diff options
43 files changed, 1658 insertions, 1 deletions
diff --git a/README.md b/README.md index 5408e6f..a06bc18 100644 --- a/README.md +++ b/README.md @@ -2,7 +2,7 @@ This used to be my competitive programming collection, now it is more of a warehouse for my computer programming journey. For historical reasons, -this README as well as commit messages are duolingo (Anglais et Vietnamien). +this README as well as commit messages are duolingo (anglais et vietnamien). | Thư mục | Nguồn đề bài | | ------------ | ------------------------------------------------------ | @@ -39,6 +39,7 @@ Phiên bản các trình dịch sử dụng test: | Common Lisp | SBCL 1.4.8+ | | Java | OpenJDK 11+ | | Lua | Lua 5.1+ | +| Octave | Octave 6+ | | Pascal | Free Pascal 2.6.4+ | | Python | Python 3.5+ | | Raku | Rakudo 2018.12+ | diff --git a/usth/ICT2.1/final/problem1.c b/usth/ICT2.1/final/problem1.c new file mode 100644 index 0000000..dce5ca7 --- /dev/null +++ b/usth/ICT2.1/final/problem1.c @@ -0,0 +1,33 @@ +/* Read a natural number from stdin and print its divisors to stdout */ +#include <stdio.h> + +/* Print all divisors of the given natural number n. */ +void print_divisors(int n, int i) +{ + if (i * i == n) + printf("%d\n", i); /* Θ(1) */ + if (i * i >= n) + return; /* Θ(1) */ + if (n % i == 0) + printf("%d\n%d\n", i, n / i); /* Θ(1) */ + print_divisors(n, i + 1); +} + +/* + * Complexity analysis: + * Let T(n, i) be the time complexity of print_divisors, it is obvious that + * T(n, i) = Θ(1) if i*i >= n + * T(n, i) = T(n, i + 1) + Θ(1) + * Thus T(n, 1) = sum(Θ(1) for i from 1 to ceil(sqrt(n))) = Θ(sqrt(n)) + * or the overall time complexity of the call from main is Θ(sqrt(n)) + * on all scenarios. + */ +int main() +{ + int n; + + scanf("%d", &n); + print_divisors(n, 1); + + return 0; +} diff --git a/usth/ICT2.1/final/problem2.c b/usth/ICT2.1/final/problem2.c new file mode 100644 index 0000000..1b3368d --- /dev/null +++ b/usth/ICT2.1/final/problem2.c @@ -0,0 +1,127 @@ +/* + * Read one natural number from stdin and print its prime factors to stdout + * The time complexity analysis of this program is commented in the source code + */ +#include <stdio.h> +#include <stdlib.h> + +typedef struct list construct; +struct list { + void *car; + construct *cdr; +}; + +typedef struct { + construct *stack; +} stack; + +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; +} + +stack *mkstack() +{ + stack *s = malloc(sizeof(stack)); + s->stack = NULL; + return s; +} + +int stack_empty(stack *s) +{ + return s->stack == NULL; +} + +void stack_push(stack *s, void *item) +{ + s->stack = cons(item, s->stack); +} + +void *stack_top(stack *s) +{ + return car(s->stack); +} + +void *stack_pop(stack *s) +{ + void *first = car(s->stack); + construct *rest = cdr(s->stack); + free(s->stack); + s->stack = rest; + return first; +} + +int main() +{ + int n, m; /* Θ(1) */ + stack *s = mkstack(); /* Θ(1) */ + + scanf("%d", &n); /* Θ(1) */ + m = n; /* Θ(1) */ + /* + * Let P be the sequence of prime factors of n and l be length of P. + * Let T(n, 2) be the time complexity of this for loop. + * Consider the function T(n, i): + * T(n, i) = Θ(1) if i*i >= n + * T(n, i) = T(n, i + 1) + Θ(1) if n is not divisible by i (*) + * T(n, i) = T(n/i, i) + Θ(1) if n is divisible by i (**) + * + * If only the (*) recurrence occurs, it is the worst case and + * T(n, 2) = sum(Θ(1) for i from 2 to floor(sqrt(n))) = Θ(sqrt(n)) + * + * If only the (**) recurrence occurs, it is the best case where n + * is power of 2. For convenience, we define R(n) = T(n, 2) and get + * R(n) = 1R(n/2) + Θ(n^log2(1)) + * By the master theorem, + * R(n) = Θ(n^log2(1) lg(n)) = Θ(lg(n)). + * + * If both occurs (average case), I can imagine that there exist numbers + * n_0, n_1, etc. and m_0, m_1, etc. that + * T(n, 2) = sum(Θ(sqrt(n_i))) + sum(Θ(lg(m_i))) = Θ(sqrt(n)) + * I, however, fail to formulate a rigorous proof for this. + */ + for (int i = 2; i * i <= n; ++i) + while (n % i == 0) { + int *tmp = malloc(sizeof(int)); /* Θ(1) */ + *tmp = i; /* Θ(1) */ + stack_push(s, tmp); /* Θ(1) */ + n /= i; /* Θ(1) */ + } + if (n != 1) { + int *tmp = malloc(sizeof(int)); + *tmp = n; + stack_push(s, tmp); + } /* Θ(1) */ + + /* + * Since each iteration of the loop above produce at most one + * prime factor, the time complexity of the loop below is O(T(n, 2)). + */ + while (!stack_empty(s)) { + printf("%d * ", *(int *) stack_top(s)); /* Θ(1) */ + stack_pop(s); /* Θ(1) */ + } + /* Terrible hack, not even portable (depending on flush behavior) */ + printf("\b\b= %d\n", m); /* Θ(1) */ + + return 0; +} + +/* + * Conclusion on time complexity: + * Best case: Θ(lg(n)) + O(Θ(lg(n))) = Θ(lg(n)) + * Average case and worst case: Θ(sqrt(n)) + O(Θ(sqrt(n))) = Θ(sqrt(n)) + */ diff --git a/usth/ICT2.1/labwork/1/Bonus.c b/usth/ICT2.1/labwork/1/Bonus.c new file mode 100644 index 0000000..e98bee5 --- /dev/null +++ b/usth/ICT2.1/labwork/1/Bonus.c @@ -0,0 +1,25 @@ +/* + * Read an integer from stdin and print its prime factors to stdout + * This is free and unencumbered software released into the public domain. + */ + +#include <stdio.h> + +int main() +{ + unsigned n, m = 0; + + scanf("%u", &n); + + for (unsigned i = 2; i * i <= n; ++i) + while (n % i == 0) { + printf(m++ ? " %u" : "%u", i); + n /= i; + } + if (n != 1) + printf(m++ ? " %u" : "%u", n); + if (m) + putchar(10); + + return 0; +} diff --git a/usth/ICT2.1/labwork/1/Ex1.cc b/usth/ICT2.1/labwork/1/Ex1.cc new file mode 100644 index 0000000..da20f22 --- /dev/null +++ b/usth/ICT2.1/labwork/1/Ex1.cc @@ -0,0 +1,28 @@ +// Read two integers from stdin and print their sum and product +// This is free and unencumbered software released into the public domain. + +#include <iostream> + +using namespace std; + +int +add (int& a, int& b) +{ + return a + b; +} + +int +mul (int& a, int& b) +{ + return a * b; +} + +int +main () +{ + int a; + int b; + + cin >> a >> b; + cout << add (a, b) << endl << mul (a, b) << endl; +} diff --git a/usth/ICT2.1/labwork/1/Ex2.c b/usth/ICT2.1/labwork/1/Ex2.c new file mode 100644 index 0000000..f783946 --- /dev/null +++ b/usth/ICT2.1/labwork/1/Ex2.c @@ -0,0 +1,28 @@ +/* + * Read an array of n int from stdin and print its sum to stdout + * This is free and unencumbered software released into the public domain. + */ + +#include <stdio.h> +#include <stdlib.h> + +int sum(int n, int *a) +{ + int s = 0; + while (n--) + s += a[n]; + return s; +} + +int main() +{ + int n; + scanf("%d", &n); + + int *a = malloc(n * sizeof(int)); + for (int i = 0; i < n; ++i) + scanf("%d", a + i); + + printf("%d\n", sum(n, a)); + return 0; +} diff --git a/usth/ICT2.1/labwork/1/Ex3.c b/usth/ICT2.1/labwork/1/Ex3.c new file mode 100644 index 0000000..f20bb54 --- /dev/null +++ b/usth/ICT2.1/labwork/1/Ex3.c @@ -0,0 +1,33 @@ +/* + * Read coordinates of 2 2D-points from stdin and print their distance to stdout + * This is free and unencumbered software released into the public domain. + */ + +#include <math.h> +#include <stdio.h> + +/* + * The overhead caused by re-evaluating x in this case is much + * to change this into a function call. + */ +#define SQR(x) ((x) * (x)) + +/* Conventionally C names are in lowercase */ +struct point { + double x, y; +}; + +double distance(struct point u, struct point v) +{ + return sqrt(SQR(u.x - v.x) + SQR(u.y - v.y)); +} + +int main() +{ + struct point m, n; + + scanf("%lf %lf %lf %lf", &m.x, &m.y, &n.x, &n.y); + printf("%g\n", distance(m, n)); + + return 0; +} diff --git a/usth/ICT2.1/labwork/1/Ex4.c b/usth/ICT2.1/labwork/1/Ex4.c new file mode 100644 index 0000000..000f73a --- /dev/null +++ b/usth/ICT2.1/labwork/1/Ex4.c @@ -0,0 +1,46 @@ +/* + * Print the area of the rectangle constructed from a pair of 2D points + * and check if a point it within this rectangle + * This is free and unencumbered software released into the public domain. + */ + +#include <math.h> +#include <stdio.h> + +/* Writing a header for just a simple struct would be overkill. */ +struct point { + double x, y; +}; + +struct rect { + struct point u, v; +}; + +double area(struct rect r) +{ + return fabs((r.u.x - r.v.x) * (r.u.y - r.v.y)); +} + +int isin(struct point p, struct rect r) +{ + return ((p.x - r.u.x) * (p.x - r.v.x) < 0 + && (p.y - r.u.y) * (p.y - r.v.y) < 0); +} + +int main() +{ + struct point m, n; + /* Don't bother logging errors, since it would pollute the pipe. */ + do { + scanf("%lf %lf %lf %lf", &m.x, &m.y, &n.x, &n.y); + } while (m.x == n.x || m.y == n.y); + + struct rect r = {m, n}; + printf("%g\n", area(r)); + + struct point p; + scanf("%lf %lf", &p.x, &p.y); + printf("%d\n", isin(p, r)); + + return 0; +} diff --git a/usth/ICT2.1/labwork/1/README.md b/usth/ICT2.1/labwork/1/README.md new file mode 100644 index 0000000..2d8236b --- /dev/null +++ b/usth/ICT2.1/labwork/1/README.md @@ -0,0 +1,38 @@ +# Algorithms and Data Structures: Tutorial 1 + +This package contains the following files: + +* Ex1.cc +* Ex2.c +* Ex3.c +* Ex4.c +* Bonus.c + +These programs operate on standard I/O directly. Except for the solution +of the first exercise which is written in C++, all solutions are in C. +The 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/> diff --git a/usth/ICT2.1/labwork/1/TT1.pdf b/usth/ICT2.1/labwork/1/TT1.pdf new file mode 100644 index 0000000..3140b19 --- /dev/null +++ b/usth/ICT2.1/labwork/1/TT1.pdf Binary files differdiff --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); diff --git a/usth/ICT2.1/labwork/3/Ex1.c b/usth/ICT2.1/labwork/3/Ex1.c new file mode 100644 index 0000000..90b3ca5 --- /dev/null +++ b/usth/ICT2.1/labwork/3/Ex1.c @@ -0,0 +1,38 @@ +/* + * Reverse name from stdin. + * This is free and unencumbered software released into the public domain. + */ + +#include <ctype.h> +#include <stdio.h> +#include <stdlib.h> + +#include "stack.h" + +int main() +{ + stack *s = mkstack(); + char c, *p; + + while ((c = getchar()) != EOF) { + p = malloc(sizeof(char *)); + *p = isspace(c) ? 32 : c; + stack_push(s, p); + } + + while (!stack_empty(s) && *(char *) stack_top(s) == 32) { + p = stack_pop(s); + free(p); + } + + c = 32; + while (!stack_empty(s)) { + p = stack_pop(s); + putchar(c == 32 ? toupper(c = *p) : tolower(c = *p)); + free(p); + } + + putchar(10); + + return 0; +} diff --git a/usth/ICT2.1/labwork/3/Ex2.c b/usth/ICT2.1/labwork/3/Ex2.c new file mode 100644 index 0000000..49be21b --- /dev/null +++ b/usth/ICT2.1/labwork/3/Ex2.c @@ -0,0 +1,61 @@ +/* + * Add hard-coded names to a queue a print them to stdout. + * This is free and unencumbered software released into the public domain. + */ + +#include <stdio.h> +#include <stdlib.h> + +#include "construct.h" + +typedef struct { + construct *front; + construct *rear; +} queue; + +queue *mkq() +{ + queue *q = malloc(sizeof(queue)); + q->front = q->rear = NULL; +} + +int qempty(queue *q) +{ + return q->front == NULL; +} + +void qpush(queue *q, void *item) +{ + if (qempty(q)) + q->front = q->rear = cons(item, NULL); + else + q->rear = q->rear->cdr = cons(item, NULL); +} + +void *qpop(queue *q) +{ + if (qempty(q)) + return NULL; + void *first = car(q->front); + construct *rest = cdr(q->front); + free(q->front); + q->front = rest; + return first; +} + +int main() +{ + queue *q = mkq(); + qpush(q, "Mahathir Mohamad"); + qpush(q, "Elizabeth II"); + qpush(q, "Sheikh Sabah Al-Ahmad Al-Jaber Al-Sabah"); + qpush(q, "Paul Biya"); + qpush(q, "Michel Aoun"); + qpush(q, "Mahmoud Abbas"); + qpush(q, "Francis"); + + while (!qempty(q)) + puts(qpop(q)); + + return 0; +} diff --git a/usth/ICT2.1/labwork/3/Ex3.c b/usth/ICT2.1/labwork/3/Ex3.c new file mode 100644 index 0000000..b934ec0 --- /dev/null +++ b/usth/ICT2.1/labwork/3/Ex3.c @@ -0,0 +1,46 @@ +/* + * Interactive guessing game. + * This is free and unencumbered software released into the public domain. + */ + +#include <stdio.h> +#include <stdlib.h> +#include <time.h> + +#include "stack.h" + +char *random10(char *c) +{ + char *p = malloc(sizeof(char)); + *p = rand() % 10; + while (c != NULL && *p == *c) { + free(p); + p = malloc(sizeof(char)); + *p = rand() % 10; + } + return p; +} + +int main() +{ + stack *s = mkstack(); + char guess, lost = 0; + srand(time(NULL)); + stack_push(s, random10(NULL)); +STEP2: + stack_push(s, random10(stack_top(s))); + char *p = stack_pop(s); + puts(lost ? "Make another guess between 0 and 9" + : "Make a guess between 0 and 9"); + scanf("%hhd", &guess); + if ((guess - *p) * (guess - *(char *) stack_top(s)) < 0) { + puts("YOU WIN!"); + return 0; + } else if (lost) { + puts("YOU LOSE!"); + return 0; + } + + lost = 1; + goto STEP2; +} diff --git a/usth/ICT2.1/labwork/3/README.md b/usth/ICT2.1/labwork/3/README.md new file mode 100644 index 0000000..a38ee6e --- /dev/null +++ b/usth/ICT2.1/labwork/3/README.md @@ -0,0 +1,42 @@ +# Algorithms and Data Structures: Tutorial 3 + +This package contains the following files: + +* `construct.h`, `construct.c`: Lisp construct (with `cons`, `car` and `cdr`) +* `stack.h`, `stack.c`: initialization, check for empty, push, top and pop +* `Ex1.c`: read from stdin and reverse the name +* `Ex2.c`: add hard-coded names to a queue a print them to stdout +* `Ex3.c`: interactive guessing game + +Compilation can be done as follows + + cc construct.c stack.c Ex1.c -o Ex1 + cc construct.c Ex2.c -o Ex2 + cc construct.c stack.c Ex3.c -o Ex3 + +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/> diff --git a/usth/ICT2.1/labwork/3/TT3.pdf b/usth/ICT2.1/labwork/3/TT3.pdf new file mode 100644 index 0000000..708d20a --- /dev/null +++ b/usth/ICT2.1/labwork/3/TT3.pdf Binary files differdiff --git a/usth/ICT2.1/labwork/3/construct.c b/usth/ICT2.1/labwork/3/construct.c new file mode 100644 index 0000000..887b6d8 --- /dev/null +++ b/usth/ICT2.1/labwork/3/construct.c @@ -0,0 +1,26 @@ +/* + * 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; +} diff --git a/usth/ICT2.1/labwork/3/construct.h b/usth/ICT2.1/labwork/3/construct.h new file mode 100644 index 0000000..35d2448 --- /dev/null +++ b/usth/ICT2.1/labwork/3/construct.h @@ -0,0 +1,14 @@ +/* + * 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 *); diff --git a/usth/ICT2.1/labwork/3/stack.c b/usth/ICT2.1/labwork/3/stack.c new file mode 100644 index 0000000..708fb59 --- /dev/null +++ b/usth/ICT2.1/labwork/3/stack.c @@ -0,0 +1,39 @@ +/* + * Stack implemented using linked list. + * This is free and unencumbered software released into the public domain. + */ + +#include <stdlib.h> + +#include "stack.h" + +stack *mkstack() +{ + stack *s = malloc(sizeof(stack)); + s->stack = NULL; + return s; +} + +int stack_empty(stack *s) +{ + return s->stack == NULL; +} + +void stack_push(stack *s, void *item) +{ + s->stack = cons(item, s->stack); +} + +void *stack_top(stack *s) +{ + return car(s->stack); +} + +void *stack_pop(stack *s) +{ + void *first = car(s->stack); + construct *rest = cdr(s->stack); + free(s->stack); + s->stack = rest; + return first; +} diff --git a/usth/ICT2.1/labwork/3/stack.h b/usth/ICT2.1/labwork/3/stack.h new file mode 100644 index 0000000..2ed8851 --- /dev/null +++ b/usth/ICT2.1/labwork/3/stack.h @@ -0,0 +1,16 @@ +/* + * Stack header. + * This is free and unencumbered software released into the public domain. + */ + +#include "construct.h" + +typedef struct { + construct *stack; +} stack; + +stack *mkstack(); +int stack_empty(stack *); +void stack_push(stack *, void *); +void *stack_top(stack *); +void *stack_pop(stack *); diff --git a/usth/ICT2.1/labwork/4/Bonus.c b/usth/ICT2.1/labwork/4/Bonus.c new file mode 100644 index 0000000..b46b3fe --- /dev/null +++ b/usth/ICT2.1/labwork/4/Bonus.c @@ -0,0 +1,26 @@ +/* + * Solve Towers of Hà Nội of height n, where towers are named foo, bar and baz. + * This is free and unencumbered software released into the public domain. + */ + +#include <stdio.h> + +void anoi(unsigned n, char *one, char *other, char *another) +{ + if (n == 0) + return; + + anoi(n - 1, one, another, other); + printf("Move from %s to %s\n", one, other); + anoi(n - 1, another, other, one); +} + +int main() +{ + unsigned n; + + scanf("%u", &n); + anoi(n, "foo", "bar", "baz"); + + return 0; +} diff --git a/usth/ICT2.1/labwork/4/Ex1.c b/usth/ICT2.1/labwork/4/Ex1.c new file mode 100644 index 0000000..4d0ab5d --- /dev/null +++ b/usth/ICT2.1/labwork/4/Ex1.c @@ -0,0 +1,25 @@ +/* + * Multiply two natural numbers from stdin and print the result to stdout. + * This is free and unencumbered software released into the public domain. + */ + +#include <stdio.h> + +int multiply(int a, int b) +{ + if (a > 0) + return multiply(a - 1, b) + b; + if (a < 0) + return multiply(a + 1, b) - b; + return 0; +} + +int main() +{ + int a, b; + + scanf("%d %d", &a, &b); + printf("%d\n", multiply(a, b)); + + return 0; +} diff --git a/usth/ICT2.1/labwork/4/Ex2.c b/usth/ICT2.1/labwork/4/Ex2.c new file mode 100644 index 0000000..6ad6b87 --- /dev/null +++ b/usth/ICT2.1/labwork/4/Ex2.c @@ -0,0 +1,46 @@ +/* + * Read n from stdin and print all primes from 1 to n to stdout. + * This is free and unencumbered software released into the public domain. + */ + +#include <stdio.h> +#include <stdlib.h> + +void subsieve(int *mask, int n, int i, int j) +{ + if (j > n) + return; + mask[j] = 1; + subsieve(mask, n, i, i + j); +} + +void sieve(int *mask, int n, int i) +{ + if (i * i > n) + return; + if (!mask[i]) + subsieve(mask, n, i, i + i); + sieve(mask, n, i + 1); +} + +void print_primes(int *mask, int n) +{ + if (!n) + return; + if (!mask[n]) + printf("%d\n", n); + print_primes(mask, n - 1); +} + +int main() +{ + int n; + scanf("%d", &n); + + int *notprime = calloc(n + 1, sizeof(int)); + notprime[0] = notprime[1] = 1; + sieve(notprime, n, 2); + print_primes(notprime, n); + + return 0; +} diff --git a/usth/ICT2.1/labwork/4/Ex3.c b/usth/ICT2.1/labwork/4/Ex3.c new file mode 100644 index 0000000..ba016fc --- /dev/null +++ b/usth/ICT2.1/labwork/4/Ex3.c @@ -0,0 +1,32 @@ +/* + * Read numbers from stdin to a link list and print their sum to stdout. + * This is free and unencumbered software released into the public domain. + */ + +#include <stdio.h> +#include <stdlib.h> + +#include "construct.h" + +construct *readoubles() +{ + double *x = malloc(sizeof(double)); + if (scanf("%lf", x) != EOF) + return cons(x, readoubles()); + free(x); + return NULL; +} + +double sum(construct *list) +{ + if (list == NULL) + return 0.0; + /* At program termination the memory will be freed anyway. */ + return *(double *) car(list) + sum(cdr(list)); +} + +int main() +{ + printf("%g\n", sum(readoubles())); + return 0; +} diff --git a/usth/ICT2.1/labwork/4/Ex4.c b/usth/ICT2.1/labwork/4/Ex4.c new file mode 100644 index 0000000..86eaabb --- /dev/null +++ b/usth/ICT2.1/labwork/4/Ex4.c @@ -0,0 +1,34 @@ +/* + * Exchange money from stdin to least number of 1, 2, 5, 10, 20 and 50 bills. + * This is free and unencumbered software released into the public domain. + */ + +#include <stdio.h> + +struct change { + unsigned amount, bill; +}; + +const unsigned BILLS[] = {50, 20, 10, 5, 2, 1, 0}; + +void print_exchange(unsigned money, const unsigned *bills) +{ + if (!*bills) + return; + if (*bills > money) { + print_exchange(money, bills + 1); + return; + } + printf("%u %u\n", money / *bills, *bills); + print_exchange(money % *bills, bills + 1); +} + +int main() +{ + unsigned n; + + scanf("%u", &n); + print_exchange(n, BILLS); + + return 0; +} diff --git a/usth/ICT2.1/labwork/4/README.md b/usth/ICT2.1/labwork/4/README.md new file mode 100644 index 0000000..a7d0eee --- /dev/null +++ b/usth/ICT2.1/labwork/4/README.md @@ -0,0 +1,46 @@ +# Algorithms and Data Structures: Tutorial 4 + +This package contains the following files: + +* `construct.h`, `construct.c`: Lisp construct (with `cons`, `car` and `cdr`) +* `Ex1.c`: take 2 integers from stdin and print there product to stdout +* `Ex2.c`: print all primes in 1..n to stdout with n from stdin +* `Ex3.c`: print to stdout the sum of elements from stdin +* `Ex4.c`: exchange given amount of money from stdin to least number + of [1 2 5 10 20 50] bills and print the pairs of (amount, bill) to stdout +* `Bonus.c`: Towers of Hà Nội problem: no link list or stack needed + +Compilation can be done as follows + + cc Ex1.c -o Ex1 + cc Ex2.c -o Ex2 + cc construct.c Ex3.c -o Ex3 + cc Ex4.c -o Ex4 + cc Bonus.c -o Bonus + +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/> diff --git a/usth/ICT2.1/labwork/4/TT4.pdf b/usth/ICT2.1/labwork/4/TT4.pdf new file mode 100644 index 0000000..630172e --- /dev/null +++ b/usth/ICT2.1/labwork/4/TT4.pdf Binary files differdiff --git a/usth/ICT2.1/labwork/4/construct.c b/usth/ICT2.1/labwork/4/construct.c new file mode 100644 index 0000000..887b6d8 --- /dev/null +++ b/usth/ICT2.1/labwork/4/construct.c @@ -0,0 +1,26 @@ +/* + * 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; +} diff --git a/usth/ICT2.1/labwork/4/construct.h b/usth/ICT2.1/labwork/4/construct.h new file mode 100644 index 0000000..35d2448 --- /dev/null +++ b/usth/ICT2.1/labwork/4/construct.h @@ -0,0 +1,14 @@ +/* + * 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 *); diff --git a/usth/ICT2.1/labwork/5/Ex1.c b/usth/ICT2.1/labwork/5/Ex1.c new file mode 100644 index 0000000..e64c6ea --- /dev/null +++ b/usth/ICT2.1/labwork/5/Ex1.c @@ -0,0 +1,58 @@ +/* + * Cocktail shaker sorting integers from stdin + * Copyright (C) 2019, Nguyễn Gia Phong + * This software is licenced under a CC BY-SA 4.0 license + */ + +#include <stdio.h> + +void strswap(char *this, char *that, size_t n) +{ + while (n--) { + this[n] ^= that[n]; + that[n] ^= this[n]; + this[n] ^= that[n]; + } +} + +void csort(void *base, size_t nmemb, size_t size, + int (*compar)(const void *, const void *)) +{ + char *i, *low = base; + char *high = low + nmemb * size; + do { + char *h = i = low; + while ((i += size) < high) + if (compar(i - size, i) > 0) + strswap(i - size, h = i, size); + high = h; + if (low + size >= high) + break; + char *l = i = high; + while ((i -= size) > low) + if (compar(i - size, i) > 0) + strswap(i - size, l = i, size); + low = l; + } while (low + size < high); +} + +int cmp(const void *x, const void *y) +{ + return *(int *) x - *(int *) y; +} + +int main() +{ + size_t n; + scanf("%zu", &n); + int a[n]; + for (int i = 0; i < n; i++) + scanf("%d", a + i); + + csort(a, n, sizeof(int), cmp); + for (int i = 0; i < n; i++) + printf("%d ", a[i]); + putchar(10); + + return 0; +} diff --git a/usth/ICT2.1/labwork/5/Ex2.c b/usth/ICT2.1/labwork/5/Ex2.c new file mode 100644 index 0000000..edb5c26 --- /dev/null +++ b/usth/ICT2.1/labwork/5/Ex2.c @@ -0,0 +1,74 @@ +/* + * Merge sorting integers from stdin + * Copyright (C) 2019, Nguyễn Gia Phong + * This software is licenced under a CC BY-SA 4.0 license + */ + +#include <stdio.h> +#include <stdlib.h> + +#include "construct.h" + +construct *merge(construct *left, construct *right, + int (*compar)(const void *, const void *)) +{ + if (left == NULL) + return right; + if (right == NULL) + return left; + if (compar(car(left), car(right)) <= 0) + return cons(car(left), merge(cdr(left), right, compar)); + return cons(car(right), merge(left, cdr(right), compar)); +} + +construct *msort(construct *list, int (*compar)(const void *, const void *)) +{ + construct *rest, *left = NULL, *right = NULL; + while (list != NULL) { + left = cons(car(list), left); + rest = cdr(list); + if (rest == NULL) + break; + right = cons(car(rest), right); + list = cdr(rest); + } + if (left == NULL) + return right; + if (right == NULL) + return left; + return merge(msort(left, compar), msort(right, compar), compar); +} + +int cmp(const void *x, const void *y) +{ + return *(int *) x - *(int *) y; +} + +construct *iread(size_t n) +{ + if (!n) + return NULL; + int *tmp = malloc(sizeof(int)); + scanf("%d", tmp); + return cons(tmp, iread(n - 1)); +} + +void iprint(construct *list) +{ + if (list == NULL) { + putchar(10); + } else { + printf("%d ", *(int *) car(list)); + iprint(cdr(list)); + } +} + +int main() +{ + size_t n; + + scanf("%zu", &n); + iprint(msort(iread(n), cmp)); + + return 0; +} diff --git a/usth/ICT2.1/labwork/5/README.pdf b/usth/ICT2.1/labwork/5/README.pdf new file mode 100644 index 0000000..8a94167 --- /dev/null +++ b/usth/ICT2.1/labwork/5/README.pdf Binary files differdiff --git a/usth/ICT2.1/labwork/5/README.tex b/usth/ICT2.1/labwork/5/README.tex new file mode 100644 index 0000000..4c71999 --- /dev/null +++ b/usth/ICT2.1/labwork/5/README.tex @@ -0,0 +1,143 @@ +\documentclass[a4paper,12pt]{article} +\usepackage[english,vietnamese]{babel} +\usepackage{amsmath} +\usepackage{hyperref} +\usepackage{lmodern} +\usepackage{mathtools} + +\title{Algorithms and Data Structures\\ Searching and Sorting} +\author{Nguyễn Gia Phong---BI9-184} +\date{\dateenglish\today} + +\begin{document} +\maketitle +\section{Cocktail Shaker Sort} +The code is implemented following the cocktail shaker sort's +pseudocode\footnote{\url{https://en.wikipedia.org/wiki/Cocktail\_shaker\_sort\#Pseudocode}} +with bubble sort's optimization\footnote{\url{https://en.wikipedia.org/wiki/Bubble\_sort\#Optimizing\_bubble\_sort}} +whose time complexity is analyzed as follows + +\subsection{Best Case} +For the matter of brevity, we consider all operations on the array's $n$ members +are in constant time ($\Theta(1)$). If the array is already sorted, after +the first \verb|while| loop (line 25), \verb|h| is still \verb|low| and thus +the \verb|do|--\verb|while| loop is broken. Since the while loop runs from +\verb|low + size| to \verb|high - size| by \verb|size| steps, the running time +is \verb|(high - low - size*2)/size + 1| or \verb|nmemb - 1|. Therefore +the best case time complexity is $\Omega(n - 1) = \Omega(n)$. + +\subsection{Average Case} +Assume the average case is when the array is uniformly shuffled, that is, +every permutation has the equal probability to occur. + +Given a permutation of an $n$-element array, consider the positive integer +$k \le n$ that exactly the last $n - k$ members are continuously in the +correct positions (as in the ascendingly sorted array). It is obvious that +for $k = 1$, the array is sorted and the probability of the permutation +to appear is $1/n!$. For $1 < k \le n$, if we fix the last $n - k$ members +in their right places, out of the $k!$ permutations of the first $k$ elements, +$(k - 1)!$ ones has the $k$-th greatest at the correct place. Therefore, +let $X$ be the number that exactly $n - X$ last elements are in +the right positions, we have +\[p_X(k) = \begin{dcases} + \frac{1}{n!} &\text{if }k = 1\\ + \frac{k! - (k - 1)!}{n!} &\text{otherwise} +\end{dcases}\] + +Applying this to the first \verb|while| (line 25) with $n$ and $X - 1$ being +the number of steps from \verb|low| to \verb|high|, before and after +\verb|high = h| respectively, the expectation of $X$ is +\begin{align*} + \mathbf E[X] &= \sum_{k=1}^n k p_X(k)\\ + &= \frac{1}{n!} + \sum_{k=2}^n\frac{k!k - k!}{n!}\\ + &= \frac{1}{n!} + \sum_{k=3}^{n+1}\frac{k!}{n!} + - \sum_{k=2}^n\frac{k!}{n!} - \sum_{k=2}^n\frac{k!}{n!}\\ + &= \frac{1}{n!} + \frac{(n+1)!}{n!} + - \frac{2!}{n!} - \sum_{k=2}^n\frac{k!}{n!}\\ + &= n + 1 - \sum_{k=1}^n\frac{k!}{n!}\\ + &= n - \sum_{k=1}^{n-1}\frac{k!}{n!} +\end{align*} + +Hence after line 28, the newly sorted length of the array is +\[n - \mathbf E[X - 1] = n - \mathbf E[X] + 1 + = 1 + \sum_{k=1}^{n-1}\frac{k!}{n!} = \Theta(1)\] + +Similarly, line 31 to 35 also sort $\Theta(1)$ element(s), thus each iteration +of the \verb|do|--\verb|while| loop to sort $\Theta(1)$ members. The overall +average-case time complexity is +\begin{align*} + T(n) &= \begin{dcases} + (n - \Theta(1)) + (n - \Theta(1)) + T(n - \Theta(1)) &\text{if }n > 0\\ + \Theta(1) &\text{otherwise} + \end{dcases}\\ + &= \begin{dcases} + 2n - \Theta(1) + T(n - \Theta(1)) &\text{if }n > 0\\ + \Theta(1) &\text{otherwise} + \end{dcases}\\ + &= \Theta(1) + \sum_{k=1}^m(2k - \Theta(1)) + = 2\sum_{k=1}^m k - \sum_{k=1}^m\Theta(1) + = m^2 + m - \sum_{k=1}^m\Theta(1) +\end{align*} +where $m$ satisfies +\begin{multline*} + \exists\{f_k\mid k\in 1\,..\,m\} \subset \Theta(1),\, + \sum_{k=1}^m f_k(n) = n + \Longrightarrow \sum_{k=1}^m\Theta(1) = \Theta(n) + \Longrightarrow m = \Theta(n)\\ + \Longrightarrow T(n) = \Theta\left(n^2\right) + \Theta(n) - \Theta(n) + = \Theta\left(n^1\right) +\end{multline*} + +\subsection{Worst Case} +If the array is reversely sorted, after each first \verb|while| (line 25), +\verb|high| is decreased by \verb|size|; and after each second +\verb|while| (line 32), \verb|low| is increased by \verb|size|. +For \verb|low + size >= high|, it takes \verb|(high-low-size)/size + 1 >> 1| +or \verb|nmemb / 2| iterations of the \verb|do|--\verb|while| loop (line 23). +The overall complexity would then be +\begin{align*} + \sum_{k=1}^{\lfloor n/2\rfloor}(n - 2k + 1 + n - 2k) + &= \sum_{k=1}^{\lfloor n/2\rfloor}(2n - 4k + 1)\\ + &= n^2 + 2\left\lfloor\frac{n}{2}\right\rfloor + \left(\left\lfloor\frac{n}{2}\right\rfloor + 1\right) + + \left\lfloor\frac{n}{2}\right\rfloor\\ + &= O\left(n^2\right) +\end{align*} + +\section{Merge Sort} +As usual, the linked list is implemented using classic Lisp's \verb|cons|-cells. +The program is thus compiled by +\begin{verbatim} +cc construct.c Ex2.c -o Ex2 +\end{verbatim} + +To keep the implementation concise, memory safety as well as stack limit +was not considered. + +It is trivial that the time complexity of \verb|merge| is $\Theta(n)$ with +$n$ being the total length of \verb|left| and \verb|right|. For \verb|msort|, +the running time of the \verb|while| loop at line 27 is also $\Theta(n)$, where +n is the length of the input \verb|list|. The overall time complexity is +\[T(n) = \begin{dcases} + \Theta(1) &\text{if }n \le 1\\ + \Theta(n) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + + T\left(\left\lceil\frac{n}{2}\right\rceil\right) &\text{otherwise} +\end{dcases}\] + +The recurrence can be stated as +\[T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)\] +\pagebreak + +By the master theorem\footnote{Let $a \ge 1$ and $b > 1$ be constants, +and let $T(n)$ be defined on the nonnegative integers by the recurrence +\[T(n) = aT\left(\frac{n}{b}\right) + \Theta\left(n^{\log_b a}\right)\] +where $n/b$ is interpreted as either $\lfloor n/b\rfloor$ or $\lceil n/b\rceil$, +then \[T(n) = \Theta\left(n^{\log_b a}\lg n\right)\]}, +\[T(n) = 2T\left(\frac{n}{2}\right) + \Theta\left(n^{\log_2 2}\right) += \Theta\left(n^{\log_2 2}\lg n\right) = \Theta(n\lg n)\] + +\section{Copying} +This report along with the source files are licensed under a +\href{https://creativecommons.org/licenses/by-sa/4.0/}{Creative Commons +Attribution-ShareAlike 4.0 International License}. +\end{document} diff --git a/usth/ICT2.1/labwork/5/TT5.pdf b/usth/ICT2.1/labwork/5/TT5.pdf new file mode 100644 index 0000000..1038597 --- /dev/null +++ b/usth/ICT2.1/labwork/5/TT5.pdf Binary files differdiff --git a/usth/ICT2.1/labwork/5/construct.c b/usth/ICT2.1/labwork/5/construct.c new file mode 100644 index 0000000..235f900 --- /dev/null +++ b/usth/ICT2.1/labwork/5/construct.c @@ -0,0 +1,27 @@ +/* + * Lisp construct implementation. + * Copyright (C) 2019, Nguyễn Gia Phong + * This software is licenced under a CC BY-SA 4.0 license + */ + +#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; +} diff --git a/usth/ICT2.1/labwork/5/construct.h b/usth/ICT2.1/labwork/5/construct.h new file mode 100644 index 0000000..a27a1c3 --- /dev/null +++ b/usth/ICT2.1/labwork/5/construct.h @@ -0,0 +1,15 @@ +/* + * Lisp construct header. + * Copyright (C) 2019, Nguyễn Gia Phong + * This software is licenced under a CC BY-SA 4.0 license + */ + +typedef struct list construct; +struct list { + void *car; + construct *cdr; +}; + +construct *cons(void *, construct *); +void *car(construct *); +construct *cdr(construct *); diff --git a/usth/ICT2.1/labwork/6/Ex1.c b/usth/ICT2.1/labwork/6/Ex1.c new file mode 100644 index 0000000..12ebb02 --- /dev/null +++ b/usth/ICT2.1/labwork/6/Ex1.c @@ -0,0 +1,123 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#define MIN(a, b) (((a) < (b)) ? (a) : (b)) +#define MAX(a, b) (((a) > (b)) ? (a) : (b)) + +int *rand_array(size_t nmemb) +{ + int *base = malloc(nmemb * sizeof(int)); + for (size_t i = 0; i < nmemb; ++i) + base[i] = rand() % (1 << nmemb); + return base; +} + +size_t bits(size_t n) +{ + size_t h = 0; + while (n) { + n >>= 1; + h++; + } + return h; +} + +void *tree(int *base, size_t *nmemb) +{ + size_t n = 1 << bits(*nmemb - 1); + if ((base = realloc(base, n * sizeof(int) << 1)) == NULL) + return NULL; + memcpy(base + n, base, *nmemb * sizeof(int)); + int max = *base; + for (size_t i = 1; i < *nmemb; ++i) + max = MAX(base[n + i], max); + for (size_t i = *nmemb; i < n; ++i) + base[n + i] = max; + for (size_t i = n; --i;) + base[i] = MIN(base[i << 1], base[(i << 1) + 1]); + *nmemb = n << 1; + return base; +} + +void display(int *base, size_t nmemb, size_t node, size_t indent) +{ + if (node < 1 || node >= nmemb) + return; + display(base, nmemb, node << 1, indent + 1); + for (size_t i = 0; i++ < indent; putchar(9)); + printf("%d", base[node]); + putchar(10); + display(base, nmemb, (node << 1) + 1, indent + 1); +} + +size_t search(int value, int *base, size_t nmemb, size_t pos) +{ + if (pos < 1 || pos >= nmemb || base[pos] > value) + return 0; + if (base[pos] == value) + return pos; + size_t left = search(value, base, nmemb, pos << 1); + return left ? left : search(value, base, nmemb, (pos << 1) + 1); +} + +void treeify(int *base, size_t nmemb, size_t node) +{ + if (node > 1 && node < nmemb && base[node >> 1] > base[node]) { + base[node >> 1] = base[node]; + treeify(base, nmemb, node >> 1); + } +} + +void insert(int value, size_t pos, int *base, size_t nmemb) +{ + if (pos >= nmemb >> 1 && pos < nmemb) { + base[pos] = value; + treeify(base, nmemb, pos); + } +} + +void delete(size_t pos, int *base, size_t nmemb) +{ + if (pos > 1 && pos < nmemb) { + base[pos] = base[pos >> 1]; + delete(pos << 1, base, nmemb); + delete((pos << 1) + 1, base, nmemb); + } +} + +int main() +{ + size_t n; + puts("Array length:"); + scanf("%zu", &n); + + srand(time(NULL)); + int *a = rand_array(n); + a = tree(a, &n); + display(a, n, 1, 0); + + int x; + puts("Value to search for:"); + scanf("%d", &x); + size_t i = search(x, a, n, 1); + if (i) + display(a, n, i, 0); + else + puts("Not found"); + + puts("Value to insert:"); + scanf("%d", &x); + puts("Leaf index to insert to:"); + scanf("%zu", &i); + insert(x, i, a, n); + display(a, n, 1, 0); + + puts("Node to be deleted:"); + scanf("%zu", &i); + delete(i, a, n); + display(a, n, 1, 0); + + return 0; +} diff --git a/usth/ICT2.1/labwork/6/TT6.pdf b/usth/ICT2.1/labwork/6/TT6.pdf new file mode 100644 index 0000000..d4d3bf5 --- /dev/null +++ b/usth/ICT2.1/labwork/6/TT6.pdf Binary files differ |