Упражнения и
задачки к курсу
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
Комментариев нет:
Отправить комментарий