{"cells":[{"cell_type":"markdown","metadata":{"id":"SgZXAO7BmQMX"},"source":["# Python Reminders\n","\n","\n","I assume that you all know Python. A brief introduction to Python Basics can be found in this notebook from last year (ipynb, html). Here we will only review some useful concepts"]},{"cell_type":"markdown","source":["A **Python List** is a versatile, ordered collection of items created using **square brackets `[]`**. It's one of Python's most powerful data structures because of three core features:\n","\n","1. **Mutable (Dynamic Change):** Lists are **changeable**. You can dynamically **add, remove, or modify** items *after* the list is created, allowing its contents to change during program execution.\n","2. **Iterable (Loopable):** Lists are **ordered** and **sequence**-based, meaning you can easily **traverse** (loop through) every item, one by one, typically using a `for` loop.\n","3. **Heterogeneous (Mixed Types):** A single list can hold items of **different data types** (numbers, strings, booleans, etc.) simultaneously."],"metadata":{"id":"x-HRPvZKbqx3"}},{"cell_type":"markdown","source":[""],"metadata":{"id":"VK8RsWULb8U3"}},{"cell_type":"markdown","metadata":{"id":"smIHwHqemQMa"},"source":["### List Comprehension\n","\n","Recall the mathematical notation:\n","\n","$$L_1 = \\left\\{x^2 : x \\in \\{0,1,\\ldots ,9\\}\\right\\}$$\n","\n","$$L_2 = \\left(1, 2, 4, 8,\\ldots, 2^{12}\\right)$$"]},{"cell_type":"code","execution_count":1,"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"sa0VxykwmQMa","executionInfo":{"status":"ok","timestamp":1760627847905,"user_tz":-180,"elapsed":79,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}},"outputId":"3ff8b83a-fbcd-47ed-adc3-1628ef885b90"},"outputs":[{"output_type":"stream","name":"stdout","text":["[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]\n"]}],"source":["L12 = []\n","for x in range(10):\n"," L12.append(x**2)\n","print(L12)"]},{"cell_type":"code","execution_count":2,"metadata":{"id":"TBTnjJjCmQMc","outputId":"cc809592-7c50-4307-d284-9ba8b5c0d7ec","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760627849801,"user_tz":-180,"elapsed":47,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["L1 = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]\n","L2 = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]\n"]}],"source":["L1 = [x**2 for x in range(10)]\n","L2 = [2**i for i in range(13)]\n","print(f\"L1 = {L1}\")\n","print(f\"L2 = {L2}\")"]},{"cell_type":"markdown","metadata":{"id":"fS3xptuimQMd"},"source":["List comprehension with conditions\n","\n","$$M = \\left\\{x \\mid x \\in L_1 \\text{ if } x \\text{ is even}\\right\\}$$"]},{"cell_type":"code","execution_count":4,"metadata":{"id":"JNbeLOpamQMd","outputId":"094df8f4-4482-4fd5-c1a3-b1edfa8f4f5b","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760627879365,"user_tz":-180,"elapsed":49,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["L3 = [0, 4, 16, 36, 64]\n"]}],"source":["L3 = [x for x in L1 if x % 2 == 0]\n","print(f\"L3 = {L3}\")"]},{"cell_type":"markdown","metadata":{"id":"4xE8XkqGmQMe"},"source":["Nested use of link comprehension"]},{"cell_type":"code","execution_count":5,"metadata":{"id":"GlMdo6fjmQMf","outputId":"b3a935c4-eaea-4477-d500-411b71e86a04","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760627882868,"user_tz":-180,"elapsed":85,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"execute_result","data":{"text/plain":["[0, 4, 16, 36, 64]"]},"metadata":{},"execution_count":5}],"source":["[x for x in [x**2 for x in range(10)] if x % 2 == 0]"]},{"cell_type":"markdown","metadata":{"id":"jyTQnwyvmQMf"},"source":["Use of list comprehension for string processing"]},{"cell_type":"code","execution_count":6,"metadata":{"id":"akE1giAtmQMg","outputId":"e50d876f-cde5-44b1-a6c8-0a383402add8","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760627900752,"user_tz":-180,"elapsed":57,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["['The', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog']\n"]}],"source":["words = 'The quick brown fox jumps over the lazy dog'.split()\n","print(words)"]},{"cell_type":"code","source":["upper = [w.upper() for w in words]\n","print(upper)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"CpMpLalgMijV","executionInfo":{"status":"ok","timestamp":1760627947213,"user_tz":-180,"elapsed":52,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}},"outputId":"18dfc34d-d33b-4f6b-e75e-d620c577dcb8"},"execution_count":7,"outputs":[{"output_type":"stream","name":"stdout","text":["['THE', 'QUICK', 'BROWN', 'FOX', 'JUMPS', 'OVER', 'THE', 'LAZY', 'DOG']\n"]}]},{"cell_type":"code","source":["upper_lower = [[w.upper(), w.lower()] for w in words]\n","print(upper_lower)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"85ctcPDuMkQH","executionInfo":{"status":"ok","timestamp":1760627985777,"user_tz":-180,"elapsed":53,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}},"outputId":"13294a60-dfba-4e49-dcb2-fba49c794228"},"execution_count":8,"outputs":[{"output_type":"stream","name":"stdout","text":["[['THE', 'the'], ['QUICK', 'quick'], ['BROWN', 'brown'], ['FOX', 'fox'], ['JUMPS', 'jumps'], ['OVER', 'over'], ['THE', 'the'], ['LAZY', 'lazy'], ['DOG', 'dog']]\n"]}]},{"cell_type":"code","source":["long_words = [x for x in words if len(x) > 3]\n","print(long_words)"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"GFGHSWfdMmNH","executionInfo":{"status":"ok","timestamp":1760628022569,"user_tz":-180,"elapsed":75,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}},"outputId":"90e438e1-90c6-4a82-e679-ef0f91d93220"},"execution_count":9,"outputs":[{"output_type":"stream","name":"stdout","text":["['quick', 'brown', 'jumps', 'over', 'lazy']\n"]}]},{"cell_type":"markdown","metadata":{"id":"MQeiMnIgmQMg"},"source":["Use list comprehension for obtaining input"]},{"cell_type":"code","execution_count":10,"metadata":{"id":"zlPJhjsPmQMh","outputId":"0f4fe156-b6b2-4967-dc9a-4bb5c261a54f","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760628159915,"user_tz":-180,"elapsed":46220,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["Give numbers separated by comma: 1,2,3,4\n","[1, 2, 3, 4]\n"]}],"source":["s = input('Give numbers separated by comma: ')\n","x = [int(n) for n in s.split(',')]\n","print(x)"]},{"cell_type":"markdown","metadata":{"id":"tbi-XyjemQMh"},"source":["**Creating vectors and matrices**"]},{"cell_type":"markdown","metadata":{"id":"i2cv2L5imQMi"},"source":["Create a vector of 10 zeros\n"]},{"cell_type":"code","execution_count":11,"metadata":{"id":"u8xiedsFmQMi","outputId":"9d3f67c6-9a27-456c-d08d-57dc7772f247","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760628185329,"user_tz":-180,"elapsed":62,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n"]}],"source":["z = [0 for i in range(10)]\n","print(z)"]},{"cell_type":"markdown","metadata":{"id":"lNAsNmAOmQMj"},"source":["#### Create a 10x10 matrix with all 0s"]},{"cell_type":"code","execution_count":12,"metadata":{"id":"WPmC-OdZmQMj","outputId":"237a8f3c-3ddf-4321-8a6e-224a82aae859","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760628205961,"user_tz":-180,"elapsed":59,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"execute_result","data":{"text/plain":["[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]"]},"metadata":{},"execution_count":12}],"source":["M = [[0 for i in range(10)] for j in range(10)]\n","M"]},{"cell_type":"markdown","metadata":{"id":"ehntB-jxmQMj"},"source":["Set the diagonal to 1"]},{"cell_type":"code","execution_count":13,"metadata":{"id":"AUozxORDmQMk","outputId":"926efc6a-ca52-43dc-fea4-797167557bd7","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760628571775,"user_tz":-180,"elapsed":61,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"execute_result","data":{"text/plain":["[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 1, 0, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 1, 0, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 1, 0, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 1, 0, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 1, 0, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 1, 0],\n"," [0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]"]},"metadata":{},"execution_count":13}],"source":["for i in range(10): M[i][i] = 1\n","M"]},{"cell_type":"markdown","metadata":{"id":"lFfwHIlomQMk"},"source":["Create a list of 10 random integers in [0,99]"]},{"cell_type":"code","execution_count":17,"metadata":{"id":"MyDk-U9dmQMl","outputId":"d9e8995d-cd95-49a7-f687-6108a6e355be","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760628658357,"user_tz":-180,"elapsed":89,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["[87, 75, 57, 69, 62, 63, 8, 15, 32, 10]\n"]}],"source":["import random\n","R = [random.choice(range(100)) for i in range(10)]\n","print(R)"]},{"cell_type":"markdown","source":["Question: By default which distribution does random.choice chooses? (remember from last lesson in statistics)"],"metadata":{"id":"ezj4pniFcilt"}},{"cell_type":"markdown","metadata":{"id":"uapesp6DmQMl"},"source":["**Removing elements from a list**"]},{"cell_type":"markdown","metadata":{"id":"mcJ6wCTHmQMl"},"source":["Removing elements from a list while you iterate through it can lead to problems..."]},{"cell_type":"code","execution_count":19,"metadata":{"id":"Iw4aKeZ2mQMl","outputId":"a68dbcae-ff9b-44ef-8b30-8fd13e81fd42","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760628842554,"user_tz":-180,"elapsed":17,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["[1, 4, 5, 8]\n"]}],"source":["L = [1,2,4,5,6,8]\n","for x in L:\n"," if x%2 == 0:\n"," L.remove(x)\n","print(L)"]},{"cell_type":"markdown","metadata":{"id":"0RWVmharmQMm"},"source":["Another way to do this using list comprehension:\n","\n","We can create a **new** list with the entries we want to keep"]},{"cell_type":"code","execution_count":20,"metadata":{"id":"Op3cZI37mQMm","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629184033,"user_tz":-180,"elapsed":55,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}},"outputId":"c72f6ec7-9563-4a85-ca10-b28401f6e7aa"},"outputs":[{"output_type":"stream","name":"stdout","text":["[1, 5]\n"]}],"source":["L = [1,2,4,5,6,8]\n","L = [x for x in L if x%2 == 1] #creates a NEW list\n","print(L)"]},{"cell_type":"markdown","metadata":{"id":"v48KPpTxmQMm"},"source":["Or create a list with the entries we want to remove"]},{"cell_type":"code","execution_count":22,"metadata":{"id":"mjeyAYLKmQMn","outputId":"d9bd873c-20c0-416f-fe00-83b81c74114b","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629237670,"user_tz":-180,"elapsed":51,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["[1, 5]\n"]}],"source":["L = [1,2,4,5,6,8]\n","R = [y for y in L if y%2 == 0] # R = [2,4,6,8]\n","for x in R: L.remove(x)\n","print(L)"]},{"cell_type":"markdown","metadata":{"id":"0hCjQAZzmQMn"},"source":["Using a **Dictionary** in the list comprehension"]},{"cell_type":"markdown","source":[""],"metadata":{"id":"8qdJLmJBM8od"}},{"cell_type":"code","execution_count":24,"metadata":{"id":"VueHAAqcmQMo","outputId":"11eee868-5dee-4279-be8b-3b47b0d16a92","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629387168,"user_tz":-180,"elapsed":21,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["['B', 'C']\n"]}],"source":["D = {'A':1,'B':5,'C':4,'D':2}\n","print([x for x in D if D[x]>2])"]},{"cell_type":"markdown","metadata":{"id":"wsG-hRremQMo"},"source":["### Dicitonary Comprehension\n","\n","We can create dictionaries in a similar way as with list comprehension"]},{"cell_type":"code","execution_count":25,"metadata":{"id":"Q4xDW_EDmQMo","outputId":"602b2c27-5702-429a-b90e-43a89797e772","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629442800,"user_tz":-180,"elapsed":124,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"execute_result","data":{"text/plain":["{'1': 1, '2': 2, '3': 3, '4': 4, '5': 5}"]},"metadata":{},"execution_count":25}],"source":["{str(i):i for i in [1,2,3,4,5]}"]},{"cell_type":"code","execution_count":26,"metadata":{"id":"nRgF6nfmmQMp","outputId":"b3833242-6a53-41b1-9e72-3f1f4f1b32c0","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629457676,"user_tz":-180,"elapsed":23,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"execute_result","data":{"text/plain":["{'apple': 5, 'mango': 5, 'banana': 6, 'cherry': 6}"]},"metadata":{},"execution_count":26}],"source":["fruits = ['apple', 'mango', 'banana','cherry']\n","fl = {f:len(f) for f in fruits}\n","fl"]},{"cell_type":"code","execution_count":27,"metadata":{"id":"paMoYIMJmQMp","outputId":"95b8e10f-3d92-432b-ce7d-eb2e4a025903","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629505224,"user_tz":-180,"elapsed":54,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["{'Apple': 0, 'Mango': 1, 'Banana': 2, 'Cherry': 3}\n"]}],"source":["f_dict = {f.capitalize():i for i,f in enumerate(fruits)}\n","print(f_dict)"]},{"cell_type":"code","execution_count":28,"metadata":{"id":"k488XtKVmQMp","outputId":"0e1294e0-ec02-4e6c-9eac-a1cb2a85ef4f","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629597105,"user_tz":-180,"elapsed":31,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"execute_result","data":{"text/plain":["{0: 'Apple', 1: 'Mango', 2: 'Banana', 3: 'Cherry'}"]},"metadata":{},"execution_count":28}],"source":["{v:k for k,v in f_dict.items()}"]},{"cell_type":"code","execution_count":29,"metadata":{"id":"D0CRzBVgmQMq","outputId":"69330519-b48e-41f6-83a4-3281222e3c79","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629631047,"user_tz":-180,"elapsed":38,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["{0: 'Apple', 1: 'Mango', 2: 'Banana', 3: 'Cherry'}\n"]}],"source":["f_dict2 = {i:f.capitalize() for i,f in enumerate(fruits)}\n","print(f_dict2)"]},{"cell_type":"markdown","metadata":{"id":"00hK8oYFmQMq"},"source":["### Using the right data structure\n","\n","Using the right data structure makes a big difference when handling large data. Dictionaries and sets have expected constant time for finding an element, while lists have linear complexity. Even logarithmic time is significantly faster than linear."]},{"cell_type":"markdown","metadata":{"id":"mWF73XPvmQMq"},"source":["**Example**\n","\n","Looking for 100K integers in a collection of 100K integers"]},{"cell_type":"code","execution_count":30,"metadata":{"id":"2Tgkb7F2mQMr","executionInfo":{"status":"ok","timestamp":1760629665314,"user_tz":-180,"elapsed":133,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[],"source":["import time\n","import random\n","L = [random.choice(range(10000000)) for i in range(100000)] # the integers we are searching in a list\n","S = set(L) # and in a set\n","Q = [random.choice(range(10000000)) for i in range(100000)] # the list of integers we will look up (queries)"]},{"cell_type":"code","execution_count":31,"metadata":{"id":"8uaoyFKTmQMr","outputId":"a628def0-1035-42b1-89e2-5c4ec6a3c2fd","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629745584,"user_tz":-180,"elapsed":99,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["0.015481948852539062\n"]}],"source":["#Searching the set\n","start = time.time()\n","[x for x in Q if x in S]\n","end = time.time()\n","print(end-start)"]},{"cell_type":"code","execution_count":32,"metadata":{"id":"-kE83tHhmQMr","outputId":"fa20bdee-57ed-4a7b-d64c-69c1bce86a76","colab":{"base_uri":"https://localhost:8080/","height":211},"executionInfo":{"status":"error","timestamp":1760629795854,"user_tz":-180,"elapsed":18919,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"error","ename":"KeyboardInterrupt","evalue":"","traceback":["\u001b[0;31m---------------------------------------------------------------------------\u001b[0m","\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)","\u001b[0;32m/tmp/ipython-input-2079384362.py\u001b[0m in \u001b[0;36m| \u001b[0;34m()\u001b[0m\n\u001b[1;32m 1\u001b[0m \u001b[0;31m#Searching the list\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[0mstart\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtime\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0;34m[\u001b[0m\u001b[0mx\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mQ\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mx\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mL\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;31m# The ONLY change now is L instead of S\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 4\u001b[0m \u001b[0mend\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtime\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 5\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mend\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mstart\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n","\u001b[0;31mKeyboardInterrupt\u001b[0m: "]}],"source":["#Searching the list\n","start = time.time()\n","[x for x in Q if x in L] # The ONLY change now is L instead of S\n","end = time.time()\n","print(end - start)"]},{"cell_type":"markdown","metadata":{"id":"OF7jm89ImQMs"},"source":["**Example**\n","\n","You are given a graph in the form of a collection of edges, that is, pairs of vertices\n","\n","How do you store it in order to be able to quickly answer if there is an edge (x,y) in the graph, and also to get all the neighbors of node?"]},{"cell_type":"markdown","metadata":{"id":"AOJ69t9umQMs"},"source":["Create a dictionary with nodes as the keys, and sets with neighboring nodes as values"]},{"cell_type":"code","execution_count":33,"metadata":{"id":"jHtzLGWTmQMs","outputId":"c9d13463-aa02-4359-e940-849a120f0866","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629926719,"user_tz":-180,"elapsed":64,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"execute_result","data":{"text/plain":["{1: {2},\n"," 2: {1, 3, 5, 6, 7},\n"," 3: {2, 4, 5},\n"," 5: {2, 3, 6, 7},\n"," 6: {2, 5},\n"," 7: {2, 5, 8},\n"," 4: {3},\n"," 8: {7, 9, 10},\n"," 9: {8},\n"," 10: {8}}"]},"metadata":{},"execution_count":33}],"source":["E = [(1,2),(2,3),(2,5),(2,6),(2,7),(3,4),(3,5),(5,6),(5,7),(7,8),(8,9),(8,10)]\n","G = {}\n","for (x,y) in E:\n"," if x not in G:\n"," G[x] = set()\n"," if y not in G:\n"," G[y] = set()\n"," G[x].add(y)\n"," G[y].add(x)\n","G"]},{"cell_type":"markdown","source":["This code builds an **Adjacency List** to represent an **undirected graph**.\n","\n","It converts the simple list of connections ($E$) into a dictionary ($G$) that shows the neighbors for every node:\n","\n","1. **Input ($E$)**: A list of **edges** (connections), like `(x, y)`.\n","2. **Output ($G$)**: The **Adjacency List** dictionary.\n"," * **Keys** are the graph **nodes** (vertices).\n"," * **Values** are **sets** of that node's **neighbors**.\n","\n","The loop ensures that for every connection $(x, y)$, both $y$ is added to $x$'s neighbors and $x$ is added to $y$'s neighbors, making the graph **undirected**."],"metadata":{"id":"xYksofwjhS9a"}},{"cell_type":"code","execution_count":34,"metadata":{"id":"B7_cDHQ1mQMs","outputId":"a8eb3ffc-cd18-4b26-d895-d5fa9dae904b","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760629997611,"user_tz":-180,"elapsed":57,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"execute_result","data":{"text/plain":["{1, 3, 5, 6, 7}"]},"metadata":{},"execution_count":34}],"source":["G[2]"]},{"cell_type":"markdown","metadata":{"id":"qD8rv64MmQMs"},"source":["## The Random library\n","\n","We will often need to work with randomness. A library for this that is part of the main Python distribution is the [random library](https://docs.python.org/3/library/random.html).\n","\n","Useful functions:\n","1. seed: Allows you to repeat the same random choices in different experiments\n","2. random: produces a random real number between 0 and 1\n","3. randint: select int for a range\n","4. choice: select an element from a list\n","5. choices: select k elements form a list with replacement. It is possible to use weights\n","6. shuffle: suffle a list of elements\n","7. sample: sample k elements from a list\n"]},{"cell_type":"markdown","metadata":{"id":"cQRzvEWlmQMt"},"source":["### Example\n","\n","How do I implement the following?\n","\n","With probability 0.7 print 'A', with probability 0.2 print 'B', and with probability 0.1 do nothing."]},{"cell_type":"code","execution_count":47,"metadata":{"id":"NoOvl6XbmQMt","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760630066086,"user_tz":-180,"elapsed":19,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}},"outputId":"4601691b-8423-4e2b-d964-f24e5f0e3a1f"},"outputs":[{"output_type":"stream","name":"stdout","text":["A\n"]}],"source":["import random\n","p = random.random()\n","if p <0.7: print('A')\n","elif p < 0.9: print('B')"]},{"cell_type":"markdown","metadata":{"id":"cJnrqUPDmQMt"},"source":["### Example\n","\n","From a list I want to sample k elements where k is a parameter. I want my samples for the different k's to have the property that smaller samples are subsets of bigger samples. That is, the sample of size k+1 will contain one more random element to the sample of size k."]},{"cell_type":"code","execution_count":49,"metadata":{"id":"dsFMQknWmQMt","executionInfo":{"status":"ok","timestamp":1760630086183,"user_tz":-180,"elapsed":12,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[],"source":["L = [i for i in range(20)]\n","random.shuffle(L)\n","sample4 = L[:4]\n","sample5 = L[:5]"]},{"cell_type":"code","execution_count":50,"metadata":{"id":"FzZCeSssmQMt","outputId":"feda9fd9-3ed7-4b3e-b43f-4e9e3ece809e","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1760630087597,"user_tz":-180,"elapsed":22,"user":{"displayName":"ΝΙΚΟΛΑΟΣ ΘΕΟΛΟΓΗΣ","userId":"11731994358221954291"}}},"outputs":[{"output_type":"stream","name":"stdout","text":["[13, 18, 10, 2]\n","[13, 18, 10, 2, 12]\n"]}],"source":["print(sample4)\n","print(sample5)"]}],"metadata":{"celltoolbar":"Slideshow","kernelspec":{"display_name":"Python 3","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.12"},"colab":{"provenance":[]}},"nbformat":4,"nbformat_minor":0} |