All the Problems

————————————————————————————————————————————————————————————————————— Pattern Searching. http://www.geeksforgeeks.org/category/pattern-searching/

• Naive Pattern Searching. * n

  • m
  • n-m
  • compare the indices.
  • return the starting point of the index.

• KMP Algorithm.

• Rabin Karp Algorithm.

• Finite Automata.

• Pattern Searching using Suffix Tree.

• Pattern Searching using Suffix Array.

• Longest Palindromic Subsequence.

• Wild Card Pattern Matching. —————————————————————————————————————————————————————————————————————

• Backtracking Problem 1: The Knights tour problem. http://www.geeksforgeeks.org/backtracking-set-1-the-knights-tour-problem/

• Backtracking Problem 2: Rat in Maze: http://www.geeksforgeeks.org/backttracking-set-2-rat-in-a-maze/

• Backtracking Problem 3: N Queen Problem http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/\

• Backtracking Problem 4: http://www.geeksforgeeks.org/backttracking-set-4-subset-sum/

• Backtracking Problem 5: M Colouring http://www.geeksforgeeks.org/backttracking-set-5-m-coloring-problem/

• Backtracking Problem 6: http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/

• Backtracking Problem 7: http://www.geeksforgeeks.org/backtracking-set-7-suduku/

• Backtracking Problem 8: http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

• Backtracking Problem 9; http://www.geeksforgeeks.org/backtracking-set-8-solving-cryptarithmetic-puzzles/

• Subset-1: https://leetcode.com/problems/subsets

• Subset-2: https://leetcode.com/problems/subsets-ii

• Permutation-1:https://leetcode.com/problems/permutations

• Permutation-2: https://leetcode.com/problems/permutations-ii

• Combination Sum” https://leetcode.com/problems/combination-sum/

• Combination Sum 2.: https://leetcode.com/problems/combination-sum-ii/

• Palindrome Partitioning.https://leetcode.com/problems/palindrome-partitioning/

• Queens 1: : https://leetcode.com/problems/n-queens/

• N Queens: 2: https://leetcode.com/problems/n-queens-ii/

