{ "nbformat": 4, "nbformat_minor": 0, "metadata": { "colab": { "provenance": [] }, "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" } }, "cells": [ { "cell_type": "markdown", "source": [ "# Practice Exam 3\n", "\n", "Topics -\n", "\n", "1. Dijkstra's algorithm and some applications\n", "\n", "2. Dynamic Programming\n", "\n", "3. Reductions\n", "\n", "Announcements\n", "\n", "1. Lab 11 due tonight\n", "\n", "2. FLEX feedback\n", "\n", "3. Practice exam tool feedback\n", "\n", "https://docs.google.com/forms/d/1N-07xGwrx7YbId0VnN3C6ffGwLiuPnqK9RzUtHru-wQ/edit" ], "metadata": { "id": "q0IHW4L2A7kh" } }, { "cell_type": "markdown", "source": [ "# Generalized shortest paths\n", "\n", "In Internet routing, there are delays on lines but also, more significantly, delays at routers. This motivates a generalized shortest-paths problem. Consider a directed graph $G = (V,E)$. Suppose that in addition to having edge lengths $\\{\\ell_e\\: |\\: e \\in E\\}$, $G$ also has vertex costs $\\{c_v\\: |\\: v \\in V\\}$. Now define the cost of a path to be the sum of its edge lengths, plus the costs of all vertices on the path (including the endpoints). Give an efficient algorithm that, given a source vertex $s$, computes the shortest distance of every vertex from $s$.\n", "\n", "We will assume that the graph $G$ is given as an adjacency list representation as presented in class: $G$ is a list of lists; the length of $G$ is the number of vertices $n$, and the vertices are $0,1,\\ldots n-1$; the $i$th list contains pairs of the the form $(v,w)$ which indicate that the graph has an edge $(i,j)$ whose weight is $w$. In addition, we assume that the input to the problem is a list $c$ (with len(c) = len(G)) such that $c(i)$ is the cost of vertex $i$.\n", "\n" ], "metadata": { "id": "qgSzdkimBVH3" } }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "jw6FpZze_Nbs", "outputId": "130fbdd6-af03-43b1-c568-319e8611c45a" }, "outputs": [ { "output_type": "stream", "name": "stdout", "text": [ "[1, 4, 8]\n" ] } ], "source": [ "def DijkstraGeneral(G,c,s):\n", " n = len(G)\n", " max_value = float('inf')\n", "\n", " dist = [max_value]*n\n", "\n", " priority_queue = []\n", " for i in range(n):\n", " priority_queue.append(i)\n", "\n", " dist[s] = c[s]\n", " priority_queue = update_vertex(priority_queue,s,dist)\n", "\n", " while (priority_queue != []):\n", " u = priority_queue.pop(0)\n", " for (v,weight) in G[u]:\n", " if (dist[v] > dist[u] + weight + c[v]):\n", " dist[v] = dist[u] + weight + c[v]\n", " priority_queue = update_vertex(priority_queue,v,dist)\n", " return dist\n", "\n", "def update_vertex(pq,v,dist):\n", " for i in range(len(pq)):\n", " if pq[i] == v:\n", " while (dist[pq[i-1]] > dist[v]) and (i > 0):\n", " pq[i] = pq[i-1]\n", " pq[i-1] = v\n", " i -= 1\n", " return pq\n", "\n", "# Example\n", "G = [[(1,1),(2,4)],[(2,2)],[]]\n", "c = [1,2,3]\n", "print(DijkstraGeneral(G,c,0))" ] }, { "cell_type": "markdown", "source": [ "# Best New road planning\n", "\n", "There is a network of roads $G = (V, E)$ connecting a set of cities $V$. Each road $e$ in $E$ has an associated length $\\ell_e$. There is a proposal to add one new road to this network, and there is a list $E’$ of pairs of cities between which the new road can be built. Each such potential road $e’ \\in E’$ has an associated length. As a designer for the public works department you are asked to determine the road $e’ \\in E’$ whose addition to the existing network $G$ would result in the maximum decrease in the driving distance between two fixed cities $s$ and $t$ in the network. Given an efficient algorithm to solve this problem.\n" ], "metadata": { "id": "Bh5efVycBqUK" } }, { "cell_type": "code", "source": [ "def BestNewRoad(G,s,t,X):\n", "\tn = len(G)\n", "\tx = len(X)\n", "\n", "\torig_dist = Dijkstras(G,s)\n", "\tcurrent_min = orig_dist[t]\n", "\tbest_road = None\n", "\n", "\tfor (a,b,w) in X:\n", "\t\tG[a].append((b,w))\n", "\t\tnew_dist = Dijkstras(G,s)\n", "\t\tif (new_dist[t] < current_min):\n", "\t\t\tcurrent_min = new_dist[t]\n", "\t\t\tbest_road = (a,b)\n", "\t\tG[a].remove(b,w)\n", "\n", "\treturn best_road\n" ], "metadata": { "id": "urUWDEM-Biu-" }, "execution_count": null, "outputs": [] }, { "cell_type": "code", "source": [ "def BestNewRoad_efficient(G,s,t,X):\n", "\tn = len(G)\n", "\tx = len(X)\n", "\n", "\tsource_dist = Dijkstras(G,s)\n", "\n", "\tRev = []\n", "\n", "\tfor i in range(n):\n", "\t\tRev.append([])\n", "\n", "\tfor i in range(n):\n", "\t\tfor (j,w) in G[i]:\n", "\t\t\tRev[j].append((i,w))\n", "\n", "\ttarget_dist = Dijkstras(Rev,t)\n", "\n", "\tcurrent_min = source_dist[t]\n", "\tbest_road = None\n", "\n", "\tfor (a,b,w) in X:\n", "\t\tnew_dist = source_dist[a] + w + target_dist[b]\n", "\t\tif (new_dist < current_min):\n", "\t\t\tcurrent_min = new_dist\n", "\t\t\tbest_road = (a,b)\n", "\n", "\treturn best_road\n" ], "metadata": { "id": "ICEdia9KCHJ8" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "# Optimal restaurant chain locations\n", "\n", "A restaurant chain M is looking to open restaurants at multiple locations along a highway. There are $n$ possible locations starting from the start of the highway. The $i$th location is located at dist[i] miles from the start. The expected annual profit for location i is profit[i].\n", "\n", "Historical data indicates that any two restaurants should be placed at least $x$ miles from each other to prevent customer fatigue.\n", "\n", "Given this information, compute the maximum annual expected profit for M efficiently.\n", "\n", "Input: Distance list dist, Expected profit list profit, prohibited distance x\n", "\n", "Output: Maximum annual expected profit\n" ], "metadata": { "id": "h5nL8vkgCNfa" } }, { "cell_type": "code", "source": [ "def OptimalLocations_DP(dist, profit, x):\n", " n = len(dist)\n", "\n", " # Declaring a list S to store S(i) values\n", " S = [float('-inf')] * n\n", " S[0] = profit[0]\n", "\n", " for i in range(1, n):\n", "\n", " # finding the largest j such that location j is at least x miles away from location i\n", " for j in range(i - 1, -1, -1):\n", " if (dist[i] - dist[j] >= x):\n", " break\n", "\n", " # No valid preceding location case\n", " if (dist[i] - dist[0] < x):\n", " S[i] = profit[i]\n", "\n", " # Valid predecessors 0,1,2...j case\n", " else:\n", " S[i] = max(S[0:j+1]) + profit[i]\n", "\n", " return max(S)\n" ], "metadata": { "id": "O3rywcmWCwm2" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "# Longest Palindromic Subsequence\n", "\n", "A subsequence of a string is any subset of its characters in the order in which they appear in the string. A subsequence is palindromic if it is the same whether it is read left to right or right to left. Give an algorithm that computes the longest palindromic subsequence of any given input string.\n", "\n", "Input - A string str\n", "\n", "Output - The length of the longest palindromic subsequence in str\n" ], "metadata": { "id": "YC_wKSG8C92d" } }, { "cell_type": "code", "source": [ "def LPS_DP(str):\n", " n = len(str)\n", " S = [[0 for col in range(n)] for row in range(n)]\n", "\n", " # Base cases\n", " for i in range(n):\n", " S[i][i] = 1\n", "\n", " # for lengths 2,3,...,n length 1 covered by base case\n", " for l in range(2, n + 1):\n", " for i in range(n - l + 1): # since starting indices can only be n-l-1 at most\n", " j = i + l - 1 # end point for start i and length l\n", " if (str[i] == str[j]):\n", " S[i][j] = max(2 + S[i+1][j-1], S[i+1][j], S[i][j-1])\n", " else:\n", " S[i][j] = max(S[i+1][j], S[i][j-1])\n", "\n", " return S[0][n-1]\n" ], "metadata": { "id": "acj6Xm1ADDOf" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "# Dictionary Distance\n", "\n", "Given a dictionary of words of equal length, and two words $s$ and $t$, find the minimum number of single-letter changes needed to transform $s$ into $t$, where each intermediate word must also be in the dictionary.\n", "\n", "Let us look at an example. Suppose our dictionary is [“cat”, \"cot\", \"cog\", \"dog\", \"dot\", \"dat\", \"dag\", \"dig\"] and $s$ is the string “cat” and $t$ is the string “dog”, one possible transformation would be \"cat\" -> \"dat\" -> \"dot\" -> \"cot\" -> \"cog\" -> “dog” which takes 5 steps. Another transformation would be \"cat\" -> \"dat\" -> \"dag\" -> \"dog\" which takes 3 steps. However, “cat” -> “dog” is not a valid transformation because more than one letter is changed in the step, and “cat” -> “cag” -> “dag” -> “dog” is not a valid transformation because “cag” is not a word in our dictionary.\n", "\n", "Hint: Consider reducing it to a graph problem.\n" ], "metadata": { "id": "N__duDukDV4O" } }, { "cell_type": "code", "source": [ "from collections import deque\n", "\n", "def oneaway(u, v):\n", " if len(u) != len(v):\n", " return False\n", "\n", " diff = 0\n", " for i in range(len(u)):\n", " if u[i] != v[i]:\n", " diff += 1\n", " if diff > 1:\n", " return False\n", "\n", " return diff == 1\n", "\n", "\n", "def bfs(G,s):\n", " # number of vertices in G\n", " n = len(G)\n", "\n", " # initialize dist to be max possible distance\n", " dist = [n]*len(G)\n", "\n", " # noting down the parent of each vertex\n", " parent = [None]*len(G)\n", "\n", " # start the search from s\n", " dist[s] = 0\n", " queue = [s]\n", " #this takes O(1) time as the list is initialized with 1 element s\n", "\n", " # start exploring\n", " while queue != []:\n", " # remove first element in the queue and explore its neighbors\n", " u = queue.pop(0)\n", " for v in G[u]:\n", " if dist[v] == n:\n", " # v has not been visited\n", " dist[v] = dist[u] + 1\n", " parent[v] = u\n", " queue.append(v)\n", "\n", " # return the list distance storing the shortest distance to each vertex\n", " return dist\n", "\n", "\n", "def dictDist(D, s, t):\n", " n = len(D)\n", "\n", " # construct graph\n", " G = []\n", " for i in range(n):\n", " neighbors = []\n", " for j in range(n):\n", " if i != j and oneaway(D[i], D[j]):\n", " neighbors.append(j)\n", " G.append(neighbors)\n", "\n", " # check if s and t exist\n", " if s not in D or t not in D:\n", " return -1\n", "\n", " start = D.index(s)\n", " target = D.index(t)\n", "\n", " dist = bfs(G, start)\n", " return dist[target]" ], "metadata": { "id": "Mxn_uVDwDfSW" }, "execution_count": null, "outputs": [] }, { "cell_type": "markdown", "source": [ "# Hamiltonian Path problem\n", "\n", "A Hamiltonian path in a directed graph $G$ is a path in $G$ that visits every vertex. For example, suppose we have a graph $H$ with 4 vertices: 0, 1, 2, 3. And additionally supposed the edges are (0,1), (1,2), (2,3). Then 0 -> 1 -> 2 -> 3 is a Hamiltonian path since it visits every vertex, but the path 1 -> 2 -> 3 is not a Hamiltonian path because it does not visit 0.\n", "\n", "Not every directed graph has a Hamiltonian path. For example, consider the graph $K$ with 3 vertices: 0, 1, and 2, with edges (0,1) and (2,1). There is no path in this graph that goes through all 3 vertices.\n", "\n", "Problem A: The Hamiltonian path problem is given a directed graph $G$ as input, determining if $G$ has a Hamiltonian path.\n", "\n", "Problem B: The Hamiltonian path starting at a vertex is the following problem: Given a directed graph $G$ and a vertex $s$, determine if $G$ has a Hamiltonian path starting at vertex $s$.\n", "\n", "Let us consider the example graph $H$ given above. The answer to Problem A for input $H$ is True, since $H$ has a Hamiltonian path (0 -> 1 -> 2 -> 3). The answer to Problem B on input $H$ and 0 is also True, since $H$ has a hamiltonian path starting at vertex 0. However, the answer to Problem B on input $H$ and 1 is False, since there is no Hamiltonian path starting at vertex 1 in $H$.\n", "Show that problem A can be reduced to problem B. That is, show how we can solve problem A, if we had an algorithm to solve problem B.\n", "Show that problem B can be reduced to problem A. That is, show how we can solve problem B, if we had an algorithm to solve problem A.\n" ], "metadata": { "id": "IS-JFfsVD-cE" } }, { "cell_type": "code", "source": [], "metadata": { "id": "hWwFS10AEGvl" }, "execution_count": null, "outputs": [] } ] }