Computer Science Textbook Solutions - 9

a. How many bits are required per node to store the height of a node in an N-node AVL tree? b.
What is the smallest AVL tree that overflows an 8-bit height counter?
In the quadratic probing hash table, suppose that instead of inserting a new item into the location
suggested by findPos, we insert it into the first inactive cell on the search path (thus, it is possible
to reclaim a cell that is marked "deleted," potentially saving space). a. Rewrite the insertion
algorithm to use t
Show the result of inserting keys 1 to 15 in order into a skew heap.
Efficiently implement a queue class using a singly linked list, with no header or tail nodes.
Give an example of input that generates the best leftist heap.
See Full Question And Answer at solutionrank.com
If a d-heap is stored as an array, for an entry located in position i, where are the parents and
children?
Prove or disprove: A perfectly balanced tree forms if keys 1 to 2k âˆ’ 1 are inserted in order into
an initially empty leftist heap.
Write a recursive method that takes a reference to the root node of a tree T and returns a
reference to the root node of the tree that results from removing all leaves from T.
Show the result of accessing the keys 3, 9, 1, 5 in order in the splay tree in Figure 4.72.
Suppose we want to add the operation findKth to our repertoire. The operation findKth(k) returns
the kth smallest item in the tree. Assume all items are distinct. Explain how to modify the binary
search tree to support this operation in O(logN) average time, without sacrificing the time
bounds of any other operation.
Given two sorted lists, L1 and L2, write a procedure to compute L1 âˆ© L2 using only the basic
list operations.
We can perform buildHeap in linear time for leftist heaps by considering each element as a one-
node leftist heap, placing all these heaps on a queue, and performing the following step: Until
only one heap is on the queue, dequeue two heaps, merge them, and enqueue the result. a. Prove
that this algorithm is O(N) in th
Show the result of rehashing the hash tables in Exercise 5.1. Given input {4371, 1323, 6173,
4199, 4344, 9679, 1989} and a hash function h(x) = x mod 10, show the resulting: a. Separate
chaining hash table. b. Hash table using linear probing. c. Hash table using quadratic probing. d.
Hash table with second hash fu
What are the advantages and disadvantages of the various collision resolution strategies?
Implement a hopscotch hash table and compare its performance with linear probing, separate
chaining, and cuckoo hashing.
Each deleteMin operation uses 2 logN comparisons in the worst case. a. Propose a scheme so
that the deleteMin operation uses only logN + log logN + O(1) comparisons between elements.
This need not imply less data movement. b. Extend your scheme in part (a) so that only logN +
log log logN + O(1) comparisons are perfo
Suppose you want to perform an experiment to verify the problems that can be caused by random
insert/remove pairs. Here is a strategy that is not perfectly random, but close enough. You build a
tree with N elements by inserting N elements chosen at random from the range 1 to M = Î±N.
You then perform N2 pairs of insert
Prove that a binomial tree Bk has binomial trees B0, B1, . . . , Bkâˆ’1 as children of the root.
Prove that a binomial tree of height k has (kd) nodes at depth d.
Show that the maximum number of nodes in a binary tree of height h is 2h+1 âˆ’ 1.
Extend the classic cuckoo hash table to use d hash functions.
Write an implementation of the TreeSet class, with associated iterators, using a binary search
tree. Add to each node a link to the next smallest and next largest node. To make your code
simpler, add a header and tail node which are not part of the binary search tree, but help make
the linked list part of the code simp
Show the result of inserting the keys 10111101, 00000010, 10011011, 10111110, 01111111,
01010001, 10010110, 00001011, 11001111, 10011110, 11011011, 00101011, 01100001,
11110000, 01101111 into an initially empty extendible hashing data structure with M = 4.
Suppose a binary tree has leaves l1, l2, . . . , lM at depths d1, d2, . . . , dM, respectively. Prove
that Î£Mi=1 2âˆ’di â‰¤ 1 and determine when the equality is true.
Design a recursive linear-time algorithm that tests whether a binary tree satisfies the search tree
order property at every node.
Can both insert and findMin be implemented in constant time?

Write the remaining procedures to implement AVL single and double rotations.
a. Give an algorithm to find all nodes less than some value, X, in a binary heap. Your algorithm
should run in O(K), where K is the number of nodes output. b. Does your algorithm extend to
any of the other heap structures discussed in this chapter? c. Give an algorithm that finds an
arbitrary item X in a binary heap
Suppose instead of quadratic probing, we use "cubic probing"; here the ith probe is at hash(x) +
i3. Does cubic probing improve on quadratic probing?
Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.
Prove Markov's Inequality: If X is any random variable and a > 0, then Pr( |X| â‰¥ a) â‰¤ E( |
X| )/a. Show how this inequality can be applied to Theorems 5.2 and 5.3.
Suppose we need to perform M percolateUps and N deleteMins on a d-heap that initially has N
elements. a. What is the total running time of all operations in terms of M, N, and d? b. If d = 2,
what is the running time of all heap operations? c. If d = Î˜(N), what is the total running time? d.
What choice of d minimi
Write a method to generate the AVL tree of height h with fewest nodes. What is the running time
of your method?
Show the result of inserting keys 1 to 15 in order into an initially empty leftist heap.
The following routine removes the first half of the list passed as a parameter: a. Why is theSize
saved prior to entering the for loop? b. What is the running time of removeFirstHalf if lst is an
ArrayList? c. What is the running time of removeFirstHalf if lst is a LinkedList? d. Does using
an iterator make removeH
Write a program that lists all files in a directory and their sizes. Mimic the routine in the online
code.
Implement the contains routine for MyLinkedList.
Show that the deletion algorithm in Figure 4.44 is correct, and explain what happens if > is used
instead of >= at lines 32 and 38 in Figure 4.39.
The Josephus problem is the following game: N people, numbered 1 to N, are sitting in a circle.
Starting at person 1, a hot potato is passed. After M passes, the person holding the hot potato is
eliminated, the circle closes ranks, and the game continues with the person who was sitting after
the eliminated person picki
The isEmpty routine for quadratic probing has not been written. Can you implement it by
returning the expression currentSize==0?
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a
currency into more than one unit of the same currency. For example, suppose that 1 U.S. dollar
buys 46.4 Indian rupees, 1 Indian rupee buys 2.5 Japanese yen, and 1 Japanese yen buys 0.0091
U.S. dollars. Then, by converting curre
Show that edge (u, v) is a. a tree edge or forward edge if and only if d[u] < d[v] < f[v] < f[u], b. a
back edge if and only if d[v] < d[u] < f[u] < f[v], and c. a cross edge if and only if d[v] < f[v] <
d[u] < f[u].
b. Describe an efficient method to determine whether or not one d-dimensional box nests inside
another. c. Suppose that you are given a set of n d-dimensional boxes {B1, B2,..., Bn}. Describe
an efficient algorithm to determine the longest sequence (Bi2, Biz,...Bik) of boxes such that nests
within Bij+1for j = 1, 2,...
There are four basic operations on red-black trees that perform structural modifications: node
insertions, node deletions, rotations, and color modifications. We have seen that RB-INSERT
and RB-DELETE use only O (1) rotations, node insertions, and node deletions to maintain the
red-black properties, but they may make m
Given a flow network G = (V, E), let f1 and f2 be functions from V Ã— V to R. The flow sum
f1 + f2 is the function from V Ã— V to R defined by (26.4) (fi + f2) (u, v) = f1 (u, v) + f2(u, v)
for all u, v Â¬ âª V. If f1 and f2 are flows in G, which of the three flow properties must the
flow sum f1 + f2 satisfy, and whic
Professor Michener claims that there is no need to create a new source vertex in line 1 of
JOHNSON. He claims that instead we can just use Gâ€² = G and let s be any vertex in V [G].
Give an example of a weighted, directed graph G for which incorporating the professor's idea
into JOHNSON causes incorrect answers. Then s
We can represent an n-input comparison network with c comparators as a list of c pairs of