• Anagrams of String using backtracking: https://leetcode.com/problems/n-queens-ii/

  Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that ccannot possibly be completed to a valid solution.[1][2

• The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned.
• Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient (if not the most efficient[citation needed]) technique for parsing, for the knapsack problem and other combinatorial optimization problems. It is also the basis of the so-called logic programming languages such as Icon, Planner and Prolog.

————————————————————————————————————————————————————————————————————— Greedy Algorithm: http://www.geeksforgeeks.org/tag/Greedy-Algorithm/ Problem 1: Activity Selection problem. Problem 2: Kruskal Minimum Spanning Tree Problem. Problem 3: Huffman Coding. Problem 4: Djkastra’s shortest path. Problem 5: Connect N Ropes with the minimum cost Problem 6: Minimum no of platforms required for Railway /Bus station. Problem 7: Minimize Cash flow between people. Problem 8: Shortest Superstring problem. ——————————————————————————————————————————————————————————————————— Arrays based Misc Trick Questions.

1. https://leetcode.com/problems/trapping-rain-water-ii/
2. https://leetcode.com/problems/container-with-most-water
3. https://leetcode.com/problems/water-and-jug-problem/
4. https://leetcode.com/problems/pacific-atlantic-water-flow/
5. https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
6. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
7. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ ————————————————————————————————————————————————————————————————————— Sum Questions.
8. https://leetcode.com/problems/3sum/
9. https://leetcode.com/problems/3sum-closest/
10. https://leetcode.com/problems/4sum/
11. https://discuss.leetcode.com/topic/44006/3sum-and-4sum-solution-see-the-similarities-yourself ————————————————————————————————————————————————————————————————————— Double Array Problems.
12. https://leetcode.com/problems/spiral-matrix/
13. https://leetcode.com/problems/spiral-matrix-ii/ ————————————————————————————————————————————————————————————————————— String;
14. Longest Sub string without repeating characters: https://leetcode.com/problems/longest-substring-without-repeating-characters/
15. Genetic Mutation: https://leetcode.com/problems/minimum-genetic-mutation/
16. Palindrome Problems: —————————————————————————————————————————————————————————————————————
17. Binary Tree: InOrder Traversal: https://leetcode.com/problems/binary-tree-inorder-traversal/
18. Unique Binary Search Trees: https://leetcode.com/problems/unique-binary-search-trees-ii/
19. Unique binary Search Trees: https://leetcode.com/problems/unique-binary-search-trees/
20. Validate binary search Trees: https://leetcode.com/problems/validate-binary-search-tree/
21. Recovery Binary Search Trees: https://leetcode.com/problems/recover-binary-search-tree/
22. Same Tree: https://leetcode.com/problems/same-tree/
23. Symettric Tree: https://leetcode.com/problems/symmetric-tree/
24. Binary Tree Level Order Traversal: https://leetcode.com/problems/binary-tree-level-order-traversal/
25. Binary Tree Zig Zag level order traversal: https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
26. Maximum depth of Binary tree: https://leetcode.com/problems/maximum-depth-of-binary-tree/
27. Construct a binary tree from pre order and in order traversal: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
28. Binary Tree Level Order Traversal: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
29. Convert Sorted Array to Binary Search Tree: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
30. Convert Sorted List to Binary Search Tree: https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
31. Balanced Binary Trees: https://leetcode.com/problems/balanced-binary-tree/
32. Minimum Depth of Binary Trees: https://leetcode.com/problems/minimum-depth-of-binary-tree/
33. Path Sum” https://leetcode.com/problems/path-sum/
34. Path sum 2: https://leetcode.com/problems/path-sum-ii/
35. Flatten BST to a linked List: https://leetcode.com/problems/flatten-binary-tree-to-linked-list/ ————————————————————————————————————————————————————————————————————— All the Linked List Problems Add two numbers in the Linked List: https://leetcode.com/problems/add-two-numbers/ Add two numbers in the Linked List https://leetcode.com/problems/add-two-numbers-ii/ Linked List Cycle: https://leetcode.com/problems/linked-list-cycle/ Linked List Cycle 2: https://leetcode.com/problems/linked-list-cycle-ii/ Insertion Sort List: https://leetcode.com/problems/insertion-sort-list/ Sort a list: https://leetcode.com/problems/sort-list/ Reverse a Linked List: https://leetcode.com/problems/reverse-linked-list/ ————————————————————————————————————————————————————————————————————— Graph Based Questions Graph based DFS Graph based BFS. Graph based Topological Sorting. Graph based Counting Sort. Floyd Marshal Algeria Directed Acyclic Graph. ————————————————————————————————————————————————————————————————————— Divide and Conquer

————————————————————————————————————————————————————————————————————— https://leetcode.com/problems/reconstruct-itinerary/

1. String array se form a directed acyclic graph.
2. perform topological sort on the graph.
3. return the output.
4. list of String will be the output ————————————————————————————————————————————————————————————————————— string based Misc questions.
5. https://leetcode.com/problems/bulls-and-cows/

List of Problems ———————————————————————————————— All the Trees Problem (15 days)

• Given binary tree print nodes from roots to leaf.

• level order traversal.

• count leaf nodes.

• get level of node in Binary Trees.

• print ancestor of binary trees.

• check if the binary tree is subtree of another

• distance between two keys in the binary trees

• find max path sum between two leaves in the binary tree.

• find the closet leaf node in Binary Tree.

• find nodes between two level of Binary Trees.

• serialize the binary tree.

• deserialize the binary tree.

• remove any node that don’t lie in the path.

• print all the nodes which are at the distance of k.

• print nodes at distance k from any given node.

• reverse alternate binary trees.

• print let view of node.

• check all the leave at the same level.

• lowest common censors from BST

• correct BST

• construct BST.

• Merge BST in Space.

• Lowest Common Ancestor.

• Min/Max Heap.

• Min Heapity

• Max Heapify. —— ———————————————————————— Graph API (15 days)

• Graph (int V)

• Graph (int V)

• Void add Edge (int v, int w)

• Iterable adjV

• Int V()

• Int E()

• String toString()

• Digraph reverse()

  • Undirected Graph
    • DFS, BSF, CC.
  • Directed Graph.
    • DFS, BFS. SC, Topological sort. ————————————————————————— Dynamic Programming Questions. (15 days)

—————————————————————————

Searching Problem.

• Practice all the questions from the HackerRank very sincerely atleast two times. Get to a stage where you are able to write the code without seeing it .
• Solve all the questions from the notebook orally. .
• Write down the programs for all the questions for the arrays.
• Write down the programs for all the questions on the linkedLists.
• Write down the program for all the questions on the queues.
• Write down the program for all the questions on the stacks.
• Write down the programs for all the questions on the Trees and Binary Trees.
• Write down the programs for all the question on the Graphs.

—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— Dynamic Programming

1. Longest Increasing Subsequence.

Arrays:

• pair sum.
• missing elements to the Nth Sequence.
• Median of two sorted array.
• Sorted array in rotation and point of inflection.
• First repeated number in an array
• Intersection of two array with an extra space.
• given array a and b, sort A in order of B.
• Merge sorted arrays without using extra space.
• find duplicates in the array.
• selection problem. Find 6th large with O(N) space.
• Search for element in bounded sorted array.
• shuffle pack of crds.
• merge N sorted arrays.
• Binary Search problems.

strings

• Anagram
• Palindrome.
• WordREverse
• Maximum occurring Characters.
• Remove duplicates from the ip string.
• Remove characters in the first string.
• Check if one string is rotation of other.
• First non repeating characters.
• length of longest substring repeating values.
• longest palindrome sequence.

LinkedList

• find Middle
• Rth from end.
• Delete linked list without pointers
• merge sort for linked list.
• quick sort for linked list.
• loop
• find loop
• remove loop
• flatten linked list.
• detect cycle.

graphs

• breadth first search
• depth first search.

——————————————————————————————

Set and String Problems.

1. Set Cover
2. Set Packing
3. String Matching
4. Text Compression.
5. Finite State Machine Minimization.
6. Longest Common Subscrting/subsequence.
7. Shortest Common Substring

Combinatorial Problems

1. Sorting
2. Searching
3. Median and Selection
4. Generating Permutations
5. Generating Subsets
6. Generating Partitions
7. Generating Graphs

Graph Problems: Easy Problems

1. Connected Components
2. Topological Sorting
3. Minimum Spanning Tree
4. Shortest Path
5. Transitive Closure and Reductions.
6. Matching.
7. Eulerian Cycle/Chinese Postman
8. Edge and Vertex Connectivity
9. Network Flow
10. Drawing Graphs Nicely
11. Drawing Trees
12. Planarity Detection and Embedding

Graph Problems: Hard Problems

1. Clique
2. Independent Set
3. Vertex Cover
4. Travelling SalesMan Problem
5. Hamiltonian Cycle
6. Graph Partition
7. Vertex Colouring
8. Edge Colouring
9. Graph IsoMorphism
10. Steiner Tree
11. Feedback edge set/ vertex set

System Design Interviews

1. https://www.quora.com/How-do-I-prepare-to-answer-design-questions-in-a-technical-interview
2. https://www.youtube.com/watch?v=-W9F__D3oY4
3. https://github.com/checkcheckzz/system-design-interview
4. Video1;https://www.youtube.com/watch?v=-W9F__D3oY
5. Video2: https://www.youtube.com/watch?v=PE4gwstWhmc
6. https://www.quora.com/Is-there-any-book-to-prepare-for-System-Design-and-Architecture-interview-questions
7. http://www.hiredintech.com/system-design

• ( Algorithms) Strings/Characters || Arrays || Linked Lists.

• ( DataStructure) Sorting || Searching || Dynamic Programming

• Do a written coding practice.

• Insertion Sort.

• Selection Sort.

Data Structures.

• Contagious and Linked List.
• Stacks and Queues.
• Dictionaries.
• Binary Search Tree.
• Priority Queue.
• Hashing and Strings.

Sorting and Searching.

• Application of Sorting.
• HeapSort.
• QuickSort
• MergeSort.
• Binary Search
• Divide and Conquer.

Graph Traversal.

• BFS.
• DFS

1. Set
2. Set Packing.
3. String Matching.
4. Approximate String Matching.
5. Text Compression.

Graph Polynomialss

• Vertex Cover

• Travelling Sales Problem

• Hamiltonian Cycle

• Graph Partition

• Vertex Colouring

• Edge Colouring

• Graph Isomorphism

• Steiner Tree

• Feedback Edge / Vertex Set

• Nearest Neighbour Search

• Range Search

• Point Location

• Intersection Detection

• Bin Packing

1. RAM Model of computation.
2. The Big Oh Notation.

Sorting Algorithms.

• Insertion Sort Algorithm
• Selection Sort Algorithm
• HeapSort
• MergeSort
• QuickSort
• Bucket Sort

Matrix Multiplication:

• String Pattern
• Matrix Multiplication
• RobotTourOptimzation Algorithm
• SuffixTree.

Trees

• minimum spanning trees.

• shortest paths.

• network flows.

• search in a tree

• insert in a tree

• Graph

  • DirectedGraph
  • UndirectedGraph

Data Structure for the Graph

• Adjutancy Matrix

• Adjancey List.

• Breadth First Search.

• application fo BFS

  • Connected components

• Depth FirstSearch

  • Queuex
  • Stack
  • Finding Cycles.

• Strongly connected components.

• Weighted Graph Algorithms.

  • Minimum Spanning Tree
  • Prim’s Algorithm
  • Kruskal’s Algorithm
  • Shortest Paths
  • Djikastras Algorithm
  • Network Flow
  • Bipartite Matching.
  • BackTracking

• Dynamic Programming

  • Fibonacci number by Caching
  • Fibonacci number by Dynamic Programming.
  • Approximate String Matching.
  • Longest Increasing subsequence.
  • Minimum Weight Triangulation

• Sets and strings both represent collections of objects—the difference is whether order matters. Sets are collections of symbols whose order is assumed to carry no significance, while strings are defined by the sequence or arrangement of symbols.

• The assumption of a fixed order makes it possible to solve string problems much more efficiently than set problems, through techniques such as dynamic programming and advanced data structures like suffix trees. The interest in and importance of string-processing algorithms have been increasing due to bioinformatics, Web searches, and other text-processing applications. Recent books on string algorithms include:

  • Longest Common Substring
    • The longest common substring of a set of strings can be identified in linear time using suffix trees, as discussed in Section 12.3 (page 377). The trick is to build a suffix tree containing all the strings, label each leaf with the input string it represents, and then do a depth-first traversal to identify the deepest node with descendants from each input string
  • Approximate String Matching
    • A text string t and a pattern string p.
    • : What is the minimum-cost way to transform t to p using insertions, deletions, and substitutions?
  • String Matching.
    • A text string t of length n. A pattern string p of length m.
    • find all the patters of instances of pattern p in the text.
  • Set Packing
    • Select and collection of mutually disjoint subset from S whose union is an universal set.
  • Set Cover.
    • A collection of Sub set of the Universal set. ———————————————————————————————————————————————— Connected Components.

• A directed or Undirected Graph.
  • Identify the different pieces or components of G, where vertices x and y are members of different components if no path exists from x to y in G.
  • The connected components of a graph represent, in grossest terms, the pieces of the graph. Two vertices are in the same component of G if and only if there exists some path between them.
  • Testing whether a graph is connected is an essential preprocessing step for every graph algorithm. Subtle, hard-to-detect bugs often result when an algorithm is run only on one component of a disconnected graph. Connectivity tests are so quick and easy that you should always verify the integrity of your input graph, even when you know for certain that it has to be connected.
  • Testing the connectivity of any undirected graph is a job for either depth-first or breadth-first search, as discussed in Section 5 (page 145). Which one you choose doesn’t really matter. Both traversals initialize the component-number field for each vertex to 0, and then start the search for component 1 from vertex v1. As each vertex is discovered, the value of this field is set to the current component
  • umber. When the initial traversal ends, the component number is incremented, and the search begins again from the first vertex whose component-number remains 0. Properly implemented using adjacency lists (as is done in Section 5.7.1 (page 166)) this runs in O(n + m) time. Other notions of connectivity also arise in practice:

What if my graph is directed? – There are two distinct notions of connected components for directed graphs. A directed graph is weakly connected if it would be connected by ignoring the direction of edges. Thus, a weakly connected graph consists of a single piece.

1. A directed graph is strongly connected if there is a directed path between every pair of vertices. This distinction is best made clear by considering the network of one- and two-way streets in any city. The network is strongly connected if it is possible to drive legally between every two positions. The network is weakly connected when it is possible to drive legally or illegally between every two positions. The network is disconnected if there is no possible way to drive from a to b.
2. Weakly and strongly connected components define unique partitions of the vertices. The output figure at the beginning of this section illustrates a directed graph consisting of two weakly or five strongly-connected components (also called blocks of G).

What is the weakest point in my graph/network? – A chain is only as strong as its weakest link. Losing one or more internal links causes a chain to become disconnected. The connectivity of graphs measures their strength—how many edges or vertices must be removed to disconnect it. Connectivity is an essential invariant for network design and other structural problems. Algorithmic connectivity problems are discussed in Section 15.8 (page 505). In particular, biconnected components are pieces of the graph that result from cutting the edges incident on a single vertex.

All biconnected components can be found in linear time using DFS. See Section 5.9.2 (page 173) for an implementation of this algorithm. Vertices whose deletion disconnects the graph belong to more than one biconnected component, whose edges are uniquely partitioned by components. • Is the graph a tree? How can I find a cycle if one exists? – The problem of cycle identification often arises, particularly with respect to directed graphs. For example, testing if a sequence of conditions can deadlock often reduces to cycle detection. If I am waiting for Fred, and Fred is waiting for Mary, and Mary is waiting for me, there is a cycle and we are all deadlocked. For undirected graphs, the analogous problem is tree identification. A tree is, by definition, an undirected, connected graph without any cycles. As described above, a depth-first search can be used to test whether it is connected. If the graph is connected and has n − 1 edges for n vertices, it is a tree. Depth-first search can be used to find cycles in both directed and undirected graphs. Whenever we encounter a back edge in our DFS—i.e. , an edge to an ancestor vertex in the DFS tree—the back edge and the tree together define a directed cycle. No other such cycle can exist in a directed graph. Directed graphs without cycles are called DAGs (directed acyclic graphs). Topological sorting (see Section 15.2 (page 481)) is the fundamental operation on DAGs

• What is the weakest point in my graph/network? – A chain is only as strong as its weakest link. Losing one or more internal links causes a chain to become disconnected. The connectivity of graphs measures their strength—how many edges or vertices must be removed to disconnect it. Connectivity is an essential invariant for network design and other structural problems. Algorithmic connectivity problems are discussed in Section 15.8 (page 505). In particular, biconnected components are pieces of the graph that result from cutting the edges incident on a single vertex. All biconnected components can be found in linear time using DFS. See Section 5.9.2 (page 173) for an implementation of this algorithm. Vertices whose deletion disconnects the graph belong to more than one biconnected component, whose edges are uniquely partitioned by components

Is the graph a tree? How can I find a cycle if one exists? – The problem of cycle identification often arises, particularly with respect to directed graphs. For example, testing if a sequence of conditions can deadlock often reduces to cycle detection. If I am waiting for Fred, and Fred is waiting for Mary, and Mary is waiting for me, there is a cycle and we are all deadlocked. For undirected graphs, the analogous problem is tree identification. A tree is, by definition, an undirected, connected graph without any cycles. As described above, a depth-first search can be used to test whether it is connected. If the graph is connected and has n − 1 edges for n vertices, it is a tree. Depth-first search can be used to find cycles in both directed and undirected graphs. Whenever we encounter a back edge in our DFS—i.e. , an edge to an ancestor vertex in the DFS tree—the back edge and the tree together define a directed cycle. No other such cycle can exist in a directed graph. Directed graphs without cycles are called DAGs (directed acyclic graphs). Topological sorting (see Section 15.2 (page 481)) is the fundamental operation on DAGs.

Topological Sort A directed acyclic graph G = (V,E), also known as a partial order or poset.

Find a linear ordering of the vertices of V such that for each edge (i,j) ∈ E, vertex i is to the left of vertex j.

: Topological sorting arises as a subproblem in most algorithms on directed acyclic graphs. Topological sorting orders the vertices and edges of a DAG in a simple and consistent way and hence plays the same role for DAGs that a depth-first search does for general graphs. Topological sorting can be used to schedule tasks under precedence constraints. Suppose we have a set of tasks to do, but certain tasks have to be performed before other tasks. These precedence constraints form a directed acyclic graph, and any topological sort (also known as a linear extension) defines an order to do these tasks such that each is performed only after all of its constraints are satisfied. Three important facts about topological sorting are

1. Only DAGs can be topologically sorted, since any directed cycle provides an inherent contradiction to a linear order of tasks.

2. Every DAG can be topologically sorted, so there must always be at least one schedule for any reasonable precedence constraints among jobs.

3. DAGs can often be topologically sorted in many different ways, especially when there are few constraints. Consider n unconstrained jobs. Any of the n! permutations of the jobs constitutes a valid topological ordering.

79). Two special considerations with respect to topological sorting are: • What if I need all the linear extensions, instead of just one of them? – In certain applications, it is important to construct all linear extensions of a DAG. Beware, because the number of linear extensions can grow exponentially in the size of the graph. Even the problem of counting the number of linear extensions is NP-hard. Algorithms for listing all linear extensions in a DAG are based on backtracking. They build all possible orderings from left to right, where each of the in-degree zero vertices are candidates for the next vertex. The outgoing edges from the selected vertex are deleted before moving on. An optimal algorithm for listing (or counting) linear extensions is discussed in the notes. Algorithms for constructing random linear extensions start from an arbitrary linear extension. We then repeatedly sample pairs of vertices. These are exchanged if the resulting permutation remains a topological ordering. This results in a random linear extension given enough random samples. See the Notes section for details.

