2022/week-6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c3de1eb5-5297-4904-b802-c1233053d800",
   "metadata": {},
   "source": [
    "Table of Contents:\n",
    "- [Introduction](#Welcome-to-CPG!)\n",
    "- [Week 6 Content](#Greedy-Algorithms)\n",
    "- [Example: Mad Scientist (I promise its brief)](#Example:-Mad-Scientist)\n",
    "- [Hackerrank Competition](#Hackerrank-Competition)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ace7c826-ee12-416f-92a0-96f23b35a30a",
   "metadata": {},
   "source": [
    "## Welcome Back to CPG!\n",
    "**Before we start...**\n",
    "\n",
    "If you'd like to follow along for yourself and run the code examples in our presentations, you can clone the repository and open up the Jupyter notebooks locally. Note this means you need to have installed [Jupyter](https://jupyter.org/install) - either JupyterLab or Jupyter Notebook will work fine. In the below example we use JupyterLab:\n",
    "```\n",
    "git clone git@github.com:UQComputingSociety/cpg\n",
    "cd cpg/2022\n",
    "jupyter-lab\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "247c640a-0fb7-4a82-b4ca-b92458d0f800",
   "metadata": {},
   "source": [
    "## Greedy Algorithms\n",
    "\n",
    "### What is a greedy algorithm?\n",
    "\n",
    "Greedy algorithms are a paradigm in which an algorithm always chooses the locally optimal solution, with the logic being this will always lead to the globally optimal solution. Because of this, greedy algorithms generally work in linear time; O(n) (usually) and is a very efficient algorithm paradigm.\n",
    "\n",
    "Example: Travelling Salesman\n",
    "\n",
    "A salesman must visit n cities; with no backtracking, what is the most efficient route he can take?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "3a5b5fa9-f7e3-4f83-ab1c-431248c34d19",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Support code\n",
    "\n",
    "from math import sqrt\n",
    "\n",
    "#Support code\n",
    "\n",
    "def distance(tup1, tup2):\n",
    "    x1, y1 = tup1\n",
    "    x2, y2 = tup2\n",
    "    return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)\n",
    "\n",
    "def main(coordinates):\n",
    "    circuit = []\n",
    "    circuit.append(coordinates.pop(0))\n",
    "    remainder = len(coordinates)\n",
    "    while remainder != 0:\n",
    "        shortest = 10\n",
    "        index = None\n",
    "        for i,v in enumerate(coordinates):\n",
    "            if shortest > distance(circuit[-1], v):\n",
    "                shortest = distance(circuit[-1], v)\n",
    "                index = i\n",
    "        if index == None:\n",
    "            print(\"Error : No index found\")\n",
    "        else:\n",
    "            circuit.append(coordinates.pop(index))\n",
    "        remainder = len(coordinates)\n",
    "    return circuit\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    coordinates = [(1,2), (5,2), (9,5),(5,10), (2,4), (0,6), (8,6), (9,10), (1,10), (4,4), (9,2), (10,7), (3,7), (2,9)]\n",
    "    main(coordinates)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e0ab2c3-cf6b-43d0-8e6f-f6d645f135a7",
   "metadata": {},
   "source": [
    "### When to use greedy algorithms\n",
    "\n",
    "Remember! Greedy algorithms are based on the constraint that the locally optimal solution is included in the globally optimal solution; this is sometimes not the case. A greedy algorithm will always give you a solution, but proving that it is the globally optimal solution is difficult. We won't have this problem today, but it is important to keep in mind when selecting this paradigm for a solution.\n",
    "\n",
    "### Applications of greedy algorithms\n",
    "\n",
    "- COMP3506 Content for minimum spanning trees and pathfinding algorithms (i.e. Dijstra's algorithm).\n",
    "- Huffman Coding (also 3506 content, but still interesting!) which is used for lossless data compression\n",
    "- 2022 Hackathon Project [opal by leadnaut] (https://github.com/leadnaut/opal 'GitHub Link to opal')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ef8dfbe-7b0f-4ea3-b147-917cbc025bd2",
   "metadata": {},
   "source": [
    "## Example: Mad Scientist\n",
    "\n",
    "You are given two strings consisiting of a series of two types of character. You are given a function that can flip a string such that one character becomes the other and vice versa i.e. HGHHHG -> GHGGGH\n",
    "\n",
    "We want to find how many times we need to flip substrings of any given input strings so that they match. Assume the first string is the string to be matched to."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "db65bc7d-209e-47e7-b0f5-d266a4f05958",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Code here!"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ed21b9d-9389-4c4f-9f1e-226415ed57de",
   "metadata": {},
   "source": [
    "## Hackerrank Competition\n",
    "\n",
    "Follow this link to the Hackerrank to begin the mini competition and start solving some searching questions!\n",
    "\n",
    "https://www.hackerrank.com/cpg-week6"
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}