Grokking_Algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "0d54a174-7c68-478a-b91a-2ccc2370751d",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "6fc53ca7-41ca-4758-9fb4-6fe4a3501208",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Match found at 3\n",
      "Length of input array is 8\n",
      "Number of operations: Worst Case 3.0\n"
     ]
    }
   ],
   "source": [
    "def BinarySearch(arr, keynumber):\n",
    "    low = 0\n",
    "    high = len(arr)-1\n",
    "    \n",
    "    flag = 1\n",
    "    itr = 0\n",
    "    while flag == 1:\n",
    "        mid = (low + high) // 2\n",
    "        if arr[mid] == keynumber:\n",
    "            print(\"Match found at {0}\".format(mid))\n",
    "            flag = 0\n",
    "            itr = itr + 1\n",
    "            break\n",
    "        elif keynumber > arr[mid]:\n",
    "            low = mid +1\n",
    "            itr = itr + 1\n",
    "        elif keynumber < arr[mid]:\n",
    "            high = mid-1\n",
    "            itr = itr + 1\n",
    "        else:\n",
    "            print(\"No Match\")\n",
    "            return None\n",
    "    return mid, itr\n",
    "            \n",
    "input = [1, 3, 5, 7, 9, 10, 11, 13]\n",
    "idx, itrs = BinarySearch(input, 7)\n",
    "print(\"Length of input array is {0}\".format(len(input)))\n",
    "\n",
    "print(\"Number of operations: Worst Case {0}\".format(np.log2(len(input))))\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3fd0a285-e294-4284-92b2-9c0a40b3867e",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Selection sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "100a39b8-22b3-494d-9f60-eb41150264ef",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 4, 6, 7, 9, 10, 11, 13]\n"
     ]
    }
   ],
   "source": [
    "def SmallestNumber(arr):\n",
    "    min_number = arr[0]\n",
    "    idx = 0\n",
    "    for i in range(len(arr)-1):\n",
    "      \n",
    "        if arr[i+1] < min_number:\n",
    "            min_number = arr[i+1]\n",
    "            idx = i+1\n",
    "    return min_number, idx\n",
    "def SelectionSort(input):\n",
    "    new_arr = []\n",
    "    while len(input)>0:\n",
    "        smallest_num, idx = SmallestNumber(input)\n",
    "        new_arr.append(smallest_num)\n",
    "        input.pop(idx)\n",
    "    return new_arr\n",
    "\n",
    "\n",
    "input = [9, 6, 4, 7, 3, 10, 11, 13]\n",
    "print(SelectionSort(input))\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "3f765551-e7b6-4c87-ac46-4359fead1638",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "## adding numbers with reccursion\n",
    "def SumRecurr(arr, sum_total):\n",
    "    if len(arr) == 1:\n",
    "        sum_total = sum_total + arr[0]\n",
    "        return sum_total\n",
    "    else:\n",
    "        sum_total = sum_total + arr[0]\n",
    "        arr.pop(0)\n",
    "        return SumRecurr(arr, sum_total)  # Return the result of the recursive call\n",
    "\n",
    "input = [3, 2, 5]\n",
    "print(SumRecurr(input, 0))  # This should now return 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "4647fc0d-4f96-4453-b364-6d7fcf922c34",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n"
     ]
    }
   ],
   "source": [
    "## Factorial \n",
    "def Factorial(number):\n",
    "    if number ==0:\n",
    "        return 1\n",
    "    else:\n",
    "        return number*Factorial(number-1)\n",
    "\n",
    "print(Factorial(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "bd835e1d-40f7-4e8f-8af8-73814d3cae72",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The number of items in list is: 6\n"
     ]
    }
   ],
   "source": [
    "## Count the number of elements in an array\n",
    "def Counter(arr, ctr):\n",
    "    if bool(arr) == False:\n",
    "        return ctr\n",
    "    elif bool(arr) == True:\n",
    "        ctr = ctr + 1\n",
    "        arr.pop(0)\n",
    "        return Counter(arr, ctr)\n",
    "        \n",
    "arr = [1, 2, 3, 5, 6, 7]  \n",
    "print(\"The number of items in list is: {0}\".format(Counter(arr, 0)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "id": "d3eafb16-4c8b-4511-aa32-f26537ba62df",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum number in list is: 12\n"
     ]
    }
   ],
   "source": [
    "## Maximum number in a list\n",
    "def MaxNumber(arr, number):\n",
    "    max_number = number\n",
    "    if bool(arr) == False:\n",
    "        return max_number\n",
    "    elif arr[0] > max_number:\n",
    "        max_number = arr[0]\n",
    "        arr.pop(0)\n",
    "        return MaxNumber(arr, max_number)\n",
    "    \n",
    "arr = [1, 2, 3, 5, 6, 7, 10, 12]  \n",
    "print(\"Maximum number in list is: {0}\".format(MaxNumber(arr, 0)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "id": "a208f95b-1b99-44c0-b22b-1d336dc9c1ec",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Your number in list is at index: 4\n"
     ]
    }
   ],
   "source": [
    "## Binary search using recurssion\n",
    "def RecBinSearch(arr, low, high, number):\n",
    "    # Base case: If the subarray is empty\n",
    "    if high < low:\n",
    "        return -1  # Indicating that the number was not found\n",
    "\n",
    "    # Calculate mid-point\n",
    "    mid = (low + high) // 2\n",
    "    # Check if the middle element is the target number\n",
    "    if arr[mid] == number:\n",
    "        return mid\n",
    "    # If the target number is smaller, search in the left subarray\n",
    "    elif arr[mid] > number:\n",
    "        return RecBinSearch(arr, low, mid - 1, number)\n",
    "    # If the target number is larger, search in the right subarray\n",
    "    else:\n",
    "        return RecBinSearch(arr, mid + 1, high, number)\n",
    "    \n",
    "\n",
    "arr = [1, 2, 3, 5, 6, 7, 10, 12] \n",
    "low = 0\n",
    "high = len(arr)-1\n",
    "number = 6\n",
    "print(\"Your number in list is at index: {0}\".format(RecBinSearch(arr, low, high, number)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "id": "1ab2185d-e754-4db2-bf46-e8be06398b8d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 5, 6, 7, 10, 12]\n"
     ]
    }
   ],
   "source": [
    "## quicksort: Divide and Conquer\n",
    "def quicksort(arr):\n",
    "    ## base case\n",
    "    if len(arr)<2:\n",
    "        return arr\n",
    "    else:\n",
    "        pivot = arr[0]\n",
    "        less = [i for i in arr[1:] if i< pivot]\n",
    "        greater = [i for i in arr[1:] if i > pivot]\n",
    "        return quicksort(less) + [pivot] + quicksort(greater) \n",
    "\n",
    "arr = [1, 2, 7, 6, 3, 5, 10, 12] \n",
    "print(quicksort(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "553e4765-0813-4926-88e7-50b5e22cc5e7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "## Breadth-first-search\n",
    "M = {\n",
    "0 : [ 3 ] ,\n",
    "1 : [ 2 ] ,\n",
    "2 : [ 1 , 3 , 4 ] ,\n",
    "3 : [ 0 , 2 , 5 ] ,\n",
    "4 : [ 2 , 6 , 7 ] ,\n",
    "5 : [ 3 ] ,\n",
    "6 : [ 4 ] ,\n",
    "7 : [ 4 ]\n",
    "}\n",
    "\n",
    "def bfs (M, target):\n",
    "\n",
    "    visited = set() # a set\n",
    "    search_queue = []\n",
    "    for node in M:\n",
    "       \n",
    "        for neighbor in M[node]:\n",
    "            if neighbor not in visited:\n",
    "                visited.add(neighbor)\n",
    "                \n",
    "                if neighbor == target:\n",
    "                    print(\"Success\")\n",
    "    return neighbor\n",
    "    \n",
    "        \n",
    " \n",
    "target = 5   \n",
    "print(bfs(M, target))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "e810531f-7798-42ea-acbf-d00d5b822c6e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from os import listdir\n",
    "from os.path import isfile, join\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "2a0a5592-ce19-4e3c-89d8-71891835a261",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stanford_Bunny.stl\n",
      ".DS_Store\n",
      "Untitled.ipynb\n",
      "Case_1.stl\n",
      "STL_to_mesh.ipynb\n",
      "STL_to_mesh-checkpoint.ipynb\n",
      "Untitled-checkpoint.ipynb\n",
      ".DS_Store\n",
      "Case_2.stl\n",
      "TO_Des_v3.stl\n",
      "TO_Des_v2.stl\n"
     ]
    }
   ],
   "source": [
    "dirname = \"STL_files\"\n",
    "def ShowContents(dir_name):\n",
    "    for file in listdir(dir_name):\n",
    "        fullpath = join(dir_name, file)\n",
    "        if isfile(fullpath):\n",
    "            print(file)\n",
    "        else:\n",
    "            ShowContents(fullpath)\n",
    "ShowContents(dirname)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cbb04a1c-bfad-48af-9148-36d542753b54",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}