What if your graph is not acyclic? – When a set of constraints contains inherent contradictions, the natural problem becomes removing the smallest set of items that eliminates all inconsistencies. The sets of offending jobs (vertices) or constraints (edges) whose deletion leaves a DAG are known as the feedback vertex set and the feedback arc set, respectively. They are discussed in Section 16.11 (page 559). Unfortunately, both problems are NPcomplete. Since the topological sorting algorithm gets stuck as soon as it identifies a vertex on a directed cycle, we can delete the offending edge or vertex and continue. This quick-and-dirty heuristic will eventually leave a DAG, but might delete more things than necessary. Section 9.10.3 (page 348) describes a better approach to the problem.

——————————————————————————————————————————————————————

• MinimumSpanningTrees
  • A graph G = (V,E) with weighted edges.
  • The minimum weight subset of edges E ⊂ E that form a tree on V The minimum spanning tree (MST) of a graph defines the cheapest subset of edges that keeps the graph in one connected component. Telephone companies are interested in minimum spanning trees, because the MST of a set of locations defines the wiring scheme that connects the sites using as little wire as possible. MST is the mother of all network design problems. Minimum spanning trees prove important for several reasons: • They can be computed quickly and easily, and create a sparse subgraph that reflects a lot about the original graph. • They provide a way to identify clusters in sets of points. Deleting the long edges from an MST leaves connected components that define natural clusters in the data set, as shown in the output figure above. • They can be used to give approximate solutions to hard problems such as Steiner tree and traveling salesman. • As an educational tool, MST algorithms provide graphic evidence that greedy algorithms can give provably optimal solutions.

