text:
## Friday, February 14, 2014

### capturing stdout in a python child process

Lately at work I've been putting together a web management console that handles execution of some of our long running Gurobi models. This makes a lot of sense to do since the models run on Gurobi Cloud for hours or even days before achieving their desired optimality gaps. Gurobi Cloud requires a persistent connection, so we use a server to handle that instead of solving models from our desktop machines. In a sense, this is a bit of a throwback to the time sharing systems from before the PC era.

As a result, I've had to update my dormant (and, to be honest, never particularly acute) administration and systems programming skills. There are always some interesting gotchas that come up in this sort of work. This time I ran into the following conundrum: I have a cron job that is responsible for constructing model instances in a child process, handing them off to Gurobi Cloud, and saving their results. Its output is redirected to a file so I can tail it in real time and store it for later. For the web console, I also want to store the output to a database so I can easily display it. And I'd like to do this in as generic a manner as possible, so I can add other types of models (custom heuristics, for instance) and also capture anything they write to standard output and standard error.

There are a number of threads available on capturing standard output. Some of the advice I found recommended using os.dup2 to clone the stdout file descriptor into another file. The problem with this approach is it requires having an open file, which is inconvenient, and it ends up closing the existing stdout. So the output does get redirected, but then it disappears from my log. Also, I could only seem to capture it once. I wanted to do this repeatedly.

Other advice got me closer to the mark: Replace sys.stdout with an instance of StringIO, then just read its contents later. This allowed me to do redirections in serial, but once again meant that standard output was essentially shut off.

The final solution was to subclass StringIO and override its write method. Every time write is called, it writes to both the in-memory string and a canonical reference to stdout. Example code is given below that captures stdout and stderr from a child process while still letting their messages be visible.

from StringIO import StringIO
from multiprocessing import Process, Queue
import sys

# Proxy classes that both write to and capture strings
# sent to stdout or stderr, respectively.
class TeeOut(StringIO):
def write(self, s):
StringIO.write(self, s)
sys.__stdout__.write(s)

class TeeErr(StringIO):
def write(self, s):
StringIO.write(self, s)
sys.__stderr__.write(s)

class Parent(object):
def run(self):
# Start child process.
queue = Queue()
child = Process(target=self.spawn, args=(queue,))
child.start()
child.join()

# Do someting with out and err...
out = queue.get()
err = queue.get()

def spawn(self, queue):
# Save everything that would otherwise go to stdout.
out = TeeOut()
sys.stdout = out

err = TeeErr()
sys.stderr = err

try:
# Do something...
print 'out 1'
print 'out 2'
sys.stderr.write('error 1\n')
print 'out 3'
sys.stderr.write('error 2\n')

finally:
# Restore stdout, stderr and send their contents.
sys.stdout = sys.__stdout__
sys.stderr = sys.__stderr__
queue.put(out.getvalue())
queue.put(err.getvalue())

if __name__ == '__main__':
Parent().run()

A few minor points:

• StringIO can't be subclassed like object-based types, thus lines 9 and 14 can't use super.
• The sys module keeps two references to stdout: sys.stdout and sys.__stdout__. We use the latter to recover the former after processing.
• The contents of standard out and standard error are transmitted from the child process to its parent at the end of processing. A smarter implementation might transfer chunks of them periodically, but I'm not expecting them to be large.
• The transfer happens in a finally block. Thus any run time exception in the child will not interfere with logging.

## Monday, February 3, 2014

### chebyshev centers of polygons with gurobipy

A common problem in handling geometric data is determining the center of a given polygon. This is not quite so easy as it sounds as there is not a single definition of center that makes sense in all cases. For instance, sometimes computing the center of a polygon's bounding box may be sufficient. In some instances this may give a point on an edge (consider a right triangle). If the given polygon is non-convex, that point may not even be inside or on its boundary.

This post looks at computing Chebyshev centers for arbitrary convex polygons. We employ essentially the same model as in Boyd & Vandenberghe's Convex Optimization text, but using Gurobi instead of CVXOPT.

Consider a polygon defined by the intersection of a finite number of half-spaces, $Au \le b$. We assume we are given the set of vertices, $V$, in clockwise order around the polygon. $E$ is the set of edges connecting these vertices. Each edge in $E$ defines a boundary of the half-space $a_i'u \le b_i$.

$V = \{(1,1), (2,5), (5,4), (6,2), (4,1)\}$
$E = \{((1,1),(2,5)), ((2,5),(5,4)), ((5,4),(6,2)), ((6,2),(4,1)), ((4,1),(1,1))\}$

The Chebyshev center of this polygon is the center point $(x, y)$ of the maximum radius inscribed circle. That is, if we can find the largest circle that will fit inside our polygon without going outside its boundary, its center is the point we are looking for. Our decision variables are the center $(x, y)$ and the maximum inscribed radius, $r$.

In order to do this, we consider the edges independently. The long line segment below shows an arbitrary edge, $a_i'u \le b_i$. The short line connected to it is orthogonal in the direction $a$. $(x, y)$ satisfies the inequality.

The shortest distance from $(x, y)$ will be in the direction of $a$. We'll call this distance $r$. If we were to move the edge so it had the same slope but went through $(x, y)$, its distance from $a_i'u = b_i$ would be $r||a_i||_2$. Thus we can add a constraint of the form $a_i'u + r||a_i||_2 \le b_i$ for each edge and maximize the value of $r$ as our objective function.

max $r$
subject to $(y_i-y_j)x + (x_j-x_i)y + r\sqrt{(x_j-x_i)^2 + (y_j-y_i)^2} \le (y_i-y_j)x_i + (x_j-x_i)y_i\, \forall\, ((x_i,y_i), (x_j,y_j)) \in E$

As this is linear, we can solve it using any LP solver. The following code does so with Gurobi.

#!/usr/bin/env python
from gurobipy import Model, GRB
from math import sqrt

vertices = [(1,1), (2,5), (5,4), (6,2), (4,1)]
edges = zip(vertices, vertices[1:] + [vertices[0]])

m = Model()
m.update()

for (x1, y1), (x2, y2) in edges:
dx = x2 - x1
dy = y2 - y1
m.addConstr((dx*y - dy*x) + (r * sqrt(dx**2 + dy**2)) <= dx*y1 - dy*x1)

m.setObjective(r, GRB.MAXIMIZE)
m.optimize()

print 'r = %.04f' % r.x
print '(x, y) = (%.04f, %.04f)' % (x.x, y.x)

The model output shows our center and its maximum inscribed radius.

r = 1.7466
(x, y) = (3.2370, 2.7466)

Question for the reader: in certain circumstances, such as rectangles, the Chebyshev center is ambiguous. How might one get around this ambiguity?

## Monday, July 29, 2013

### network splitting

Last week, Paul Rubin wrote an excellent post on Extracting a Connected Graph from an existing graph. Lately I've been performing related functions on data from OpenStreetMap, though without access to a solver. In my case I'm taking in arbitrary network data and splitting it into disconnected subnetworks. I thought it might be a good case study to show an algorithmic way doing this and some of the performance issues I ran into.

A small example can be seen below (click on the image to enlarge it). This shows a road network around the Las Vegas strip. There is one main (weakly) connected network in black. The roads highlighted in red are disconnected from the main network. We want code that will split these into connected subnetworks.

Say we have data that looks like the following. Instead of nodes, the numbers in quotes represent edges. Think of these as streets.

{
"0": [1, 2, 3],
"1": [9248, 9249, 9250],
"2": [589, 9665, 9667],
"3": [0, 5, 6],
"4": [0, 5, 6],
"5": [588],
"6": [4, 8, 9],
...
}

Our basic strategy is the following:

1. Start with every edge alone in its own subnetwork.
2. For each connection, merge the networks of the source and destination edges.

#!/usr/bin/env python
import json
import sys
import time

class hset(set):
'''A hashable set. Note that it only hashes by the pointer, and not by the elements.'''
def __hash__(self):
return hash(id(self))

def __cmp__(self, other):
return cmp(id(self), id(other))

if __name__ == '__main__':
try:
inputfile = sys.argv[1]
except:
print 'usage: %s network.json' % sys.argv[0]
sys.exit()

print time.asctime(), 'parsing json input'

edge_to_net = {} # Edge ID -> set([edges that are in the same network])
nets = set()     # Set of known networks

print time.asctime(), 'detecting disconnected subgraphs'
for i, (from_edge, to_set) in enumerate(connections.iteritems()):
from_edge = int(from_edge)

try:
from_net = edge_to_net[from_edge]
except KeyError:
from_net = edge_to_net[from_edge] = hset([from_edge])

if not (i+1) % (25 * 1000):
print time.asctime(), '%d edges processed / %d current subnets' % (i+1, len(nets))

for to in to_set:
try:
to_net = edge_to_net[to]

# If we get here, merge the to_net into the from_net.
if to_net is not from_net:
to_net.update(from_net)
for e in from_net:
edge_to_net[e] = to_net
nets.remove(from_net)
from_net = to_net

except KeyError:
edge_to_net[to] = from_net

print time.asctime(), len(nets), 'subnets found'

We run this against the network pictured above and it works reasonably quickly, finishing in about 7 seconds:

Mon Jul 29 12:22:38 2013 parsing json input
Mon Jul 29 12:22:38 2013 detecting disconnected subgraphs
Mon Jul 29 12:22:38 2013 25000 edges processed / 1970 current subnets
Mon Jul 29 12:22:44 2013 50000 edges processed / 124 current subnets
Mon Jul 29 12:22:45 2013 60 subnets found

However, when run against a road network for an entire city, the process continues for several hours. What is the issue?

The inefficiency occurs from lines 46 to 50. In this we are frequently removing references to every element in a large set. Instead, it would be better to remove as few references as possible. Therefore, instead of merging from_net into to_net, we will determine which network is the smaller of the two and marge that one into the larger one. Note that this does not necessarily change the worst case time complexity of the algorithm, but it should make the code fast enough to be useful. The new version appears below.

#!/usr/bin/env python
import json
import sys
import time

class hset(set):
'''A hashable set. Note that it only hashes by the pointer, and not by the elements.'''
def __hash__(self):
return hash(id(self))

def __cmp__(self, other):
return cmp(id(self), id(other))

if __name__ == '__main__':
try:
inputfile = sys.argv[1]
except:
print 'usage: %s network.json' % sys.argv[0]
sys.exit()

print time.asctime(), 'parsing json input'

edge_to_net = {} # Edge ID -> set([edges that are in the same network])
nets = set()     # Set of known networks

print time.asctime(), 'detecting disconnected subgraphs'
for i, (from_edge, to_set) in enumerate(connections.iteritems()):
from_edge = int(from_edge)

try:
from_net = edge_to_net[from_edge]
except KeyError:
from_net = edge_to_net[from_edge] = hset([from_edge])

if not (i+1) % (25 * 1000):
print time.asctime(), '%d edges processed / %d current subnets' % (i+1, len(nets))

for to in to_set:
try:
to_net = edge_to_net[to]

# If we get here, merge the to_net into the from_net.
if to_net is not from_net:
# Update references to and remove the smaller set for speed.
if len(to_net) < len(from_net):
smaller, larger = to_net, from_net
else:
smaller, larger = from_net, to_net

larger.update(smaller)
for e in smaller:
edge_to_net[e] = larger
nets.remove(smaller)
edge_to_net[to] = larger
from_net = larger

except KeyError:
edge_to_net[to] = from_net

print time.asctime(), len(nets), 'subnets found'

Indeed, this is significantly faster. And on very large networks it runs in minutes instead of hours or days. On the small test case used for this post, it runs in under a second. While this could probably be done faster, that's actually good enough for right now.

Mon Jul 29 12:39:55 2013 parsing json input
Mon Jul 29 12:39:55 2013 detecting disconnected subgraphs
Mon Jul 29 12:39:55 2013 25000 edges processed / 1970 current subnets
Mon Jul 29 12:39:55 2013 50000 edges processed / 124 current subnets
Mon Jul 29 12:39:55 2013 60 subnets found

## Wednesday, July 17, 2013

### stack in go

I've been using an increasing amount of Go lately. One of my favorite features is its ability to add methods to any existing type. This is possible for primitive types by simply providing an alias for them, similar to using typedef in C.

Recently, I found I needed a stack container. Nothing complicated, merely an implementation of push, pop, and empty methods. While this is easy enough to do using slices, wrapping the required code makes for a much nicer interface.

package main

import "fmt"

type Element float64
type Stack []Element

func (s *Stack) Push(e Element) {
*s = append(*s, e)
}

func (s *Stack) Pop() Element {
e := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return e
}

func (s *Stack) Empty() bool {
return len(*s) < 1
}

func main() {
s := Stack([]Element{})

for i := 0; i < 10; i++ {
s.Push(Element(i))
}

for !s.Empty() {
fmt.Println("pop:", s.Pop())
}
}

Since there aren't real classes in Go, or inheritance, this doesn't do anything scary like monkey patching. It's just a bit of syntactic sugar to make our lives better. For instance, the Push method could just as easily look like this to the compiler:

func Push(s *Stack, e Element) {
*s = append(*s, e)
}

## Monday, October 8, 2012

### web slides with python & math using deck.js, syntaxhighlighter, and mathjax

In putting together some slides for class that include both Python code and math models, I realized that it was high time to update the technology stack I'm using. If anyone else finds this useful, please feel free to copy my starting template and use or improve upon it.

