Записки программиста, обо всем и ни о чем. Но, наверное, больше профессионального.

2016-05-12

Exercises

Упражнения и задачки к курсу
Algorithms, Part II. Princeton University, Robert Sedgewick


WordNet (find shortest ancestral path in DAG)

WordNet groups words into sets of synonyms called synsets and describes semantic relationships between them.
One such relationship is the is-a relationship, which connects a hyponym (more specific synset) to a hypernym (more general synset).
For example, a root is a hypernym of carrot and carrot is a hyponym of root.

we have to
– parse CSV files, store data to symbol tables
ST<Integer, String> stable = new ST<>(); // synset id, synset
ST<String, Bag<Integer>> nounstab = new ST<>(); // noun, bag sid
In fh = new In(synsets);
while (fh.hasNextLine()) {
    String[] line = fh.readLine().split(delim);
    int sid = Integer.parseInt(line[0]);
    String[] nouns = line[1].split(" ");
    putNouns2ST(nounstab, nouns, sid);
    stable.put(sid, line[1]); }
– create a Digraph and check it for 'one root DAG' property
Digraph dg = new Digraph(numSynsets());
In fh = new In(hypernyms);
while (fh.hasNextLine()) {
    String[] line = fh.readLine().split(delim);
    int sid = Integer.parseInt(line[0]);
    for (int n = 1; n < line.length; n++) {
        int parentid = Integer.parseInt(line[n]);
        dg.addEdge(sid, parentid); } }
...
DirectedCycle dc = new DirectedCycle(graph);
if (!dc.hasCycle()) {
    for (int v = 0; v < graph.V(); v++)
        if (graph.outdegree(v) == 0) numroots++;
    if (numroots == 1) rdag = true; }
– find shortest ancestral path in DAG
int len = Integer.MAX_VALUE;
int anc = -1;
branchA = new BreadthFirstDirectedPaths(graph, v);
branchB = new BreadthFirstDirectedPaths(graph, w);
for (int n = 0; n < graph.V(); n++) {
    int lenA = branchA.distTo(n);
    int lenB = branchB.distTo(n);
    int nlen = lenA + lenB;
    if (lenA <= numEdges && lenB <= numEdges && nlen < len) {
        len = nlen;
        anc = n; } }

quiz: Minimum Spanning Tree

Which of the following statements about minimum spanning trees (MSTs) are guaranteed to be true in any edge-weighted graph G? Assume that G is connected and has no parallel edge or self-loops. Do not assume the edge weights are distinct unless this is specifically stated. Check all that apply.

– If edge e is a heaviest edge in some cycle C, then there exists a MST which does not contain e.
true
Let T be any MST of G. If edge e is in T, then we are done. Otherwise, assume that edge e is not in T. Consider the cut (A, B) defined by deleting edge e from T. There is (at least) one other edge f in C that crosses the cut. By assumption w(f) ≤ w(e). Thus, replacing edge e with edge f in T yields a MST which contains edge e.

– Let T be a MST of G. Suppose that we decrease the weight of some edge e in T from w(e) to w'(e). Then, T is a MST in the modified edge-weighted graph G'.
true
Let T be any spanning tree in G. If T does not contain edge e, then the weight of T in G equals the weight of T in G'; if T contains edge e, then the weight of T in G is exactly w(e) - w'(e) units more than the weight of T in G'. Thus, T is a MST in G if and only if T is a MST in G

– Let T be a MST of G and let e be an edge in G that is not in T. Then, edge e is a heaviest edge in the cycle C defined by adding edge e to T.
true
Suppose (for the sake of contradiction) that e is not a heaviest edge in C. Let f be a heaviest edge in C. Then, replacing e with f in T yields a lighter spanning tree (a contradiction).

– Let T be a MST of G and let e be an edge in T. Then, edge e is a lightest edge crossing the cut (A, B) defined by deleting edge e from T.
true
Suppose (for the sake of contradiction) that e is not a lightest edge crossing (A, B). Let f be a lightest edge crossing (A, B). Then, replacing e with f in T yields a lighter spanning tree (a contradiction).

– Let T and T' be two MSTs of G. Then, if T contains k edges of weight w, then so does T'. In other words, T and T' have the same sorted list of edge weights.
true
This is a tricky one. Let T and T' be two MSTs of G that have different sorted arrays of edge weights; moreover, among all such pairs of MSTs, assume that T and T' have as many edges in common as possible. Let e be any edge that is in T but not in T'. Consider the cut (A, B) defined by deleting edge e from T. Adding edge e to T' creates a cycle C. Let f be some other edge in the cycle C that crosses the cut (A, B). Note that f is not in T because e is the only edge in T that crosses the cut. Observe that w(e) = w(f): if w(f) < w(e), then we could improve T by replacing edge e with edge f; if w(e) < w(f), then we could improve T' by replacing edge f with edge e. Now, the tree T'' = T' + e - f is a MST and has the same sorted array of edge weights as T'. But T'' has more edges in common with T than T' (a contradiction).

