quiz_04-.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q1\n",
    "\n",
    "A shapefile actually consists of three files with different extensions. Each of these contains different information about the objects that are in the file.\n",
    "\n",
    "Which file contains a dataset containing information about the shapes? Write the file extension (three letters, with or without the leading dot, e.g. \"txt\" or \".txt\").\n",
    "\n",
    "`.dbf`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q2\n",
    "Which of the following algorithms best matches the following description?\n",
    "\n",
    "`Given a set of points P and a number k, the algorithm separates the points into k different clusters. Each point from P is assigned a unique cluster.`\n",
    "\n",
    "Fun note: All these algorithms start with \"k\" and are related to spatial data processing :)\n",
    "\n",
    "`k-means`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q3\n",
    "\n",
    "The following code draws a map of Bulgaria:\n",
    "`\n",
    "sofia = {\"lat\": 42.6977, \"lng\": 23.3219}\n",
    "\n",
    "m = Basemap(projection = \"merc\", llcrnrlat = 41, llcrnrlon = 22, urcrnrlat = 44.5, urcrnrlon = 29, resolution = \"i\")\n",
    "m.drawcoastlines()\n",
    "m.drawcountries()\n",
    "x, y = m(???, ???)\n",
    "m.plot(x, y, \"o\")\n",
    "plt.show()\n",
    "`\n",
    "On it, we need to draw a dot where Sofia is, using the coordinates given in the variable sofia. To do this, we need to convert them to x and y coordinates.\n",
    "\n",
    "The function call contains two unknown parameters, replaced by ???. They both should reference the sofia dictionary.\n",
    "\n",
    "What is the value of the first parameter?\n",
    "`sofia[\"lng\"]`\n",
    "How about the second parameter?\n",
    "`sofia[\"lat\"]`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q4\n",
    "\n",
    "True or false?\n",
    "\n",
    "We can use Basemap to plot objects on any spherical surface, not only Earth's.\n",
    "\n",
    "`Yes, we can use Basemap to plot objects on any spherical surface.`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q5\n",
    "\n",
    "One famous graph in social network analysis is the \"Florentine families\" graph. It is implemented by default in networkx.\n",
    "\n",
    "Each node represents a family, each edge - a marital relationship (i.e. someone from family A married someone from family B). Since marriage is mutual (at least, it should be :D), the graph is undirected.\n",
    "\n",
    "You can load it and visualize it like this:\n",
    "`\n",
    "g = nx.florentine_families_graph()\n",
    "nx.draw(g, with_labels = True)\n",
    "`\n",
    "\n",
    "We will use this graph in the following questions.\n",
    "\n",
    "How many nodes does the shortest path from Pazzi to Peruzzi contain, including the starting and the final one?\n",
    "\n",
    "`nodes = nx.shortest_path(families_graph, \"Pazzi\", \"Peruzzi\")\n",
    "print(nodes)\n",
    "print(len(nodes))`\n",
    "\n",
    "`6 nodes`\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q6\n",
    "\n",
    "What is the name of the most important / famous family in this graph?\n",
    "\n",
    "`The most important node maybe is this one which is in combination with the most number of short paths. We can use betweenness centrality to find this one.`\n",
    "\n",
    "`Medici 0.521978021978022`\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Q7\n",
    "\n",
    "The most popular (and arguably, easiest to implement) algorithms in graphs involve traversing. The problem is stated like this: given a graph G and a starting node S, explore all nodes connected (directly or not) to S. The two most common ways of graph traversal are depth-first search (DFS) and breadth-first search (BFS). You can look them up on the internet.\n",
    "\n",
    "Let's now imagine another problem. The problem is finding a shortest path between two nodes. We already saw (many times) how it works. Let's state the problem more formally: given a graph G, a start node S, and an end node P, find a path from S to P which has minimal length (i.e. minimal number of edges).\n",
    "\n",
    "In networkx, the code will look like this: nx.shortest_path(G, S, P).\n",
    "\n",
    "We can solve this new problem by adapting one of the previous algorithms.\n",
    "\n",
    "Which traversal algorithm can we adapt to find a shortest path?\n",
    "\n",
    "`BFS`"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}