integers in the range from 1 to n. If two pairs contain an integer in common, the order of the
corresponding comparators in the network is determined by the order of the pairs in the list.
Given this representation, describe an O
Let G = (V, E) be a directed graph in which each vertex u âª Â¬ V is labeled with a unique
integer L(u) from the set {1, 2,..., |V|}. For each vertex u Â¬âª V, let R(u) = (v Îµ V : u â†’ v)
be the set of vertices that are reachable from u. Define min(u) to be the vertex in R(u) whose
label is minimum, i.e., min(u) is
The PERT chart formulation given above is somewhat unnatural. It would be more natural for
vertices to represent jobs and edges to represent sequencing constraints; that is, edge (u, v) would
indicate that job u must be performed before job v. Weights would then be assigned to vertices,
not edges. Modify the DAG-SHORTE
Professor Green street claims that there is a simpler way to re-weight edges than the method used
in Johnson's algorithm. Letting w* = min (u, v)¬E {w(u, v)}, just define w(u, v) = w(u, v) - w*
for all edges (u, v) ¬ E. What is wrong with the professor's method of reweighing?
Give an algorithm that determines whether or not a given undirected graph G = (V, E) contains a
cycle. Your algorithm should run in O (V) time, independent of |E|.
Give a dynamic-programming solution to the 0â€“1 knapsack problem that runs in O (n W) time,
where n is number of items and W is the maximum weight of items that the thief can put in his
knapsack.
How do pie charts differ from doughnut charts?
Suppose that a graph G has a minimum spanning tree already computed. How quickly can the
minimum spanning tree be updated if a new vertex and incident edges are added to G?
Give an example of a directed graph G = (V, E), a source vertex s Â¬ V, and a set of tree edges
E Ï€ Â¬ E such that for each vertex v Â¬ V, the unique path in the graph (V, E Ï€) from s to v is
a shortest path in G, yet the set of edges E Ï€ cannot be produced by running BFS on G, no
matter how the vertices are ordered
Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car's gas
tank, when full, holds enough gas to travel n miles, and his map gives the distances between gas
stations on his route. The professor wishes to make as few gas stops as possible along the way.
Give an efficient method by which P
Professor Adam has two children who, unfortunately, dislike each other. The problem is so
severe that not only do they refuse to walk to school together, but in fact each one refuses to
walk on any block that the other child has stepped on that day. The children have no problem
with their paths crossing at a corner. Fo
Show how to express the single-source shortest-paths problem as a product of matrices and a
vector. Describe how evaluating this product corresponds to a Bellman-Ford-like algorithm (see
Section 24.1).
What formula would you write to do each of the following? a. Add a range of numbers in cells
B2:B12. b. Find the largest value in cells C2:F2. c. Find the smallest value in cells A1 through
X10. d. Find the average value in cells C1 through C10, assuming blank cells will be ignored. e.
Find the total number of ite
Given an m Ã— n matrix T over some field (such as the reals), show that (S,â„“) is a matroid,
where S is the set of columns of T and A Â¬â„“ if and only if the columns in A are linearly
independent.
Consider an ordinary binary min-heap data structure with n elements that supports the
instructions INSERT and EXTRACT-MIN in O (lg n) worst-case time. Give a potential function
Î¦ such that the amortized cost of INSERT is O (lg n) and the amortized cost of EXTRACT-MIN
is O (1), and show that it works.
List and describe the significance of each of Tufteâ€™s five data graphics principles.
Suppose that every row in the matrix A of a linear program Ax â‰¤ b corresponds to a
difference constraint, a single-variable constraint of the form xi â‰¤ bk, or a single-variable
constraint of the form -xi â‰¤ bk. Show how to adapt the Bellman-Ford algorithm to solve this
variety of constraint system.
Given a directed graph G = (V, E), explain how to create another graph Gâ€² = (V, Eâ€²) such
that (a) Gâ€² has the same strongly connected components as G, (b) Gâ€² has the same
component graph as G, and (c) Eâ€² is as small as possible. Describe a fast algorithm to compute
Gâ€².
Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you
make Kruskalâ€™s algorithm run? What if the edge weights are integers in the range from 1 to
W for some constant W?
Given a graph G and a minimum spanning tree T, suppose that we decrease the weight of one of
the edges in T. Show that T is still a minimum spanning tree for G. More formally, let T be a
minimum spanning tree for G with edge weights given by weight function w. Choose one edge
(x, y) Â¬âª T and a positive number k, and
Given a weighted, directed graph G = (V, E) with no negative-weight cycles, let m be the
maximum over all pairs of vertices u, v Â¬âª V of the minimum number of edges in a shortest
path from u to v. (Here, the shortest path is by weight, not the number of edges.) Suggest a
simple change to the Bellman-Ford algorithm t
The incidence matrix of a directed graph G = (V, E) is a |V| Ã— |E| matrix B = (bij) such that
Describe what the entries of the matrix product B BT represent, where BT is the transpose of B.
Show that the depth of SORTER [n] is exactly (lg n) (lg n + 1)/2.
As it appears above, the Floyd-War shall algorithm requires Î˜ (n3) space, since we compute for
d (k) i, j, k = 1, 2,...,n. Show that the following procedure, which simply drops all the
superscripts, is correct, and thus only Î˜ (n2) space is required.
Let G = (V, E) be a weighted, directed graph with weight function w: E â†’ {0, 1, ..., W } for
some nonnegative integer W . Modify Dijkstra' s algorithm to compute the shortest paths from a
given source vertex s in O(W V + E) time.
Prove that any sorting network on n inputs has depth at least lg n.
Argue that in a breadth-first search, the value d[u] assigned to a vertex u is independent of the
order in which the vertices in each adjacency list are given. Using Figure 22.3 as an example,
show that the breadth-first tree computed by BFS can depend on the ordering within adjacency
lists
Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you
make Primâ€™ s algorithm run? What if the edge weights are integers in the range from 1 to W
for some constant W?
Let G = (V, E) be a weighted, directed graph that contains no negative-weight cycles. Let s Â¬ V
be the source vertex, and let G be initialized by INITIALIZE-SINGLE-SOURCE (G, s). Prove
that there exists a sequence of |V | - 1 relaxation steps that produces d[v] = Î´(s, v) for all v âª
Â¬ V.
How can the output of the Floyd-War shall algorithm be used to detect the presence of a
negative-weight cycle?
Define the following terms: syntax, arguments, and algorithm.
Suppose that we have a set of activities to schedule among a large number of lecture halls. We
wish to schedule all the activities using as few lecture halls as possible. Give an efficient greedy
algorithm to determine which activity should use which lecture hall. (This is also known as the
interval-graph coloring prob
Show how to solve the fractional knapsack problem in O (n) time. Assume that you have a
solution to Problem 9-2.
Give a counterexample to the conjecture that if there is a path from u to v in a directed graph G,
then any depth-first search must result in d[v] â‰¤ f[u].
Express the single-pair shortest-path problem as a linear program.
Prove that the number of comparators in any sorting network is Î© (n lg n).
Suppose that a maximum flow has been found in a flow network G = (V, E) using a pusher label
algorithm. Give a fast algorithm to find a minimum cut in G.
Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a
unique light edge crossing the cut. Show that the converse is not true by giving a
counterexample.
Give an O (V + E)-time algorithm to compute the component graph of a directed graph G = (V,
E). Make sure that there is at most one edge between two vertices in the component graph your
algorithm produces.
What are the differences between a bar chart and a column chart? Give an example of when you
would use each one.
Suppose that we order the edge relaxations in each pass of the Bellman-Ford algorithm as
follows. Before the first pass, we assign an arbitrary linear order v1, v2,..., v |v| to the vertices of
the input graph G = (V, E). Then, we partition the edge set E into Ef Â¬âª Eb, where Ef = {(vi,
vj) Â¬âª E: i < j} and Eb =
Suppose we change line 4 of Dijkstra' s algorithm to the following. 4 while |Q| > 1. This change
causes the while loop to execute |V | - 1 times instead of |V | times. Is this proposed algorithm
correct?
Modify your algorithm from Exercise 24.3-6 to run in O ((V + E) lg W ) time. (Hint: How many
distinct shortest-path estimates can there be in V - S at any point in time?)
What does the matrix used in the shortest-paths algorithms correspond to in regular matrix
multiplication?

Show that if (S, â„“) is a matroid, then (S, â„“â€²) is a matroid, where â„“â€² = {Aâ€²: S - Aâ€²
contains some maximal A âª Â¬â„“}. That is, the maximal independent sets of (S, â„“â€²) are
just the complements of the maximal independent sets of (S, â„“).
In the depth-determination problem, we maintain a forest F = (Ti) of rooted trees under three
operations: â€¢ MAKE-TREE (v) creates a tree whose only node is v. â€¢ FIND-DEPTH (v)
returns the depth of node v within its tree. â€¢ GRAFT(r, v) makes node r, which is assumed to
be the root of a tree, become the child of no
Show that line 7 of INITIALIZE-PREFLOW can be changed to 7 h[s] â† |V [G]| - 2 without
affecting the correctness or asymptotic performance of the generic pusher label algorithm.
Suppose we wish not only to increment a counter but also to reset it to zero (i.e., make all bits in
it 0). Show how to implement a counter as an array of bits so that any sequence of n
INCREMENT and RESET operations takes time O(n) on an initially zero counter.
The off-line minimum problem asks us to maintain a dynamic set T of elements from the domain
{1, 2, ..., n} under the operations INSERT and EXTRACT-MIN. We are given a sequence S of n
INSERT and m EXTRACT-MIN calls, where each key in {1, 2, ..., n} is inserted exactly once.
We wish to determine which key is returned by
Prove that for any pair of vertices u and v and any capacity and flow functions c and f, we have
cf (u, v) + cf (v, u) = c(u, v) + c(v, u).
Consider the problem of making change for n cents using the fewest number of coins. Assume
that each coin's value is an integer. a. Describe a greedy algorithm to make change consisting of
quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution. d.
Give an O (nk)-time algorithm that
Show how a system of difference constraints can be solved by a Bellman-Ford-like algorithm

that runs on a constraint graph without the extra vertex v0.
Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of
n words of lengths l1, l2, ..., ln, measured in characters. We want to print this paragraph neatly
on a number of lines that hold a maximum of M characters each. Our criterion of "neatness" is as
follows. If a given line c
Suppose that instead of always selecting the first activity to finish, we instead select the last
activity to start that is compatible with all previously selected activities. Describe how this
approach is a greedy algorithm, and prove that it yields an optimal solution.

What are the differences between a column chart and an area chart? Give an example of when
you would use each one.
Suppose that a flow network G = (V, E) has symmetric edges, that is, (u, v) Â¬âª E if and only
if (v, u) Â¬âª E. Show that the Edmonds-Karp algorithm terminates after at most |V| |E|/4
iterations.
Suppose you are given two sets A and B, each containing n positive integers. You can choose to
reorder each set however you like. After reordering, let ai be the ith element of set A, and let bi
be the ith element of set B. You then receive a payoff of. Give an algorithm that will maximize
your payoff. Prove that your
A sequence of n operations is performed on a data structure. The ith operation costs i if i is an

exact power of 2, and 1 otherwise. Use aggregate analysis to determine the amortized cost per
operation.
Give an efficient algorithm to find the length (number of edges) of a minimum-length negative-
weight cycle in a graph.
Explain how a vertex u of a directed graph can end up in a depth-first tree containing only u,
even though u has both incoming and outgoing edges in G.
Prove that a comparison network with n inputs correctly sorts the input sequence âªÂ¬n, n -
1,..., 1Â¬ if and only if it correctly sorts the n - 1 zero-one sequences âªÂ¬1, 0, 0,..., 0, 0âªÂ¬,
âªÂ¬1, 1, 0,..., 0, 0Â¬âª,..., Â¬âª1, 1, 1,..., 1, 0Â¬âª.
When an adjacency-matrix representation is used, most graph algorithms require time Î© (V2),
but there are some exceptions. Show that determining whether a directed graph G contains a
universal sink-a vertex with in-degree |V| - 1 and out-degree 0-can be determined in time O (V),
given an adjacency matrix for G.
Suppose that you are given an n Ã— n checkerboard and a checker. You must move the checker
from the bottom edge of the board to the top edge of the board according to the following rule.
At each step you may move the checker to one of three squares: 1. The square immediately
above, 2. The square that is one up and one
When should you use a 100% stacked line, column, or area chart? How do the 100% stacked
charts differ from stacked charts?

Let G = (V, E) be a bipartite graph with vertex partition V = L ¬ R, and let G' be its
corresponding flow network. Give a good upper bound on the length of any augmenting path
found in G' during the execution of FORD-FULKERSON.
Show that a depth-first search of an undirected graph G can be used to identify the connected
components of G, and that the depth-first forest contains as many trees as G has connected
components. More precisely, show how to modify depth-first search so that each vertex v is
assigned an integer label cc[v] between 1 an
Prove that the generic pusher label algorithm spends a total of only O(V E) time in performing
all the O(V2) relabel operations.
The edge connectivity of an undirected graph is the minimum number k of edges that must be
removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge
connectivity of a cyclic chain of vertices is 2. Show how the edge connectivity of an undirected
graph G = (V, E) can be determined
Another way to perform topological sorting on a directed acyclic graph G = (V, E) is to

repeatedly find a vertex of in-degree 0, output it, and remove it and all of its outgoing edges from
the graph. Explain how to implement this idea so that it runs in time O (V + E). What happens to
this algorithm if G has cycles?
A directed graph G = (V, E) is said to be semi connected if, for all pairs of vertices u, v Â¬âª V,
we have u â†’v or vâ†’ u. Give an efficient algorithm to determine whether or not G is semi
connected. Prove that your algorithm is correct, and analyze its running time.
Not just any greedy approach to the activity-selection problem produces a maximum-size set of
mutually compatible activities. Give an example to show that the approach of selecting the
activity of least duration from those that are compatible with previously selected activities does
not work. Do the same for the approa
Let G = (V, E) be an undirected, connected graph with weight function w : E â†’ R, and suppose
that |E| â‰¥ |V| and all edge weights are distinct. A second-best minimum spanning tree is
defined as follows. Let be the set of all spanning trees of G, and let Tâ€² be a minimum spanning
tree of G. Then a second-best minimu
An Euler tour of a connected, directed graph G = (V, E) is a cycle that traverses each edge of G
exactly once, although it may visit a vertex more than once. a. Show that G has an Euler tour if
and only if in-degree (v) = out-degree (v) for each vertex v Â¬âª V. b. Describe an O (E)-time
algorithm to find an Euler t
How many comparators are there in SORTER [n]?

Let G be an arbitrary weighted, directed graph with a negative-weight cycle reachable from the
source vertex s. Show that an infinite sequence of relaxations of the edges of G can always be
constructed such that every relaxation causes a shortest-path estimate to change.
A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A
breadth-first tree can also be used to classify the edges reachable from the source of the search
into the same four categories. a. Prove that in a breadth-first search of an undirected graph, the
following properties hold
Suppose that we wish to maintain the transitive closure of a directed graph G = (V, E) as we
insert edges into E. That is, after each edge has been inserted, we want to update the transitive
closure of the edges inserted so far. Assume that the graph G has no edges initially and that the
transitive closure is to be rep
Let G = (V, E) be a weighted, directed graph with source vertex s, and let G be initialized by
INITIALIZE-SINGLE-SOURCE(G, s). Prove that if a sequence of relaxation steps sets Ï€[s] to a
non-NIL value, then G contains a negative-weight cycle.
Give a simple example of a graph such that the set of edges {(u, v): there exists a cut (S, V - S)
such that (u, v) is a light edge crossing (S, V - S)} does not form a minimum spanning tree.
A path cover of a directed graph G = (V, E) is a set P of vertex-disjoint paths such that every
vertex in V is included in exactly one path in P. Paths may start and end anywhere, and they may
be of any length, including 0. A minimum path cover of G is a path cover containing the fewest
possible paths. a. Give an effic
What is the meaning of each of the following error messages? â€¢ ###### â€¢ #NAME? â€¢
#N/A â€¢ #REF! â€¢ #VALUE! â€¢ #NUM! â€¢ #DIV/0!
Let f be a flow in a network, and let Î± be a real number. The scalar flow product, denoted Î± f, is
a function from V Ã— V to R defined by (Î±f)(u, v) = Î± â€¢ f (u, v). Prove that the flows in a
network form a convex set. That is, show that if f1 and f2 are flows, then so is Î±f1 + (1 - Î±) f2
for all Î± in the rang
Give a counterexample to the conjecture that if there is a path from u to v in a directed graph G,
and if d[u] < d[v] in a depth-first search of G, then v is a descendant of u in the depth-first forest
produced.
Explain the difference between a â€œwhat-ifâ€ analysis and Goal Seek by giving an example
based on the worksheet shown in Question 11.
Although merge sort runs in Î˜ (n lg n) worst-case time and insertion sort runs in Î˜(n2) worst-
case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to
use insertion sort within merge sort when sub problems become sufficiently small. Consider a
modification to merge sort in
In order to transform one source string of text x [1 Â¬ m] to a target string y [1 Â¬ n], we can
perform various transformation operations. Our goal is, given x and y, to produce a series of
transformations that change x to y. We use an array zâ€”assumed to be large enough to hold all
the characters it will needâ€”to h
There are two types of professional wrestlers: "good guys" and "bad guys." Between any pair of
professional wrestlers, there may or may not be a rivalry. Suppose we have n professional
wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O (n + r)-
time algorithm that determines wh
A sequence is bitonic if it monotonically increases and then monotonically decreases, or if it can

be circularly shifted to monotonically increase and then monotonically decrease. For example the
sequences ¬1, 4, 6, 8, 3, -2¬, ¬9, 2, -4, -10, -5¬, and ¬1, 2, 3, 4¬ are bitonic, but ¬1, 3, 12, 4, 2,
10¬ is not bitonic. (
What new formula results for each of the following formulas if you copy it from cell C10 to cell
E12? a. =A1+A2 b. =$A$1+A2 c. =$A1+A2 d. =A$1+A2
Let G = (V, E) be a flow network with source s, sink t, and integer capacities. Suppose that we
are given a maximum flow in G. a. Suppose that the capacity of a single edge (u, v) âªÂ¬ E is
increased by 1. Give an O (V + E)-time algorithm to update the maximum flow. b. Suppose that
the capacity of a single edge (u,
We are given a directed graph G = (V, E) on which each edge (u, v) Â¬ E has an associated
value r(u, v), which is a real number in the range 0 â‰¤ r(u, v) â‰¤ 1 that represents the
reliability of a communication channel from vertex u to vertex v. We interpret r(u, v) as the
probability that the channel from u to v will
A sequence of stack operations is performed on a stack whose size never exceeds k. After every
k operations, a copy of the entire stack is made for backup purposes. Show that the cost of n
stack operations, including copying the stack, is O (n) by assigning suitable amortized costs to
the various stack operations.
Binary search of a sorted array takes logarithmic search time, but the time to insert a new
element is linear in the size of the array. We can improve the time for insertion by keeping
several sorted arrays. Specifically, suppose that we wish to support SEARCH and INSERT on a
set of n elements. Let k = [lg (n + 1)], an
Let G = (V, E) be a flow network with source s, sink t, and an integer capacity c (u, v) on each
edge (u, v) Â¬ âª E. Let C = max (u, v) âª Ec (u, v). a. Argue that a minimum cut of G has
capacity at most C |E|. b. For a given number K, show that an augmenting path of capacity at
least K can be found in O(E) time, i
What are the five comparison operators that you can use in Solver?
In a recent court case, a judge cited a city for contempt and ordered a fine of $2 for the first day.
Each subsequent day, until the city followed the judge's order, the fine was squared (that is, the
fine progressed as follows: $2, $4, $16, $256, $65, 536, . . .). a. What would be the fine on day
N? b. How many day
Programs A and B are analyzed and found to have worst-case running times no greater than
150N log2 N and N2, respectively. Answer the following questions, if possible: a. Which
program has the better guarantee on the running time, for large values of N (N > 10,000)? b.
Which program has the better guarantee on the ru
C allows statements of the form #include filename which reads filename and inserts its contents
in place of the include statement. Include statements may be nested; in other words, the file
filename may itself contain an include statement, but, obviously, a file can't include itself in any
chain. Write a program that
Add support for a ListIterator to the MyLinkedList class, as was done in Exercise 3.13. Add
support for a ListIterator to the MyArrayList class. The ListIterator interface in java.util has
more methods than are shown in Section 3.3.5. Notice that you will write a listIterator method to
return a newly constructed ListI
What are the three required parameters of a Solver model and what do they represent?
Swap two adjacent elements by adjusting only the links (and not the data) using: a. Singly linked
lists. b. Doubly linked lists.
Complete the table in Figure 2.2 with estimates for the running times that were too long to
simulate. Interpolate the running times for these algorithms and estimate the time required to
compute the maximum subsequence sum of 1 million numbers. What assumptions have you
made?
What are two advantages of creating a constraints table in a worksheet that includes a Solver
model?
Rewrite the MyLinkedList class without using header and tail nodes and describe the differences
between the class and the class provided in Section 3.5.
What is a scenario in Solver?
What is the difference between a one-variable data table and a two-variable data table? When
would you use each type of data table?
What is an infeasible solution? What steps can you take to attempt to change an infeasible
solution into a feasible solution?
What is an assignment problem?
Write a recursive method that returns the number of 1's in the binary representation of N. Use the
fact that this is equal to the number of 1's in the representation of N/2, plus 1, if N is odd.
a. Write a program to determine if a positive integer, N, is prime. b. In terms of N, what is the

worst-case running time of your program? (You should be able to do this in O(âˆšN).) c. Let B
equal the number of bits in the binary representation of N. What is the value of B? d. In terms of
B, what is the worst-case
What are the types of Solver reports? What information is described in an answer report? What is
the difference between a binding status and a not binding status? What is slack?
What is the difference between the LOOKUP function and the VLOOKUP or HLOOKUP
function?
Describe two methods to document information in a workbook.
The delivery charges used in the Delivery worksheet are as follows: â€¢ For orders under $10,
there is a $6 delivery fee. â€¢ Orders of at least $10 but less than $40 have a $7.50 delivery fee.
â€¢ Orders over $40 are delivered free of charge. Create a lookup table for the Delivery
worksheet so that you can use a l
Identify three ways to run a macro in Excel.

Suppose T1(N) = O(f (N)) and T2(N) = O(f (N)). Which of the following are true? a. T1(N) +
T2(N) = O(f (N)) b. T1(N) âˆ’ T2(N) = o(f (N)) c. T1(N) / T2(N) = O(1) d. T1(N) = O(T2(N))
Explain the steps you must take to import data stored in an Access database into Excel.
Prove the following formulas: a. b.
True or False. 1. The lookup_value of a HLOOKUP function can be a continuous cell range. 2.
In a VLOOKUP formula with a TRUE lookup type, the lookup table referenced must be in
ascending order to retrieve the correct value. 3. The result_vector of a LOOKUP function must
be sorted in ascending order. 4. Reference an
An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the
running time is the following (assume low-order terms are negligible): a. Linear b. O(N logN) c.
Quadratic d. Cubic
Explain the difference between the lookup table in cells A3:E4 of the Grades worksheet and the
lookup table in cells A6:E7 in the same worksheet.
Estimate NÎ£i=[N/2] 1/i
Write a program to evaluate a postfix expression.
Suppose you need to generate a random permutation of the first N integers. For example, {4, 3,
1, 5, 2} and {3, 1, 4, 2, 5} are legal permutations, but {5, 4, 1, 2, 1} is not, because one number
(1) is duplicated and another (3) is missing. This routine is often used in simulation of
algorithms. We assume the existence
Explain the two basic steps you must perform to protect the contents of a worksheet.
What is the Query Wizard and when would you use it?
List and describe the eight available options when using the AutoFilter feature in an Excel Table.
Compare break-even analysis and sensitivity analysis.
What are the advantages and disadvantages of using the Subtotal tool to analyze data?
An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the
running time is the following (assume low-order terms are negligible): a. linear b. O(N logN) c.
quadratic d. cubic
List and describe the steps you would take to create a structured list of data from a text file that
contains values stored on separate lines.
How does a radar chart differ from other charts? Give an example of when you would consider
using a radar chart.
Explain how you must vary the setup of a two-variable data table to run a simulation.
When should you create a scenario instead of a data table? Give an example of a business
situation that could best be analyzed with scenarios.
How do sparklines differ from charts?
For MyLinkedList, implement addFirst, addLast, removeFirst, removeLast, getFirst, and getLast
by making calls to the private add, remove, and getNode routines, respectively.
How does a data table help you perform what-if analysis?
You are given a list, L, and another list, P, containing integers sorted in ascending order. The
operation printLots(L,P) will print the elements in L that are in positions specified by P. For
instance, if P = 1, 3, 4, 6, the elements in positions 1, 3, 4, and 6 in L are printed. Write the
procedure printLots(L,P). You
A majority element in an array, A, of size N is an element that appears more than N/2 times
(thus, there is at most one). For example, the array 3, 3, 4, 2, 4, 4, 2, 4, 4 has a majority element
(4), whereas the array 3, 3, 4, 2, 4, 4, 2, 4 does not. If there is no majority element, your program
should indicate this
a. Propose a data structure that supports the stack push and pop operations and a third operation
findMin, which returns the smallest element in the data structure, all in O(1) worst-case time. b.
Prove that if we add the fourth operation deleteMin which finds and removes the smallest
element, then at least one of the
What is a data validation rule? When would you use the Circle Invalid Data feature?
Let Fi be the Fibonacci numbers as defined in Section 1.2. Prove the following: a. Î£Nâˆ’2i=1 Fi
= FN âˆ’ 2 b. FN < Ï•N, with Ï• = (1 + âˆš5)/2 c. Give a precise closed-form expression for FN.
What are the three steps involved in using the INSERT tab to create a chart?
What is 2100 (mod 5)?

Find two functions f (N) and g(N) such that neither f (N) = O(g(N)) nor g(N) = O(f (N)).
What is the difference between an input message and an error alert in the context of Excel data
validation?
When should you include integer constraints in a Solver model? What is the disadvantage of
using an integer constraint?
Write the fast exponentiation routine without recursion.
What is an unbounded solution?
Determine, for the typical algorithms that you use to perform calculations by hand, the running
time to do the following: a. Add two N-digit integers. b. Multiply two N-digit integers. c. Divide
two N-digit integers.
Define a bubble chart and explain what type of data is suitable for plotting on a bubble chart.
An alternative to providing a ListIterator is to provide a method with signature Iterator

reverseIterator( ) that returns an Iterator, initialized to the last item, and for which next and
hasNext are implemented to be consistent with the iterator advancing toward the front of the list,
rather than the back. Then you
What are false positives and false negatives, and which are harder to detect in worksheets?
How do you import an XML map into a workbook and map its elements into the worksheet?
What chart sub-types are available for the stock chart in Excel? Explain how you interpret the
data markers on each of the sub-types.
What is the difference between a linear function and a nonlinear function?
Show that X62 can be computed with only eight multiplications.
Order the following functions by growth rate: N, âˆšN, N1.5, N2, N logN, N log logN, N log2 N,
N log(N2), 2/N, 2N, 2N/2, 37, N2 logN, N3. Indicate which functions grow at the same rate.
List and describe the four areas of a PivotTable report.

An alternative to the deletion strategy we have given is to use lazy deletion. To delete an
element, we merely mark it deleted (using an extra bit field). The number of deleted and
nondeleted elements in the list is kept as part of the data structure. If there are as many deleted
elements as nondeleted elements, we tra
Assume that a singly linked list is implemented with a header node, but no tail node, and that it
maintains only a reference to the header node. Write a class that includes methods to a. Return
the size of the linked list b. Print the linked list c. Test if a value x is contained in the linked list
d. Add a value x
What is a macro? How could you use one in an Excel workbook?
How does Excel store date and time values?
Describe the steps for saving a Solver model. What is the advantage of saving a Solver model?
What is the primary advantage of storing data in a database and importing that data into Excel?
Suppose that line 15 in the binary search routine had the statement low = mid instead of low =
mid + 1. Would the routine still work?
Suppose that lines 15 and 16 in algorithm 3 (Fig. 2.7) are replaced by 15......................int
maxLeftSum = maxSubSum( a, left, center - 1 ); 16......................int maxRightSum =
maxSubSum( a, center, right ); Would the routine still work?
Describe the steps you would take to import XML data as an XML Table in Excel.
Why is it important to assume that integers in our computer model have a fixed size?
Write routines to implement two stacks using only one array. Your stack routines should not
declare an overflow unless every slot in the array is used.
Evaluate the following sums: a. Î£âˆži=0 1/4i b. Î£âˆži=0 i/4i c. Î£âˆži=0 i2/41 d. Î£âˆži=0 iN/4i
Give a precise count on the number of multiplications used by the fast exponentiation routine.
Provide an implementation of a removeAll method for the MyLinkedList class. Method

removeAll removes all items in the specified collection given by items from the MyLinkedList.
Also provide the running time of your implementation. The method signature for you to use is
slightly different than the one in the Java Collec
What is the difference between a policy constraint and a physical constraint? Give one example
of each type of constraint.
How do you change the chart type of an existing chart?
a. Write a program to convert an infix expression that includes (, ), +, -, *, and / to postfix. b.

Add the exponentiation operator to your repertoire. c. Write a program to convert a postfix
expression to infix.
Prove the following formulas: a. log X < X for all X > 0 b. log(AB) = B log A
For each of the following six program fragments: a. Give an analysis of the running time (Big-
Oh will do). b. Implement the code in Java, and give the running time for several values of N. c.
Compare your analysis with the actual running times. (1) sum = 0; for( i = 0; i < n; i++ ) sum++;
(2) sum = 0; for( i =
What is a decision support system?
Prove that for any constant, k, logk N = o(N).
Repeat Exercise 3.11, maintaining the singly linked list in sorted order. Assume that a singly
linked list is implemented with a header node, but no tail node, and that it maintains only a
reference to the header node. Write a class that includes methods to a. Return the size of the
linked list b. Print the linked l
Which function grows faster: N log N or N1+Îµ / âˆšlog N, Îµ > 0?
How much time is required to compute f (x) = Î£Ni=0 aixi: a. Using a simple routine to perform
exponentiation? b. Using the routine in Section 2.4.4?
Design efficient algorithms that take an array of positive numbers a, and determine: a. the
maximum value of a[j] + a[i], with j â‰¥ i. b. the maximum value of a[j] - a[i], with j â‰¥ i. c.
the maximum value of a[j] * a[i], with j â‰¥ i. d. the maximum value of a[j] / a[i], with j â‰¥ i.
What are the differences and similarities between a line chart and an X Y (Scatter) chart? When
should you use each one?
Add support for a ListIterator to the MyArrayList class. The ListIterator interface in java.util has
more methods than are shown in Section 3.3.5. Notice that you will write a listIterator method to
return a newly constructed ListIterator, and further, that the existing iterator method can return a
newly constructed Li
Show how to implement three stacks in one array.
The Sieve of Eratosthenes is a method used to compute all primes less than N. We begin by
making a table of integers 2 to N. We find the smallest integer, i, that is not crossed out, print i,
and cross out i, 2i, 3i, . . . . When i > âˆšN, the algorithm terminates. What is the running time of
this algorithm?
Match the information below A. Compound Interest E. IRR I. PMT M. ROI B. CUMIPMT F.
NPER J. PPMT N. Simple Interest C. FV G. NPV K. PV O. SLN D. IPMT H. Payback
Period L. RATE P. Type 1. Function to calculate value of the end of a financial transaction 2.
Function to calculate the inte
Give an efficient algorithm to determine if there exists an integer i such that Ai = I in an array of
integers A1 < A2 < A3 < Â• Â• Â• < AN. What is the running time of your algorithm?
Explain the difference between the data points in a line chart and an X Y (Scatter) chart.
The inner loop of the cubic maximum subsequence sum algorithm performs N(N+1)(N+2)/6
iterations of the innermost code. The quadratic version performs N(N + 1)/2 iterations. The linear
version performs N iterations. What pattern is evident? Can you give a combinatoric explanation
of this phenomenon?
The input is an N by N matrix of numbers that is already in memory. Each individual row is
increasing from left to right. Each individual column is increasing from top to bottom. Give an
O(N) worst-case algorithm that decides if a number X is in the matrix.
What is the advantage of linking the constraints in the Solver Parameters dialog box to values in
a constraints table in the worksheet?
Look at the list of things that the re planning agent canâ€™t do. Sketch an algorithm that can
handle one or more of them.
Section 10.5 used the predicates Link and Link Text to describe connections between web pages.
Using the In Tag and Get Page predicates, among others, write definitions for Link and Link
Text.
The following quotes are from the backs of shampoo bottles. Identify each as an unconditional,
conditional, or execution monitoring plan. (a) â€œLather, Rinse, Repeat,â€™ (b) â€œApply
shampoo to scalp and let it remain for several minutes. Rinse and repeat if necessaryâ€™ (c)
â€œSee a doctor if problems persist:â€™
Write out the axioms required for reasoning about the wumpusâ€™s location, using a constant
symbol Wumpus and a binary predicate In (Wumpus, Location). Remember that there is only
one wumpus.
Trace the execution of the backward chaining algorithm in figure when it is applied solves the
crime problem. Show the sequence of values taken on by the goals variable, and arrange them
into a tree.
Rewrite the propositional wumpus world facts from Section 7.5 into first-order logic. How much
more compact is this version?
Explain how to write any given 3-SAT problem of arbitrary size using a single first-order
definite clause and no more than 30 ground facts.
Figure shows a blocks-world problem known as the Sussman anomaly. The problem was
considered anomalous because the non interleaved planners of the early 1970s could not solve it.
Write a definition of the problem in STRIPS notation and solve it, either by hand or with a
planning program. A non interleaved planner is a
Define the predicates Before, After, during, and Overlap, using the predicate Meet and the
functions Start and End, hut not the function Time or the predicate <.
Write down logical representations for the following sentences, suitable for use with Generalized
Modus Ponens: a. Horses, cows and pigs arc mammals. b. An offspring of a horse is a horse. c.
Bluebeard is a horse, d. Bluebeard is Charlieâ€™s parent. e. Offspring and parent are inverse
relations. f. Every mammal has a p
Explain why the process for generating predecessors in backward search does not need to add the
literals that are negative effects of the action.
Giving examples from the airport domain, explain how symbol-splitting reduces the size of the
precondition axioms and the action exclusion axioms. Derive a general formula for the size of
each axiom set in terms of the number of rime steps, the number of action schemata, their antics,
and the number of objects.
Using the set axioms as examples write axioms for the list domain, including all the constants,
functions, and predicates mentioned in the chapter.
Write axioms describing the predicates Grand Child, Great Grandparent, Brother, Sister,
Daughter, Son, Aunt, Uncle, Brother In Law, Sister In Law, and First cousin. Find out the proper
definition of mth cousin n times removed, and write the definition in first-order logic. Now write
down the basic facts depicted in the
The following Prolog code defines a predicate P: P(X, [X | Y]). P (X, [Y| Z]):- P (X, Z). a. Show
proof trees and solutions for the queries P (A, [1, 2, 3]) and P (2, [1, A, 3]) b. What standard list
operation does P represent?
Show how a standard STRIPS action description can be rewritten as HTN decomposition, using
the notation Achieve (p) to denote the activity of achieving the condition p.
One might suppose that the syntactic distinction between unboxed links and singly boxed links in
semantic networks is unnecessary, because singly boxed links are always attached to categories
an inheritance algorithm could simply assume that an unboxed link attached to a category is
intended to apply to all members of
Write action descriptions, analogous to Equation (12.2), for the Right and Suck actions. Also
write a description for Cheek Location, analogous to Equation (12.3). Repeat using the
alternative set of propositions from Exercise 12.11.
A diffuse surface having the following spectral characteristics is maintained at 500 K when
situated in a large furnace enclosure whose walls are maintained at 1500 K: (a) Sketch the
spectral distribution of the surface emissive power E A and the emissive power EÎ»,h that the
surface would have if it were a blackbody.
Add rules to extend the definition of the predicate Name (s, c.) so that a siring such as â€œlaptop
computerâ€ matches against the appropriate category names from a variety of stores. Try to
make your definition general. Test it by looking at ten online stores, and at the category names
they give for three different c
A popular childrenâ€™s riddle is â€˜Brothers and sisters have I none, but that manâ€™s father
my fatherâ€™s son.â€ Use the rules of the family domain to show who that man is. You may
apply any of the inference methods described in this chapter. Why do you think that this riddle is
difficult?
After your yearly checkup, the doctor has bad news and good news. The bad news is that you
tested positive for a serious disease and that the test is 99% accurate (i.e., the probability of
testing positive when you do have the disease is 0.99, as is the probability of testing negative
when you donâ€™t have the disease)
Consider the subscription lattices shown in Figure. a. Construct the lattice for the sentence
Employs (Mother (John), Father (Richard)). b. Construct the lattice for the sentence Employs
(IBM. y) (â€œEveryone works for IBMâ€). Remember to include every kind of query that
unifies with the sentence. c. Assume that STORE
Consider the following problem: A patient arrives at the doctorâ€™s office with symptoms that
could have been caused either by dehydration or by disease D (but not both). There are two
possible actions: Drink, which unconditionally cures dehydration, and Medicate, which cures
disease D, but has an undesirable side-effe
Specify in full the belief state update procedure for partially observable environments. That is,
the method for computing the new belief state representation (as a list of knowledge
propositions) from the current belief-state representation and an action description with
conditional effects.
We said in this chapter that resolution cannot be used to generate all logical consequences of a
set of sentences. Can any algorithm do this?
In this exercise, we will look at sorting in Prolog. a. Write Prolog clauses that define the
predicate sorted (L), which is true if and only if list L is sorted in ascending order. b. Write a
Prolog definition for the predicate perm (L, M), which is true if and only if L is a permutation of
M. c. Define sort (L, M) (M
How can resolution be used to show that a sentence is valid un-satisfiable?
Using the axioms of probability prove that any probability distribution on a discrete random
variable must sum to 1.
Why canâ€™t conditional planning deal with unbounded indeterminacy?
Figure shows the top levels of a hierarchy for everything. Extend it to include as many real
categories as possible. A good way to do this is to cover all the things in your everyday life. This
includes objects and events. Start with waking up, and proceed in an orderly fashion noting
everything that you see, touch, do
Prove the following assertions about planning graphs: â€¢ A literal that does not appear in the
final level of the graph cannot he achieved. â€¢ The level cost of a literal in a serial graph is no
greater than the actual cost of an optimal plan for achieving it.
Describe the differences and similarities between problem solving and planning.
To the medication problem in the previous exercise, add a Jest action that has the conditional
effect Culture Growth when Disease is true and in any case has the perceptual effect Know
(Culture Growth). Diagram a conditional plait that solves the problem and minimizes the use of
the Medicate action.
One part of the shopping process that was not covered in this chapter is checking for
compatibility between items. For example, if a customer orders a computer, is it matched with
the right peripherals? If a digital camera is ordered, does it have the right memory card and
batteries? Write a knowledge base that will de
Examine carefully the representation of time and resources in Section 12.1. a. Why is it a good
idea to have Duration (d) be an effect of an action, rather than having a separate field in the
action of the form DURATION: d? b. Why is RFSOURCE: m a separate field in the action,
rather than being an effect?
In this exercise, we will consider the problem of planning a route for a robot to take from one
city to another. The basic action taken by the robot is Go (x, y), which takes it from City x to city
y if there is a direct route between those cities. Direct Route (x, y) is true if and only if there is a
direct route from
We saw that planning graphs can handle only propositional actions. What if we want to use
planning graphs for a problem with variables in the goal, such as At (P1, x) ^ At (P2, x), where x
ranges over a finite domain of locations? How could you encode such a problem to work with
planning graphs?
You are to create a system for advising computer science undergraduates on what courses to take
over an extended period in order to satisfy the program requirements. (Use whatever
requirements are appropriate for your institution.) First, decide on a vocabulary for representing
all the information, and then represent i
Explain why dropping negative effects from every action schema in a STRIPS problem results in
a relaxed problem.
The circuit representation in the chapter is more detailed than necessary if we care only about
Circuit functionality. A simpler formulation describes any rn-input, n-output gate or circuit using
a predicate with m + n arguments, such that the predicate is true exactly when the inputs and
outputs are consistent. For ex
Write a set of sentences that allows one to calculate the price of an individual tomato (or other
object), given the price per pound. Extend the theory to allow the price of a bag of tomatoes to be
calculated.
Consider the following argument: In a framework that allows uncertain initial stares, disjunctive
effects are just a notational convenience, not a source of additional representational power. For
any action schema a with disjunctive effect P V Q, we could always replace it with the
conditional effects when R: P ^ when
Consider the domain of dealing 5-card poker hands from a standard deck of 52 cards, under the
assumption that the dealer is fair. a. How many atomic events are there in the joint probability
distribution (i.e., how many 5-card hands are there)? b. What is the probability of each atomic
event? c. What is the probability
Give an example in the house-building domain of two abstract sub plans that cannot be merged
into a consistent plan without sharing steps.
Prove from first principles that Universal Instantiation is sound and that Existential Instantiation
produces an inferentially equivalent knowledge base.
b. Is (A) true under this interpretation? c. Is (B) true under this interpretation? d. Does (A)
logically entail (B)? e. Does (B) logically entail (A)? f. Using resolution, try to prove that (A)
follows from (B). Do this even if you think that (B) does not logically entail (A); Continue until
the proof breaks down and
An alternative scheme for representing measures involves applying the units function to an
abstract length object. In such a scheme, one would write Inches (Length (L1)) = 1.5. How does
this scheme compare with the one in the chapter? Issues include conversion axioms, names for
abstract quantities (such as â€œ50 dollar
Show that the three forms of independence in Equation (13.8) are equivalent.
A consumable resource is a resource that is (partially) used up by an action. For example,

attaching engines to cars requires screws. The screws, once used, are not available for other
attachments. a. Explain how to modify the representation in Figure so that there are 100 screws
initially, engine E1 requires 40 screws
This exercise concerns the relationships between event categories and the time intervals in which
they occur, a. Define the predicate T(c, i) in terms of during and Ð„. b. Explain precisely why we
do not need two different notations to describe conjunctive event categories. c. Give a formal
definition for T (One Of
One might suppose that we can avoid the problem of variable conflict in unification during
backward chaining by standardizing apart all of the sentences in the knowledge base once and
for all. Show that, for some sentences, this approach cannot work.
Given the axioms from Figure, what are all the applicable concrete instances of Fly (p, from, to)
in the state described by At (P1, JFK) ^ At (P2, SF0) ^ Plane (P1) ^ Plane (P2) A Airport (JFK) ^
Airport(SFO)?
Our description of Internet shopping omitted the all-important step of actually buying the
product Provide a formal logical description of buying, using event calculus That is, define the
sequence of events that occurs when a buyer submits a credit card purchase and then eventually
gets billed and receives the product.
Conditional effects were illustrated for the Suck action in the vacuum worldâ€”which square
becomes clean depends on which square the robot is in. Can you think of a new set of
propositional variables to define states of the vacuum world, such that Suck has an unconditional
description? Write out the descriptions of Su
A complete solution to the problem of inexact matches to the buyerâ€™s description in shopping
is very difficult and requires a full array of natural language processing and information retrieval
techniques. (See Chapters 22 and 23) One small step is to allow the user to specify minimum and
maximum values for various a
The two preceding exercises assume a fairly primitive notion of ownership. For example, the
buyer starts by owning the dollar bills. This picture begins to break down when, for example,
oneâ€™s money is in the bank, because there is no longer any specific collection of dollar bills
that one owns. The picture is complic
In this exercise, we will look at the recursive application of rewrite rules, using logic
programming. A rewrite rule (or demodulator in OTTER terminology) is an equation with
specified direction. For example, the rewrite rule x + O ( x suggests replacing any expression that
matches x + 0 with the expression x. The app
Write sentences to define the effects of the Shoot action in the wumpus world. Describe its
effects on the wumpus and remember that shooting uses the agentâ€™s arrow
From â€œHorses are animals:â€™ it follows that â€œThe head of a horse is the head of
animal.â€ Demonstrate that this inference is valid by carrying out the following steps: a.
Translate the premise and the conclusion into the language of first-order logic. Use three
predicates: Head Of (h, x) (meaning â€œhis head of x

Write definitions for the following: a. Exhaustive Part Decomposition b. Part Partition c. Part
wise Disjoint These should he analogous to the definitions for Exhaustive Decomposition,
Partition, and Disjoint. Is it the case that Part Partition (s, Bunch Of(s))? If so, prove it; if not,
give a counterexample and define
In the blocks world we were forced to introduce two STRIPS actions, Move and Move to Table,
in order to maintain the clear predicate properly. Show how conditional effects can be used to
represent both of these cases with a single action.
The original STRIPS program was designed to control Shakey the robot Figure shows a version
of Shakeyâ€™s world consisting of four rooms lined up along a corridor, where each room has a
door and a light switch. The actions in Shakeyâ€™s world include moving from place to place,
pushing movable objects (such as boxes) c
Consider the problem of putting on oneâ€™s shoes and socks, as defined in Section 11.3. Apply
GRAPHPLAN to this problem and show the solution obtained. Now add actions for putting on a
coat and a hat. Show the partial order plan that is a solution, and show that there are 180 different
linearizationâ€™s of the partial-
In this question we will use the sentences you wrote in Exercise 9.9 to answer a question using a
backward-chaining algorithm. a. Draw the proof tree generated by an exhaustive backward-
chaining algorithm for the query Ð¬h Horse (h), where clauses arc matched in the order given. b.
What do you notice about this domai
Give decompositions for the Hire Builder and Get Permit steps in Figure, and show how the
decomposed sub plans connect into the overallplan.
Suppose we put into a logical database a segment of the U.S. census data listing the age, city of
residence, date of birth, and mother of every person, using social security numbers as identifying
constants for each person. Thus, Georgeâ€™s age is given by Age (443-65-1282, 56). Which of
the indexing schemes S1 â€”S5 f
Explain what is wrong with the following proposed definition of adjacent squares in the
wumpusworld:
Explain what is wrong with the following proposed definition of the set membership predicate
â‚¬:
Represent the following seven sentences using and extending the representations developed in
the chapter: a. Water is a liquid between 0 and 100 degrees. b. Water boils at 100 degrees. c The
water in Johnâ€™s water bottle is frn7en. d. Perrier is a kind of water. e. John has Perrier in his
water bottle. f. All liquids
This question deals with the properties of atomic events, as discussed. a. Prove that (lie
disjunction of all possible atomic events is logically equivalent to true. b. Prove that any
proposition is logically equivalent to the disjunction of the atomic events that entail its truth.
Resolution can produce non-constructive proofs for queries with variables, so we had to
introduce special mechanisms to extract definite answers. Explain why this issue does not arise
with knowledge bases containing only definite clauses.
Write down a sentence asserting that + is a commutative function. Does your sentence follow
from the Peano axioms? If so explain why: if not, give a model in which the axioms are true and
your sentence is false.
Would it he rational for an agent to hold the three beliefs P (A) = 0.4, P (B) = 0.3, and P (A V B)
= 0.5? If so, what range of probabilities would be rational for the agent to hold for A ^ B. Make
tip a table like the one in Figure, and show how it supports your argument about rationality. Then
draw another version of
What axiom is needed to infer the fact Female (Laura) given the facts Male (Jim) and Spouse
(Jim, Laura)?
Extend the vocabulary from Section 8.4 to define addition for n-bit binary numbers. Then encode
the description of the four-bit adder in Figure and pose the queries needed to verify that it is in
factcorrect.
We saw that planning graphs can handle only propositional actions. What if we want to use
planning graphs for a problem with variables in the goal, such as At (P1, x) ^ At (P2, x), where x
ranges over a finite domain of locations? How could you encode such a problem to work with
planning graphs?
Construct a representation for exchange rates between currencies that allows fluctuations on a
daily basis.
Represent the sentence â€œAll Germans speak the same languagesâ€ in predicate calculus. Use
Speaks (x, 1), meaning that person x speaks language l.
Let us consider how we might translate a set of STRIPS schemata into the successor-state
axioms of situation calculus. â€¢ Consider the schema for Fly (p, from. to). Write a logical
definition for the predicate Fly Precond (p, from. to, s), which is true if the preconditions for Fly
(p, from, to) are satisfied in situa

Describe the event of trading something for something else. Describe buying as a kind of trading
in which one of the objects traded is a sum of money.
Given the full joint distribution shown in Figure, calculate the following: a. P (toothache) b. P
(Cavity) c. P (Toothache â”‚cavity) d. P (Cavity â”‚ toothache V catch).
For each pair of atomic sentences, give the most general unifier if it exists: a. P(A, B, B), P(x, y,
z). b. Q(y, G (A, B)), Q (G(x, x), y) c. Older (Father (y), y), Older (Father(x), John). d. Knows
(Father (y), y), Knows(x, x).
From Likes (Jerry, Ice Cream) it seems reasonable to infer Ð¬x Likes (x, Ice Cream). Write
down a general inference rule, Existential Introduction that sanctions this inference. State
carefully the conditions that must be satisfied by the variables and terms involved.
We contrasted forward and backward state-space search planners with partial-order planners,
saying that the latter is a plan-space searcher. Explain how forward and backward state-space
search can also be considered plan-space searchers, and say what the plan refinement operators
are.
In this exercise, we will consider the implementation of search algorithms in Prolog. Suppose
that successor (X, Y) is true when state Y is a successor of state X; and that goal (X) is true when
X is a goal state. Write a definition for solve (X, P), which means that P is a path (list of states)
beginning with X, endin
Define the predicate Fixed, where Fixed (Location(x)) means that the location of object x is fixed
over time.
Write out the full description of Suck for the double Murphy vacuum cleaner that sometimes
deposits dirt when it moves to a clean destination square and sometimes deposits dirt if Suck is
applied to a clean square.
The monkey-and-bananas problem is faced by a monkey in a laboratory with some bananas

hanging out of reach from the ceiling. A box is available that will enable the monkey to reach the
bananas if he climbs on it. Initially, the monkey is at A, the bananas at B. and the box at C. The
monkey and box have height Low, hut
Write a general set of facts and axioms to represent the assertion â€˜Wellington heard about
Napoleonâ€™s deathâ€ and to correctly answer the question â€˜Did Napoleon hear about
Wellingtonâ€™s death?â€

Computer Science Textbook Solutions - 9

Uploaded by

Copyright:

Available Formats

Computer Science Textbook Solutions - 9

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Computer Science Textbook Solutions - 9

Uploaded by

Copyright:

Available Formats

a. How many bits are required per node to store the height of a node in an N-node AVL tree? b.

Show the result of inserting keys 1 to 15 in order into a skew heap.

Give an example of input that generates the best leftist heap.

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

Prove that a binomial tree of height k has (kd) nodes at depth d.

See Full Question And Answer at solutionrank.com

Extend the classic cuckoo hash table to use d hash functions.

See Full Question And Answer at solutionrank.com

Can both insert and findMin be implemented in constant time?

Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

Implement the contains routine for MyLinkedList.

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

We can represent an n-input comparison network with c comparators as a list of c pairs of

See Full Question And Answer at solutionrank.com

How do pie charts differ from doughnut charts?

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

Prove that any sorting network on n inputs has depth at least lg n.

See Full Question And Answer at solutionrank.com

Define the following terms: syntax, arguments, and algorithm.

See Full Question And Answer at solutionrank.com

Express the single-pair shortest-path problem as a linear program.

Prove that the number of comparators in any sorting network is Î© (n lg n).

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

Show how a system of difference constraints can be solved by a Bellman-Ford-like algorithm

See Full Question And Answer at solutionrank.com

A sequence of n operations is performed on a data structure. The ith operation costs i if i is an

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

Another way to perform topological sorting on a directed acyclic graph G = (V, E) is to

See Full Question And Answer at solutionrank.com

How many comparators are there in SORTER [n]?

See Full Question And Answer at solutionrank.com

A sequence is bitonic if it monotonically increases and then monotonically decreases, or if it can

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

See Full Question And Answer at solutionrank.com

What is a scenario in Solver?

What is an assignment problem?

See Full Question And Answer at solutionrank.com

a. Write a program to determine if a positive integer, N, is prime. b. In terms of N, what is the

Describe two methods to document information in a workbook.

See Full Question And Answer at solutionrank.com

Identify three ways to run a macro in Excel.

Prove the following formulas: a. b.

See Full Question And Answer at solutionrank.com

Estimate NÎ£i=[N/2] 1/i

Write a program to evaluate a postfix expression.

See Full Question And Answer at solutionrank.com