Seam Carving (shortest path in a pixels grid)

Seam-carving is a content-aware image resizing technique where the image is reduced in size by one pixel of height (or width) at a time
A vertical seam in an image is a path of pixels connected from the top to the bottom with one pixel in each row.
In this assignment, you will create a data type that resizes a W-by-H image using the seam-carving technique.

we have to
– deal with caching and mutable Picture
if (cache == null) {
    cache = new Picture(currPic);
    return cache; }
if (cache.height() != height || cache.width() != width) {
    cache = new Picture(currPic);
    return cache; }
for (int row = 0; row < height; row++) {
    for (int col = 0; col < width; col++) {
        if (currPic.get(col, row) != cache.get(col, row)) {
            cache = new Picture(currPic);
            return cache; } } }
return cache;
– find shortest path in a grid
int size = 1 + (width * height); // + 1 for virtual target vertex
this.cameFrom = new int[size];
this.distTo = new double[size];
for (int n = width; n < size; n++) // init distances (0 for first row-source)
    this.distTo[n] = Double.POSITIVE_INFINITY;
for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++)
        relaxEdges(x, y); // relax edges from x,y pixel }
– resize Picture
Picture pic = new Picture(width - 1, height);
for (int row = 0; row < height; row++) {
    int skip = seam[row], diff = 0;
    for (int col = 0; col < width; col++) {
        if (col == skip) {
            diff++;
            continue; }
        pic.set(col - diff, row, currPic.get(col, row)); } }

quiz: Maxflow and Mincut

Which of the following statements about maxflow and mincut are guaranteed to be true in any flow network G? Check all that apply. As usual, we use the term maxflow to refer to an st-maxflow and mincut to refer to an st-mincut and we assume the network is directed.

– Suppose that the capacity of one edge in G is increased by x > 0, then the value of the maxflow in the modified network G' will increase by at most x units.
true
The capacity of any cut (including the mincut) can increase by at most x. By the maxflow-mincut theorem, the value of the maxflow can increase by at most x

– Let (A, B) be a mincut in G. Suppose that one edge e from B to A is deleted. Then, (A, B) is a mincut in the modified network G'.
true
Any maxflow f in G must have f(e) = 0 for any edge from B to A, so f will be a maxflow in G' of the same value. Also, the capacity of the cut (A, B) in G' will equal the capacity of cut (A, B) in G. Thus, (A, B) is a cut in G' whose capacity equals the value of some flow f. Therefore, (A, B) is a mincut in G'.

– The value of the maxflow from s to t equals the value of the maxflow from t to s in the reverse network G^R.
true
(A, B) is a cut of capacity c in G if and only if (B, A) is a cut of capacity c in G^R.

– Let (A, B) be a min st-cut and let x be any vertex in A and y be any vertex in B. Then (A, B) is also a min xy-cut.
true
Consider a network with these edges and capacities: s->v (3), v->t (1), s->t (1). The unique min st-cut is A = { s, v } and B = { t }. However, the unique min vt-cut is A' = { v }, B' = { s, t }

– Let (A, B) be a mincut in G. Suppose that the capacity of one edge e from A to B is decreased by x > 0. Then, the value of the maxflow in the modified network G' decreases by exactly x units.
true
The capacity of the cut (A, B) decreases by exactly x units (and the capacity of every other cut decreases by at most x). Thus, (A, B) is still a mincut. The maxflow-mincut theorem implies that since the capacity of the mincut decreases by x units, so will the value of the maxflow.

Baseball Elimination (reduction to maxflow problem)

The baseball elimination problem: a team is mathematically eliminated if it cannot possibly finish the season in (or tied for) first place
In the baseball elimination problem, there is a division consisting of N teams.
At some point during the season,
team i has w[i] wins,
l[i] losses,
r[i] remaining games,
and g[i][j] games left to play against team j.
The goal is to determine exactly which teams are mathematically eliminated.
For simplicity, we assume that no games end in a tie (as is the case in Major League Baseball)
and that there are no rainouts (i.e., every scheduled game is played).

we have to
– parse input data, teams table
In fh = new In(filename);
int numTeams = fh.readInt();
for (int n = 0; n < numTeams; n++) {
    Team t = new Team(fh, n, numTeams);
    steams.put(t.name, t);
    nteams.put(t.number, t); }
– detect trivial elimination
Team xt = steams.get(team);
int x = xt.number;
for (int n = 0; n < numberOfTeams(); n++) {
    if (n == x)
        continue;
    // check team n versus x
    if ((xt.wins + xt.remain) < nteams.get(n).wins) {
        trivialWinner = nteams.get(n).name;
        return true; } } 
– detect elimination using maxflow-mincut solution
boolean elim = trivialElimination(team);
if (elim || numberOfTeams() < 3) return elim;
prepareGraph(team);
// Eliminated: If some edges pointing from s are not full,
// then there is no scenario in which team x can win the division
int s = flowSource; // source vertex
for (FlowEdge e : digraph.adj(s)) {
    if (e.capacity() > e.flow())
        return true; }
– build FlowNetwork and find maxflow-mincut
Team xt = steams.get(team);
int x = xt.number; // current team number
int numTeams = numberOfTeams();
int numPairs = choose(2, numTeams - 1);
// source, target, games: t1-t2 pairs, teams
int numverts = 2 + numTeams + numPairs;
digraph = new FlowNetwork(numverts);
int s = numverts - 1; // source vertex
int t = numverts - 2; // target vertex
// 0..numTeams-1 : team vertex id
int pair = numTeams; // next game (pair) vertex number
flowSource = s; // save for later queries
for (int t1 = 0; t1 < numTeams; t1++) { // source-game, game-teams edges
    if (t1 == x) continue;
    for (int t2 = t1 + 1; t2 < numTeams; t2++) {
        if (t2 == x) continue;
        addGameEdges(t1, t2, s, pair); // process a team1-team2 pair
        pair++; } }
