{
"cells": [
{
"cell_type": "markdown",
"id": "8c52d3d4",
"metadata": {},
"source": []
},
{
"cell_type": "markdown",
"id": "74aa4459",
"metadata": {},
"source": [
"# INF TC1 - Algorithmes et structures de données\n",
"\n",
"## Exercices"
]
},
{
"cell_type": "markdown",
"id": "d9a28297",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "markdown",
"id": "e58599e3-9ab7-4d43-bb22-aeccade424ce",
"metadata": {},
"source": [
"# Lists, search, sort"
]
},
{
"cell_type": "markdown",
"id": "691b3c38-0e83-4bb2-ac90-ef76d2dd9a7a",
"metadata": {},
"source": [
"---"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "1095285f-26e2-43ce-a1c5-9358c5256a0b",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"list_complexities = [\"O(1)\", \"O(log(n))\", \"O(n)\", \"O(n^2)\", \"O(nlog(n))\", \"O(n^3)\", \"O(2^n)\", \"O(n!)\", \"O(n^n)\"]"
]
},
{
"cell_type": "markdown",
"id": "11a124a7-1279-469a-b091-2833d3fd1a0f",
"metadata": {},
"source": [
"## Exercise 0: Search the index first occurence of a target value\n",
"\n",
"_Write a Python function `search_list(L, v)` that takes a list `L` and a target element `v` as input. The function should return the index of the first occurrence of the target element in the list `L`._"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "665c7b64-428d-468a-860b-65d0d12e98e1",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"def search_list(L, target):\n",
" for n, i in enumerate(L):\n",
" if i == target:\n",
" return n\n",
" return -1"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "d776ca94-1ed2-4443-91e2-a1591a1690b8",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"search_list([1, 2, 2], 2)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e7b5950c-a6f0-4795-995b-903d717f35c9",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"assert search_list([1, 2, 3, 4, 5], 3) == 2\n",
"assert search_list([1, 2, 3, 4, 5], 6) == -1\n",
"assert search_list([1, 2, 3, 4, 5], 6) == -1\n",
"assert search_list([], 42) == -1\n",
"assert search_list([7, 2, 3, 4, 5], 7) == 0\n",
"assert search_list([1, 2, 3, 4, 5, 6], 7) == -1"
]
},
{
"cell_type": "markdown",
"id": "9d813205-b709-42ab-b414-6f3fc947022a",
"metadata": {},
"source": [
"## Exercise 1: Search in a list with an odd index\n",
"\n",
"_Write a Python function `search_list(L, v)` that takes a list `L` and a target element `v` as input. The function should return the index of the first occurrence of the target element in the list `L`._"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f3b233ec-7077-479d-9c04-f1a4c35f3111",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "2791444cbfd4f0f74f1ce7f2a330ecec",
"grade": false,
"grade_id": "search_list",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def search_list(L, target):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "f280eeea-4812-4a30-80b5-3fe1cafa9283",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"search_list([1, 2, 2], 3)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "423d2637-8bd6-4e8f-95ff-2765dae5bce7",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "6054e435b1f5635d18f61f94bfb05e62",
"grade": true,
"grade_id": "correct_correct_search_list",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"assert search_list([1, 2, 3, 4, 5], 3) == 2\n",
"assert search_list([1, 2, 3, 4, 5], 6) == -1\n",
"assert search_list([1, 2, 3, 4, 5, 6], 6) == -1\n",
"assert search_list([], 42) == -1\n",
"assert search_list([7, 2, 3, 4, 5, 7], 7) == 0\n",
"assert search_list([1, 2, 3, 4, 5, 6], 6) == -1"
]
},
{
"cell_type": "markdown",
"id": "6d8dc6cd-aad0-42a9-b768-6a1a5289e354",
"metadata": {},
"source": [
"## Exercise 2: Sort a list of tuples\n",
"\n",
"_Given a list of lists of length N, sort by the N-th element of the list._"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8271ff47-efb4-48a0-ac4c-bba6ede7e578",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "18319fc9882c760de9d2f2dde25e2c76",
"grade": false,
"grade_id": "sort_list_of_lists_by_nth_element",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def sort_list_of_lists_by_nth_element(list_of_lists, N):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "4577bd24-9e50-4172-8246-d1bccfa21618",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"list_of_lists = [[3, 5, 1], [1, 2, 9], [7, 4, 6], [2, 8, 3]]\n",
"sorted_list = sort_list_of_lists_by_nth_element(list_of_lists, 2)\n",
"print(sorted_list)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ed3cdeed-07fa-461f-b7ae-210e1605ca76",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "135ef51ad6ac5ce059a50fccc46a99e4",
"grade": true,
"grade_id": "correct_sort_list_of_lists_by_nth_element",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"list1 = [[3, 5, 1], [1, 2, 9], [7, 4, 6], [2, 8, 3]]\n",
"sorted_list1 = sort_list_of_lists_by_nth_element(list1, 2)\n",
"assert sorted_list1 == [[3, 5, 1], [2, 8, 3], [7, 4, 6], [1, 2, 9]], \"Test Case 1 Failed\"\n",
"\n",
"list2 = [[9, 5, 7], [3, 6, 1], [0, 2, 4], [8, 1, 5]]\n",
"sorted_list2 = sort_list_of_lists_by_nth_element(list2, 0)\n",
"assert sorted_list2 == [[0, 2, 4], [3, 6, 1], [8, 1, 5], [9, 5, 7]], \"Test Case 2 Failed\"\n",
"\n",
"list3 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]\n",
"sorted_list3 = sort_list_of_lists_by_nth_element(list3, 1)\n",
"assert sorted_list3 == [[1, 2, 3], [4, 5, 6], [7, 8, 9]], \"Test Case 3 Failed\"\n"
]
},
{
"cell_type": "markdown",
"id": "0bbda1ba-a5e7-4a1d-a742-84d0215b1e24",
"metadata": {},
"source": [
"## Exercise 3: Access a list element\n",
"\n",
"_Given an input list `L`, and `index` value, access a given `key` and return the value._"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "2d6a6f11-d24b-4f0e-a7d2-298243e35c4d",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "df3e8c605c7e96af2267865e04990e5a",
"grade": false,
"grade_id": "cell-1ab0b636df63501a",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def access_dict_element(L, index, key):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "ea0883dc-d08c-40ea-9e0b-4f0a3abc517f",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"example_list = [{'name': 'Alice', 'age': 30}, {'name': 'Bob', 'age': 25}]\n",
"result = access_dict_element(example_list, 0, 'name')\n",
"print(result) "
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "88ae441e-58b1-4d6c-a639-530919658d03",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "efa0cb4d52536298b425a5e9d5154374",
"grade": true,
"grade_id": "correct_access_dict_element",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"example_list = [{'name': 'Alice', 'age': 30}, {'name': 'Bob', 'age': 25}]\n",
"assert access_dict_element(example_list, 0, 'name') == 'Alice'\n",
"assert access_dict_element(example_list, 1, 'city') is None\n",
"assert access_dict_element(example_list, 2, 'name') is None\n",
"assert access_dict_element(example_list, 0, 'city') is None"
]
},
{
"cell_type": "markdown",
"id": "98405b12-ad61-4007-8c9f-6955d238df41",
"metadata": {
"tags": []
},
"source": [
"## Exercise 4: Remove Elements from a List\n",
"\n",
"_Write a Python function `remove_elements(L, condition)` that takes a list `L` and a function `condition` as input._"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e079e47b-2f9e-42d1-a78b-56c92ad84d63",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"def is_odd(x):\n",
" return x % 2 != 0"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "536734bd-d4cc-4f83-8042-3c0e774c4034",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "46e9b2d0caa1061f9d00cf2859441701",
"grade": false,
"grade_id": "remove_elements",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def remove_elements(lst, condition):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "a65bb6f1-b7c7-4156-ba8b-9b72a25616f3",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"remove_elements(my_list, is_odd)\n",
"print(my_list) # Should print [2, 4, 6, 8]"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "254155dc-b271-4881-ac65-5a11d13990ea",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "d60a1be7322087e5612fb15fc5677539",
"grade": true,
"grade_id": "correct_remove_elements",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"test_list_1 = [12, 5, 18, 9, 25, 3, 15]\n",
"remove_elements(test_list_1, lambda x: x > 10)\n",
"assert test_list_1 == [5, 9, 3], \"Remove greater than 30\"\n",
"\n",
"test_list_2 = [-3, 7, -9, 2, 0, -1, 8]\n",
"remove_elements(test_list_2, lambda x: x < 0)\n",
"assert test_list_2 == [7, 2, 0, 8], \"Remove negative elements\"\n",
"\n",
"def custom_condition(x):\n",
" return x % 3 == 0\n",
"test_list_3 = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"remove_elements(test_list_3, custom_condition)\n",
"assert test_list_3 == [1, 2, 4, 5, 7, 8]\n",
"\n",
"test_list_4 = [42, 99, 101]\n",
"remove_elements(test_list_4, lambda x: True)\n",
"assert test_list_4 == [], \"Remove all elements\"\n",
"\n",
"test_list_5 = [10, 20, 30, 40]\n",
"remove_elements(test_list_5, lambda x: False)\n",
"assert test_list_5 == [10, 20, 30, 40], \"No element to remove\""
]
},
{
"cell_type": "markdown",
"id": "d75dba4b-ac22-4f2c-9a6c-cf333b1ec5e8",
"metadata": {},
"source": [
"## Exercise 5: Sort a dictionnary by values\n",
"\n",
"List a dictionnary (not a list!) by value."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "556be9d8-b8c3-4f1d-bcb1-8f099968af9d",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "6bfb51c12c41947733534307eb1cf5c4",
"grade": false,
"grade_id": "sort_dict_by_values",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def sort_dict_by_values(input_dict):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()\n",
" return sorted_dict"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "3c32c4ee-56f5-46b5-a8b6-b740e6d5fef5",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"test_dict3 = {'c': 3, 'b': 2, 'a': 1}\n",
"sorted_dict3 = sort_dict_by_values(test_dict3)\n",
"assert sorted_dict3 == {'a': 1, 'b': 2, 'c': 3}"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "532e5225-a2d8-4c10-a036-1efde9acc5fd",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "8a4001090e87ce0c5d773621ed0a3ea9",
"grade": true,
"grade_id": "correct_sort_dict_by_values",
"locked": true,
"points": 0,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"test_dict = {'banana': 3, 'apple': 1, 'cherry': 2}\n",
"sorted_dict = sort_dict_by_values(test_dict)\n",
"assert sorted_dict == {'apple': 1, 'cherry': 2, 'banana': 3}\n",
"\n",
"test_dict2 = {'zebra': 42, 'lion': 7, 'elephant': 15, 'giraffe': 23}\n",
"sorted_dict2 = sort_dict_by_values(test_dict2)\n",
"assert sorted_dict2 == {'lion': 7, 'elephant': 15, 'giraffe': 23, 'zebra': 42}\n",
"\n",
"test_dict3 = {'one': 3, 'two': 3, 'three': 3, 'four': 3}\n",
"sorted_dict3 = sort_dict_by_values(test_dict3)\n",
"assert sorted_dict3 == {'one': 3, 'two': 3, 'three': 3, 'four': 3}"
]
},
{
"cell_type": "markdown",
"id": "fef2ad7f-55ef-43f2-991d-5067bb085eb6",
"metadata": {},
"source": [
"## Exercise 6: insertion sort\n",
"\n",
"Implement the `insertion sort` that operates as follows:\n",
"\n",
"- Start with an unsorted list.\n",
"- Iterate through each element in the list.\n",
"- For each element, compare it with the elements to its left in the list.\n",
"- Move elements to the right until you find the correct position for the current element.\n",
"- Insert the current element into its proper place in the sorted portion of the list.\n",
"- Repeat this process for all elements, gradually building a sorted list from left to right."
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "51a86852-f8e2-4c05-8053-13fdf2a4832b",
"metadata": {
"deletable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "84421b7199764b6fe3485117b23fb0a1",
"grade": false,
"grade_id": "insertion_sort",
"locked": false,
"schema_version": 3,
"solution": true,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"def insertion_sort(arr):\n",
" # YOUR CODE HERE\n",
" raise NotImplementedError()"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "fbfa74f1-4675-452f-897b-21b0c7025f81",
"metadata": {
"tags": []
},
"outputs": [],
"source": [
"print(insertion_sort([2, 1, 3, 4, 5]))"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "266e89e0-4b59-441f-bb67-69ad4e35e2a9",
"metadata": {
"deletable": false,
"editable": false,
"nbgrader": {
"cell_type": "code",
"checksum": "dc6fc6f16aa2c62a5e1e39382106b0bf",
"grade": true,
"grade_id": "correct_insertion_sort",
"locked": true,
"points": 1,
"schema_version": 3,
"solution": false,
"task": false
},
"tags": []
},
"outputs": [],
"source": [
"# Test case 2: Already sorted list\n",
"arr = [1, 2, 3, 4, 5]\n",
"assert insertion_sort(arr) == arr\n",
"\n",
"# Test case 3: Reverse sorted list\n",
"arr = [5, 4, 3, 2, 1]\n",
"assert insertion_sort(arr) == [1, 2, 3, 4, 5]\n",
"\n",
"# Test case 4: Random order list\n",
"arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]\n",
"assert insertion_sort(arr) == [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]"
]
},
{
"cell_type": "markdown",
"id": "ab78dd44-bb6a-451d-8642-223639d31bf9",
"metadata": {},
"source": [
"## Bonus\n",
"\n",
"You may get bonus points for the following answers:\n",
"\n",
"- add exceptions https://docs.python.org/3/library/exceptions.html\n",
"- add more test cases"
]
}
],
"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
}