Three classical algorithms efficiently construct MSTs. Detailed implementations of two of them (Prim’s and Kruskal’s) are given with correctness arguments in Section 6.1 (page 192). The third somehow manages to be less well known despite being invented first and (arguably) being both easier to implement and more efficient. The contenders are —————————————————————————————————————————— • Kruskal’s algorithm – Each vertex starts as a separate tree and these trees merges together by repeatedly adding the lowest cost edge that spans two distinct subtrees (i.e. , does not create a cycle). Kruskal(G) Sort the edges in order of increasing weight count = 0 while (count < n − 1) do get next edge (v,w) if (component (v) �= component(w)) add to T component(v) = component(w) The “which component?” tests can be efficiently implemented using the union-find data structure (Section 12.5 (page 385)) to yield an O(m lg m) algorithm.

—————————————————————————————————————————— Prim’s algorithm – Starts with an arbitrary vertex v and “grows” a tree from it, repeatedly finding the lowest-cost edge that links some new vertex into this tree. During execution, we label each vertex as either in the tree, in the fringe (meaning there exists an edge from a tree vertex), or unseen (meaning the vertex is still more than one edge away from the tree). Prim(G) Select an arbitrary vertex to start While (there are fringe vertices) select minimum-weight edge between tree and fringe add the selected edge and vertex to the tree update the cost to all affected fringe vertices This creates a spanning tree for any connected graph, since no cycle can be introduced via edges between tree and fringe vertices. That it is in fact a tree of minimum weight can be proven by contradiction. With simple data structures, Prim’s algorithm can be implemented in O(n2) time

—————————————————————————————————————————— Boruvka’s algorithm – Rests on the observation that the lowest-weight edge incident on each vertex must be in the minimum spanning tree. The union of these edges will result in a spanning forest of at most n/2 trees. Now for each of these trees T, select the edge (x,y) of lowest weight such that x ∈ T and 486 15. GRAPH PROBLEMS: POLYNOMIAL-TIME y �∈ T. Each of these edges must again be in an MST, and the union again results in a spanning forest with at most half as many trees as before: Boruvka(G) Initialize spanning forest F to n single-vertex trees While (F has more than one tree) for each T in F, find the smallest edge from T to G − T add all selected edges to F, thus merging pairs of trees The number of trees are at least halved in each round, so we get the MST after at most lg n iterations, each of which takes linear time. This gives an O(m log n) algorithm without using any fancy data structures. MST is only one of several spanning tree problems that arise in practice. The following questions will help you sort your way through them: —————————————————————————————————————————— 15.4 Shortest Path

• An edge-weighted graph G, with vertices s and t. The problem of finding shortest paths in a graph has several applications, some quite surprising:

• The most obvious applications arise in transportation or communications, such as finding the best route to drive between Chicago and Phoenix or figuring how to direct packets to a destination across a network.
• Consider the task of partitioning a digitized image into regions containing distinct objects—a problem known as image segmentation. Separating lines are needed to carve the space into regions, but what path should these lines take through the grid? We may want a line that relatively directly goes from x to y, but avoids cutting through object pixels as much as possible. This grid of pixels can be modeled as a graph, with the cost of an edge reflecting the color transitions between neighboring pixels. The shortest path from x to y in this weighted graph defines the best separating line.

Transitive Closure and Reductio n: For transitive closure, construct a graph G = (V,E ) with edge (i,j) ∈ E iff there is a directed path from i to j in G. For transitive reduction, construct a small graph G = (V,E ) with a directed path from i to j in G iff there is a directed path from i to j in G. Dis
——— ——— ——— ——— ——— ——— ——— ——— ——— Matching Problem

Input description: A (weighted) graph G = (V,E). Problem description: Find the largest set of edges E from E such that each vertex in V is incident to at most one edge of E .

——— ——— ——— ——— ——— ——— ——— ——— ——— 15.7 Eulerian Cycle/Chinese Postman

——— ——— ——— ——— ——— ——— ——— ——— ——— 15.8 Edge and Vertex Connectivity

——— ——— ——— ——— ——— ——— ——— ——— ——— 15.9 Network Flow ——— ——— ——— ——— ——— ——— ——— ——— ———

Knowledge based Problems on Java: http://www.geeksforgeeks.org/java/ Knowledge based Questions of C: http://www.geeksforgeeks.org/c/ Knowledge based problems in Python: http://www.geeksforgeeks.org/python/

Grap

The Problem 2 Sum

BruteForce public int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { ret
urn new int[] { i, j }; } } } throw new IllegalArgumentException("No two sum solution"); } Time Complexity = O(n2); Space Complexity = O(1);