for (int t1 = 0; t1 < numTeams; t1++) { // team-sink edges
    if (t1 == x) continue;
    addSinkEdge(t1, t, xt); // process a team }
maxflowMincut = new FordFulkerson(digraph, s, t);
currTeam = team;
…
private void addSinkEdge(int t1, int t, Team xt) {
    int v = t1, w = t;
    int flow = 0;
    double cap = xt.wins + xt.remain - nteams.get(t1).wins;
    if (cap < 0.0) cap = 0.0;
    FlowEdge edge = new FlowEdge(v, w, cap, flow);
    digraph.addEdge(edge); }
private void addGameEdges(int t1, int t2, int s, int pair) {
    // source-game edge
    int v = s, w = pair;
    int flow = 0;
    double cap = nteams.get(t1).against[t2];
    FlowEdge edge = new FlowEdge(v, w, cap, flow);
    digraph.addEdge(edge);
    // game-teams edges
    v = pair;
    cap = Double.POSITIVE_INFINITY;
    flow = 0;
    w = t1;
    edge = new FlowEdge(v, w, cap, flow);
    digraph.addEdge(edge);
    w = t2;
    edge = new FlowEdge(v, w, cap, flow);
    digraph.addEdge(edge); }
– find elimination 'certificate', teams that can eliminate team x
boolean elim = trivialElimination(team);
if (elim) {
    bag.add(trivialWinner);
    return bag; }
if (numberOfTeams() < 3) return null;
prepareGraph(team);
Team xt = steams.get(team);
int x = xt.number; // current team number
for (int n = 0; n < numberOfTeams(); n++) {
    if (n == x) continue;
    if (maxflowMincut.inCut(n)) // check team n
        bag.add(nteams.get(n).name); }

Boggle (dictionary trie, prefixes; grid dfs)

Boggle is a word game designed by Allan Turoff and distributed by Hasbro. It involves a board made up of 16 cubic dice, where each die has a letter printed on each of its sides. At the beginning of the game, the 16 dice are shaken and randomly distributed into a 4-by-4 tray, with only the top sides of the dice visible. The players compete to accumulate points by building valid words out of the dice according to the following rules:
– A valid word must be composed by following a sequence of adjacent dice
– two dice are adjacent if they are horizontal, vertical, or diagonal neighbors
– A valid word can use each die at most once
– A valid word must contain at least 3 letters
– A valid word must be in the dictionary

we have to
– load words from dictionary file to trie
private class Dictionary {
    private static final int R = 26;
    private class Node {
        private int score = -1;
        private Node[] next = new Node[R]; }
    private Node root;
    private Node currentNode; // isPrefix-contains cache
    private Dictionary(String[] words) {
        for (String word : words) {
            int score = computeScore(word);
            put(word, score); } }
private void put(String word, int score) {
    root = put(root, word, score, 0); }
private Node put(Node n, CharSequence word, int score, int pos) {
    if (n == null) n = new Node();
    if (pos == word.length()) n.score = score;
     else {
        int c = linkNumber(word, pos); // word.charAt(pos);
        n.next[c] = put(n.next[c], word, score, pos + 1); }
    return n; }
– retrieve info from dictionary trie
private boolean isPrefix(StringBuilder sb) {
    Node n = get(root, sb, 0);
    currentNode = n;
    if (n == null) return false;
    return true; }
private boolean contains(StringBuilder sb) {
    if (currentNode == null || currentNode.score < 0) return false;
    return true; }
private int get(CharSequence word) {
    Node n = get(root, word, 0);
    if (n == null) return -1;
    return n.score; }
private Node get(Node n, CharSequence word, int pos) {
    if (n == null) return null;
    if (pos == word.length()) return n;
    int c = linkNumber(word, pos);
    return get(n.next[c], word, pos + 1); }
– collect unique words, and do it fast enough
public Iterable<String> getAllValidWords(BoggleBoard board) {
// custom three-way trie ST with bag of keys?
    ResizingArrayBag<String> words = new ResizingArrayBag<>();
    for (int row = 0; row < board.rows(); row++) {
        for (int col = 0; col < board.cols(); col++) {
            // start dfs with row,col first char
            explore(board, row, col, words); } }
    res = new LinearProbingHashST<String, Boolean>(words.size() * 2);
    for (String s : words) res.put(s, true);
    return res.keys(); }
– explore game board, dfs
private class Walker {
...
private Walker(BoggleBoard board, int row, int col, ResizingArrayBag<String> words) {
    sb = new StringBuilder();
    marked = new boolean[rows][cols];
    getSymbol(row, col); // 1 or 2 chars for now
    marked[row][col] = true;
    for (int r = row - 1; r < row + 2; r++) {
        for (int c = col - 1; c < col + 2; c++) {
            if (r >= 0 && r < rows && c >= 0 && c < cols && !marked[r][c])
                dfs(r, c); } } }
private void dfs(int row, int col) {
    marked[row][col] = true;
    char ch = board.getLetter(row, col);
    if (ch == 'Q') sb.append("QU");
    else sb.append(ch);
    if (dict.isPrefix(sb)) {
        if (sb.length() > 2 && dict.contains(sb))
            words.add(sb.toString());
        for (int r = row - 1; r < row + 2; r++) {
            for (int c = col - 1; c < col + 2; c++) {
                if (r >= 0 && r < rows && c >= 0 && c < cols && !marked[r][c])
                    dfs(r, c); } } }
    sb.deleteCharAt(sb.length() - 1);
    if (ch == 'Q') sb.deleteCharAt(sb.length() - 1);
    marked[row][col] = false; }
private void getSymbol(int row, int col) {
    char c = board.getLetter(row, col);
    if (c == 'Q') sb.append("QU");
    else sb.append(c); }

Burrows-Wheeler transformation (suffixes array, radix sort, 3-way radix qsort, index-counting)

This revolutionary algorithm outcompresses gzip and PKZIP, is relatively easy to implement, and is not protected by any patents.
It forms the basis of the Unix compression utility bzip2.
The Burrows-Wheeler compression algorithm consists of three algorithmic components, which are applied in succession:
1 -- Burrows-Wheeler transform. Given a typical English text file, transform it into a text file in which sequences of the same character occur near each other many times.
2 – Move-to-front encoding. Given a text file in which sequences of the same character occur near each other many times, convert it into a text file in which certain characters appear more frequently than others.
3 – Huffman compression. Given a text file in which certain characters appear more frequently than others, compress it by encoding frequently occurring characters with short codewords and rare ones with long codewords.
To expand a message, apply the inverse operations in reverse order: first apply the Huffman expansion, then the move-to-front decoding, and finally the inverse Burrows-Wheeler transform.
Your task is to implement Burrows-Wheeler and move-to-front components efficiently.

we have to
– implement move-to-front encode/decode
private static char[] newAlphabet() {
    char[] abet = new char[R];
    for (char n = 0; n < R; n++) abet[n] = n; }
private static char getPos(char[] abet, char ch) {
    for (char n = 0; n < R; n++)
        if (abet[n] == ch) return n; }
private static void move2Front(char[] abet, char ch, char pos) {
    for (int n = pos; n > 0; n--) abet[n] = abet[n - 1];
    abet[0] = ch; }
public static void encode() {
    char[] abet = newAlphabet();
    while (!BinaryStdIn.isEmpty()) {
        char ch = BinaryStdIn.readChar();
        char pos = getPos(abet, ch);
        BinaryStdOut.write(pos);
        move2Front(abet, ch, pos); }
    BinaryStdOut.close(); }
public static void decode() {
    char[] abet = newAlphabet();
    while (!BinaryStdIn.isEmpty()) {
        char pos = BinaryStdIn.readChar();
        char ch = abet[pos];
        BinaryStdOut.write(ch);
        move2Front(abet, ch, pos); }
    BinaryStdOut.close(); }
– sort suffix array avoiding creating new strings
public CircularSuffixArray(String s) {
    refs = new int[length()];
    for (int n = 0; n < length(); n++) refs[n] = n;
    sort(); }
private void sort() {
    StdRandom.shuffle(refs);
    int lo = 0;
    int hi = length() - 1;
    int d = 0;
    qsort(lo, hi, d); }
private void qsort(int lo, int hi, int d) {
    // 3-way radix qsort, skipped
private int charAt(int suff, int d) {
    int pos = (suff + d) % length();
    return str.charAt(pos); }
private void swap(int i, int j) {
    int t = refs[i];
    refs[i] = refs[j];
    refs[j] = t; }
public int index(int i) { return refs[i]; }
– implement Burrows-Wheeler encoder
public static void encode() {
    String str = BinaryStdIn.readString();
    CircularSuffixArray csa = new CircularSuffixArray(str);
    int first = findFirst(csa, str);
    BinaryStdOut.write(first);
    for (int n = 0; n < csa.length(); n++) {
        char ch = getSuffixLastChar(str, csa.index(n));
        BinaryStdOut.write(ch); }
    BinaryStdOut.close(); }
– and decoder
public static void decode() {
    int first = BinaryStdIn.readInt();
    String lastCol = BinaryStdIn.readString();
    char[] firstCol = lastCol.toCharArray();
    firstCol = radixSort(firstCol); // ~10% vs. Arrays.sort(firstCol);
    int[] next = new int[firstCol.length];
    computeNext(lastCol, firstCol, next); // ~50% using index-counting
    int idx = first;
    for (int n = 0; n < firstCol.length; n++) {
        char ch = firstCol[idx];
        BinaryStdOut.write(ch);
        idx = next[idx]; }
    BinaryStdOut.close(); }
private static void computeNext(String lastCol, char[] firstCol, int[] next) {
    int len = firstCol.length;
    int R = 256;
    int[] idx = new int[R]; // index of first occurrence for each char in lastCol
    Arrays.fill(idx, -1);
    // index-counting, skipped
    int m = 0;
    for (int n = 0; n < len; n++) {
        char ch = firstCol[n];
        if ((n > 0 && firstCol[n - 1] != ch) || n == 0) m = idx[ch];
        for (; m < len; m++)
            if (lastCol.charAt(m) == ch) break;
        next[n] = m;
        m++; } }
– do some suffix shit
private static char suffCharAt(String str, int suff, int d) {
    int pos = (suff + d) % str.length();
    return str.charAt(pos); }
private static int findFirst(CircularSuffixArray csa, String str) {
    // TODO binary search
    for (int n = 0; n < csa.length(); n++) {
        int suff = csa.index(n);
        if (suffixEqual(str, suff))  return n; } }
private static boolean suffixEqual(String str, int suff) {
    for (int n = 0; n < str.length(); n++) {
        char ch = suffCharAt(str, suff, n);
        if (ch != str.charAt(n)) return false; }
    return true; }

quiz: Final Exam

Which of the following statements about connectivity in an undirected graph are true?

– Removing any one edge from a connected graph breaks the graph into exactly two connected components.
false

– If there are two edge-disjoint paths connecting vertices u and v, then there is a simple cycle containing both u and v.
false

– A graph is a tree if and only if there is a unique path from any vertex to any other vertex.
true

– If you delete two edges from a graph, its number of connected components can increase by 3.
false

– Every Eulerian bipartite graph has an even number of edges.
true

Which of the following statements about depth-first search in a digraph are guaranteed to be true?

– If there is a unique vertex reachable from every other vertex, it will be first in some postorder.
true

– If there is a unique vertex reachable from every other vertex, it will be first in any postorder.
false

– Suppose that dfs(v) is called after dfs(w) is called but before dfs(w) returns. Then, there is a directed path from v to w.
false

– The postorder of a digraph is the reverse of its preorder.
false

– Suppose that dfs(v) is called after dfs(w) is called but before dfs(w) returns. Then, there is a directed path from w to v.
true

Which of the following statements about minimum spanning trees (MSTs) are guaranteed to be true in any edge-weighted graph G? Assume that G is connected and has no parallel edge or self-loops. Do not assume the edge weights are distinct unless this is specifically stated.

– Let w(e) > 0 denote the weight of edge e in G. Let G' be the same edge-weighted graph but with edge weights w'(e) = 17 * w(e) for each edge e. Then, T is a MST of G if and only if T is a MST of G'.
true
T is a spanning tree in G of weight x if and only if T is a spanning tree in G' of weight 17x. We note that the property is still true even if the weights can be zero or negative

– Let T be a spanning tree in G. T is a MST iff for every edge e in T, e is a lightest edge crossing the cut defined by deleting edge e from T.
true
This is a tricky one. These are known as the cut optimality conditions. See http://www.cs.princeton.edu/~wayne/cs423/lectures/mst-4up.pdf

– Let T and T' be two different MSTs of G. Let e' be any edge in T' that is not in T. Then, there exists an edge e in T but not T' such that replacing edge e with edge e' in T is also a MST of G.
true
Adding e' to T results in a unique cycle C. There must be some edge e in this cycle C that is not in T' (since otherwise T' would be cyclic). Observe that w(e) = w(e'): if w(e') < w(e), we could improve T by replacing edge e' with edge e; if w(e) < w(e'), we could improve T' by replacing edge e' with edge e. Thus, replacing edge e with edge e' in T yields a MST of G. This is known as the exchange property: it implies that we can "walk" between any MSTs via a sequence of MSTs, by exchanging edges one at a time.

– Assume that the edge weights in G are distinct. Let (A, B) be a cut. Suppose that edge e is not the lightest edge that crosses (A, B). Then, edge e is not in the MST.
false
The cut property asserts that the lightest edge crossing the cut (A, B) is in the MST, but there may be other crossing edges in the MST. For example, consider an edge-weighted graph with these edges and capacities: v-w (1), w-x (3), x-v (2). Let A = { v } and B = { w, x }. Then, x-v is not the lightest edge that crosses (A, B) but it is in the MST.

– Let e be an edge in some MST T of G. Then, there exists a cut (A, B) for which e is a lightest crossing edge.
true
Consider the cut (A, B) defined by deleting edge e from T. Suppose (for the sake of contradiction) that there exists a crossing edge f that is lighter than edge e. Then, replacing edge e with edge f in T yields a lighter spanning tree (a contradiction).

Which of the following statements about shortest paths are true?

-- Give a DAG with positive and distinct edge weights, Dijkstra's algorithm and the topological sort algorithm relax the vertices in the same order.
false

-- Let P be a shortest path from some s to t in an edge-weighted digraph G. If the weight of each edge in G is multiplied by 17, then P will still be a shortest path from s to t in the modified digraph G'.
true

-- Bellman-Ford finds the shortest simple path from s to every other vertex, even if the edge weights are arbitrary positive or negative integers.
false

-- Let G be a digraph with positive edge weights. Suppose that you remove an edge with weight x. Then, the length of the shortest path from s to t can increase by more than x.
true

-- Let P be a shortest path from some s to t in an edge-weighted digraph G. If the weight of each edge in G is increased by one, then P will still be a shortest path from s to t in the modified digraph G'.
false

Which of the following statements about maxflow and mincut are guaranteed to be true in any flow network G? As usual, we use the term maxflow to refer to an st-maxflow and mincut to refer to an st-mincut and we assume the network is directed.

-- The capacity of any cut is greater than or equal to the value of any flow.
true
This is weak duality.

-- If there are two different integer-valued maxflows f and f', then there is a third integer-valued maxflow f'' (different from both f and f').
false
Consider a network with these edges and capacities: s->v (1), v->w (1), w->t (1), v->x (1), x->t (1). There are exactly two integer-valued maxflows: either send 1 unit of flow along the path s->v->w->t or send 1 unit of flow along the path s->v->x->t.

-- Let G be a network that has edges entering the source s and leaving the sink t. Then, there exists a maxflow for which f(e) = 0 for every edge e entering s or leaving t.
true
This is a tricky one. We'll consider edges leaving t; the case for edges entering s is analogous. Let v be some vertex for which f(t->v) > 0. Follow the edge t->v to v. Then, find an edge leaving v with positive flow. (Flow conservation ensures that such an edge exists.) Continue until you repeat a vertex (possibly t). Now, reduce the flow on each edge in this cycle until one (or more) edges have zero flow. Repeat this whole process, starting at t. After each cycle-canceling step, the number of edges with positive capacity decreases, so the process will eventually terminate (with no edge leaving t having positive flow).

-- Let (A, B) be a mincut in G. Suppose that the capacity of one edge e from A to B is increased by x > 0. Then, then the value of the maxflow in the modified network G' will increase by exactly x units.
false
The value of the maxflow in G and G' may be equal, e.g., if there is another mincut (A', B') in G in which both endpoints of e in are in A'.

-- If all edge capacities are distinct, then the maxflow is unique.
false
Consider a network with these edges and capacities: s->v (1), v->w (2), v->t (3), w->t (4). Then, one maxflow uses only the path s->v->t while another maxflow uses only the path s->v->w->t.

Which of the following problems can be linear-time reduced *to* the standard maximum st-flow problem in digraphs?

-- Given a digraph with positive edge weights and two vertices s and t, find a shortest path from s to t.
false

-- Given an array of N comparable elements, find the kth smallest one.
false

-- Given a digraph with positive edge weights and two disjoint *sets* of vertices S and T, find a minimum capacity cut where all vertices in S are on one side and all vertices in T are on the other side.
true

-- Given a bipartite graph, find a matching of maximum cardinality.
true

-- Given N variables and M linear inequalities, find a solution.
false

Which of the following would imply that P != NP?

-- Proving that some problem in NP has as an exponential lower bound.
true

-- Proving that some problem in NP has as a polynomial-time algorithm.
false

-- Proving that there exists a polynomial-time algorithm for FACTOR (factoring an integer).
false

-- Proving that there is no polynomial-time algorithm for LONGEST-PATH (longest simple path in a graph).
true

-- Proving that there is no polynomial-time algorithm for FACTOR (factoring an integer).
true

You are applying for a job at a new software technology company. Your interviewer asks you to identify which of the following graph-processing tasks are possible using techniques discussed in Algorithms, Part II.

-- Given a bipartite graph, design an E + V algorithm to find a maximum matching.
false
Best known algorithm is E V^(1/2).

-- Given a set of tasks with precedence constraints, design an E + V algorithm determine an order in which to schedule the tasks.
true
Topologial sort.

-- Given a digraph, design an E + V algorithm to find a directed cycle.
true
DFS.

-- Given an edge-weighted graph with ~ 1/6 V^2 edges, design an E + V algorithm to find an MST.
true
Prim's algorithm is optimal (V^2) in dense graphs if it uses a brute-force priority queue. Here E ~ 1/6 V^2.

-- Given an edge-weighted graph where the weights are 0, 1, or 2, find an MST in E + V time.
true
EXPLANATION NEEDED

You are applying for a job at a new software technology company. Your interviewer asks you to identify which of the following string-processing tasks are possible using techniques discussed in Algorithms, Part II.

-- Determine whether a pattern string of length M is a substring of a text string of length N in time proportional to M + N in the worst case.
true
Knuth-Morris-Pratt.

-- Design a data compression algorithm that achieve a 50% compression ratio for typical natural language inputs.
true
LZW and Burrows-Wheeler achieve this.

-- Given an array of N items whose keys are W-digit strings, stably sort them in time linear in W * N.
true
LSD radix sort.

-- Determine whether an M-character regular expression matches an N-character text in time polynomial in M and N.
true
Our RE-to-NFA construction algorithm + NFA simulation algorithm.

-- Construct a DFA corresponding to an M-character regular expression in time proportional to M^2.
false
The DFA may require an exponential number of states as a function of M.

quiz: Reductions

Which of the following problems can be linear-time reduced *from* element distinctness: Given an array of N real numbers, are they all distinct? Assume the quadratic decision tree model of computation.

-- Given N coins and a balance scale, determine if the coins all weigh different amounts.
true

-- Given an array of N real numbers, rearrange them in ascending order.
true

-- Given an edge-weighted graph, compute the minimum spanning tree.
false

-- Given an array of N real numbers, find the kth smallest one.
false

-- Given N points in the plane, compute the minimum spanning tree, where the weight between two points is its Euclidean distance.
true

Which problems are known to have the same asymptotic complexity as sorting an array of N real numbers? Assume the quadratic decision tree model of computation.

-- Given an array of N real numbers, determine if any two are equal.
true

-- Given an array of N real numbers and an integer k, find the kth smallest one.
false

-- Given an array of N real numbers, determine if any two sum to zero.
true

-- Given N points in the plane, find all sets of 3 or more points that are collinear.
false

-- Given an array of N real numbers, find the median.
false

Suppose that problem A linear-time reduces to problem B. Which of the following can you infer?

-- If A cannot be solved in poly-time, then neither can B.
true

-- If A cannot be solved in linear time, then neither can B.
true

-- If B cannot be solved in quadratic time, then neither can A.
false

-- If A cannot be solved in quadratic time, then B cannot be solved in poly-time.
false

-- A cannot be solved in poly-time.
false

quiz: Intractability

Suppose that problem A poly-time reduces to problem B. Which of the following can you infer?

-- If A can be solved in linear time, then so can B.
false

-- If B can be solved in quadratic time, then A can be solved in poly-time.
true

-- If A can be solved in poly-time, then so can B.
false

-- If B can be solved in linear time, then A can be solved in poly-time.
true

-- If A can be solved in linear time, then B can be solved in poly-time.
false

Suppose that a search problem X is NP-complete. Which of the following statements can you infer?

-- X cannot be solved in polynomial time.
false

-- if X cannot be solved in polynomial time, then neither can FACTOR (and every other problem in NP).
false

-- X polynomial reduces to all search problems.
false

-- X polynomial reduces to SAT.
true

-- All search problems polynomial reduce to X.
true

quiz: Linear Programming

Which of the following problems can be reduced to linear programming?

-- Given an N-bit integer, find its factors.
false

-- Given a digraph with edge weights, find a negative cycle.
true

-- Given a digraph and two vertices s and t, find a path from s to t with the fewest number of edges.
true

-- Given an N-by-N two-person zero-sum game, find a Nash equilibrium.
true

-- Given a digraph with positive edge weights and two vertices s and t, find a shortest path from s to t.
true

– Consider the following linear programming simplex tableaux with 3 equations and 8 variables:
maximize Z
                       -  3/4 x2  -  1/4 x3  -    2 x4  +    3 x5  +    9 x6               -  Z    = -294
---------------------------------------------------------------------------------------------------------
                       -  4/5 x2  -  9/5 x3  +    1 x4  +  5/2 x5  +  5/4 x6  +    1 x7            =   12
            +    1 x1  +  5/2 x2  -  3/2 x3  -  4/5 x4  +    1 x5  +    1 x6                       =   48
 +    1 x0             +  1/3 x2  -  2/3 x3  -    4 x4  +  1/5 x5  +    2 x6                       =   42
        x0  ,      x1  ,      x2  ,      x3  ,      x4  ,      x5  ,      x6  ,      x7           >=    0
Which variable could be the next to *enter* the basis?
The basis is { x7, x1, x0 }.
The nonbasic variables are { x2, x3, x4, x5, x6 }.
The entering variables are those nonbasic variables with a positive objective function coefficient.

– Consider the following linear programming simplex tableaux with 5 equations and 9 variables:
maximize Z
 +  9/4 x0             -    2 x2  -  5/2 x3                        -  7/5 x6                          -  Z    = -120
--------------------------------------------------------------------------------------------------------------------
 -  4/5 x0             -  2/5 x2  +  4/3 x3  +    1 x4             +  1/4 x6                                  =   24
 +    2 x0             +    1 x2  -    2 x3                        -    1 x6             +    1 x8            =   12
 -  1/2 x0             -    2 x2  +  1/2 x3                        +    4 x6  +    1 x7                       =   18
 +    4 x0             +    4 x2  -    3 x3             +    1 x5  +  2/3 x6                                  =   48
 +    7 x0  +    1 x1  +   10 x2  -  2/5 x3                        -   10 x6                                  =   42
        x0  ,      x1  ,      x2  ,      x3  ,      x4  ,      x5  ,      x6  ,      x7  ,      x8           >=    0
Suppose that variable x0 is the variable chosen to enter the basis.
Which variable or variables could be the next to *leave* the basis? Check all that apply.

The basis is { x4, x8, x7, x5, x1 }.
The nonbasic variables are { x0, x2, x3, x6 }.
The entering variable is x0.
The min ratio test determines the leaving variable: min ratio = { *, 6, *, 12, 6 } = 6.
The minimum occurs in rows 1 and 4, which corresponds to basic variables x8 and x1.
The leaving variables are { x8 x1 }.






original post http://vasnake.blogspot.com/2016/05/exercises.html

Комментариев нет:

Отправить комментарий

Архив блога

Ярлыки

linux (241) python (191) citation (186) web-develop (170) gov.ru (159) video (124) бытовуха (115) sysadm (100) GIS (97) Zope(Plone) (88) бурчалки (84) Book (83) programming (82) грабли (77) Fun (76) development (73) windsurfing (72) Microsoft (64) hiload (62) internet provider (57) opensource (57) security (57) опыт (55) movie (52) Wisdom (51) ML (47) driving (45) hardware (45) language (45) money (42) JS (41) curse (40) bigdata (39) DBMS (38) ArcGIS (34) history (31) PDA (30) howto (30) holyday (29) Google (27) Oracle (27) tourism (27) virtbox (27) health (26) vacation (24) AI (23) Autodesk (23) SQL (23) Java (22) humor (22) knowledge (22) translate (20) CSS (19) cheatsheet (19) hack (19) Apache (16) Manager (15) web-browser (15) Никонов (15) functional programming (14) happiness (14) music (14) todo (14) Klaipeda (13) PHP (13) course (13) scala (13) weapon (13) HTTP. Apache (12) SSH (12) frameworks (12) hero (12) im (12) settings (12) HTML (11) SciTE (11) USA (11) crypto (11) game (11) map (11) HTTPD (9) ODF (9) Photo (9) купи/продай (9) benchmark (8) documentation (8) 3D (7) CS (7) DNS (7) NoSQL (7) cloud (7) django (7) gun (7) matroska (7) telephony (7) Microsoft Office (6) VCS (6) bluetooth (6) pidgin (6) proxy (6) Donald Knuth (5) ETL (5) NVIDIA (5) Palanga (5) REST (5) bash (5) flash (5) keyboard (5) price (5) samba (5) CGI (4) LISP (4) RoR (4) cache (4) car (4) display (4) holywar (4) nginx (4) pistol (4) spark (4) xml (4) Лебедев (4) IDE (3) IE8 (3) J2EE (3) NTFS (3) RDP (3) holiday (3) mount (3) Гоблин (3) кухня (3) урюк (3) AMQP (2) ERP (2) IE7 (2) NAS (2) Naudoc (2) PDF (2) address (2) air (2) british (2) coffee (2) fitness (2) font (2) ftp (2) fuckup (2) messaging (2) notify (2) sharepoint (2) ssl/tls (2) stardict (2) tests (2) tunnel (2) udev (2) APT (1) CRUD (1) Canyonlands (1) Cyprus (1) DVDShrink (1) Jabber (1) K9Copy (1) Matlab (1) Portugal (1) VBA (1) WD My Book (1) autoit (1) bike (1) cannabis (1) chat (1) concurrent (1) dbf (1) ext4 (1) idioten (1) join (1) krusader (1) license (1) life (1) migration (1) mindmap (1) navitel (1) pneumatic weapon (1) quiz (1) regexp (1) robot (1) science (1) serialization (1) spatial (1) tie (1) vim (1) Науру (1) крысы (1) налоги (1) пианино (1)