{ "cells": [ { "cell_type": "markdown", "id": "a016336c", "metadata": {}, "source": [ "NAME:" ] }, { "cell_type": "markdown", "id": "db477b79", "metadata": {}, "source": [ "<center>\n", " <h3>ASSIGNMENT#1 (Algorithms) - Nov. 27, 2023</h3>\n", "</center>\n", "\n", "Due date: **December 8th, 2023, 5pm** (no extension will be allowed).\n", "\n", "Submit your solution by email: romain.vuillemot@ec-lyon.fr\n", "\n", "You may work as a group (max 2) but all members are required to submit their solution and indicate their collaborator (if any).\n", "\n", "## Goal of this assignment\n", "\n", "In this assignment we provide you with a dataset of characters from a movie. Your role will be to answer the questions below programmatically, using Pyhon. **Please note you need to answer with fully working python code embedded in this notebook as solution (no external modules or files can be included).** You may then replace the code below with your answer for each question:\n", "\n", "```python\n", "# YOUR CODE HERE\n", "raise NotImplementedError()\n", "```\n", "\n", "## Grading\n", "\n", "- 20% for the results to the questions\n", "- 60% for the code quality\n", "- 20% for the notebook presentation\n", "- +10% bonus question\n", "\n", "## Getting started\n", "\n", "We provide you with a dataset containing movie characters. Each character is represented as a row, along with connections to other characters, based on the movie script. You will use those connections to create a graph-based data structure and answer the questions. \n", "\n", "To get you started with the dataset, we provide you with the code that loads it:" ] }, { "cell_type": "code", "execution_count": null, "id": "cf409997-537f-4f89-a039-c2b3494972f2", "metadata": { "tags": [] }, "outputs": [], "source": [ "data_file = 'users.csv'\n", "\n", "with open(data_file, 'r') as file:\n", " lines = file.readlines()\n", " data = [tuple(line.strip().split(',')) for line in lines[1:]]" ] }, { "cell_type": "markdown", "id": "c48b6391-d858-4a35-b428-b99434ee2d57", "metadata": { "tags": [] }, "source": [ "The `data` variable contains the list of characters. You may look at the `users.csv` file to grasp the values of this variable. Here is a sample:\n", "\n", "```\n", "[('Tony_Stark',\n", " '40',\n", " 'Male',\n", " '1.85',\n", " 'Steve_Rogers Natasha_Romanoff Bruce_Banner Thor_Odinson'),\n", " ('Steve_Rogers',\n", " '98',\n", " 'Male',\n", " '1.88',\n", " 'Tony_Stark Natasha_Romanoff Sam_Wilson Bucky_Barnes'),\n", "...\n", "```" ] }, { "cell_type": "markdown", "id": "70e93e78-f4dd-435f-b0f7-d56d928d7051", "metadata": {}, "source": [ "**Question 1 -** How many characters are there in the dataset?" ] }, { "cell_type": "code", "execution_count": null, "id": "9022b450-6fa6-41d0-999e-e019917cda79", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "6474e3afbe1bbdb5b06ce64fc0534c4f", "grade": false, "grade_id": "cell-f45150625899eb53", "locked": false, "schema_version": 3, "solution": true, "task": false }, "tags": [] }, "outputs": [], "source": [ "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "markdown", "id": "0a1a4c6c-f95c-4dc3-8bb3-863d1048ae79", "metadata": {}, "source": [ "**Question 2 -** Write a function that turns the `data` variable into a dictionnary data structure like the one below. You may then be able to plot it with the `plot_character_connections` function provided in the next cell:\n", "\n", "```\n", "{'Tony_Stark': ['Steve_Rogers', 'Natasha_Romanoff', 'Bruce_Banner', 'Thor_Odinson'], 'Steve_Rogers': ['Tony_Stark', 'Natasha_Romanoff', 'Sam_Wilson', 'Bucky_Barnes'],\n", "..\n", "```" ] }, { "cell_type": "code", "execution_count": null, "id": "7139b3cf-1c00-43bb-bc1b-67b4a8e2a92d", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "65a8683bbae1730e7882a91135df6dfa", "grade": false, "grade_id": "cell-2b24cbad2d825c82", "locked": false, "schema_version": 3, "solution": true, "task": false }, "tags": [] }, "outputs": [], "source": [ "adjacency_list = {}\n", "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "code", "execution_count": null, "id": "fbbdd57e-6895-4d3c-b561-406d5e6668a9", "metadata": { "tags": [] }, "outputs": [], "source": [ "# please run the cells below the \"Utils\" section first\n", "plot_character_connections(adjacency_list)" ] }, { "cell_type": "markdown", "id": "4a62b350-2bc8-476d-b9c6-13a08d649bdc", "metadata": {}, "source": [ "**Question 3 -** Is there a character self-connected to her/himself?" ] }, { "cell_type": "code", "execution_count": null, "id": "232f3d2a-8300-40c1-a908-ebfa5e380ae1", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "12487a86c6f58024a3ebbe0d242b5d48", "grade": false, "grade_id": "cell-641c5f735f36d3f6", "locked": false, "schema_version": 3, "solution": true, "task": false }, "tags": [] }, "outputs": [], "source": [ "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "markdown", "id": "b79c97bc-e7d5-4ff4-bb1c-5bdf1e3abae2", "metadata": {}, "source": [ "**Question 4 -** How many communities can you identify? We define a community as a sub-graph of connected people by a path (i.e. a connected component)." ] }, { "cell_type": "code", "execution_count": null, "id": "98186a3a-bd4c-4bf8-9ebd-2f350a83c856", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "dcfadd1483b4e91449dcd93f77e36868", "grade": false, "grade_id": "cell-7b6675c6e2784006", "locked": false, "schema_version": 3, "solution": true, "task": false }, "tags": [] }, "outputs": [], "source": [ "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "markdown", "id": "840a8875-2f71-4da9-bbe7-0f1aab5f612b", "metadata": {}, "source": [ "**Question 5 -** Are connections mutual in the graph?" ] }, { "cell_type": "code", "execution_count": null, "id": "12d15b4d-cf98-45aa-994c-e41070b9ea3a", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "90802fd6bde9d5da3b4577c3d86f9774", "grade": false, "grade_id": "cell-8875e1c325dd6853", "locked": false, "schema_version": 3, "solution": true, "task": false }, "tags": [] }, "outputs": [], "source": [ "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "markdown", "id": "5e1b0409-1dff-4d8b-a5d8-a1efa1c10125", "metadata": {}, "source": [ "**Question 6 (BONUS) -** Among the community of characters, is there a fully connected one? (i.e. where all characters are directly connected to the others)." ] }, { "cell_type": "code", "execution_count": null, "id": "d8a1900d-c15f-4ef4-83d8-1ecfbc8bfcf8", "metadata": { "deletable": false, "nbgrader": { "cell_type": "code", "checksum": "8a0cd9235224e442fb7dfe36544029cf", "grade": false, "grade_id": "cell-777cc851157e530d", "locked": false, "schema_version": 3, "solution": true, "task": false }, "tags": [] }, "outputs": [], "source": [ "# YOUR CODE HERE\n", "raise NotImplementedError()" ] }, { "cell_type": "markdown", "id": "00c753ed-0905-4132-b276-4b415ba31408", "metadata": {}, "source": [ "## Utils" ] }, { "cell_type": "code", "execution_count": null, "id": "d9f71538-98b6-4730-adc1-7ca84aa3748e", "metadata": { "tags": [] }, "outputs": [], "source": [ "import networkx as nx\n", "import matplotlib.pyplot as plt\n", "\n", "def plot_character_connections(adjacency_list):\n", " G = nx.DiGraph()\n", " for character, connections in adjacency_list.items():\n", " G.add_node(character)\n", " for connection in connections:\n", " G.add_edge(character, connection)\n", "\n", " plt.figure(figsize=(12, 8))\n", " pos = nx.spring_layout(G, seed=42)\n", "\n", " nx.draw(\n", " G,\n", " pos,\n", " with_labels=True,\n", " node_size=500,\n", " node_color='skyblue',\n", " font_weight='bold',\n", " font_size=10\n", " )\n", " plt.title('Movie characters')\n", " plt.show()" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.10.9" } }, "nbformat": 4, "nbformat_minor": 5 }