To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { i, map.get(complement) }; } } throw new IllegalArgumentException("No two sum solution"); }

Time Complexity= O(n) Space complexity = O(n)

public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } Time Complexity: O(n) Space complexity: O(n) ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— The Problem 3 Sum

——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— The Problem 4 Sum

——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— 3Sum Closet Misc Graph Questions.

1. Delete a vertex without disconnecting a graph. Given a connected graph, design a linear-time algorithm to find a vertex whose removal (deleting the vertex and all incident edges) does not disconnect the graph. Hint 1 (using DFS): run DFS from some vertex s and consider the first vertex in DFS that finishes. Hint 2 (using BFS): run BFS from some vertex s and consider any vertex with the highest distance.
2. All paths in a graph. Write a program AllPaths.java that enumerates all simple paths in a graph between two specified vertices. Hint: use DFS and backtracking. Warning: there many be exponentially many simple paths in a graph, so no algorithm can run efficiently for large graphs.
3. Degree. The degree of a vertex is the number of incident edges. Add a method int degree(int v) to Graph that returns the degree of the vertex v.
4. Suppose you use a stack instead of a queue when running breadth-first search. Does it still compute shortest paths?
5. DFS with an explicit stack. Give an example of possibility of stack overflow with DFS using the function call stack, e.g., line graph. Modify DepthFirstPaths.java so that it uses an explicit stack instead of the function call stack.
6. Perfect maze. Generate a perfect maze like this one 

7.  6.  
   

 8. 
Write a program Maze.java that takes a command line parameter N, and generates a random N-by-N perfect maze. A maze is perfect if it has exactly one path between every pair of points in the maze, i.e., no inaccessible locations, no cycles, and no open spaces. Here's a nice algorithm to generate such mazes. Consider an N-by-N grid of cells, each of which initially has a wall between it and its four neighboring cells. For each cell (x, y), maintain a variable north[x][y] that is true if there is wall separating (x, y) and (x, y + 1). We have analogous variables east[x][y], south[x][y], andwest[x][y] for the corresponding walls. Note that if there is a wall to the north of (x, y) then north[x][y] = south[x][y+1] = true. Construct the maze by knocking down some of the walls as follows: * Start at the lower level cell (1, 1). * Find a neighbor at random that you haven't yet been to. * If you find one, move there, knocking down the wall. If you don't find one, go back to the previous cell. * Repeat steps ii. and iii. until you've been to every cell in the grid. 9. Hint: maintain an (N+2)-by-(N+2) grid of cells to avoid tedious special cases.
 10. Getting out of the maze. Given an N-by-N maze (like the one created in the previous exercise), write a program to find a path from the start cell (1, 1) to the finish cell (N, N), if it exists. To find a solution to the maze, run the following algorithm, starting from (1, 1) and stopping if we reach cell (N, N) explore(x, y) 11. ------------- 12. - Mark the current cell (x, y) as "visited." 13. - If no wall to north and unvisited, then explore(x, y+1). 14. - If no wall to east and unvisited, then explore(x+1, y). 15. - If no wall to south and unvisited, then explore(x, y-1). 16. - If no wall to west and unvisited, then explore(x-1, y). 17. 
 18. 
 18. Maze game. Develop a maze game like this one from gamesolo.com, where you traverse a maze, collecting prizes. 19. Actor graph. An alternate (and perhaps more natural) way to compute Kevin Bacon numbers is to build a graph where each node is an actor. Two actors are connected by an edge if they appear in a movie together. Calculate Kevin Bacon numbers by running BFS on the actor graph. Compare the running time versus the algorithm described in the text. Explain why the approach in the text is preferable. Answer: it avoids multiple parallel edges. As a result, it's faster and uses less memory. Moreover, it's more convenient since you don't have to label the edges with the movie names - all names get stored in the vertices. 20. Center of the Hollywood universe. We can measure how good of a center that Kevin Bacon is by computing their Hollywood number. The Hollywood number of Kevin Bacon is the average Bacon number of all the actors. The Hollywood number of another actor is computed the same way, but we make them be the source instead of Kevin Bacon. Compute Kevin Bacon's Hollywood number and find an actor and actress with better Hollywood numbers. 21. Fringe of the Hollywood universe. Find the actor (who is connected to Kevin Bacon) that has the highest Hollywood number. 22. Word ladders. Write a program WordLadder.java that takes two 5 letter strings from the command line, and reads in a list of 5 letter words from standard input, and prints out a shortest word ladder connecting the two strings (if it exists). Two words can be connected in a word ladder chain if they differ in exactly one letter. As an example, the following word ladder connects green and brown. 23. green greet great groat groan grown brown 24. 
 26. 
You can also try out your program on this list of 6 letter words.
 25. Faster word ladders. To speed things up (if the word list is very large), don't write a nested loop to try all pairs of words to see if they are adjacent. To handle 5 letter words, first sort the word list. Words that only differ in their last letter will appear consecutively in the sorted list. Sort 4 more times, but cyclically shift the letters one position to the right so that words that differ in the ith letter will appear consecutively in one of the sorted lists.Try out this approach using a larger word list with words of different sizes. Two words of different lengths are neighbors if the smaller word is the same as the bigger word, minus the last letter, e.g., brow and brown.
 26. Suppose you delete all of the bridges in an undirected graph. Are the connected components of the resulting graph the biconnected components? Answer: no, two biconnected components can be connected through an articulation point.
