Problem: finding subsetsFrom subsets to graphs with bitsWord ladderVocabularyGraph questions/algorithmsVocabulary/TraversalsBreadth first searchGeneral graph traversalBreadth-first searchHow do we search in SequenceSync?Problems with approach?Greedy AlgorithmsDijkstra’s Shortest Path AlgorithmShortest paths, more detailsA Rose by any other name…C or Java?Why do we learn other languages?C++ on two slidesC++ on a second slideHow do we read a file in C++ and Java?How do we read a file in C?CompSci 10012.1Problem: finding subsetsSee CodeBloat APT, requires finding sums of all subsetsGiven {72, 33, 41, 57, 25} what is sum closest (not over) 100?How do we do this in general?Consider three solutions (see also SubsetSums.java)Recursively generate all sums: similar to backtracking•Current value part of sum or not, two recursive callsUse technique like sieve to form all sums•Why is this so fast?Alternative solution for all sums: use bit patterns to represent subsets•What do 10110, 10001, 00111, 00000, and 11111 represent?•How do we generate sums from these representations?CompSci 10012.2From subsets to graphs with bitsWe’ll consider SequenceSync APTWhat is a “vertex” in the graph? Where are arcs?For state-0, we have {1,5,4,2} for transitionsWe’ll consider a graph in which vertices are sets of statesStart with every possible state in our initial vertex0145021023CompSci 10012.3Word ladderCompSci 10012.4VocabularyGraphs are collections of vertices and edges (vertex also called node)Edge connects two vertices•Direction can be important, directed edge, directed graph•Edge may have associated weight/costA vertex sequence v0, v1, …, vn-1 is a path where vk and vk+1 are connected by an edge.If some vertex is repeated, the path is a cycleA graph is connected if there is a path between any pair of verticesNYCPhilBostonWash DC20478190268394LGALAXORDDCA$186$186$412$1701$441CompSci 10012.5Graph questions/algorithmsWhat vertices are reachable from a given vertex?Two standard traversals: depth-first, breadth-firstFind connected components, groups of connected verticesShortest path between any two vertices (weighted graphs?)Breadth first search is storage expensiveDijkstra’s algorithm is efficient, uses a priority queue too!Longest path in a graphNo known efficient algorithmVisit all vertices without repeating? Visit all edges?With minimal cost? Hard!CompSci 10012.6Vocabulary/TraversalsConnected?Connected components?•Weakly connected (directionless)Degree: # edges incident a vertex•indegree (enter), outdegree (exit)Starting at 7 where can we get?Depth-first search, envision each vertex as a room, with doors leading out•Go into a room, mark the room, choose an unused door, exit–Don’t go into a room you’ve already been in (see mark)•Backtrack if all doors used (to room with unused door)Rooms are stacked up, backtracking is really recursionOne alternative uses a queue: breadth-first search1234567CompSci 10012.7Breadth first searchIn an unweighted graph this finds the shortest path between a start vertex and every vertexVisit every node one away from startVisit every node two away from start•This is every node one away from a node one awayVisit every node three away from start, …Put vertex on queue to start (initially just one)Repeat: take vertex off queue, put all adjacent vertices onDon’t put a vertex on that’s already been visited (why?)When are 1-away vertices enqueued? 2-away? 3-away?How many vertices on queue?CompSci 10012.8General graph traversalCOLLECTION_OF_VERTICES fringe;fringe = INITIAL_COLLECTION;while (!fringe.isEmpty()) { Vertex v = fringe.removeItem(QUEUE_FN); if (! MARKED(v)) { MARK(v); VISIT(v); for each edge (v,w) { if (NEEDS_PROCESSING(w)) Add w to fringe according to QUEUE_FN; } }}CompSci 10012.9Breadth-first searchVisit each vertex reachable from some source in breadth-first orderLike level-order traversalQueue fringe;fringe = {v};while (!fringe.isEmpty()) { Vertex v = fringe.dequeue(); if (! getMark(v)) { setMark(v); VISIT(v); for each edge (v,w) { if (MARKED(w)) fringe.enqueue(w); } }}How do we change to make depth-first search?How does the order visited change?1234567CompSci 10012.10How do we search in SequenceSync?Given a vertex (collection of states) how do we determine what vertex it’s connected to?Consider each transition from each state in our vertex (remember this is a set of states)This yields a new set of states/vertex 1-away from vertexWhat does the code look like for bfs? When do we stop? while (q.size() != 0){ TreeSet<Integer> current = q.remove(); for(int k=0; k < 4; k++){ TreeSet<Integer> next = new TreeSet<Integer>(); for(int val : current){ next.add(matrix[val][k]); } q.add(next); // if not already seen } }CompSci 10012.11Problems with approach?Creating sets and looking them up in map takes timeThis solution times out, how to improve it? Don’t represent set of states explicitly, use sequence of bitsSimilar to CodeBloat, advantages? Disadvantages?How do we determine when we’re done?How to store distances (how is array like a map?)Rewrite solution to be efficient using int for setInitial set is all ones, how to make this?CompSci 10012.12Greedy AlgorithmsA greedy algorithm makes a locally optimal decision that leads to a globally optimal solutionHuffman: choose two nodes with minimal weight, combine•Leads to optimal coding, optimal Huffman treeMaking change with American coins: choose largest coin possible as many times as possible•Change for $0.63, change for $0.32•What if we’re out of nickels, change for $0.32?Greedy doesn’t always work, but it does sometimesWeighted shortest path algorithm is Dijkstra’s algorithm, greedy and uses priority queueCompSci 10012.13Dijkstra’s Shortest Path AlgorithmSimilar to breadth first search, but uses a priority queue instead of a queue. Code below is for breadth first search q.dequeue(vertex w) foreach (vertex v adjacent to w) if (distance[v] == INT_MAX) // not visited {distance[v] = distance[w] + 1;q.enqueue(v); }Dijkstra: Find minimal unvisited node, recalculate costs through node q.deletemin(vertex w) foreach (vertex v adjacent to w) if (distance[w] + weight(w,v) < distance[v]) {distance[v] =
View Full Document
Unlocking...