{"id":76,"date":"2016-05-18T11:33:01","date_gmt":"2016-05-18T15:33:01","guid":{"rendered":"http:\/\/www.notexponential.com\/notes\/?page_id=76"},"modified":"2018-10-31T08:22:38","modified_gmt":"2018-10-31T12:22:38","slug":"project-3","status":"publish","type":"page","link":"https:\/\/www.notexponential.com\/notes\/projects\/project-3\/","title":{"rendered":"Project 3"},"content":{"rendered":"

Dynamic Programming and DFS\/BFS Problems<\/strong><\/p>\n

\/\/ Option 1\u00a0 ==> ID ends in 1, Option 2 ==> ID ends in 2, Option 0 ==> ID ends in 0<\/strong><\/em>.<\/p>\n

    \n
  1. Teleportation in Astro haunted galaxies<\/li>\n
  2. Box Stacking<\/li>\n
  3. Magical eggs and floors<\/li>\n
  4. Longest common subsequence<\/li>\n
  5. Maximum Value but Limited Neighbors<\/li>\n
  6. Fast response k-server problem<\/li>\n
  7. Diameter of a graph<\/li>\n
  8. Pseudo-polynomial partition<\/li>\n
  9. Bi-connectivity<\/li>\n
  10. Maze using DFS<\/li>\n<\/ol>\n

    Detailed Descriptions<\/h3>\n

    \u201cTeleportation in Astro Haunted Galaxies\u201d<\/strong>
    \nYou have a teleporter that can take you from galaxy i to galaxy j. Cost to teleport is given by c(i,j), which can be arbitrary. Some galaxies are \u201castro-haunted\u201d – this is specified by a(i) which can be 0 or 1 (1 means that that galaxy is \u201castro-haunted\u201d). Give a polynomial time algorithm that minimizes the cost of going from galaxy 1 to galaxy n, such that you pass through no more than k astro-haunted galaxies. (You can assume that galaxies 1 and n are not astro-haunted.)<\/p>\n

    Box Stacking<\/strong>
    \nYou are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.<\/p>\n

    Magical eggs and tiny floors (aka<\/em>\u00a0“The Cellphone Drop Testing Problem”)<\/strong>
    \nYou are given m eggs and an n floor building. You need to figure out the highest floor an egg can be dropped without breaking, assuming that (i) all eggs are identical, (ii) if an egg breaks after being dropped from one floor, then the egg will also break if dropped from all higher floors, and (iii) if an egg does not break after being thrown from a certain floor, it retains all of its strength and you can continue to use that egg. Your goal is to minimize the number of throws. Describe an algorithm to find the floor from which to drop the first egg.<\/p>\n

    Longest common subsequence<\/strong>
    \nGiven two strings (sequences of characters), the longest common subsequence (LCS) problem is to find the longest subsequence (not necessarily contiguous) that exists in both of the input strings. For example, given strings \u201cmangoes\u201d and \u201cmementos\u201d, the subsequence \u201cmnos\u201d is common in both and is in fact the longest common subsequence. Given two strings of sizes n1 and n2 respectively, find a dynamic programming algorithm to find the longest common subsequence in O(n1n2) time.<\/p>\n

    Maximum Value But Limited Neighbors<\/strong>
    \nYou are given an array a[1..n] of positive numbers and an integer k. You have to produce an array b[1..n], such that: (i) For each j, b[j] is 0 or 1, (ii) Array b has adjacent 1s at most k times, and (iii) sum_{j=1 to n} a[j]*b[j] is maximized. For example, given an array [100, 300, 400, 50] and integer k = 1, the array b can be: [0 1 1 0], which maximizes the sum to be 700. Or, given an array [10, 100, 300, 400, 50, 4500, 200, 30, 90] and k = 2, the array b can be [1, 0, 1, 1, 0, 1, 1, 0, 1] which maximizes the sum to 5500.
    \nTo be precise about the definition of adjacency: sequence [0, 1, 0, 1, 0, 1, 1, 1] has two adjacent 1s. Sequence [0, 1, 0, 0, 1, 1, 1, 1] has 3 adjacent 1s. Sequence [1, 0, 1, 1, 0, 1, 1, 1] also has 3 adjacent 1s.<\/p>\n

    Fast Response k-Server Problem
    \n<\/strong>A series of client machines [1, 2, \u2026 n] are located along a linear network. The i-<\/em>th client generates amount of traffic that is given by w[i]<\/em>. You want to place k<\/em> servers along the linear network that minimizes the total amount of traffic carried by the network. Total traffic is given by sum of each client\u2019s individual traffic, multiplied by the distance (the number of hops) from the server. Provide a polynomial time algorithm to identify the optimal locations for k<\/em> servers.<\/p>\n

    Diameter of a Graph
    \n<\/strong>Diameter of a graph is defined as the largest distance between any pair of vertices of G.\u00a0 Give an efficient polynomial algorithm to find the diameter of the graph.<\/p>\n

    Pseudo-polynomial Partition
    \n<\/strong>Given a set consisting of n<\/em> integers [a1<\/sub>, a2<\/sub>, \u2026 an<\/sub>]<\/em>, you want to partition into two parts so that the sum of the two parts is equal.\u00a0 Suppose s = <\/em>\u00a0a1<\/sub> + a2<\/sub> \u2026 + an.<\/sub><\/em> The time complexity of your algorithm should be O(ns)<\/em> or better.\u00a0\u00a0[Note: <\/strong>Due to the presence of the term s<\/em> in the time complexity, such an algorithm is called pseudo polynomial algorithm.]<\/p>\n

    Biconnectivity<\/strong>
    \nGiven a graph G, check if the graph is biconnected or not. If it is not, identify all the articulation points.\u00a0 The algorithm should run in linear time. Use the given input sets as tests.<\/p>\n

    Maze using DFS<\/strong>
    \nModel a given maze as a graph.\u00a0 Find the target using depth first search.\u00a0 The algorithm should run in linear time. Use the given input sets as tests.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Dynamic Programming and DFS\/BFS Problems \/\/ Option 1\u00a0 ==> ID ends in 1, Option 2 ==> ID ends in 2, Option 0 ==> ID ends in 0. Teleportation in Astro haunted galaxies Box Stacking Magical eggs and floors Longest common subsequence Maximum Value but Limited Neighbors Fast response k-server problem Diameter of a graph Pseudo-polynomial […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":66,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-76","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/76","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/comments?post=76"}],"version-history":[{"count":13,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/76\/revisions"}],"predecessor-version":[{"id":258,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/76\/revisions\/258"}],"up":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/66"}],"wp:attachment":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/media?parent=76"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}