Week 08 - Workshop.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Worksheet 7\n",
    "## Overview\n",
    "The workshop for week 8 will start with a tutorial on Mergesort, Master Theorem and Recurrences. You will implement Mergesort.\n",
    "## Tutorial Questions\n",
    "**Question 7.1** Trace the action of bottom-up mergesort on the same keys as in last week's workshop:\n",
    "- 2 3 97 23 15 21 4 23 29 37 5 23\n",
    "\n",
    "Is mergesort stable?\n",
    "## Programming exercises\n",
    "**Programming 7.1** Write code for bottom-up mergesort where the data are contained in an initially unsorted *linked list*. You will have to construct an artificial linked list to test your code. You can populate your linked list with random numbers before sorting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/* ll.h */\n",
    "struct linkedList {\n",
    "    struct linkedList *next;\n",
    "    int item;\n",
    "};\n",
    "\n",
    "/* Add a linked list item before the head of the given item. */\n",
    "struct linkedList *prepend(struct linkedList *head, int item);\n",
    "\n",
    "/* Add a linked list item to the end of the list, traversing all items. */\n",
    "struct linkedList *append(struct linkedList *head, int item);\n",
    "\n",
    "/* ll.c */\n",
    "#include <stdlib.h>\n",
    "#include <assert.h>\n",
    "/* #include \"ll.h\" */\n",
    "\n",
    "struct linkedList *prepend(struct linkedList *head, int item){\n",
    "    /* FILL IN if using. */\n",
    "    return NULL;\n",
    "}\n",
    "\n",
    "/* Add a linked list item to the end of the list, traversing all items. */\n",
    "struct linkedList *append(struct linkedList *head, int item){\n",
    "    /* FILL IN if using. */\n",
    "    return NULL;\n",
    "}\n",
    "\n",
    "/* queue.h */\n",
    "/* #include \"ll.h\" */\n",
    "struct llq;\n",
    "\n",
    "/* A simple function that appends the given list to the end\n",
    "    of the queue. If the given queue is NULL, one is allocated\n",
    "    with the queueHead being set to the given list, otherwise\n",
    "    the existing queue is returned appended with the new item. */\n",
    "struct llq *add(struct llq *oldQ, struct linkedList *list);\n",
    "\n",
    "/* Removes head of queue from queue and returns it. Queue will\n",
    "    be set to NULL if it becomes empty. */\n",
    "struct linkedList *dequeue(struct llq **queue);\n",
    "\n",
    "/* queue.c */\n",
    "#include <stdlib.h>\n",
    "#include <assert.h>\n",
    "/* #include \"ll.h\" */\n",
    "\n",
    "struct llq {\n",
    "    struct linkedList *queueHead;\n",
    "    struct llq *next;\n",
    "};\n",
    "\n",
    "struct llq *add(struct llq *oldQ, struct linkedList *list){\n",
    "    if(! oldQ){\n",
    "        oldQ = (struct llq *) malloc(sizeof(struct llq));\n",
    "        assert(oldQ);\n",
    "        oldQ->queueHead = list;\n",
    "        oldQ->next = NULL;\n",
    "    } else {\n",
    "        oldQ->next = add(oldQ->next, list);\n",
    "    }\n",
    "    return oldQ;\n",
    "}\n",
    "\n",
    "struct linkedList *dequeue(struct llq **queue){\n",
    "    struct linkedList *res = (*queue)->queueHead;\n",
    "    struct llq *oldQ = *queue;\n",
    "    \n",
    "    *queue = (*queue)->next;\n",
    "    /* Clean up memory we allocated. */\n",
    "    free(oldQ);\n",
    "    \n",
    "    return res;\n",
    "}\n",
    "\n",
    "/* merge.h */\n",
    "/* #include \"ll.h\" */\n",
    "/* Bottom-up sorts the given list, the original list may\n",
    "    be mangled in any way (and most likely will). */\n",
    "struct linkedList *mergeSort(struct linkedList *list);\n",
    "\n",
    "/* merge.c */\n",
    "/* #include \"ll.h\" */\n",
    "/* #include \"merge.h\" */\n",
    "struct linkedList *mergeSort(struct linkedList *list){\n",
    "    /* FILL IN SETUP FOR Linked List BOTTOM-UP mergesort */\n",
    "    \n",
    "    /* FILL IN loop */\n",
    "}\n",
    "\n",
    "/* main.c */\n",
    "#include <stdlib.h>\n",
    "#include <stdio.h>\n",
    "#include <time.h>\n",
    "\n",
    "/* 8 is a power of 2, so should be the least trouble. */\n",
    "/* Try 7 to have to deal with an empty list */\n",
    "#define SIZE 8\n",
    "\n",
    "int main(int argc, char **argv){\n",
    "    int inputs[SIZE];\n",
    "    int i;\n",
    "    \n",
    "    struct linkedList *list = NULL;\n",
    "    struct linkedList *current;\n",
    "    \n",
    "    /* Initialise random number generator. */\n",
    "    time_t t;\n",
    "    srand((unsigned) time(&t));\n",
    "    \n",
    "    printf(\"Original Array: \");\n",
    "    for(i = 0; i < SIZE; i++){\n",
    "        /* values between 0 and 99 are easier to read. */\n",
    "        inputs[i] = rand() % 100;\n",
    "        printf(\"%d \",inputs[i]);\n",
    "    }\n",
    "    \n",
    "    printf(\"\\n\");\n",
    "    \n",
    "    printf(\"Adding all inputs to linked list.\\n\");\n",
    "    for(i = 0; i < SIZE; i++){\n",
    "        list = prepend(list, inputs[i]);\n",
    "    }\n",
    "    \n",
    "    printf(\"Mergesorting.\\n\");\n",
    "    list = mergeSort(list);\n",
    "    printf(\"MergeSorted list: \");\n",
    "    current = list;\n",
    "    while(current){\n",
    "        printf(\"%d \",current->item);\n",
    "        current = current->next;\n",
    "    }\n",
    "    printf(\"\\n\");\n",
    "    \n",
    "    return 0;\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Programming 7.2** Write code for bottom-up mergesort where the data are contained in an initially unsorted *array*. You will have to construct an artificial array to test your code. You can populate your array with random numbers before sorting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/* merge.h */\n",
    "/* Bottom-up mergeSorts the given list. */\n",
    "int *mergeSort(int *list, int size);\n",
    "\n",
    "/* merge.c */\n",
    "#include <stdlib.h>\n",
    "#include <assert.h>\n",
    "int *mergeSort(int *list, int size){\n",
    "    /* FILL IN loop */\n",
    "}\n",
    "\n",
    "/* main.c */\n",
    "#include <stdlib.h>\n",
    "#include <stdio.h>\n",
    "#include <time.h>\n",
    "/* #include \"merge.h\" */\n",
    "\n",
    "/* 8 is a power of 2, so should be the least trouble. */\n",
    "/* Try 7 to have to deal with an empty list */\n",
    "#define SIZE 8\n",
    "\n",
    "int main(int argc, char **argv){\n",
    "    int list[SIZE];\n",
    "    int *sortedList;\n",
    "    int i;\n",
    "    \n",
    "    /* Initialise random number generator. */\n",
    "    time_t t;\n",
    "    srand((unsigned) time(&t));\n",
    "    \n",
    "    printf(\"Original Array: \");\n",
    "    for(i = 0; i < SIZE; i++){\n",
    "        /* values between 0 and 99 are easier to read. */\n",
    "        list[i] = rand() % 100;\n",
    "        printf(\"%d \",list[i]);\n",
    "    }\n",
    "    \n",
    "    printf(\"\\n\");\n",
    "    \n",
    "    printf(\"Mergesorting.\\n\");\n",
    "    sortedList = mergeSort(list, SIZE);\n",
    "    printf(\"MergeSorted list: \");\n",
    "    for(i = 0; i < SIZE; i++){\n",
    "        printf(\"%d \",sortedList[i]);\n",
    "    }\n",
    "    printf(\"\\n\");\n",
    "    \n",
    "    return 0;\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C",
   "language": "c",
   "name": "jupyter_c_kernel"
  },
  "language_info": {
   "file_extension": ".c",
   "mimetype": "text/plain",
   "name": "c"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}