Lab/Solutions_NAME_SURNAME.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 1\n",
    "\n",
    "---\n",
    "### Exercise: Selection Sort\n",
    "Write the function ```SelectionSort(coll)``` that returns a sorted list with the elements in *coll*. \n",
    "You have to implements Selection Sort algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Exercise: Insertion Sort\n",
    "Write the function ```InsertionSort(coll)``` that returns a sorted list with the elements in *coll*. \n",
    "You have to implements Insertion Sort algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Exercise: Strange orderings\n",
    "Given a list, write and test comparators to obtain the following orderings:\n",
    "- Even number precede odd ones. Even numbers are sorted in non-decreasing  order while odd ones are sorted in non-increasing order.\n",
    "- Strings are sorted in non-increasing order based on their lengths. Strings having the same length are sorted in non-increasing lexicographic order. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "### Exercise: Insertion Sort with a comparator\n",
    "Write the function ```InsertionSort(coll, cmp)``` that returns a sorted list with the elements in *coll* using \n",
    "```cmp```as a comparator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "\n",
    "### Exercise: Intersection of two lists\n",
    "Write a function ```intersection_slow(l1, l2)``` which returns the intersection of the two lists l1 and l2.\n",
    "\n",
    "Use the trivial algorithms that runs in $\\Theta(|l1|\\times|l2|)$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Exercise: Faster intersection of two lists\n",
    "Write a function ```intersection(l1, l2)``` which returns the intersection of the two lists l1 and l2.\n",
    "\n",
    "Assume that both l1 and l2 are sorted!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Exercise: You own search engine\n",
    "You are given a collection of texts and you want to build your own search engine, people at Google are already very scared!\n",
    "\n",
    "Modern search engines are based on a data structure called *Inverted Index*. \n",
    "\n",
    "Each document of the collection is assigned an identifier, starting from 0.\n",
    "An inverted index stores a list, called *inverted list*, for each term of the collection.\n",
    "The list for a term *t* contains the identifiers of all the documents containing term *t*. The list is sorted.\n",
    "\n",
    "For example,\n",
    "\n",
    "````\n",
    "C = [\"dog cat elephant monkey\",  \"dog lion tiger\", \"fish dog dog cat cow\"]\n",
    "\n",
    "````\n",
    "\n",
    "The list of term *cat* is [0,2], the list of *elephant* is [0].\n",
    "\n",
    "Given two terms, an AND query reports all the documents containing both terms. For example, \n",
    "*query(\"cat\", \"dog\"), the result is [0, 2].\n",
    "\n",
    "You goal is to implement a simple search engine. Do the following. \n",
    "\n",
    "- Given the collection, build a dictionary that maps each term to its inverted list. Observe that \n",
    "each document occurs at most once in each list. \n",
    "- Implement a function *query* which answers an AND query. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "# Lecture 2\n",
    "---\n",
    "### Exercise: Binary Vector\n",
    "You are given a binary vector, i.e., each element is either 0 or 1. Implements an easy variant of partition to sort the vector.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "---\n",
    "### Exercise: QuickSort\n",
    "Below an implementation of QuickSort. \n",
    "\n",
    "In this exercise you have to:\n",
    "- Write detailed comments to describe crucial parts of the code below (to prove you have understand it)\n",
    "- Implement a random selection of the pivot element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Exercise: Merge Sort\n",
    "Complete the implementation of Merge Sort by implementing function ```merge()```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "# Lecture 3\n",
    "----\n",
    "### Exercise: Activity Selection Problem\n",
    "Activity selection problem is a problem in which a person has a list of works to do. \n",
    "\n",
    "Each of the activities has a starting time and ending time. \n",
    "\n",
    "We need to schedule the activities in such a way the person can complete a maximum number of activities. \n",
    "\n",
    "Since the timing of the activities  may overlap, so it might not be possible to complete all the activities and thus we need to schedule the activities in such a way that the maximum number of activities can be finished."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Exercise: Fractional Knapsack Problem\n",
    "\n",
    "Your goal: Write a function fractional_knapsack(L,W) which takes a list L of pairs (value, weight) and the capacity  𝑊  and returns maximum possible value we can obtain by selecting items."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "# Lecture 4\n",
    "\n",
    "----\n",
    "\n",
    "### Exercise: K-largest elements of a array\n",
    "\n",
    "We want to compute the K-largest elements of a array A. \n",
    "\n",
    "There are three possible algorithms to solve this problem:\n",
    "\n",
    "\n",
    "#### Algorithm 1: Sorting\n",
    "The easiest way to solve this is by sorting the array in decreasing order and reporting the first K elements. \n",
    "\n",
    "This algorithm costs $\\Theta(n\\log n)$ time. \n",
    "\n",
    "Implement this algorithm in a function ```k_largest_sort(A, K)```and test its correctness.\n",
    "\n",
    "#### Algorithm 2: QuickSelect\n",
    "Implement the QuickSelect algorithm and use it to find the K-largest element E in the array A. Then, scan A again \n",
    "to collect the K elements larger than or equal to E. Finally, sort the collected elements.\n",
    "\n",
    "This algorithm costs $\\Theta(n + K\\log K)$ time (in expectation). \n",
    "\n",
    "Implement this algorithm in a function ```k_largest_quickselect(A, K)```and test its correctness.\n",
    "\n",
    "\n",
    "#### Algorithm 3: Heap\n",
    "You have to implement the following faster algorithm as a function ```k_largest(A,K)```.\n",
    "- Scan the array from left to right and keep a min-heap. The min-heap will contain at most K elements.\n",
    "- Insert the current element into the heap, if the heap has less than K elements or the current element is larger than the minimum in the heap. If the heap has more than K elements, remove the minimum. \n",
    "- Sort the collected elements.\n",
    "\n",
    "This algorithm runs in $\\Theta(n\\log K)$ time.\n",
    "\n",
    "Implement this algorithm in a function ```k_largest_heap(A, K)```and test its correctness."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Algorithm 1 goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Algorithm 2 goes here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Algorithm 3 goes here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "---\n",
    "\n",
    "### Exercise: compute distinct elements\n",
    "You are given a list A of elements and you want to obtain the list of distict elements in A.\n",
    "\n",
    "There are two possible algorithms to do this:\n",
    "\n",
    "- Use ```list(set(A))```\n",
    "- Sort A and then scan. Implement this as a function ```distinct(A)``` \n",
    "\n",
    "Compare these two approaches by varying the size of the array and the number of distinct elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "\n",
    "### Exercise: Pareto frontier of a set of points in 2-D space (aka Skyline problem)\n",
    "We are given a set $S$ of $n$ 2D points.\n",
    "A point $(x,y)$ dominates a point $(x',y')$ iff $𝑥'\\leq 𝑥$ and $y'\\leq 𝑦$. \n",
    "Our goal is to find the set $P$ of dominating points in $S$. \n",
    "This corresponds to find the Pareto frontier (or, equivalently, the skyline). \n",
    "\n",
    "The problem can be solved in $\\Theta(n\\log n)$ time.\n",
    "\n",
    "To find $P$ we need to sort points in $S$ by $x$ in descending order, \n",
    "and if $x$′𝑠 the same by $y$ in descending order. This takes $\\Theta(n\\log n)$ time. \n",
    "Then, we do the following.\n",
    "\n",
    "- Include first point in $P$ and remember this point as $𝑇$. \n",
    "- Iterates through the point (let $C$ current point):\n",
    "* if $C$ is dominated by $T$, then skip $C$ and go to next point;\n",
    "* Otherwise, include $C$ in $P$ and set $𝑇=𝐶$.\n",
    "\n",
    "This step can be performed in linear time.\n",
    "\n",
    "Implement the function ```pareto_frontier(S)```, which returns the pareto frontier $P$ of the points in $S$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "# Lecture 5\n",
    "----\n",
    "\n",
    "### Exercise: Open Addressing with linear probing\n",
    "Complete the implementation below by implementing ```Lookup```and ```Delete```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Exercise: Hashing with Chains\n",
    "Complete the implementation below by implementing ```Lookup``` and ```Delete```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "### Exercise: Dictionary\n",
    "Modify the previous code (i.e., Hashing with Chains) to implement a dictionary, i.e., store a value together with each key. \n",
    "You need to implement methods:\n",
    "- ```Insert(key, value)```: insert the key with its value. If the key was already present, change its value;\n",
    "- ```Delete(key)```: remove the key;\n",
    "- ```Lookup(key)```: return True if the key is present, False otherwise;\n",
    "- ```Value(key)```: return the value associated with the key. It returns None, if the key is not present.\n",
    "\n",
    "I suggest to store pairs (key, value) within the lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Lecture 6\n",
    "\n",
    "--- \n",
    "### Exercise: Implements your own GroupBy\n",
    "\n",
    "In the rest of your life you are going to use GroupBy implemented in some library, but in this exercise we will implement our own simplified version. \n",
    "\n",
    "You are give a list of tuples, all with the same number of components. In our simplified implementation  of a pandas' DataFrame each tuple in the list is a row of the DataFrame. Each component of a tuple is a value of a column.\n",
    "\n",
    "#### Part I\n",
    "Our first goal is to implement an index to efficiently group by one of the component in the list. \n",
    "\n",
    "We'd like to implement a function ```groupBy(L, id)``` which takes the list of tuples ```L``` and the ```id``` of the component and returns a dictionary. The dictionary is an index very similar to what you implemented for a search engine. \n",
    "We have a key for each distinct value in column ```id```. The value of a certain key ```k``` is the list of indexes of all the tuple having value ```k``` in the column ```id```.\n",
    "This means that, if index ```p``` is in the list of key ```k```, then ```L[p][id] = k```.\n",
    "\n",
    "For example it we have tuples \n",
    "\n",
    "|   | \n",
    "|:-|\n",
    "(1, 5, 11)\n",
    "(0, 4, 1000)\n",
    "(1, 2, 11)\n",
    "(1, 4, 66) \n",
    "(0, 3, 99)\n",
    "\n",
    "The groupBy with id=0 will group by first column.\n",
    "\n",
    "The index is\n",
    "\n",
    "|   | \n",
    "|:--| \n",
    "0: [1, 4]\n",
    "1: [0, 2, 3]\n",
    " \n",
    "#### Part II\n",
    "We'd like to implement a function ```max_groupBy(index, L)``` which takes the index built in previous part on list ```L``` and returns a dictionary. \n",
    "We have a key for each distinct value in column ```id```. The value of a certain key ```k``` is the list. The list has a element for each column: the maximum value in that column for each tuple having value ```k``` in the column ```id```. This, of course, must be implemented by using the index.\n",
    "\n",
    "In the example before, we would obtain the dictionary\n",
    "\n",
    "|   | \n",
    "|:--| \n",
    "0: [0, 4, 1000]\n",
    "1: [1, 5, 66]\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Lecture 7\n",
    "---\n",
    "### Exercise: Static sorted map\n",
    "Complete and test the implementation below. You have to use binary search to solve predecessor and successor queries on a sorted array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### Exercise: Binary Search Tree\n",
    "Extend the previous implementation of Binary Search Trees to support **search(x)** operation. Test your implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Lecture 8\n",
    "---\n",
    "### Exercise: Strongly Connected Components\n",
    "The goal of this exercise is to implement the following algorithm to compute the strongly connected components of a directed graph $G$. [See here](https://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/tutorial/). \n",
    "\n",
    "In a directed graph a component is strongly connected if there is a directed path from any vertex to every other vertex of the component. The problem asks to is to partition the graph into maximal strongly connected components.\n",
    "\n",
    "NetworkX provides a method to compute the strongly connected components of a graph [here](https://networkx.github.io/documentation/stable/reference/algorithms/generated/networkx.algorithms.components.strongly_connected_components.html#networkx.algorithms.components.strongly_connected_components). \n",
    "\n",
    "Your goal is to implement the Kosaraju's Linear time algorithm to find Strongly Connected Component. \n",
    "The algorithm is described [here](https://www.hackerearth.com/practice/algorithms/graphs/strongly-connected-components/tutorial).\n",
    "\n",
    "It works in three steps. \n",
    "\n",
    "- Do a DFS on the original graph, keeping track of the DFS finish times of each node. This can be done with a stack, when some  finishes put the source vertex on the stack. This way node with highest finishing time will be on top of the stack.\n",
    "- Reverse the original graph, i.e., if there is an edge $(u,v)$ in the original graph, add the edge $(v,u)$ in the reversed one.\n",
    "-  Do DFS on the reversed graph, with the source vertex as the vertex on top of the stack. When DFS finishes, all nodes visited will form one Strongly Connected Component. If any more nodes remain unvisited, this means there are more Strongly Connected Component's, so pop vertices from top of the stack until a valid unvisited node is found. This will have the highest finishing time of all currently unvisited nodes.\n",
    "\n",
    "Take a look at [DFS traversal documentation](https://networkx.github.io/documentation/stable/reference/algorithms/traversal.html#module-networkx.algorithms.traversal.depth_first_search).\n",
    "Note that the finishing time of a node can be inferred from its position in the DFS tree. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Your implementation here!!!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}