I'm hosting my slides directly out of Dropbox since I can do so without uploading them to a web server. It also means I can edit and view them locally without have to go through any sort of manual syncing process. This is possibly the simplest way in existence to share a page on the internet.

Steps:

1. Create the directories /public/, /public/www/, /public/www/slides/, and /public/www/slides/boilerplate/ in your Dropbox folder.
3. Download SyntaxHighlighter and decompress it into /public/www/syntaxhighlighter/.
4. Download MathJax and decompress it into /public/www/mathjax/.
5. Save this template into /public/www/slides/boilerplate/boilerplate.html.

Now to create a new slide deck, copy the boilerplate directory to something new in /public/www/slides/. You should be able to begin with something that looks like this. Search through its source for "slides start" to see how to create slides that show beautifully rendered Python and LaTeX.

Use the left and right arrow keys or the icons that appear when you hover over the left and right of the slides to navigate.

## Monday, September 24, 2012

### roll your own gurobi shell

Note: These instructions have been updated to use the setup.py from the Gurobi distribution.

I've recently started using Gurobi for a class. While I'm pleased with the level of Python support they provide, I'm not a fan of the Gurobi shell they ship it with.

• The shell is Python, which is good. However, instead of bundling the Gurobi libraries as a Python module that I can install alongside my system's native Python, they ship their own Python binaries. If I want to use any third-party modules I have to make them available to Gurobi somehow.
• They appear to have removed distutils from the Python they ship.
• The Gurobi shell doesn't give me module docs, tab completion, or anything I'd get from either ipython or bpython. It's nothing more than the rudimentary cPython shell.

They do, however, provide a setup.py script, so we don't have to use gurobi.sh or the Python that's in the distribution. Here are simple instructions for using bpython as your shell. You should have Gurobi 5.0.1 installed and the GUROBI_HOME environment variable set. (I assume you are installing it into your home directory.)

$mkdir -p$HOME/lib/python2.7/site-packages/
$cd$GUROBI_HOME
$PYTHONPATH=$HOME/lib/python2.7/site-packages/ python setup.py install --prefix=$HOME  Update your environment's PYTHONPATH and LD_LIBRARY_PATH: $ echo "export PYTHONPATH=\$PYTHONPATH:\$HOME/lib/python2.7/site-packages/" >> $HOME/.bashrc$ echo "export LD_LIBRARY_PATH=\$LD_LIBRARY_PATH:\$GUROBI_HOME/lib/" >> $HOME/.bashrc$ source $HOME/.bashrc  Install bpython: $ sudo apt-get install bpython

Now type bpython and you should have the lovely interface you see below, complete with tab completion and module docs. Isn't that better?

## Saturday, September 22, 2012

### lagrangian relaxation with gurobipy

Note: this is still a new technique to me, so please point out any errors and I will correct them in the post.

Correction: $b_{ij}$ is now $b_j$ in the second set of constraints.

We've been studying Lagrangian Relaxation (LR) in the combinatorial optimization course I'm taking this term, and I had some difficulty finding a simple example covering its application. In case anyone else finds it useful, I'm posting a Python version for solving the Generalized Assignment Problem (GAP). This won't discuss the theory of LR at all, just give example code using Gurobi 5.0.1.

The GAP as defined by Wolsey consists of a maximization problem subject to a set of set packing constraints followed by a set of knapsack constraints:

max $\sum_i \sum_j c_{ij} x_{ij}$
subject to $\sum_j x_{ij} \leq 1 \forall i$
$\sum_i a_{ij} x_{ij} \leq b_{ij} \forall j$
$x_{ij} \in \{0, 1\}$

An unadulterated version of this BIP using gurobipy might look like the following:

#!/usr/bin/env python

# This is the GAP per Wolsey, pg 182

from gurobipy import GRB, Model

model = Model('GAP per Wolsey')
model.modelSense = GRB.MAXIMIZE
model.setParam('OutputFlag', False) # turns off solver chatter

b = [15, 15, 15]
c = [
[ 6, 10,  1],
[12, 12,  5],
[15,  4,  3],
[10,  3,  9],
[ 8,  9,  5]
]
a = [
[ 5,  7,  2],
[14,  8,  7],
[10,  6, 12],
[ 8,  4, 15],
[ 6, 12,  5]
]

# x[i][j] = 1 if i is assigned to j
x = []
for i in range(len(c)):
x_i = []
for j in c[i]:
x.append(x_i)

# We have to update the model so it knows about new variables
model.update()

# sum j: x_ij <= 1 for all i
for x_i in x:

# sum i: a_ij * x_ij <= b[j] for all j
for j in range(len(b)):
model.addConstr(sum(a[i][j] * x[i][j] for i in range(len(x))) <= b[j])

# max sum i,j: c_ij * x_ij
model.setObjective(
sum(
sum(c_ij * x_ij for c_ij, x_ij in zip(c_i, x_i))
for c_i, x_i in zip(c, x)
)
)
model.optimize()

# Pull objective and variable values out of model
print 'objective =', model.objVal
print 'x = ['
for x_i in x:
print '   ', [1 if x_ij.x >= 0.5 else 0 for x_ij in x_i]
print ']'

The solver quickly finds the following optimal solution of this toy problem:

objective = 46.0
x = [
[0, 1, 0]
[0, 1, 0]
[1, 0, 0]
[0, 0, 1]
[0, 0, 0]
]

There are two sets of constraints we can dualize. It can be beneficial to apply Lagrangian Relaxation against problems composed of knapsack constraints, so we will dualize the set packing ones. The first thing we do is replace the constraints generated in lines 39-40 with a new set of variables, penalties, which take the values of the slacks on the set packing constraints. We then modify the objective function, adding Lagrangian multipliers times these penalties.

Instead of optimizing once, we do so iteratively. An important consideration is we may get nothing more than a dual bound from this process. Any integer solution is not guaranteed to be primal feasible unless it satisfies complementary slackness conditions -- for each dualized constraint either its multiplier or penalty must be zero.

Setting the intial multiplier values to 2 and using subgradient optimization with a step size of 1 / (iteration #) to adjust them, we arrive at the following model:

#!/usr/bin/env python

# This is the GAP per Wolsey, pg 182, using Lagrangian Relaxation

from gurobipy import GRB, Model

model = Model('GAP per Wolsey with Lagrangian Relaxation')
model.modelSense = GRB.MAXIMIZE
model.setParam('OutputFlag', False) # turns off solver chatter

b = [15, 15, 15]
c = [
[ 6, 10,  1],
[12, 12,  5],
[15,  4,  3],
[10,  3,  9],
[ 8,  9,  5]
]
a = [
[ 5,  7,  2],
[14,  8,  7],
[10,  6, 12],
[ 8,  4, 15],
[ 6, 12,  5]
]

# x[i][j] = 1 if i is assigned to j
x = []
for i in range(len(c)):
x_i = []
for j in c[i]:
x.append(x_i)

# As stated, the GAP has these following constraints. We dualize these into
# penalties instead, using variables so we can easily extract their values.
penalties = [model.addVar() for _ in x]
model.update()

# Dualized constraints: sum j: x_ij <= 1 for all i
for p, x_i in zip(penalties, x):
model.addConstr(p == 1 - sum(x_i))

# sum i: a_ij * x_ij <= b[j] for all j
for j in range(len(b)):
model.addConstr(sum(a[i][j] * x[i][j] for i in range(len(x))) <= b[j])

# u[i] = Lagrangian Multiplier for the set packing contraint i
u = [2.0] * len(x)

# Re-optimize until either we have run a certain number of iterations
# or complementary slackness conditions apply.
for k in range(1, 101):
# max sum i,j: c_ij * x_ij
model.setObjective(
sum(
# Original objective function
sum(c_ij * x_ij for c_ij, x_ij in zip(c_i, x_i))
for c_i, x_i in zip(c, x)
) + sum (
# Penalties for dualized constraints
u_j * p_j for u_j, p_j in zip(u, penalties)
)
)
model.optimize()

print 'iteration', k, 'obj =', model.objVal, \
'u =', u, 'penalties =', [p.x for p in penalties]

# Test for complementary slackness
stop = True
eps = 10e-6
for u_i, p_i in zip(u, penalties):
if abs(u_i) > eps and abs(p_i.x) > eps:
stop = False
break

if stop:
print 'primal feasible & optimal'
break

else:
s = 1.0 / k
for i in range(len(x)):
u[i] = max(u[i] - s*(penalties[i].x), 0.0)

# Pull objective and variable values out of model
print 'objective =', model.objVal
print 'x = ['
for x_i in x:
print '   ', [1 if x_ij.x >= 0.5 else 0 for x_ij in x_i]
print ']'

On this problem LR converges very quickly to an optimal solution, as we can see here:

iteration 1 obj = 48.0 u = [2.0, 2.0, 2.0, 2.0, 2.0] penalties = [0.0, 0.0, 0.0, 0.0, 1.0]
iteration 2 obj = 47.0 u = [2.0, 2.0, 2.0, 2.0, 1.0] penalties = [0.0, 0.0, 0.0, 0.0, 1.0]
iteration 3 obj = 46.5 u = [2.0, 2.0, 2.0, 2.0, 0.5] penalties = [0.0, 0.0, 0.0, 0.0, 1.0]
iteration 4 obj = 46.1666666667 u = [2.0, 2.0, 2.0, 2.0, 0.16666666666666669] penalties = [0.0, 0.0, 0.0, 0.0, 1.0]
iteration 5 obj = 46.0 u = [2.0, 2.0, 2.0, 2.0, 0.0] penalties = [0.0, 0.0, 0.0, 0.0, 1.0]
primal feasible & optimal
objective = 46.0
x = [
[0, 1, 0]
[0, 1, 0]
[1, 0, 0]
[0, 0, 1]
[0, 0, 0]
]

Exercise for the reader: change the script to dualize the knapsack constraints instead of the set packing constraints. What is the result of this change in terms of convergence?

## Thursday, March 29, 2012

### python-zibopt 0.7.2 released

python-zibopt 0.7.2 has been released and the big news is that it supports both Python 2 and 3. (Thanks to Guillaume Sagnol for the patch!)

Other changes include:

• Added magic square and normal magic square examples
• Fixed issue with single-variable objectives subject to constraints:
solver += x >= y
solution = solver.minimize(objective=x)
• Constant objectives no longer raise errors:
solver.minimize(objective=3)
• Fixed obscure constraint issue:
solver += x <= (y-1) + 100*(1-z)

From here I'm hoping to focus my efforts on the Cython port, which should give a better basis for more advanced functionality in future versions.

## Tuesday, March 27, 2012

### spring coding haiku

Spring priorities
ever shift as with the winds.
Effort flows downstream.

## Monday, March 26, 2012

### a few thoughts on music and computer programming

Greg Linch started a discussion recently on Twitter regarding music and coding. The apex of the conversation was Zed Shaw pointing to his own well-stated comments on the matter.

I got back just over a couple hours ago from a weekly rehearsal, so I've got a number of things I'd like to mention swimming around in my head. Here are a few:

1. To "Linguistic Skills" I'd add that musical notation is specifically built to enable certain domain-specific elements. Its staved nature allows a high degree of parallelism. I can't think of any other common language that succinctly expresses multiple concurrent paths in a readable format. One can glean a great deal of information about independently moving pieces from something like an orchestral score very quickly, in ways that we cannot with programming or other languages. Thinking concurrently is increasingly important in our contemporary computing environment.

2. Musical notation is evolving rapidly. If one studies modern music, one will be constantly presented with new types and forms of instruction. In a way, this is like introducing new op-codes or programming constructs and can help form a desirable malleability of mind. Consider the notation, for example, in Penderecki's "Threnody for the Victims of Hiroshima" or much crazier looking things by composers such as Xenakis. Sometimes learning a single piece requires understanding the structure of an entirely new language.

3. Music encourages team playing. In a chamber ensemble, one is expected to become so in sync with the other members that you do things like breathe together. A well-rehearsed group will practice such things as playing notes slowly to try and achieve better temperament (consistent intonation which should result in more commonly placed overtones) and vibratos that waver at the same rates. Communication is rehearsed in the form of breaths, nods, eye contact, and other physical gestures (chamber players cannot over-communicate). Most chamber music involves a lot of passing back and forth of musical phrases, which can be analogous to message passing in a synchronous computing system.

4. Interpretation of a piece is largely subjective and therefore requires lots of compromise in order to become cohesive. This sort of compromise doesn't just mean allowing someone else to have his or her way, but means accepting and buying into it once a decision is made. If a member of my group plays a passage a certain way, I'm now expected to play that passage in a similar manner. Once a design decision is agreed upon, the impetus is on the players to accept and use it to improve the overall structure.


text:
Annals of Mathematics

Citation preview

Annals of Mathematics 160 (2008), 17–46 http://dx.doi.org/10.4007/annals.2008.160.1.12 1 2 3

Sample Paper for the aomart Class

4 5

By American Mathematical Society and Boris Veytsman

6 7 8 9 10 11

Abstract This is a test file for aomart class based on the testmath.tex file from the amsmath distribution. It was changed to test the features of the Annals of Mathematics class.

12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

Contents 1. Introduction 2. Enumeration of Hamiltonian paths in a graph 3. Main theorem 4. Application 5. Secret key exchanges 6. Review 7. One-way complexity 8. Various font features of the amsmath package 8.1. Bold versions of special symbols 8.2. “Poor man’s bold” 9. Compound symbols and other features 9.1. Multiple integral signs 9.2. Over and under arrows 9.3. Dots 9.4. Accents in math 9.5. Dot accents 9.6. Roots 9.7. Boxed formulas 9.8. Extensible arrows 9.9. \overset, \underset, and \sideset 9.10. The \text command 9.11. Operator names

39 40 41

The class was commissioned by Annals of Mathematics. c 2008–2012 Boris Veytsman.

42

17

18 18 19 22 23 23 28 35 35 35 36 36 36 36 37 37 37 37 38 38 38 38

18 1 2 3 4 5 6 7 8 9

AMS and BORIS VEYTSMAN

9.12. \mod and its relatives 9.13. Fractions and related constructions 9.14. Continued fractions 9.15. Smash 9.16. The ‘cases’ environment 9.17. Matrix 9.18. The \substack command 9.19. Big-g-g delimiters References

39 39 41 41 41 42 43 44 44

10 11 12

1. Introduction

13 14 15 16 Are these quotations necessary?

17 18

This paper demonstrates the use of aomart class. It is based on testmath.tex from AMS-LATEX distribution. The text is (slightly) reformatted according to the requirements of the aomart style. See also [LO74, Zarh92, MO08, Arn89, Mic48, Mic38, Zarb, Zara, dGWH+ 92]. It is always a pleasure to cite Knuth [Knu94].

19

2. Enumeration of Hamiltonian paths in a graph

20 21 22 23 24 25

Let A = (aij ) be the adjacency matrix of graph G. The corresponding Kirchhoff matrix K = (kij ) is obtained from A by replacing in −A each diagonal entry by the degree of its corresponding vertex; i.e., the ith diagonal entry is identified with the degree of the ith vertex. It is well known that

26

(1)

27

where K(i|i) is the ith principal submatrix of K.

28 29

det K(i|i) = the number of spanning trees of G,

i = 1, . . . , n

\det\mathbf{K}(i|i)=\text{ the number of spanning trees of $G$},

33

Let Ci(j) be the set of graphs obtained from G by attaching edge (vi vj ) S to each spanning tree of G. Denote by Ci = j Ci(j) . It is obvious that the collection of Hamiltonian cycles is a subset of Ci . Note that the cardinality of “ = {ˆ Ci is kii det K(i|i). Let X x1 , . . . , x ˆn }.

34

$\wh X=\{\hat x_1,\dots,\hat x_n\}$

35

“ by Define multiplication for the elements of X

30 31 32

36 37 38 39

(2)

42

x ˆ2i = 0,

i, j = 1, . . . , n.

Let kˆij = kij x ˆj and kˆij = − j6=i kˆij . Then the number of Hamiltonian cycles Hc is given by the relation [LC84] P

40 41

x ˆi x ˆj = x ˆj x ˆi ,

(3)

Ç n Y

å

1 “ x ˆj Hc = kˆij det K(i|i), 2 j=1

i = 1, . . . , n.

Proof: page numbers may be temporary

19

SAMPLE PAPER 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

The task here is to express (3) in a form free of any x ˆi , i = 1, . . . , n. The result also leads to the resolution of enumeration of Hamiltonian paths in a graph. It is well known that the enumeration of Hamiltonian cycles and paths in a complete graph Kn and in a complete bipartite graph Kn1 n2 can only be found from first combinatorial principles [HP73]. One wonders if there exists a formula which can be used very efficiently to produce Kn and Kn1 n2 . Recently, using Lagrangian methods, Goulden and Jackson have shown that Hc can be expressed in terms of the determinant and permanent of the adjacency matrix [GJ81]. However, the formula of Goulden and Jackson determines neither Kn nor Kn1 n2 effectively. In this paper, using an algebraic method, we parametrize the adjacency matrix. The resulting formula also involves the determinant and permanent, but it can easily be applied to Kn and Kn1 n2 . In addition, we eliminate the permanent from Hc and show that Hc can be represented by a determinantal function of multivariables, each variable with domain {0, 1}. Furthermore, we show that Hc can be written by number of spanning trees of subgraphs. Finally, we apply the formulas to a complete multigraph Kn1 ...np . The conditions aij = aji , i, j = 1, . . . , n, are not required in this paper. All formulas can be extended to a digraph simply by multiplying Hc by 2. Some other discussion can be found in [Fre08, Fre94].

20 21 22

3. Main theorem

23

Notation. For p, q ∈ P and n ∈ ω we write (q, n) ≤ (p, n) if q ≤ p and Aq,n = Ap,n .

24 25 26 27 28 29 30

\begin{notation} For $p,q\in P$ and $n\in\omega$ ... \end{notation} Let B = (bij ) be an n×n matrix. Let n = {1, . . . , n}. Using the properties of (2), it is readily seen that

31

Lemma 3.1.

32 33 34

(4)

i∈n

35 36

å

bij x ˆi

Ç

=

j∈n

å Y

x ˆi per B

i∈n

where per B is the permanent of B.

37

“ = {ˆ “ by Let Y y1 , . . . , yˆn }. Define multiplication for the elements of Y

38 39

Ç Y X

(5)

yˆi yˆj + yˆj yˆi = 0,

i, j = 1, . . . , n.

40 41

Then, it follows that

42 Proof: page numbers may be temporary

20 1

AMS and BORIS VEYTSMAN

Lemma 3.2.

Ç Y X

2 3

(6)

i∈n

4 5 6

X

(7)

13 14 15

22 23 24 25 26 27

bij yˆj + (bii − λi )ˆ yi yˆ

j∈n

bii = λi ,

(λ)

i 6= j.

bij = bij ,

(λ)

Let B(λ) = (bij ). By (6) and (7), it is straightforward to show the following result: Theorem 3.3. (9)

det B =

n X Y X

(bii − λi ) det B(λ) (Il |Il ),

l=0 Il ⊆n i∈Il

19

21

X (λ)

bij yˆj =

17

20

yˆi det B.

i∈n

(λ)

(8)

16

18

Y

where

11 12

=

j∈n

j∈n

9 10

bij yˆj

å

Ç

Note that all basic properties of determinants are direct consequences of Lemma 3.2. Write

7 8

å

where Il = {i1 , . . . , il } and B(λ) (Il |Il ) is the principal submatrix (obtained from B(λ) by deleting its i1 , . . . , il rows and columns ). Remark 3.1 (convention). Let M be an n × n matrix. The convention M(n|n) = 1 has been used in (9) and hereafter. Before proceeding with our discussion, we pause to note that Theorem 3.3 yields immediately a fundamental formula which can be used to compute the coefficients of a characteristic polynomial [MM64]:

28

Corollary 3.4. Write det(B − xI) =

29 30 31

(10)

bl = Let

33

37

(11)

K(t, t1 , . . . , tn ) =

D1 t −a12 t2 . . . −a1n tn −a21 t1 D2 t . . . −a2n tn ...................... −an1 t1 −an2 t2 . . . Dn t

38 39 40 41 42

Then

det B(Il |Il ).

á

34

36

l l l=0 (−1) bl x .

Il ⊆n

32

35

X

Pn

\begin{pmatrix} D_1t&-a_{12}t_2&\dots&-a_{1n}t_n\\ -a_{21}t_1&D_2t&\dots&-a_{2n}t_n\\ \hdotsfor[2]{4}\\ -a_{n1}t_1&-a_{n2}t_2&\dots&D_nt\end{pmatrix} Proof: page numbers may be temporary

ë

,

21

SAMPLE PAPER 1

where

2 3

(12)

Di =

X

aij tj ,

4

Set

5 6

D(t1 , . . . , tn ) =

7 8

Then

9

(13)

D(t1 , . . . , tn ) =

10 11 12 13 14

17 18

(14) det K(t1 , t1 , . . . , tn ) =

I∈n

Ç

(16)

33 34 35 36

Ç

i∈I

j∈I

X

x ˆi

(−1)|I| per A(λ) (I|I) det A(λ) (I ∪ {l}|I ∪ {l}).

I⊆n−{l}

By (3), (6), and (7), we have

38 39

Proposition 3.5.

40

42

j∈I

\begin{multline} \biggl(\sum_{\,i\in\mathbf{n}}a_{l _i}x_i\biggr) \det\mathbf{K}(t=1,x_1,\dots,x_n;l |l )\\ =\biggl(\prod_{\,i\in\mathbf{n}}\hat x_i\biggr) \sum_{I\subseteq\mathbf{n}-\{l \}} (-1)^{\envert{I}}\per\mathbf{A}^{(\lambda)}(I|I) \det\mathbf{A}^{(\lambda)} (\overline I\cup\{l \}|\overline I\cup\{l \}). \label{sum-ali} \end{multline}

37

41

(Dj +λj tj ) det A(λt) (I|I).

å Y i∈n

26

32

i∈I

Y

ali xi det K(t = 1, x1 , . . . , xn ; l|l) =

25

31

ti

å X i∈n

24

30

Y

Let ti = x ˆi , i = 1, . . . , n. Lemma 3.1 yields

22

29

(−1)|I| tn−|I|

Note that (15) X Y Y det K(t = 1, t1 , . . . , tn ) = (−1)|I| ti (Dj + λj tj ) det A(λ) (I|I) = 0.

21

28

X I∈n

20

27

Di det K(t = 1, t1 , . . . , tn ; i|i),

where K(t = 1, t1 , . . . , tn ; i|i) is the ith principal submatrix of K(t = 1, t1 , . . . , tn ). Theorem 3.3 leads to

19

23

X

δ det K(t, t1 , . . . , tn )|t=1 . δt

i∈n

15 16

i = 1, . . . , n.

j∈n

(17)

Hc =

n 1 X (−1)l Dl , 2n l=0

Proof: page numbers may be temporary

22 1

AMS and BORIS VEYTSMAN

where

2 3

(18)

Dl =

X

D(t1 , . . . , tn )2|

ti =

Il ⊆n

4

¶ 0, if i∈I l 1, otherwise

, i=1,...,n

.

5 6

4. Application

7 8 9 10

We consider here the applications of Theorems 5.1 and 5.2 to a complete multipartite graph Kn1 ...np . It can be shown that the number of spanning trees of Kn1 ...np may be written

11 12

p Y

T = np−2

(19)

13 14 15 16

(n − ni )ni −1

i=1

where n = n1 + · · · + np .

(20)

17

It follows from Theorems 5.1 and 5.2 that

18 19 20 21 22

(21)

n 1 X Hc = (−1)l (n − l)p−2 2n l=0 l

X

p Y

1 +···+lp =l

i=1

ñ

ni −li

ni li

2

· (n − l) −

· [(n − l) − (ni − li )]

23

Ç å

26 27

and

29

(22)

X 1 n−1 (−1)l (n − l)p−2 Hc = 2 l=0 l

X

p Y

1 +···+lp =l

i=1

· [(n − l) − (ni − li )]

32

34 35 36 37

40 41 42

lp 1− np

Ç å

ni li

å

[(n − l) − (np − lp )].

The enumeration of Hc in a Kn1 ···np graph can also be carried out by Theorem 7.2 or 7.3 together with the algebraic method of (2). Some elegant representations may be obtained. For example, Hc in a Kn1 n2 n3 graph may be written

38 39

Ç

ni −li

31

33

(ni − li ) .

... \binom{n_i}{l _i}\\

28

30

ô 2

j=1

24 25

p X

(23)

n1 ! n2 ! n3 ! X Hc = n1 + n2 + n3 i Ç

+

n1 − 1 i

åÇ

ñÇ

n1 i

åÇ

åÇ

n2 n3 − n1 + i

åÇ

n2 − 1 n3 − n1 + i

n3 − 1 n3 − n2 + i

Proof: page numbers may be temporary

å

n3 n3 − n2 + i

åô

.

SAMPLE PAPER 1

23

5. Secret key exchanges

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Modern cryptography is fundamentally concerned with the problem of secure private communication. A Secret Key Exchange is a protocol where Alice and Bob, having no secret information in common to start, are able to agree on a common secret key, conversing over a public channel. The notion of a Secret Key Exchange protocol was first introduced in the seminal paper of Diffie and Hellman [DH76]. [DH76] presented a concrete implementation of a Secret Key Exchange protocol, dependent on a specific assumption (a variant on the discrete log), specially tailored to yield Secret Key Exchange. Secret Key Exchange is of course trivial if trapdoor permutations exist. However, there is no known implementation based on a weaker general assumption. The concept of an informationally one-way function was introduced in [ILL89]. We give only an informal definition here: Definition 5.1 (one way). A polynomial time computable function f = {fk } is informationally one-way if there is no probabilistic polynomial time algorithm which (with probability of the form 1 − k −e for some e > 0) returns on input y ∈ {0, 1}k a random element of f −1 (y).

19 20 21 22 23

In the non-uniform setting [ILL89] show that these are not weaker than one-way functions: Theorem 5.1 ([ILL89] (non-uniform)). The existence of informationally one-way functions implies the existence of one-way functions.

24 25 26 27 28 29 30 31

We will stick to the convention introduced above of saying “non-uniform” before the theorem statement when the theorem makes use of non-uniformity. It should be understood that if nothing is said then the result holds for both the uniform and the non-uniform models. It now follows from Theorem 5.1 that Theorem 5.2 (non-uniform). Weak SKE implies the existence of a oneway function.

32 33 34 35 36 37 38

More recently, the polynomial-time, interior point algorithms for linear programming have been extended to the case of convex quadratic programs [MA87, Ye87], certain linear complementarity problems [KMY87b, MYK88], and the nonlinear complementarity problem [KMY87a]. The connection between these algorithms and the classical Newton method for nonlinear equations is well explained in [KMY87b].

39 40

6. Review

41 42

We begin our discussion with the following definition: Proof: page numbers may be temporary

24 1 2 3 4

AMS and BORIS VEYTSMAN

Definition 6.1. A function H : 1 − a2 . The radial Laplacian

22 23

∆0 ln ψ0 (r) =

Ç 2 d

24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

1 d + 2 dr r dr

å

ln ψ0 (r)

has smooth coefficients for r > 1 − 2a. Therefore, we may apply the existence and uniqueness theory for ordinary differential equations. Simply let ln ψ0 (r) be the solution of the differential equation Ç 2 d

1 d + 2 dr r dr

å

ln ψ0 (r) = h(r)

with initial conditions given by ln ψ0 (1) = 0 and ln ψ00 (1) = 0. Next, let Dν be a finite collection of pairwise disjoint disks, all of which are contained in the unit disk centered at the origin in C. We assume that Dν = {z | |z − zν | < δ}. Suppose that Dν (a) denotes the smaller concentric disk Dν (a) = {z | |z − zν | ≤ (1 − 2a)δ}. We define a smooth weight function S S Φ0 (z) for z ∈ C − ν Dν (a) by setting Φ0 (z) = 1 when z ∈ / ν Dν and Φ0 (z) = ψ0 ((z − zν )/δ) when z is an element of Dν . It follows from Lemma 6.1 that Φ0 satisfies the properties: (i) Φ0 (z) is bounded above and below by positive constants c1 ≤ Φ0 (z) ≤ c2 . S (ii) ∆0 ln Φ0 ≥ 0 for all z ∈ C − ν Dν (a), the domain where the function Φ0 is defined. Proof: page numbers may be temporary

25

SAMPLE PAPER 1 2 3 4 5 6 7 8 9

(iii) ∆0 ln Φ0 ≥ c3 δ −2 when (1 − 2a)δ < |z − zν | < (1 − a)δ. Let Aν denote the annulus Aν = {(1 − 2a)δ < |z − zν | < (1 − a)δ}, and S set A = ν Aν . The properties (2) and (3) of Φ0 may be summarized as ∆0 ln Φ0 ≥ c3 δ −2 χA , where χA is the characteristic function of A.  Suppose that α is a nonnegative real constant. We apply Proposition 3.5 2 S with Φ(z) = Φ0 (z)eα|z| . If u ∈ C0∞ (R2 − ν Dν (a)), assume that D is a S bounded domain containing the support of u and A ⊂ D ⊂ R2 − ν Dν (a). A calculation gives

10

Z Z Z 2 2 2 α|z|2 α|z|2 −2 ≥ c4 α |u| Φ0 e + c5 δ |u|2 Φ0 eα|z| . ∂u Φ0 (z)e

11

Z Z Z 2 2 2 α|z|2 |u|2 eα|z| . ≥ c6 α |u|2 eα|z| + c7 δ −2 ∂u e

14 15

17 18

A

The boundedness, property (1) of Φ0 , then yields

13

16

D

D

12

D

D

A

Let B(X) be the set of blocks of ΛX and let b(X) = |B(X)|. If φ ∈ QX then φ is constant on the blocks of ΛX . PX = {φ ∈ M | Λφ = ΛX },

QX = {φ ∈ M | Λφ ≥ ΛX }.

19

(24)

20

If Λφ ≥ ΛX then Λφ = ΛY for some Y ≥ X so that

21

Thus by M¨ obius inversion

25 26

29 30

X

|PY | =

Thus there is a bijection from QX to W B(X) . In particular |QX | = wb(X) . Next note that b(X) = dim X. We see this by choosing a basis for X consisting of vectors v k defined by

31 32 33 34 35 36 37 38 39 40 41

µ(Y, X) |QX | .

X≥Y

27 28

PY .

Y ≥X

23 24

[

QX =

22

vik =

 1

if i ∈ Λk ,

0

otherwise.

$v^{k}_{i}= \begin{cases} 1 & \text{if i \in \Lambda_{k}},\\ 0 &\text{otherwise.} \end{cases}$ Lemma 6.2. Let A be an arrangement. Then χ(A, t) =

X

(−1)|B| tdim T (B) .

B⊆A

42 Proof: page numbers may be temporary

26 1 2 3

AMS and BORIS VEYTSMAN

In order to compute R00 recall the definition of S(X, Y ) from Lemma 3.1. Since H ∈ B, AH ⊆ B. Thus if T (B) = Y then B ∈ S(H, Y ). Let L00 = L(A00 ). Then

4

R00 =

5

H∈B⊆A

6

=

7

X Y

8 9

(25)

=− =−

X

µ(H, Y )tdim Y

Corollary 6.3. Let (A, A0 , A00 ) be a triple of arrangements. Then π(A, t) = π(A0 , t) + tπ(A00 , t).

16

19

(−1)|B−AH | tdim Y

X

= −χ(A , t).

13

18

B∈S(H,Y )

X

Y ∈L00 00

12

17

(−1)|B| tdim Y

Y ∈L00 B∈S(H,Y )

11

15

X

∈L00

10

14

(−1)|B| tdim T (B)

X

Definition 6.2. Let (A, A0 , A00 ) be a triple with respect to the hyperplane H ∈ A. Call H a separator if T (A) 6∈ L(A0 ).

20

Corollary 6.4. Let (A, A0 , A00 ) be a triple with respect to H ∈ A.

21

(i) If H is a separator then

22

µ(A) = −µ(A00 )

23 24

and hence |µ(A)| = µ(A00 ) .

25 26 27

(ii) If H is not a separator then µ(A) = µ(A0 ) − µ(A00 )

28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

and |µ(A)| = µ(A0 ) + µ(A00 ) .

Proof. It follows from Theorem 5.1 that π(A, t) has leading term (−1)r(A) µ(A)tr(A) . The conclusion follows by comparing coefficients of the leading terms on both sides of the equation in Corollary 6.3. If H is a separator then r(A0 ) < r(A) and there is no contribution from π(A0 , t).  The Poincar´e polynomial of an arrangement will appear repeatedly in these notes. It will be shown to equal the Poincar´e polynomial of the graded algebras which we are going to associate with A. It is also the Poincar´e polynomial of the complement M (A) for a complex arrangement. Here we prove Proof: page numbers may be temporary

27

SAMPLE PAPER 1 2 3 4 5 6 7 8 9 10 11 12

Figure 1. Q(A1 ) = xyz(x − z)(x + z)(y − z)(y + z)

13 14 15 16 17 18 19 20 21 22 23 24 25

Figure 2. Q(A2 ) = xyz(x + y + z)(x + y − z)(x − y + z)(x − y − z)

26 27 28 29 30 31 32 33 34 35 36 37

that the Poincar´e polynomial is the chamber counting function for a real arrangement. The complement M (A) is a disjoint union of chambers M (A) =

[

C.

C∈Cham(A)

The number of chambers is determined by the Poincar´e polynomial as follows. Theorem 6.5. Let AR be a real arrangement. Then |Cham(AR )| = π(AR , 1). Proof. We check the properties required in Corollary 6.4: (i) follows from π(Φl , t) = 1, and (ii) is a consequence of Corollary 3.4.

38 39 40 41 42

Theorem 6.6. Let φ be a protocol for a random pair (X, Y ). If one of σφ (x0 , y) and σφ (x, y 0 ) is a prefix of the other and (x, y) ∈ SX,Y , then ∞ 0 ∞ hσj (x0 , y)i∞ j=1 = hσj (x, y)ij=1 = hσj (x, y )ij=1 .

Proof: page numbers may be temporary

28

AMS and BORIS VEYTSMAN

1

Proof. We show by induction on i that

2

hσj (x0 , y)iij=1 = hσj (x, y)iij=1 = hσj (x, y 0 )iij=1 .

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

The induction hypothesis holds vacuously for i = 0. Assume it holds for i−1 0 ∞ i − 1, in particular [σj (x0 , y)]j=1 = [σj (x, y 0 )]i−1 j=1 . Then one of [σj (x , y)]j=i 0 ∞ 0 and [σj (x, y )]j=i is a prefix of the other which implies that one of σi (x , y) and σi (x, y 0 ) is a prefix of the other. If the ith message is transmitted by PX then, by the separate-transmissions property and the induction hypothesis, σi (x, y) = σi (x, y 0 ), hence one of σi (x, y) and σi (x0 , y) is a prefix of the other. By the implicit-termination property, neither σi (x, y) nor σi (x0 , y) can be a proper prefix of the other, hence they must be the same and σi (x0 , y) = σi (x, y) = σi (x, y 0 ). If the ith message is transmitted by PY then, symmetrically, σi (x, y) = σi (x0 , y) by the induction hypothesis and the separatetransmissions property, and, then, σi (x, y) = σi (x, y 0 ) by the implicit-termination property, proving the induction step.  If φ is a protocol for (X, Y ), and (x, y), (x0 , y) are distinct inputs in SX,Y , 0 ∞ then, by the correct-decision property, hσj (x, y)i∞ j=1 6= hσj (x , y)ij=1 . Equation (25) defined PY ’s ambiguity set SX|Y (y) to be the set of possible X values when Y = y. The last corollary implies that for all y ∈ SY , the multiset1 of codewords {σφ (x, y) : x ∈ SX|Y (y)} is prefix free.

22

7. One-way complexity

23 24 25 26 27

Cˆ1 (X|Y ), the one-way complexity of a random pair (X, Y ), is the number of bits PX must transmit in the worst case when PY is not permitted to transmit any feedback messages. Starting with SX,Y , the support set of (X, Y ), we define G(X|Y ), the characteristic hypergraph of (X, Y ), and show that

28

Cˆ1 (X|Y ) = d log χ(G(X|Y ))e .

29 30 31 32 33 34

Let (X, Y ) be a random pair. For each y in SY , the support set of Y , equation (25) defined SX|Y (y) to be the set of possible x values when Y = y. The characteristic hypergraph G(X|Y ) of (X, Y ) has SX as its vertex set and the hyperedge SX|Y (y) for each y ∈ SY . We can now prove a continuity theorem.

35

Theorem 7.1. Let Ω ⊂ Rn be an open set, let u ∈ BV (Ω; Rm ), and let

36

®

37 38

(26)

Txu

Æ

m

= y∈R

:y=u ˜(x) +

Du (x), z |Du|

´

n

for some z ∈ R

39 40 41 42

1A multiset allows multiplicity of elements. Hence, {0, 01, 01} is prefix free as a set, but

not as a multiset.

Proof: page numbers may be temporary

29

SAMPLE PAPER 1 2

for every x ∈ Ω\Su . Let f : Rm → Rk be a Lipschitz continuous function such that f (0) = 0, and let v = f (u) : Ω → Rk . Then v ∈ BV (Ω; Rk ) and

3 4 5 6 7

Jv = (f (u+ ) − f (u− )) ⊗ νu · Hn−1

(27)

(28)

10 11 12

.

‹ -almost every x ∈ Ω the restriction of the function f to In addition, for Du Txu is differentiable at u ˜(x) and

8 9

Su

‹ = ∇( f | u )(˜ Dv Tx u)

‹ Du

‹ . · Du ‹ Du

Before proving the theorem, we state without proof three elementary remarks which will be useful in the sequel.

13 14 15

Remark 7.1. Let ω : ]0, +∞[ → ]0, +∞[ be a continuous function such that ω(t) → 0 as t → 0. Then

16

lim g(ω(h)) = L ⇔ lim g(h) = L

17 18

h→0+

h→0+

for any function g : ]0, +∞[ → R.

19 20 21 22 23 24 25 26 27 28 29

Remark 7.2. Let g : Rn → R be a Lipschitz continuous function and assume that g(hz) − g(0) L(z) = lim h h→0+ n exists for every z ∈ Q and that L is a linear function of z. Then g is differentiable at 0. Remark 7.3. Let A : Rn → Rm be a linear function, and let f : Rm → R be a function. Then the restriction of f to the range of A is differentiable at 0 if and only if f (A) : Rn → R is differentiable at 0 and ∇( f |Im(A) )(0)A = ∇(f (A))(0).

30 31

Proof. We begin by showing that v ∈ BV (Ω; Rk ) and

32 33

(29)

|Dv| (B) ≤ K |Du| (B)

∀B ∈ B(Ω),

34 35 36 37

where K > 0 is the Lipschitz constant of f . By (13) and by the approximation result quoted in §3, it is possible to find a sequence (uh ) ⊂ C 1 (Ω; Rm ) converging to u in L1 (Ω; Rm ) and such that

38 39

Z

lim

h→+∞ Ω

|∇uh | dx = |Du| (Ω).

40 41 42

The functions vh = f (uh ) are locally Lipschitz continuous in Ω, and the definition of differential implies that |∇vh | ≤ K |∇uh | almost everywhere in Ω. The Proof: page numbers may be temporary

30 1

AMS and BORIS VEYTSMAN

lower semicontinuity of the total variation and (13) yield

2

|Dv| (Ω) ≤ lim inf |Dvh | (Ω) = lim inf

3 4

h→+∞

(30)

h→+∞

h→+∞

6 7

Since f (0) = 0, we have also

8

Z

9 10

12 13 14 15 16

|v| dx ≤ K

Z

|∇vh | dx

≤ K lim inf

5

11

Z

Z

|∇uh | dx = K |Du| (Ω).

|u| dx;

therefore u ∈ BV (Ω; Rk ). Repeating the same argument for every open set A ⊂ Ω, we get (29) for every B ∈ B(Ω), because |Dv|, |Du| are Radon measures. To prove Lemma 6.1, first we observe that Sv ⊂ Su ,

(31)

v˜(x) = f (˜ u(x))

∀x ∈ Ω\Su .

In fact, for every ε > 0 we have

17 18 19 20

{y ∈ Bρ (x) : |v(y) − f (˜ u(x))| > ε} ⊂ {y ∈ Bρ (x) : |u(y) − u ˜(x)| > ε/K}, hence lim

21

ρ→0+

22 23 24 25 26 27

whenever x ∈ Ω\Su . By a similar argument, if x ∈ Su is a point such that there exists a triplet (u+ , u− , νu ) satisfying (14), (15), then (v + (x) − v − (x)) ⊗ νv = (f (u+ (x)) − f (u− (x))) ⊗ νu

30

Z

Jv(B) =

(v + − v − ) ⊗ νv dHn−1 =

B∩Sv

Z

(f (u+ ) − f (u− )) ⊗ νu dHn−1

B∩Sv

Z

=

31

(f (u+ ) − f (u− )) ⊗ νu dHn−1

B∩Su

32 33

if x ∈ Sv

and f (u− (x)) = f (u+ (x)) if x ∈ Su \Sv . Hence, by (1.8) we get

28 29

|{y ∈ Bρ (x) : |v(y) − f (˜ u(x))| > ε}| =0 n ρ

and Lemma 6.1 is proved.

34 35 36 37 38 39 40 41 42

To prove (31), it is not restrictive to assume that k = 1. Moreover, to simplify our notation, from now on we shall assume that Ω = Rn . The proof of (31) is divided into two steps. In the first step we prove the statement in the one-dimensional case (n = 1), using Theorem 5.2. In the second step we achieve the general result using Theorem 7.1. Step 1. Assume that n = 1. Since Su is at most countable, (7) yields ‹ ‹ + Jv is the that Dv (Su \Sv ) = 0, so that (19) and (21) imply that Dv = Dv Proof: page numbers may be temporary

31

SAMPLE PAPER 1 2 3

Radon-Nikod´ ym decomposition of Dv in absolutely continuous and singular ‹ part with respect to Du . By Theorem 5.2, we have ‹ Dv Dv([t, s[) lim , ‹ (t) = s→t + ‹ Du Du ([t, s[)

4 5 6 7 8 9 10 11 12 13

‹ Du Du([t, s[) lim ‹ (t) = s→t + ‹ Du Du ([t, s[)

‹ Du -almost everywhere in R.

It is well known (see, for instance, [Ste70, 2.5.16]) that every one-dimensional function of bounded variation w has a unique left continuous representative, i.e., a function w ˆ such that w ˆ = w almost everywhere and lims→t− w(s) ˆ = w(t) ˆ for every t ∈ R. These conditions imply (32)

u ˆ(t) = Du(]−∞, t[),

vˆ(t) = Dv(]−∞, t[)

∀t ∈ R

14 15

and

16 17 18 19 20 21 22 23

(33)

limits in (22) exist. By (23) and (24) we get vˆ(s) − vˆ(t)

= ‹ Du ([t, s[)

24

f (ˆ u(s)) − f (ˆ u(t)) ‹ Du ([t, s[)

=

‹ Du ([t, s[)

27 28

30

+

31 32 33 34 35 36 37 38 39 40 41 42

‹ Du

‹ ([t, s[)) − f (ˆ (t) Du u(t)) ‹ Du ‹ Du ([t, s[)

f (ˆ u(t) +

29

‹ Du

‹ ([t, s[)) (t) Du ‹ Du

f (ˆ u(s)) − f (ˆ u(t) +

25 26

∀t ∈ R.

vˆ(t) = f (ˆ u(t))

‹ Let t ∈ R be such that Du ([t, s[) > 0 for every s > t and assume that the

for every s > t. Using the Lipschitz condition on f we find f (ˆ u(t) + vˆ(s) − vˆ(t) − ‹ Du ([t, s[)

‹ Du

‹ ([t, s[)) − f (ˆ (t) Du u (t)) ‹ Du ‹ Du ([t, s[) ‹ u ˆ (s) − u ˆ (t) Du ≤ K − (t) . ‹ ‹ Du ([t, s[) Du

Proof: page numbers may be temporary

32 1 2

AMS and BORIS VEYTSMAN

‹ ([t, s[) is continuous and converges to 0 as s ↓ t. By (29), the function s → Du Therefore Remark 7.1 and the previous inequality imply

3 4

‹ Dv

5

lim ‹ (t) = h→0 + Du

6 7 8 9

h

11

14

lim ‹ (t) = h→0 Du

15

and our statement is proved.

13

18 19 20 21

26 27

lim

h→0

(34)

30 31 32 33 34 35 36 37 38 39

42

‹ y Dv

(t) ‹ y Du

‹ Duy -a.e. in R

‹ y ‹ νi hDu, Du (y + tν) = ‹ ‹ (t) hDu, νi Duy

‹ Duy -a.e. in R

for Hn−1 -almost every y ∈ πν . In fact, by (16) and (18) we get Z ‹ y Du ‹ y dHn−1 (y) = ‹ y dHn−1 (y) · Du Du ‹ πν πν Du y Z ‹ νi ‹ νi hDu, hDu, ‹ ‹ ‹ y dHn−1 (y) · hDu, νi = (y + ·ν) · Du = hDu, νi = ‹ ‹ νi πν hDu, νi hDu, Z

and (24) follows from (13). By the same argument it is possible to prove that

40 41

h

=

for Hn−1 -almost every y ∈ πν . We claim that

28 29

‹ y Du

(t)) − f (˜ u(y + tν)) ‹ y Du

f (˜ u(y + tν) + h

23

25

h

‹ Du -a.e. in R

Step 2. Let us consider now the general case n > 1. Let ν ∈ Rn be such that |ν| = 1, and let πν = {y ∈ Rn : hy, νi = 0}. In the following, we shall identify Rn with πν × R, and we shall denote by y the variable ranging in πν and by t the variable ranging in R. By the just proven one-dimensional result, and by Theorem 3.3, we get

22

24

‹ Du

(t)) − f (˜ u(t)) ‹ Du

f (˜ u(t) + h

‹ Dv

12

17

‹ Du -a.e. in R.

By (22), u ˆ(x) = u ˜(x) for every x ∈ R\Su ; moreover, applying the same argument to the functions u0 (t) = u(−t), v 0 (t) = f (u0 (t)) = v(−t), we get

10

16

‹ Du

(t)) − f (ˆ u(t)) ‹ Du

f (ˆ u(t) + h

(35)

‹ νi ‹ y hDv, Dv (y + tν) = ‹ ‹ (t) hDu, νi Duy

‹ Duy -a.e. in R

Proof: page numbers may be temporary

33

SAMPLE PAPER 1

for Hn−1 -almost every y ∈ πν . By (24) and (25) we get

2 3 4 5

‹ νi hDu,

(y + tν)) − f (˜ u(y + tν)) ‹ νi hDu,

f (˜ u(y + tν) + h lim

h

h→0

=

(y + tν) ‹ νi hDu,

6 7

for Hn−1 -almost every y ∈ πν , and using again (14), (15) we get

8

10

lim

14 15

‹ νi / Du ‹ is strictly positive hDu, ‹ νi -almost evSince the function hDu, erywhere, we obtain also

17 18

lim

‹ ‹ νi hDu, νi hDv, (x) = (x) ‹ ‹ νi Du hDu,

22

25 26 27 28 29 30 31 32 33

‹ hDu, νi -almost everywhere in Rn .

Finally, since

∞ ∫ ‹ ‹ νi ‹ νi ‹ hDu, νi hDu, hDu, Du ‹ = = , ν Du -a.e. in ‹ ‹ ‹ ‹ Du hDu, νi Du Du ∞ ∫ ‹ ‹ νi ‹ νi ‹ hDu, νi hDv, hDv, Dv ‹ = = , ν Du -a.e. in ‹ ‹ ‹ ‹ Du hDu, νi Du Du ‹ and since both sides of (33) are zero Du -almost everywhere on

negligible sets, we conclude that Ñ

34 35

f

36 37

lim

h→0

u ˜(x) + h

‹ Du

‹ (x), ν Du

h

40 41 42

Rn

Rn ‹ hDu, νi -

∫é ∞

− f (˜ u(x)) =

38 39

h

h→0

21

24

‹ ‹ νi hDu, νi hDu, (x)) − f (˜ f (˜ u(x) + h (x) u(x)) ‹ ‹ νi Du hDu,

20

23

‹ νi hDv,

(x) ‹ νi hDu,

=

‹ hDu, νi -a.e. in Rn .

16

19

h

h→0

11

13

‹ νi hDu,

(x)) − f (˜ u(x)) ‹ νi hDu,

f (˜ u(x) + h

9

12

‹ νi hDv,

‹ Dv

‹ (x), ν Du

,

‹ Du -a.e. in Rn . Since ν is arbitrary, by Remarks 7.2 and 7.3 the restriction of ‹ f to the affine space Txu is differentiable at u ˜(x) for Du -almost every x ∈ Rn

and (26) holds.

 Proof: page numbers may be temporary

34 1

AMS and BORIS VEYTSMAN

It follows from (13), (14), and (15) that

2 3

(36)

D(t1 , . . . , tn ) =

(−1)|I|−1 |I|

I∈n

4 5

X

Y

ti

i∈I

Y

(Dj + λj tj ) det A(λ) (I|I).

j∈I

Let ti = x ˆi , i = 1, . . . , n. Lemma 1 leads to

6 7

(37)

D(ˆ x1 , . . . , x ˆn ) =

x ˆi

i∈n

8 9

Y

X

(−1)|I|−1 |I| per A(λ) (I|I) det A(λ) (I|I).

I∈n

By (3), (13), and (37), we have the following result:

10

Theorem 7.2.

11 12 13

(38)

Hc =

14 15 16 17

where (39)

(λ)

Al

=

20 21 22 23 24 25 26

X

per A(λ) (Il |Il ) det A(λ) (I l |I l ), |Il | = l.

Il ⊆n

18 19

n 1 X (λ) l(−1)l−1 Al , 2n l=1

(λ)

It is worth noting that Al of (39) is similar to the coefficients bl of the characteristic polynomial of (10). It is well known in graph theory that the coefficients bl can be expressed as a sum over certain subgraphs. It is interesting to see whether Al , λ = 0, structural properties of a graph. We may call (38) a parametric representation of Hc . In computation, the parameter λi plays very important roles. The choice of the parameter usually depends on the properties of the given graph. For a complete graph Kn , let λi = 1, i = 1, . . . , n. It follows from (39) that

27 28 29

(40)

(1) Al

=

 n!,

if l = 1

0,

otherwise.

30 31

By (38)

32 33

(41)

1 Hc = (n − 1)!. 2

34 35

For a complete bipartite graph Kn1 n2 , let λi = 0, i = 1, . . . , n. By (39),

36 37

(42)

38 39 40 41 42

 −n !n !δ 1 2 n1 n2 , Al = 0,

if l = 2 otherwise .

Hc =

1 n1 !n2 !δn1 n2 . n1 + n2

Proof: page numbers may be temporary

35

SAMPLE PAPER 1

Now, we consider an asymmetrical approach. Theorem 3.3 leads to

2 3

(44)

det K(t = 1, t1 , . . . , tn ; l|l)

4

=

5 6 7 8 9 10 11 12

(−1)|I|

X

Y i∈I

I⊆n−{l}

ti

Y

(Dj + λj tj ) det A(λ) (I ∪ {l}|I ∪ {l}).

j∈I

By (3) and (16) we have the following asymmetrical result: Theorem 7.3. 1 X (−1)|I| per A(λ) (I|I) det A(λ) (I ∪ {l}|I ∪ {l}) (45) Hc = 2 I⊆n−{l} which reduces to Goulden–Jackson’s formula when λi = 0, i = 1, . . . , n [MM64].

13 14 15 16 17 18 19

8. Various font features of the amsmath package 8.1. Bold versions of special symbols. In the amsmath package \boldsymbol is used for getting individual bold math symbols and bold Greek letters— everything in math except for letters of the Latin alphabet, where you’d use \mathbf. For example,

22

A_\infty + \pi A_0 \sim \mathbf{A}_{\boldsymbol{\infty}} \boldsymbol{+} \boldsymbol{\pi} \mathbf{A}_{\boldsymbol{0}}

23

looks like this:

20 21

24 25 26 27 28 29 30

A∞ + πA0 ∼ A∞ + πA0 8.2. “Poor man’s bold”. If a bold version of a particular symbol doesn’t exist in the available fonts, then \boldsymbol can’t be used to make that symbol bold. At the present time, this means that \boldsymbol can’t be used with symbols from the msam and msbm fonts, among others. In some cases, poor man’s bold (\pmb) can be used instead of \boldsymbol:

∂x ∂y ∂y ∂z

31 32 33 34 35 36

$\frac{\partial x}{\partial y} \pmb{\bigg\vert} \frac{\partial y}{\partial z}$ P

37 38 39 40 41 42

Q

So-called “large operator” symbols such as and require an additional command, \mathop, to produce proper spacing and limits when \pmb is used. For further details see The TEXbook. X Y i0.\] \esssup and \meas would be defined in the document preamble as \DeclareMathOperator*{\esssup}{ess\,sup} \DeclareMathOperator{\meas}{meas} The following special operator names are predefined in the amsmath package: \varlimsup, \varliminf, \varinjlim, and \varprojlim. Here’s what they look like in use:

11 12

(48)

13

(49)

lim Q(un , un − u# ) ≤ 0

n→∞

lim |an+1 | / |an | = 0

n→∞

14 15

(50)

16

(51)

17

lim(mλi ·)∗ ≤ 0 −→ lim Ap ≤ 0 ←−

p∈S(A)

18 19 20 21 22 23 24 25 26 27 28 29

\begin{align} &\varlimsup_{n\rightarrow\infty} \mathcal{Q}(u_n,u_n-u^{\#})\le0\\ &\varliminf_{n\rightarrow\infty} \left\lvert a_{n+1}\right\rvert/\left\lvert a_n\right\rvert=0\\ &\varinjlim (m_i^\lambda\cdot)^*\le0\\ &\varprojlim_{p\in S(A)}A_p\le0 \end{align} 9.12. \mod and its relatives. The commands \mod and \pod are variants of \pmod preferred by some authors; \mod omits the parentheses, whereas \pod omits the ‘mod’ and retains the parentheses. Examples:

30 31

(52)

x≡y+1

(mod m2 )

32

(53)

x≡y+1

mod m2

(54)

x≡y+1

(m2 )

33 34 35 36 37 38 39

\begin{align} x&\equiv y+1\pmod{m^2}\\ x&\equiv y+1\mod{m^2}\\ x&\equiv y+1\pod{m^2} \end{align}

40 41 42

9.13. Fractions and related constructions. The usual notation for binomials is similar to the fraction concept, so it has a similar command \binom with Proof: page numbers may be temporary

40 1

AMS and BORIS VEYTSMAN

two arguments. Example:

2

X

3

γ∈ΓC

4 5

Ç å

Ç å

k k−1 k k−2 Iγ = 2 − 2 + 2 1 2 k

Ç å

(55)

l

+ · · · + (−1)

6

k k−l 2 + · · · + (−1)k l

= (2 − 1)k = 1

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

$$\begin{split} [\sum_{\gamma\in\Gamma_C} I_\gamma& =2^k-\binom{k}{1}2^{k-1}+\binom{k}{2}2^{k-2}\\ &\quad+\dots+(-1)^l\binom{k}{l}2^{k-l} +\dots+(-1)^k\\ &=(2-1)^k=1 \end{split}$$ There are also abbreviations \dfrac \dbinom \tfrac \tbinom for the commonly needed constructions {\displaystyle\frac ... } {\displaystyle\binom ... } {\textstyle\frac ... } {\textstyle\binom ... } The generalized fraction command \genfrac provides full access to the six TEX fraction primitives: Æ ∏ n+1 n+1 (56) \overwithdelims: \over: 2 2 (57)

n+1 \atop: 2

(58)

n+1 \above: 2

30 31 32 33 34 35 36 37 38 39 40 41 42

Ç

\atopwithdelims: ñ

n+1 2

n+1 \abovewithdelims: 2

\text{\cn{over}: }&\genfrac{}{}{}{}{n+1}{2}& \text{\cn{overwithdelims}: }& \genfrac{\langle}{\rangle}{}{}{n+1}{2}\\ \text{\cn{atop}: }&\genfrac{}{}{0pt}{}{n+1}{2}& \text{\cn{atopwithdelims}: }& \genfrac{(}{)}{0pt}{}{n+1}{2}\\ \text{\cn{above}: }&\genfrac{}{}{1pt}{}{n+1}{2}& \text{\cn{abovewithdelims}: }& \genfrac{[}{]}{1pt}{}{n+1}{2} Proof: page numbers may be temporary

å

ô

41

SAMPLE PAPER 1

9.14. Continued fractions. The continued fraction

2 3

(59)

4 5

1 √

2+

1 √

6

2+

1 √

7

2+

1 √

8 9 10

can be obtained by typing

11

\cfrac{1}{\sqrt{2}+ \cfrac{1}{\sqrt{2}+ \cfrac{1}{\sqrt{2}+ \cfrac{1}{\sqrt{2}+ \cfrac{1}{\sqrt{2}+\dotsb }}}}}

12 13 14 15 16 17 18 19

2+ √

1 2 + ···

Left or right placement of any of the numerators is accomplished by using \cfrac[l] or \cfrac[r] instead of \cfrac.

24

9.15. Smash. In amsmath there are optional arguments t and b for the plain TEX command \smash, because sometimes it is advantageous to be able to ‘smash’ only the top or only the bottom of something while retaining the √ 0 natural depth or height. In the formula Xj = (1/ λj )Xj \smash[b] has been used to limit the size of the radical symbol.

25

$X_j=(1/\sqrt{\smash[b]{\lambda_j}})X_j’$

20 21 22 23

26 27 28

Without the use of \smash[b] the formula would have appeared thus: Xj = p (1/ λj )Xj0 , with the radical extending to encompass the depth of the subscript j.

29 30 31

9.16. The ‘cases’ environment. ‘Cases’ constructions like the following can be produced using the cases environment.

32 33 34 35 36 37 38 39 40

(60)

Pr−j =

 0

if r − j is odd,

r! (−1)(r−j)/2

if r − j is even.

$$P_{r-j}= \begin{cases} 0& \text{if r-j is odd},\\ r!\,(-1)^{(r-j)/2}& \text{if r-j is even}. \end{cases}$$

41 42

Notice the use of \text and the embedded math. Proof: page numbers may be temporary

42 1 2

AMS and BORIS VEYTSMAN

9.17. Matrix. Here are samples of the matrix environments, \matrix, \pmatrix, \bmatrix, \Bmatrix, \vmatrix and \Vmatrix:

3 4 5 6 7

(61)

ϑ % ϕ $Ç ϑ % ϕ$

å

ñ

ϑ % ϕ $ô ® ϑ % ϕ$

´

ϑ % ϕ $ϑ % ϕ$

8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

\varpi

\varpi

\varpi

\varpi

\varpi

\varpi

29 30 31

To produce a small matrix suitable for use in text, use the smallmatrix environment.

32 33 34 35 36 37

\begin{math} \bigl( \begin{smallmatrix} a&b\\ c&d \end{smallmatrix} \bigr) \end{math}

38 39 40 41 42

To show the Äeffect ä of the matrix on the surrounding lines of a paragraph, we put it here: ac db and follow it with enough text to ensure that there will be at least one full line below the matrix. Proof: page numbers may be temporary

SAMPLE PAPER 1 2

43

\hdotsfor{number } produces a row of dots in a matrix spanning the given number of columns:

3

ϕ

0 . . . 0

(ϕ1 , ε1 )

ϕkn2

ϕ

0

(ϕ , ε ) (ϕ , ε ) . . . W (Φ) = 2 1

2 2

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ϕkn2 ϕ ϕkn n−1

ϕkn1

(ϕn , ε1 ) (ϕn , ε2 ) . . . (ϕn , εn−1 ) (ϕn , εn )

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

$W(\Phi)= \begin{Vmatrix} \dfrac\varphi{(\varphi_1,\varepsilon_1)}&0&\dots&0\\ \dfrac{\varphi k_{n2}}{(\varphi_2,\varepsilon_1)}& \dfrac\varphi{(\varphi_2,\varepsilon_2)}&\dots&0\\ \hdotsfor{5}\\ \dfrac{\varphi k_{n1}}{(\varphi_n,\varepsilon_1)}& \dfrac{\varphi k_{n2}}{(\varphi_n,\varepsilon_2)}&\dots& \dfrac{\varphi k_{n\,n-1}}{(\varphi_n,\varepsilon_{n-1})}& \dfrac{\varphi}{(\varphi_n,\varepsilon_n)} \end{Vmatrix}$ The spacing of the dots can be varied through use of a square-bracket option, for example, \hdotsfor[1.5]{3}. The number in square brackets will be used as a multiplier; the normal value is 1. 9.18. The \substack command. The \substack command can be used to produce a multiline subscript or superscript: for example

27

\sum_{\substack{0\le i\le m\\ 0

format: plain


text:
## Monday, November 9, 2020

### Antenna for SOTA, POTA, and DXpeditions

Initial Prototype:  The initial prototype had a turns ratio of 14:2 (14 secondary and 2 primary).  It used a single 100 pF capacitor across the center conductor to ground.  The tests of this initial prototype after pruning for a best compromise resulted in:

2:1 SWR Bandwidth on 40 meters is 6.730 -> 7.530 MHz with a dip to 1.3:1 SWR at 7.060 MHz

2:1 SWR Bandwidth on 20 meters is 13.910 -> 14.806 MHz with a dip to 1:1 SWR at 14.360 MHz

2:1 SWR Bandwidth on 15 meters is 21.010 -> 22.070 MHz with a dip to 1.6:1 SWR at 21.610 MHz

2:1 SWR Bandwidth on 10 meters is 29.1 -> 30.8 MHz with a dip to 1.8:1 SWR at 29.900 MHz

On 10m it is not very usable unless one has an ATU.

The second prototype (photo below) used two 220 pF capacitors in series which technically by the numbers should be 110 pF.  My measurements of the capacitance was closer to 130 - 140 pF.  This had a substantial effect on making 10 meters usable without a tuner.   The results are as follows:

2:1 SWR Bandwidth on 40 meters is 6.820 -> 7.510 MHz with a dip to 1.3:1 SWR at 7.150 MHz

2:1 SWR Bandwidth on 20 meters is 13.990 -> 14.840 MHz with a dip to 1:1 SWR at 14.430 MHz

2:1 SWR Bandwidth on 15 meters is 20.950 -> 22.270 MHz with a dip to 1.1:1 SWR at 21.650 MHz

2:1 SWR Bandwidth on 10 meters is 29.1 -> 30.8 MHz with a dip to 1.3:1 SWR at 29.900 MHz

Being a link dipole for 30m - here are the results for 30m:

2:1 SWR Bandwidth on 30 meters is 9.730 -> 10.880 MHz with a dip to 1.0:1 SWR at 10.280 MHz with a SWR between 1.3 and 1.2:1 from 10.100 to 10.150 MHz

A third prototype had the following results (identical in construction to the second one) with the following results.

2:1 SWR Bandwidth on 40 meters is 6.820 -> 7.500 MHz with a dip to 1.3:1 SWR at 7.150 MHz

2:1 SWR Bandwidth on 20 meters is 13.980 -> 14.850 MHz with a dip to 1:1 SWR at 14.440 MHz

2:1 SWR Bandwidth on 15 meters is 20.780 -> 22.280 MHz with a dip to 1.2:1 SWR at 21.600 MHz

2:1 SWR Bandwidth on 10 meters is 24.5 -> 29.9 MHz (which actually overlaps into 12 meters) with a dip to 1.1:1 SWR which is wide - 28.0 to 28.5 MHz so 10 meters is now perfectly usable without a tuner and so is 12m which is a very narrow band.

This is one heck of an antenna - requiring no tuner on 40m, 20m, 15m, 12m and 10m and power handling ability as follows SSB 60w, CW - 40w and Digital (key down) - 30w.

The final product:


text:
# How do you solve 45a = 9?

Apr 15, 2018

$a = \frac{1}{5}$

#### Explanation:

$45 a = 9$ Isolate $a$ (divide each side by $45$)
$\left(45 \frac{a}{45}\right) = \left(\frac{9}{45}\right)$ ($\frac{45}{45} = 1$)
$a = \frac{9}{45}$ Simplify 9/45 by dividing by $9$
$a = \frac{\frac{9}{9}}{\frac{45}{9}}$
$a = \frac{1}{5}$

Apr 15, 2018

$a = 0.2$

#### Explanation:

To solve this type of equation, you need to isolate the variable by itself on one side of the equation. The variable in this problem is $a$.

$45 a$ means the same thing as $45 \times a$, so it means multiplication:

Since we see multiplication, we know that we have to use the opposite function, which would be division to isolate $a$.

OPPOSITES:

$\textcolor{red}{\text{addition}}$$\leftrightarrow$$\textcolor{b l u e}{\text{subtraction}}$
$\textcolor{red}{\text{multiplication}}$ $\leftrightarrow$ $\textcolor{b l u e}{\text{division}}$

So we will divide both sides by $45$ to isolate $a$. Since the one side is already being multiplied by $45$, we can cancel the $45$'s:

$\frac{\cancel{45} a}{\cancel{45}} = \frac{9}{45}$

$a = \frac{9}{45}$

Now just divide $9$ by $45$

$a = 0.2$


text:
# Ambit field

In mathematics, an ambit field is a d-dimensional random field describing the stochastic properties of a given system. The input is in general a d-dimensional vector (e.g. d-dimensional space or (1-dimensional) time and (d − 1)-dimensional space) assigning a real value to each of the points in the field. In its most general form, the ambit field, ${\displaystyle Y}$, is defined by a constant plus a stochastic integral, where the integration is done with respect to a Lévy basis, plus a smooth term given by an ordinary Lebesgue integral. The integrations are done over so-called ambit sets, which is used to model the sphere of influence (hence the name, ambit, Latin for "sphere of influence" or "boundary") which affect a given point.

The use and development of ambit fields is motivated by the need of flexible stochastic models to describe turbulence[1] and the evolution of electricity prices[2] for use in e.g. risk management and derivative pricing. It was pioneered by Ole E. Barndorff-Nielsen and Jürgen Schmiegel to model turbulence and tumour growth.[1]

Note, that this article will use notation that includes time as a dimension, i.e. we consider (d − 1)-dimensional space together with 1-dimensional time. The theory and notation easily carries over to d-dimensional space (either including time herin or in a setting involving no time at all).

## Intuition and motivation

In stochastic analysis, the usual way to model a random process, or field, is done by specifying the dynamics of the process through a stochastic (partial) differential equation (SPDE). It is known, that solutions of (partial) differential equations can in some cases be given as an integral of a Green's function convolved with another function – if the differential equation is stochastic, i.e. contaminated by random noise (e.g. white noise) the corresponding solution would be a stochastic integral of the Green's function. This fact motivates the reason for modelling the field of interest directly through a stochastic integral, taking a similar form as a solution through a Green's Function, instead of first specifying a SPDE and then trying to find a solution to this. This provides a very flexible and general framework for modelling a variety of phenomena.[2]

## Definition

A tempo-spatial ambit field, ${\displaystyle Y}$, is a random field in space-time ${\displaystyle \chi \times \mathbb {R} }$ taking values in ${\displaystyle \mathbb {R} }$. Let ${\displaystyle \mu \in \mathbb {R} ,A_{t}(x),B_{t}(x)}$ be ambit sets in ${\displaystyle \chi \times \mathbb {R} _{+},g,q}$ deterministic kernel functions, ${\displaystyle a}$ a stochastic function, ${\displaystyle \sigma \geq 0}$ a stochastic field (called the energy dissipation field in turbulence and volatility in finance) and ${\displaystyle L}$ a Lévy basis. Now, the ambit field ${\displaystyle Y}$ is

${\displaystyle Y_{t}(x)=\mu +\int _{A_{t}(x)}g(\eta ,s,x,t)\sigma _{s}(\eta )L(d\eta ,ds)+\int _{B_{t}(x)}q(\eta ,s,x,t)a_{s}(\eta )\,d\eta \,ds}$

### Ambit sets

In the above, the ambit sets ${\displaystyle A_{t}(x)}$ and ${\displaystyle B_{t}(x)}$ describe the sphere of influence for a given point in space-time. I.e. at a given point, ${\displaystyle (t,x)\in \chi \times \mathbb {R} }$ the sets ${\displaystyle A_{t}(x)}$ and ${\displaystyle B_{t}(x)}$ are the points in space-time which affect the value of the ambit field at ${\displaystyle (t,x),Y_{t}(x)}$. When time is considered as one of the dimensions, the sets are often taken to only include time-coordinates which are at or prior to the current time, t, so as to preserve causality of the field (i.e. a given point in space-time can only be affected by events that happened prior to time ${\displaystyle t}$ and can thus not be affected by the future).

The ambit sets can be of a variety of forms and when using ambit fields for modelling purposes, the choice of ambit sets should be made in a way that captures the desired properties (e.g. stylized facts) of the system considered in the best possible way. In this sense, the sets can be used to make a particular model fit the data as closely as possible and thus provides a very flexible – yet general – way of specifying the model.

### Ambit process

Often, the object of interest is not the ambit field itself, but instead a process taking a particular path through the field. Such a process is called an ambit process. As an example such a process can represent the price of a particular financial object – e.g. the price of a forward contract for a certain time and point in space, space representing things such as time to delivery, spot price, period of delivery etc.[2] This motivates the following definition:

Let the ambit field, Y, be given as above and consider a curve in space-time ${\displaystyle \tau (\theta )=(x(\theta ),t(\theta ))\in \chi \times \mathbb {R} }$. An ambit process is defined as the value of the field along the curve, i.e.

${\displaystyle X_{\theta }=Y_{t(\theta )}(x(\theta ))}$

### Stochastic intermittency/volatility

The energy dissipation field/volatility, ${\displaystyle \sigma }$, is, in general, stochastic (called intermittency in the context of turbulence), and can be modelled as a stochastic variable or field. Particularly, it may itself be modelled by another ambit field, i.e.

${\displaystyle \sigma _{t}^{2}(x)=\int _{C_{t}(x)}h(\eta ,s,x,t){\tilde {L}}(d\eta ,ds)}$

where ${\displaystyle {\tilde {L}}}$ is a non-negative Lévy basis.

## Integration with respect to a Lévy basis

The stochastic integral, ${\displaystyle \int _{A_{t}(x)}g(\eta ,s,x,t)\sigma _{s}(\eta )L(d\eta ,ds)}$, in the definition of the ambit process is an integral of a stochastic field (the integrand) over Lévy basis (the integrator), and is thus more complicated than the usual stochastic Itô-integral. A new theory of integration was provided by Walsh (1987)[3] where integration is done with respect to random fields and this theory can be extended to integration with respect to so-called Lévy bases,[4] which is the main building block of the ambit field.

### Definition of Lévy basis

A family ${\displaystyle (\Lambda (A):A\in \mathbb {B} _{b}(S))}$ of random vectors in ${\displaystyle \mathbb {R} ^{d}}$ is called a Lévy basis on ${\displaystyle S}$ if:

1. The law of ${\displaystyle \Lambda (A)}$ is infinitely divisible for all ${\displaystyle A\in \mathbb {B} _{b}(S)}$.
2. If ${\displaystyle A_{1},A_{2},\ldots ,A_{n}\in \mathbb {B} _{b}(S)}$ are disjoint, then ${\displaystyle \Lambda (A_{1}),\Lambda (A_{2}),\ldots ,\Lambda (A_{n})}$ are independent.
3. If ${\displaystyle A_{1},A_{2},\ldots \in \mathbb {B} _{b}(S)}$ are disjoint with ${\displaystyle \bigcup _{i=1}^{\infty }A_{i}\in \mathbb {B} _{b}(S)}$, then
${\displaystyle \Lambda (\bigcup _{i=1}^{\infty }A_{i})=\sum _{i=1}^{\infty }\Lambda (A_{i})}$, a.s.

where the convergence on the right hand side of 3. is a.s.

Note that properties 2. and 3. define an independently scattered random measure.

## A stationary example

In some data (e.g. commodity prices) there is often found a stationary component, which a good model should be able to capture. The ambit field can be made stationary in a straightforward way. Consider the ambit field ${\displaystyle Y}$, defined as

${\displaystyle Y_{t}=\mu +\int _{A_{t}(x)}g(\eta ,t-s,x)\sigma _{s}(\eta )L(d\eta ,ds)+\int _{B_{t}(x)}q(\eta ,t-s,x)a_{s}(\eta )\,d\eta \,ds}$

where the ambit sets, ${\displaystyle A_{t}(x),B_{t}(x)}$ are of the form ${\displaystyle A_{t}(x)=A+(x,t)}$ where the time-coordinates of ${\displaystyle A}$ are negative (same for ${\displaystyle B}$). Furthermore, we take ${\displaystyle g(\eta ,t,x)=q(\eta ,t,x)=0}$ for ${\displaystyle t\leq 0}$ and that ${\displaystyle \sigma }$ and ${\displaystyle a}$ are also stationary random variables/fields. In particular, we can take ${\displaystyle \sigma }$ to be a stationary ambit field itself:

${\displaystyle \sigma _{t}^{2}(x)=\int _{C_{t}(x)}h(\eta ,t-s,x){\tilde {L}}(d\eta ,ds)}$

where ${\displaystyle {\tilde {L}}}$ is a non-negative Lévy basis and ${\displaystyle h}$ is a positive function.

## References

1. ^ a b Barndorff-Nielsen, O. E., Schmiegel, J. "Ambit processes; with applications to turbulence and tumour growth", Research report, Thiele Centre, December 2005
2. ^ a b c Barndorff-Nielsen, O. E., Benth, F. E., and Veraart, A., "Modelling electricity forward markets by ambit fields", CREATES research center, 2010
3. ^ Walsh, J., "An introduction to stochastic partial differential equations", Lecture Notes in Mathematics, 1986
4. ^ Barndorff–Nielsen, O. E., Benth, F. E., and Veraart, A., "Ambit processes and stochastic partial differential equations", CREATES research center, 2010


text:
# Question e676b

##### 1 Answer
Aug 16, 2017

$\text{density} = 1.85$ ${\text{g/cm}}^{3}$

#### Explanation:

Well, if you know part 1, then the mass of the corn oil is $204$ $\text{g}$ (zero decimal places, as per rules of significant figures), and we're given its volume is $110.0$ ${\text{cm}}^{3}$.

The equation for density is

$\text{density" = "mass"/"volume}$

We know:

• $\text{mass} = 204$ $\text{g}$

• $\text{volume} = 110.0$ ${\text{cm}}^{3}$

Plugging these in:

"density" = (204color(white)(l)"g")/(110.0color(white)(l)"cm"^3) = color(red)(ulbar(|stackrel(" ")(" "1.85color(white)(l)"g/cm"^3" ")|)#

rounded to $3$ significant figures.


text:
### Author Topic: Text Book 2.4 Example 2.1  (Read 263 times)

#### Yifei Hu

• Full Member
• Posts: 15
• Karma: 0
##### Text Book 2.4 Example 2.1
« on: February 19, 2022, 09:16:55 PM »
In this problem, $-1 < t < -\infty$, when applying D' Alembert's formula, why we integrate from 0 to t instead of from -1 to t?
We integrate from $t=0$ because for $t=0$ initial conditions are done. $-1<t$ is a domain where $f(x,t)$ is defined


text:
# A2-Math and Memory

## Objectives

• Start practicing C++ commands
• Start declaring and using numerical variables
• Obtain and store user input
• Perform arithmetic operations to solve problems using C++.
• Make use of modulus operators
• Work with mathematical functions.
• Debug errors in your code
• Write your first complete C++ programs!

Read the Scholastic Honesty Policy and Assignment Integrity policies of the syllabus. Here are some clarifications for this particular assignment:

• You may not show your project work to another person or look at another person's project work until you complete and submit this assignment.
• You may get help from others if you get stuck, but only if they do not show or tell you what to type.
• Remember that the instructor performs similarity tests on programming project submissions, and copied or plagiarized code is very easy to detect.

This is a solo assignment.

## Preparation

1. Make sure you have completed the exercises from lesson 2.
2. Complete the Review Exercises in CodeLab 2. These exercises will help prepare you for the problem-solving program and should be completed first.

## Project Specifications

Note that these are solo programming projects and not pair-programming projects. Your solutions to these project must only use techniques we have covered so far.

#### Programming Style

For all programs, remember to follow all the style rules we covered including:

2. Placement of curly braces and indentation within curly braces.
3. Limiting line length to about 80 characters.

TextPad, and most other text editors, tell you both the line and column location, which lets you check the line length.

4. Spaces before and after operators.

#### Project 1: Math Worksheet

Use this worksheet to improve your understanding of how to convert math equations to C++ code. Refer to lesson 2 for more information on C++ maths.

For this worksheet, the user enters three numbers. You write code to display the value of the equations listed below.

##### Project Specifications

Add to the existing code to complete the project. Leave the existing code unchanged, except for comments.

2. You must name the source code file that you turn in mathwork.cpp and include all your code in this single file.

Be careful of the spelling, including capitalization, as you will lose points for a misspelled name. Naming is important in programming.

3. Add your name and the date to the file comment block at the top of the file where shown in the comments.
4. User input is already coded into the worksheet.

Do not add any other input commands or change the input order.

5. Convert each of the following equations to C++ code in the worksheet. The letter x represents the expression.
1. Summation means to add up a sequence of numbers. For expression 1, use the following formula to the sum all the inputs.

Where a, b and c are the user input.

Code this equation in the mathwork.cpp program where indicated in the comments. See the Example Run to verify correctness.

2. For expression 2, calculate the average (arithmetic mean) using the following formula. Code this equation in the mathwork.cpp program where indicated in the comments. See the Example Run to verify correctness.

Where a, b and c are the user input.

3. For expression 3, calculate the weighted average (wa) of the input using the following formula.

Where a, b and c are the user input.

Code this equation in the mathwork.cpp program where indicated in the comments. See the Example Run to verify correctness.

4. For expression 4, calculate the variance (var) using the following formula.

Where a, b and c are the user input.

Code this equation in the mathwork.cpp program where indicated in the comments. See the Example Run to verify correctness.

5. For expression 5, calculate the standard deviation (sd) of the formula shown below.

Where a, b and c are the user input.

Code this equation in the mathwork.cpp program where indicated in the comments. See the Example Run to verify correctness.

6. Example Run: The input prompts and outputs of the program must look like the following for full credit, including the same order of input and exact wording of the output. For the input shown you must get the same output. However, the output must change properly if the inputs are different.
***Math Worksheet***
Enter three numbers separated by spaces, and press the Enter key
For example: 1 2 3[Enter]: 1 2 3

You entered: a = 1, b = 2, c = 3
Parenthesis show correct results with the example numbers.
Expression1 (6): 6
Expression2 (2): 2
Expression3 (2.125): 2.125
Expression4 (0.666667): 0.666667
Expression5 (0.816497): 0.816497

***Math Worksheet***
Enter three numbers separated by spaces, and press the Enter key
For example: 1 2 3[Enter]: 4 6 8

You entered: a = 4, b = 6, c = 8
Parenthesis show correct results with the example numbers.
Expression1 (6): 18
Expression2 (2): 6
Expression3 (2.125): 6.25
Expression4 (0.666667): 2.66667
Expression5 (0.816497): 1.63299

In the above example runs, the user entered the values shown in aqua italics (for emphasis) to produce the output. Your program does NOT print the characters in aqua italics, nor does the user input appear in aqua italics. The values in (parentheses) are expected values when entering the example input of  1 2 3 .

7. Display the output using the default formatting and precision for the numbers -- do NOT add any formatting statements to the code.
8. After displaying the output, exit the program.
9. Submit the source code file mathwork.cpp with the rest of the assignment as described in Deliverables.

#### Project 2: Applying Division and Modulus

In C++, dividing one integer by another truncates the remainder, which removes the decimal part. To compute the integer remainder, we use the remainder operator (%), also known as the modulus operator.

The % operator finds the remainder after division of one number by another. The C++ expression a % b (pronounced a mod b) returns the remainder of the division of a by b if both numbers are positive. For example:

    3  r 1
2 ) 7
-6
1 remainder

For this project we will use both the division and remainder operators to extract single digits form an integer number.

Before starting to code, develop an understanding of the problem and plan as as we discussed in lesson 2.4. You must include both your problem restatement and your plan's algorithm within your C++ source code file (see specification 2).

##### Project Specifications
1. Write a program that gets three numbers from the user and then sums:
1. the hundreds digit of the first number
2. with the tens digit of the second number and
3. the unit digit of the third number.
For example, the sum of the diagonal digits of the following three numbers is 3 because the numbers are all 1 on the diagonal as shown by the highlight.
123
416
781

After reading these specifications, restate the problem in your own words and develop a plan as we discussed in lesson 2.4.

2. Name the source code file sumdiag.cpp and include all your code in this single file.

Be careful of the spelling, including capitalization, as you will lose points for a misspelled name. Naming is important in programming.

When starting your coding effort, restate the problem in the file comment at the top of the file and copy your algorithm into the main function as we discussed in lesson 2.4.4.

3. Ask the user for the three integer numbers, and no other input, as shown in the Example Run.
4. Use the division operator (/) and remainer operator (%) to extract digits from the numbers entered by the user.
5. Example Run: The input prompts and outputs of the program must look like the following for full credit, including the same order of input and same wording of the output. For the input shown you must get the same output. However, the output must change properly if the inputs are different.
Enter first number:  123
Enter second number: 416
Enter third number:  781
Sum of diagonal digits is 3

Enter first number:  123
Enter second number: 456
Enter third number:  789
Sum of diagonal digits is 15

Enter first number:  1234
Enter second number: 56
Enter third number:  789
Sum of diagonal digits is 16

Enter first number:  1
Enter second number: 2
Enter third number:  3
Sum of diagonal digits is 3

In the above example run, the user entered the values shown in aqua italics (for emphasis) to produce the output. Your program does NOT print the characters in aqua italics, nor does the user input appear in aqua italics.

Notice the fourth example. Entering a 1 is the same as 001. Similarly, entering a 2 is the same as entering 002 and entering a 3 is the same as entering 003. Thus arranging the three numbers in a matrix of rows and columns shows us how the answer was derived.

001
002
003

6. After displaying the output, exit the program.
7. Do not use if-statements, strings or techniques we have not covered.
8. Submit the source code file sumdiag.cpp with the rest of the assignment as described in Deliverables.
Hints:

#### Project 3: Exploring Other Worlds

The mass of every moon and planet in our solar system differs. Since mass affects our weight [1], how much we weigh will differ on other worlds [2]. Mass also affects how high we can jump on other worlds.

Before starting to code, develop an understanding and plan as as we discussed in lesson 2.4. You must include both your problem restatement and your plan's algorithm within your C++ source code file (see specification 2).

##### Project Specifications
1. Write a program that calculates your weight and how high you can jump on the moon and other worlds.

After reading these specifications, restate the problem in your own words and develop a plan as we discussed in lesson 2.4.

2. You must name the source code file worlds.cpp and include all your code in this single file.

Be careful of the spelling, including capitalization, as you will lose points for a misspelled name. Naming is important in programming.

When starting your coding effort, restate the problem in the file comment at the top of the file and copy your algorithm into the main function as we discussed in lesson 2.4.4.

3. Ask the user for the following inputs (and no other input) in this order, as shown in the Example Run below:
1. What do you weigh (in pounds) on Earth?
2. How high can you jump (in feet) on Earth?
4. Use the following table of values to calculate the weight and jump height on the moon and other worlds:
Name Gravity Relative to Earth
Moon 0.166
Mercury 0.378
Venus 0.907
Mars 0.377
Jupiter 2.364

Source: NASA [3]

The gravity numbers in the table are relative to Earth's gravity. So, if you weigh 110 lbs on Earth you will weigh 18.15 lbs (110 lbs * 0.166) on the Moon. Similarly, if you can jump 2.5 feet high on Earth, you can jump 15.2 feet (2.5 feet / 0.166) on the Moon.

5. Example Run: The input prompts and outputs of the program must look like the following for full credit, including the same order of input and exact wording of the output. For the input shown you must get the same output. However, the output must change properly if the inputs are different.
Planetary Exploration

What do you weigh (in pounds) on Earth? 110
How high can you jump (in feet) on Earth? 2

Name    Weight  Jump Height
----    ------  -----------
Moon    18.26   12.0482
Mercury 41.58   5.29101
Venus   99.77   2.20507
Mars    41.47   5.30504
Jupiter 260.04  0.846024

Planetary Exploration

What do you weigh (in pounds) on Earth? 175.5
How high can you jump (in feet) on Earth? 2.1

Name    Weight  Jump Height
----    ------  -----------
Moon    29.133  12.6506
Mercury 66.339  5.55556
Venus   159.179 2.31533
Mars    66.1635 5.57029
Jupiter 414.882 0.888325

In the above example run, the user entered the values shown in aqua italics (for emphasis) to produce the output. Your program does NOT print the characters in aqua italics, nor does the user input appear in aqua italics.

6. The output must line up nicely as shown in the Example Run. Print "\t" (inside quotes) before the gap shown in the Example Run to line up the output.
7. Use the default formatting and precision for the numbers -- do NOT add any numerical formatting statements to the code.
8. After displaying the output, exit the program.
9. Submit this project with the rest of the assignment as described in Deliverables.
1. Newton's law of universal gravitation: Wikipedia
2. Your Weight On Other Worlds: Exploratorium
3. Planetary Fact Sheet - Ratio to Earth Values: NASA

#### Project 4: Pair Programming Worksheet

Pair programming is where two programmers work together at one computer to develop code projects. One, the driver, writes code while the other, the observer or navigator,[1] reviews each line of code as it is typed in. The two programmers switch roles frequently [1]. Students generally have higher confidence in their work and perform better when pair programming [2]. These effects were tested at Cabrillo College among other places [3].

Programming can be beneficial, but following certain guidelines is important to maximize success [4][5]. This project introduces you to the concepts and best practices of pair programming for our course programming projects.

##### Project Specifications
1. Watch the video Introduction to Pair Programming, a professionally developed video (10 minutes).
2. Save this Pair Programming Worksheet following the menu File > Download as > Plain Text (.txt), and save the file as pairprogramming.txt.
3. Fill out and answer the questions in pairprogramming.txt without deleting any of the existing text.

Provide thoughtful answers for full credit.

4. Submit the pairprogramming.txt file with the rest of the assignment as described in Deliverables.
5. For reference, here is a link to the The Rules of Pair Programming
1. Pair programming: Wikipedia article
2. The effects of pair-programming on performance in an introductory programming course.
3. Pair Programming (Case Study 1)
4. The Rules of Pair Programming
5. All I Really Need to Know about Pair Programming I Learned in Kindergarten: Good suggestions on how to program in pairs.

## Extra Credit

Completing the following is worth the extra credit points shown in parenthesis.

1. Add an additional interesting and useful math equation derived from mathworks.cpp making use of all three of the variables and a math function. (1 point for completing with a math function and 1 point for interest and usefulness.)
1. Submit the source code with the extra math equation in a file named xcmathwork.cpp.
2. Describe what the equation is used for in your README.txt file.
3. Include the data input section of the original mathwork.cpp file.
4. Follow the format of the previous equations by assigning the solution to a unique variable.
5. Follow the output of the previous equations by labeling the equation with a cout statement displaying the label Equation6 followed by the value assigned to the unique variable when entering the example values 1 2 3 and then the equation result itself, like:
Equation6 (42): 42
Equation6 (42): 210
2. Look up constant variables in the textbook (p.39) and declare and use constants integers in sumdiag.cpp for all numbers in equations. (1 point)

Look up magic numbers in the textbook (p.39) or on the internet to understand the solution to magic numbers.

3. Make use of named constants in worlds.cpp so the program does not use any magic numbers. (1 point)

Look up magic numbers in the textbook (p.39) or on the internet to understand the solution to magic numbers.

Make sure to list the extra credit you complete in the README.txt file.

## Tutorial Lab

In preparation for next weeks lessons, complete the following:

2. Complete the Tutorial Exercises in CodeLab 2 before the specified due date.

Refer to the assigned reading for the next lesson to help you understand the problems. Also, you can use the online lecture notes for more information as the notes become available. You can look at solutions if you miss your first few attempts and are stuck by clicking the "Solution" tab.

The instructor will evaluate your assignment using the following criteria. Thus you should check your assignment against these criteria to maximize your score.

Each criteria represents a specific achievement of your assignment and has a scoring guide. The scoring guide explains the possible scores you can receive. Some scoring guides have a list of indicators. These indicators are a sign of meeting, or a symptom of not meeting, the specific criterion. Note that a single indicator may not always be reliable or appropriate in a given context. However, as a group, they show the condition of meeting the criterion.

For information on grading policies, including interpretation of scores, see the syllabus.

#### Lesson Exercises

• 2: All lesson exercises attempted and turned in
• 1: Some lesson exercises completed and turned in
• 0: No lesson exercises completed or turned in

#### Programming Projects (x3)

• 4: Demonstrates mastery of the program
• Applies concepts from the lessons appropriately
• Meets all specifications (see above)
• Runs to completion with no abnormal error conditions
• Generates correct output given correct input
• Correct file name
• 3: Has most of the functionality expected of the program
• Demonstrates some techniques from the lesson
• Attempts to meet all but one of the specifications (see above)
• Implementation seems more complicated than necessary.
• May have one minor error
• 2: Has some of the functionality expected of the program
• Demonstrates some techniques from the lesson
• Attempts to meet at least 1/2 of the specifications (see above)
• Implementation seems excessively complicated.
• May have 2-3 minor errors
• 1: Serious functional problems but shows some effort and understanding
• Attempts to meet less than 1/2 of the of the specifications (see above)
• Has a major error or many minor errors
• Implementation seems very convoluted
• Demonstrates few techniques from the lesson
• 0: Not turned in or uses techniques not covered

#### Pair Programming Worksheet

• 4: Student completed and submitted the learning worksheet with masterful effort
• 3: Student completed and submitted the learning worksheet with substantial effort
• 2: Student completed and submitted the learning worksheet with minimal effort
• 1: Student submitted the learning worksheet
• 0: No learning worksheet submitted

#### Programming Style

• 2: Code is well-documented including:
• 1: Code has some documentation errors
• 0: No apparent attempt to follow documentation standards or write documentation comments

#### CodeLab Exercises

Number completed correctly / number exercises * 8 and rounded up to the nearest integer.

#### README.txt File

• 2: README.txt file submitted following the instructions
• 1: README.txt file submitted but some information was missing
• 0: No README.txt file submitted

Total possible: 30, plus extra credit

## Deliverables

Students submit some homework as they work on it like CodeLab. However, students must submit other homework in Canvas following the link to A2-Math and Memory. For detailed instructions see: How To Submit Homework Assignments. Include the following items when submitting to Canvas:

1. README.txt file prepared by following the instructions for submitting homework.
2. All the exercise files from Lesson 2
• hellome.cpp
• syntax.txt
• variables.cpp
• arithmetic.cpp
• plan.txt
• double.cpp
• errors.txt
• erroneous.cpp
3. mathwork.cpp
4. sumdiag.cpp
5. worlds.cpp
6. pairprogramming.txt
7. Optionally, xcmathwork.cpp (extra credit)

Note: Make certain your programs compile before you turn them in. When a program does not compile then it does not function either. For all programming projects, you should expect little or no credit if your program does not compile and run. For more information see the Grading Criteria.

You must submit all the files needed to complete your assignment together. Your assignment must work as submitted. Remember to test and double check your files before submitting them. If you make a mistake, you can resubmit up to the deadline. If you resubmit, you must include all your assignment files in the last submission as Canvas hides prior submissions.

Last Updated: September 18 2018 @00:49:25


text:
# How to format the outputs of several properties of ComponentMeasurements?

I know someone may have asked similar questions but the solution doesn't work to me.

My code is like this:

a = ComponentMeasurements[
MorphologicalComponents[rb], {"Centroid" , "Area"}, #2 > 60 &]

My output is

{1 -> {{134.861, 140.779}, 65.5}, 2 -> {{168.362, 140.052}, 62.5}}

How can I make the output be {{134.861,140.799},{168.362,140.052}}?

• Please format your code properly. Have a look at the FAQ for how it is done. I'll do it for you this time... – Ajasja Nov 5 '13 at 16:50
• @Ajasja Thank you very much!:) – KathyLL Nov 5 '13 at 19:25

You can use Part, or the short hand notation [[]].

out = {1 -> {{134.861, 140.779}, 65.5}, 2 -> {{168.362, 140.052}, 62.5}}
out[[All, 2, 1]]

produces the desired result.

They are rules:

out = {1 -> {{134.861, 140.779}, 65.5}, 2 -> {{168.362, 140.052}, 62.5}};
First /@ (Range@2 /. out)
(*
{{134.861, 140.779}, {168.362, 140.052}}
*)