Bridges and articulation points. A bridge (or cut edge) is an edge whose removal disconnects the graph. An articulation point (or cut vertex) is a vertex whose removal (and removal of all incident edges) disconnects the remaining graph. Bridges and articulations points are important because they represent a single point of failure in a network. Brute force: delete edge (or vertex) and check connectivity. Takes O(E(V + E)) and O(V(V + E)) time, respectively. Can improve both to O(E + V) using clever extension to DFS.
 27. Biconnected components. An undirected graph is biconnected if for every pair of vertices v and w, there are two vertex-disjoint paths between v and w. (Or equivalently a simple cycle through any two vertices.) We define a cocyclicity equivalence relation on the edges: two edges e1 and e2 are are in same biconnected component if e1 = e2 or there exists a cycle containing both e1 and e2. Two biconnected components share at most one vertex in common. A vertex is an articulation point if and only if it is common to more than one biconnected component. Program Biconnected.javaidentifies the bridges and articulation points.
 28. Biconnected components. Modify Biconnected to print out the edges that constitute each biconnected component. Hint: each bridge is its own biconnected component; to compute the other biconnected components, mark each articulation point as visited, and then run DFS, keeping track of the edges discovered from each DFS start point.
 29. Perform numerical experiments on the number of connected components for random undirected graphs. Phase change around 1/2 V ln V. (See Property 18.13 in Algs Java.) 30. Rogue. (Andrew Appel.) A monster and a player are each located at a distinct vertex in an undirected graph. In the role playing game Rogue, the player and the monster alternate turns. In each turn the player can move to an adjacent vertex or stays put. Determine all vertices that the player can reach before the monster. Assume the player gets the first move. 31. Rogue. (Andrew Appel.) A monster and a player are each located at a distinct vertex in an undirected graph. The goal of the monster is to land on the same vertex as the player. Devise an optimal strategy for the monster. 32. Articulation point. Let G be a connected, undirected graph. Consider a DFS tree for G. Prove that vertex v is an articulation point of G if and only if either (i) v is the root of the DFS tree and has more than one child or (ii) v is not the root of the DFS tree and for some child w of v there is no back edge between any descendant of w (including w) and a proper ancestor of v. In other words, v is an articulation point if and only if (i) v is the root and has more than one child or (ii) v has a child w such that low[w] >= pre[v]. 33. Sierpinski gasket. Nice example of an Eulerian graph. 34. Preferential attachment graphs. Create a random graph on V vertices and E edges as follows: start with V vertices v1, .., vn in any order. Pick an element of sequence uniformly at random and add to end of sequence. Repeat 2E times (using growing list of vertices). Pair up the last 2E vertices to form the graph.Roughly speaking, it's equivalent to adding each edge one-by-one with probability proportional to the product of the degrees of the two endpoints. Reference.

 35. Wiener index. The Wiener index of a vertex is the sum of the shortest path distances between v and all other vertices. The Wiener index of a graph G is the sum of the shortest path distances over all pairs of vertices. Used by mathematical chemists (vertices = atoms, edges = bonds).
 36. Random walk. Easy algorithm for getting out of a maze (or st connectivity in a graph): at each step, take a step in a random direction. With complete graph, takes V log V time (coupon collector); for line graph or cycle, takes V^2 time (gambler's ruin). In general the cover time is at most 2E(V-1), a classic result of Aleliunas, Karp, Lipton, Lovasz, and Rackoff.
 37. Deletion order. Given a connected graph, determine an order to delete the vertices such that each deletion leaves the (remaining) graph connected. Your algorithm should take time proportional to V + E in the worst case.
 38. Center of a tree. Given a graph that is a tree (connected and acyclic), find a vertex such that its maximum distance from any other vertex is minimized.Hint: find the diameter of the tree (the longest path between two vertices) and return a vertex in the middle.
 39. Diameter of a tree. Given a graph that is a tree (connected and acyclic), find the longest path, i.e., a pair of vertices v and w that are as far apart as possible. Your algorithm should run in linear time.Hint. Pick any vertex v. Compute the shortest path from v to every other vertex. Let w be the vertex with the largest shortest path distance. Compute the shortest path from w to every other vertex. Let x be the vertex with the largest shortest path distance. The path from w to x gives the diameter.

 40. Bridges with union-find. Let T be a spanning tree of a connected graph G. Each non-tree edge e in G forms a fundamental cycle consisting of the edge e plus the unique path in the tree joining its endpoings. Show that an edge is a bridge if and only if it is not on some fundamental cycle. Thus, all bridges are edges of the spanning tree. Design an algorithm to find all of the bridges (and bridge components) using E + V time plus E + V union-find operations.
 41. Nonrecursive depth-first search. Write a program NonrecursiveDFS.java that implements depth-first search with an explicit stack instead of recursion.Here is an alternate implementation suggested by Bin Jiang in the early 1990s. The only extra memory is for a stack of vertices but that stack must support arbitrary deletion (or at least the movement of an arbitrary item to the top of the stack). 42. private void dfs(Graph G, int s) { 43. SuperStack stack = new SuperStack(); 44. stack.push(s); 45. while (!stack.isEmpty()) { 46. int v = stack.peek(); 47. if (!marked[v]) { 48. marked[v] = true; 49. for (int w : G.adj(v)) { 50. if (!marked[w]) { 51. if (stack.contains(w)) stack.delete(w); 52. stack.push(w); 53. } 54. } 55. } 56. else { 57. // v's adjacency list is exhausted 58. stack.pop(); 59. } 60. } 61. } 62. 
 65. 
Here is yet another implementation. It is, perhaps, the simplest nonrecursive implementation, but it uses space proportional to E + V in the worst case (because more than one copy of a vertex can be on the stack) and it explores the vertices adjacent to v in the reverse order of the standard recursive DFS. Also, an edgeTo[v]entry may be updated more than once, so it may not be suitable for backtracking applications. 63. private void dfs(Graph G, int s) { 64. Stack stack = new Stack(); 65. stack.push(s); 66. while (!stack.isEmpty()) { 67. int v = stack.pop(); 68. if (!marked[v]) { 69. marked[v] = true; 70. for (int w : G.adj(v)) { 71. if (!marked[w]) { 72. edgeTo[w] = v; 73. stack.push(w); 74. } 75. } 76. } 77. } 78. } 79. 
 83. 

 80. Nonrecursive depth-first search. Explan why the following nonrecursive method (analogous to BFS but using a stack instead of a queue) does not implement depth-first search. 81. private void dfs(Graph G, int s) { 82. Stack stack = new Stack(); 83. stack.push(s); 84. marked[s] = true; 85. while (!stack.isEmpty()) { 86. int v = stack.pop(); 87. for (int w : G.adj(v)) { 88. if (!marked[w]) { 89. stack.push(w); 90. marked[w] = true; 91. edgeTo[w] = v; 92. } 93. } 94. } 95. } 96. 
 101. 
Solution: Consider the graph consisting of the edges 0-1, 0-2, 1-2, and 2-1, with vertex 0 as the source.
 97. Matlab connected components. bwlabel() or bwlabeln() in Matlab label the connected components in a 2D or kD binary image. bwconncomp() is newer version. 98. Shortest path in complement graph. Given a graph G, design an algorithm to find the shortest path (number of edges) between s and every other vertex in the complement graph G'. The complement graph contains the same vertices as G but includes an edge v-w if and only if the edge v-w is not in G. Can you do any better than explicitly computing the complement graph G' and running BFS in G'? 99. Delete a vertex without disconnecting a graph. Given a connected graph, design a linear-time algorithm to find a vertex whose removal (deleting the vertex and all incident edges) does not disconnect the graph.Hint 1 (using DFS): run DFS from some vertex s and consider the first vertex in DFS that finishes.
Hint 2 (using BFS): run BFS from some vertex s and consider any vertex with the highest distance.
 100. Spanning tree. Design an algorithm that computes a spanning tree of a connected graph is time proportional to V + E. Hint: use either BFS or DFS. 101. All paths in a graph. Write a program AllPaths.java that enumerates all simple paths in a graph between two specified vertices. Hint: use DFS and backtracking. Warning: there many be exponentially many simple paths in a graph, so no algorithm can run efficiently for large graphs. 102. Degree. The degree of a vertex is the number of incident edges. Add a method int degree(int v) to Graph that returns the degree of the vertex v. 103. Suppose you use a stack instead of a queue when running breadth-first search. Does it still compute shortest paths? 104. DFS with an explicit stack. Give an example of possibility of stack overflow with DFS using the function call stack, e.g., line graph. Modify DepthFirstPaths.java so that it uses an explicit stack instead of the function call stack. 105. Perfect maze. Generate a perfect maze like this one  106. 6.
 107. 
Write a program Maze.java that takes a command line parameter N, and generates a random N-by-N perfect maze. A maze is perfect if it has exactly one path between every pair of points in the maze, i.e., no inaccessible locations, no cycles, and no open spaces. Here's a nice algorithm to generate such mazes. Consider an N-by-N grid of cells, each of which initially has a wall between it and its four neighboring cells. For each cell (x, y), maintain a variable north[x][y] that is true if there is wall separating (x, y) and (x, y + 1). We have analogous variables east[x][y], south[x][y], andwest[x][y] for the corresponding walls. Note that if there is a wall to the north of (x, y) then north[x][y] = south[x][y+1] = true. Construct the maze by knocking down some of the walls as follows: * Start at the lower level cell (1, 1). * Find a neighbor at random that you haven't yet been to. * If you find one, move there, knocking down the wall. If you don't find one, go back to the previous cell. * Repeat steps ii. and iii. until you've been to every cell in the grid. 108. Hint: maintain an (N+2)-by-(N+2) grid of cells to avoid tedious special cases.
 109. Getting out of the maze. Given an N-by-N maze (like the one created in the previous exercise), write a program to find a path from the start cell (1, 1) to the finish cell (N, N), if it exists. To find a solution to the maze, run the following algorithm, starting from (1, 1) and stopping if we reach cell (N, N). 110. explore(x, y) 111. ------------- 112. - Mark the current cell (x, y) as "visited." 113. - If no wall to north and unvisited, then explore(x, y+1). 114. - If no wall to east and unvisited, then explore(x+1, y). 115. - If no wall to south and unvisited, then explore(x, y-1). 116. - If no wall to west and unvisited, then explore(x-1, y). 117. 
 18. 
 118. Maze game. Develop a maze game like this one from gamesolo.com, where you traverse a maze, collecting prizes. 119. Actor graph. An alternate (and perhaps more natural) way to compute Kevin Bacon numbers is to build a graph where each node is an actor. Two actors are connected by an edge if they appear in a movie together. Calculate Kevin Bacon numbers by running BFS on the actor graph. Compare the running time versus the algorithm described in the text. Explain why the approach in the text is preferable. Answer: it avoids multiple parallel edges. As a result, it's faster and uses less memory. Moreover, it's more convenient since you don't have to label the edges with the movie names - all names get stored in the vertices. 120. Center of the Hollywood universe. We can measure how good of a center that Kevin Bacon is by computing their Hollywood number. The Hollywood number of Kevin Bacon is the average Bacon number of all the actors. The Hollywood number of another actor is computed the same way, but we make them be the source instead of Kevin Bacon. Compute Kevin Bacon's Hollywood number and find an actor and actress with better Hollywood numbers. 121. Fringe of the Hollywood universe. Find the actor (who is connected to Kevin Bacon) that has the highest Hollywood number. 122. Word ladders. Write a program WordLadder.java that takes two 5 letter strings from the command line, and reads in a list of 5 letter words from standard input, and prints out a shortest word ladder connecting the two strings (if it exists). Two words can be connected in a word ladder chain if they differ in exactly one letter. As an example, the following word ladder connects green and brown. 123. green greet great groat groan grown brow
You can also try out your program on this list of 6 letter words.
 124. Faster word ladders. To speed things up (if the word list is very large), don't write a nested loop to try all pairs of words to see if they are adjacent. To handle 5 letter words, first sort the word list. Words that only differ in their last letter will appear consecutively in the sorted list. Sort 4 more times, but cyclically shift the letters one position to the right so that words that differ in the ith letter will appear consecutively in one of the sorted lists.Try out this approach using a larger word list with words of different sizes. Two words of different lengths are neighbors if the smaller word is the same as the bigger word, minus the last letter, e.g., brow and brown.
 125. Suppose you delete all of the bridges in an undirected graph. Are the connected components of the resulting graph the biconnected components? Answer: no, two biconnected components can be connected through an articulation point.
Bridges and articulation points. A bridge (or cut edge) is an edge whose removal disconnects the graph. An articulation point (or cut vertex) is a vertex whose removal (and removal of all incident edges) disconnects the remaining graph. Bridges and articulations points are important because they represent a single point of failure in a network. Brute force: delete edge (or vertex) and check connectivity. Takes O(E(V + E)) and O(V(V + E)) time, respectively. Can improve both to O(E + V) using clever extension to DFS.
 126. Biconnected components. An undirected graph is biconnected if for every pair of vertices v and w, there are two vertex-disjoint paths between v and w. (Or equivalently a simple cycle through any two vertices.) We define a cocyclicity equivalence relation on the edges: two edges e1 and e2 are are in same biconnected component if e1 = e2 or there exists a cycle containing both e1 and e2. Two biconnected components share at most one vertex in common. A vertex is an articulation point if and only if it is common to more than one biconnected component. Program Biconnected.javaidentifies the bridges and articulation points.
 127. Biconnected components. Modify Biconnected to print out the edges that constitute each biconnected component. Hint: each bridge is its own biconnected component; to compute the other biconnected components, mark each articulation point as visited, and then run DFS, keeping track of the edges discovered from each DFS start point.
 128. Perform numerical experiments on the number of connected components for random undirected graphs. Phase change around 1/2 V ln V. (See Property 18.13 in Algs Java.) 129. Rogue. (Andrew Appel.) A monster and a player are each located at a distinct vertex in an undirected graph. In the role playing game Rogue, the player and the monster alternate turns. In each turn the player can move to an adjacent vertex or stays put. Determine all vertices that the player can reach before the monster. Assume the player gets the first move. 130. Rogue. (Andrew Appel.) A monster and a player are each located at a distinct vertex in an undirected graph. The goal of the monster is to land on the same vertex as the player. Devise an optimal strategy for the monster. 131. Articulation point. Let G be a connected, undirected graph. Consider a DFS tree for G. Prove that vertex v is an articulation point of G if and only if either (i) v is the root of the DFS tree and has more than one child or (ii) v is not the root of the DFS tree and for some child w of v there is no back edge between any descendant of w (including w) and a proper ancestor of v. In other words, v is an articulation point if and only if (i) v is the root and has more than one child or (ii) v has a child w such that low[w] >= pre[v]. 132. Sierpinski gasket. Nice example of an Eulerian graph. 133. Preferential attachment graphs. Create a random graph on V vertices and E edges as follows: start with V vertices v1, .., vn in any order. Pick an element of sequence uniformly at random and add to end of sequence. Repeat 2E times (using growing list of vertices). Pair up the last 2E vertices to form the graph.Roughly speaking, it's equivalent to adding each edge one-by-one with probability proportional to the product of the degrees of the two endpoints. Reference.

 134. Wiener index. The Wiener index of a vertex is the sum of the shortest path distances between v and all other vertices. The Wiener index of a graph G is the sum of the shortest path distances over all pairs of vertices. Used by mathematical chemists (vertices = atoms, edges = bonds).
 135. Random walk. Easy algorithm for getting out of a maze (or st connectivity in a graph): at each step, take a step in a random direction. With complete graph, takes V log V time (coupon collector); for line graph or cycle, takes V^2 time (gambler's ruin). In general the cover time is at most 2E(V-1), a classic result of Aleliunas, Karp, Lipton, Lovasz, and Rackoff.
 136. Deletion order. Given a connected graph, determine an order to delete the vertices such that each deletion leaves the (remaining) graph connected. Your algorithm should take time proportional to V + E in the worst case.
 137. Center of a tree. Given a graph that is a tree (connected and acyclic), find a vertex such that its maximum distance from any other vertex is minimized.Hint: find the diameter of the tree (the longest path between two vertices) and return a vertex in the middle.
 138. Diameter of a tree. Given a graph that is a tree (connected and acyclic), find the longest path, i.e., a pair of vertices v and w that are as far apart as possible. Your algorithm should run in linear time.Hint. Pick any vertex v. Compute the shortest path from v to every other vertex. Let w be the vertex with the largest shortest path distance. Compute the shortest path from w to every other vertex. Let x be the vertex with the largest shortest path distance. The path from w to x gives the diameter.

 139. Bridges with union-find. Let T be a spanning tree of a connected graph G. Each non-tree edge e in G forms a fundamental cycle consisting of the edge e plus the unique path in the tree joining its endpoings. Show that an edge is a bridge if and only if it is not on some fundamental cycle. Thus, all bridges are edges of the spanning tree. Design an algorithm to find all of the bridges (and bridge components) using E + V time plus E + V union-find operations.
 140. Nonrecursive depth-first search. Write a program NonrecursiveDFS.java that implements depth-first search with an explicit stack instead of recursion.Here is an alternate implementation suggested by Bin Jiang in the early 1990s. The only extra memory is for a stack of vertices but that stack must support arbitrary deletion (or at least the movement of an arbitrary item to the top of the stack). 141. private void dfs(Graph G, int s) { 142. SuperStack stack = new SuperStack(); 143. stack.push(s); 144. while (!stack.isEmpty()) { 145. int v = stack.peek(); 146. if (!marked[v]) { 147. marked[v] = true; 148. for (int w : G.adj(v)) { 149. if (!marked[w]) { 150. if (stack.contains(w)) stack.delete(w); 151. stack.push(w); 152. } 153. } 154. } 155. else { 156. // v's adjacency list is exhausted 157. stack.pop(); 158. } 159. } 160. } 161. 
 65. 
Here is yet another implementation. It is, perhaps, the simplest nonrecursive implementation, but it uses space proportional to E + V in the worst case (because more than one copy of a vertex can be on the stack) and it explores the vertices adjacent to v in the reverse order of the standard recursive DFS. Also, an edgeTo[v]entry may be updated more than once, so it may not be suitable for backtracking applications. 162. private void dfs(Graph G, int s) { 163. Stack stack = new Stack(); 164. stack.push(s); 165. while (!stack.isEmpty()) { 166. int v = stack.pop(); 167. if (!marked[v]) { 168. marked[v] = true; 169. for (int w : G.adj(v)) { 170. if (!marked[w]) { 171. edgeTo[w] = v; 172. stack.push(w); 173. } 174. } 175. } 176. } 177. } 178. 
 83. 

 179. Solution: Consider the graph consisting of the edges 0-1, 0-2, 1-2, and 2-1, with vertex 0 as the source.
 180. Matlab connected components. bwlabel() or bwlabeln() in Matlab label the connected components in a 2D or kD binary image. bwconncomp() is newer version. 181. Shortest path in complement graph. Given a graph G, design an algorithm to find the shortest path (number of edges) between s and every other vertex in the complement graph G'. The complement graph contains the same vertices as G but includes an edge v-w if and only if the edge v-w is not in G. Can you do any better than explicitly computing the complement graph G' and running BFS in G'? 182. Delete a vertex without disconnecting a graph. Given a connected graph, design a linear-time algorithm to find a vertex whose removal (deleting the vertex and all incident edges) does not disconnect the graph.Hint 1 (using DFS): run DFS from some vertex s and consider the first vertex in DFS that finishes.
Hint 2 (using BFS): run BFS from some vertex s and consider any vertex with the highest distance. 183. Spanning tree. Design an algorithm that computes a spanning tree of a connected graph is time proportional to V + E. Hint: use either BFS or DFS. 184. All paths in a graph. Write a program AllPaths.java that enumerates all simple paths in a graph between two specified vertices. Hint: use DFS and backtracking. Warning: there many be exponentially many simple paths in a graph, so no algorithm can run efficiently for large graphs.

Anagrams in the String

find all the anagram of the string p and form a string array. take each string array and then apply the best string matching algorithm. ———————————————————————————————————————— Strong Password Checker

1. Between 6 characters and 20 character.
2. one lower case and one upper case and atlas one digit.
3. three repeating characters.

return minimum no of changes required to make it strong.

check for the length first, if the length is not between 0 and 20. increase the count; convert it to character array and check if it has one upper case, one lower case and at least one digit. check for three repeating digits straight.

————————————————————————————————————————

third max no from the array. sort the array. find the third max no. ————————————————————————————————————

three elements with with same difference.

part 1. will be taking 3 arrays and and comparing the differences among them to tell if they are aritchmten or snow. part 2. will break down the arrays in the groups of three and pass it to the function 1 return the no of part 2. that is arithmetic slices.

—— Misc house robbery questions. solve the problem and then translate it in to

1. https://leetcode.com/problems/house-robber/
2. https://leetcode.com/problems/house-robber-ii/

with the Misc problems convert them in to the programming questions. after converting them in to programming questions,

————————————————————————————————————————————— robbing the house. we can only rob adjacent houses. figure out the maximum value of adjacent integers. calculate the amount for the house starting with the index 0: add all of them. calculate the amount for the house starting with the index 1: add all of them.

—————————————————————————————————————————————

total no of course 0 to n-1 to take course 0 you have to take 1. straight case of topological sort.

list of courses will form the vertex of the graph. The dependency among the graph is given.

figure out the topological sort. or the order we will be visiting the vertex. return the vertex. —————————————————————————————————————————————

course schedule. ————————————————————————————————————————————— longest increasing sub sequence is a dynamic programming question. ————————————————————————————————————————————— remove invalid parenthesis: use the stack to solve the problem. —————————————————————————————————————————————— find the smallest no from the left and the largest number from the right. ————————————————————————————————————————————————

1. Practice all the graph questions.
2. Practice all the linked list questions.
3. Practice all the binary search tree questions.
4. Practice all the questions that can be solved by backtracking
5. Practice all the questions that are of the types Misc Arrays.
6. Practice all the stack based questions. ——————————————————————————————

Misc https://leetcode.com/problems/triangle/ https://leetcode.com/problems/pascals-triangle-ii/ https://leetcode.com/problems/pascals-triangle/

Misc Array based questions https://leetcode.com/problems/bulb-switcher/

convert in to character array. for each character set up a bit set. bites of 26

remove through the bit set and return the list of characters. convert the list of characters in to strings.

Intersection of two arrays.

1 2, 2 1

2,2, sort array 1 0(long) sort array 2. O(Olong) remove duplicates from array 1 O(n) remove duplicates from array 2. O(n) compare both the array and match them keep a count. return the no of counts (O(N).

nlogn. ——— ——— ——— ——— ——— ——— ——— No of Elements in the Array are known. Take a HashMap. # code