text:
# comm.ACPR

Measure adjacent channel power ratio (ACPR)

## Description

The `comm.ACPR` System object™ measures the ACPR of an input signal.

To measure the ACPR of an input signal:

1. Create the `comm.ACPR` object and set its properties.

2. Call the object with arguments, as if it were a function.

## Creation

### Syntax

``acpr = comm.ACPR``
``acpr = comm.ACPR(Name,Value)``

### Description

````acpr = comm.ACPR` creates an ACPR measurement System object.```

example

````acpr = comm.ACPR(Name,Value)` sets properties using one or more name-value arguments. For example, `comm.ACPR('NormalizedFrequency',true)` creates an ACPR measurement object with normalized frequency values.```

## Properties

expand all

Unless otherwise indicated, properties are nontunable, which means you cannot change their values after calling the object. Objects lock when you call them, and the `release` function unlocks them.

If a property is tunable, you can change its value at any time.

Normalized frequency values, specified as one of these logical values.

• `0` (`false`) — Frequency values are measured in Hz.

• `1` (`true`) — Frequency values are normalized in the range [-1, 1].

Data Types: `logical` | `double`

Sample rate of input signal in Hz, specified as a positive scalar.

#### Dependencies

To enable this property, set the `NormalizedFrequency` property to `false`.

Data Types: `double`

Main channel center frequency, specified as a numeric scalar.

• If you set the `NormalizedFrequency` property to `true`, specify the center frequency as a normalized value in the range [−1, 1].

• If you set the `NormalizedFrequency` property to `false`, specify the center frequency in Hz.

This property specifies where the object measures the main channel power in the bandwidth specified by the `MainMeasurementBandwidth` property. For more details on how to set these two properties, see Algorithms.

Data Types: `double`

Main channel measurement bandwidth, specified as a positive scalar.

• If you set the `NormalizedFrequency` property to `true`, specify the measurement bandwidth as a normalized value in the range [0, 1].

• If you set the `NormalizedFrequency` property to `false`, specify the measurement bandwidth in Hz.

This property specifies the bandwidth in which the object measures the main channel power. The measurement is taken at the center of the frequency, specified by the `MainChannelFrequency` property. For more details on how to set these two properties, see Algorithms.

Data Types: `double`

Adjacent channel frequency offsets, specified as a numeric scalar or row vector comprising frequencies that define the location of adjacent channels of interest.

• If you set the `NormalizedFrequency` property to `true`, specify the adjacent channel frequency offsets as normalized values in the range [−1, 1].

• If you set the `NormalizedFrequency` property to `false`, specify the adjacent channel frequency offsets in Hz.

The offset values indicate the distance between the main channel center frequency and adjacent channel center frequencies. Positive offsets indicate adjacent channels to the right of the main channel center frequency. Negative offsets indicate adjacent channels to the left of the main channel center frequency. For more details on how to set properties of the adjacent channels, see Algorithms.

Data Types: `double`

Measurement bandwidth for each adjacent channel, specified as one of these options.

• Numeric scalar — The object obtains all adjacent channel power measurements within equal measurement bandwidths.

• Numeric row vector of length equal to the number of offsets specified in the `AdjacentChannelOffset` property — The object obtains each adjacent channel power measurement based on its specific bandwidth that is centered at the frequency defined by the corresponding frequency offset. The `AdjacentChannelOffset` property defines this frequency offset.

Set the values of this property with respect to the `NormalizedFrequency` property.

• If you set the `NormalizedFrequency` property to `true`, specify the measurement bandwidth values as normalized values in the range [0, 1].

• If you set the `NormalizedFrequency` property to `false`, specify the measurement bandwidth values in Hz.

For more details on how to set properties of the adjacent channels, see Algorithms.

Data Types: `double`

Source of the measurement filter, specified as one of these values.

• `'None'` — The object does not apply filtering to obtain ACPR measurements.

• `'Property'` — The object applies a measurement filter to the main channel before measuring the average power. Specify the measurement filter coefficients by using the `MeasurementFilter` property. Each of the adjacent channel bands also receives a measurement filter.

Data Types: `char` | `string`

Measurement filter coefficients, specified as a numeric row vector containing the coefficients of an FIR filter in descending polynomial powers. Center the response of the filter at DC. The object automatically shifts and applies the filter response at each of the main and adjacent channel center frequencies before obtaining the average power measurements. The internal filter states persist between calls to the object. To clear the states, call the `reset` object function.

The default value specifies an all-pass filter that has no effect on the measurements.

#### Dependencies

To enable this property, set the `MeasurementFilterSource` property to `'Property'`.

Data Types: `double`

Spectral estimation control, specified as one of these values.

• `'Auto'` — The object obtains power measurements with a Welch spectral estimator with zero-percent overlap, a Hamming window, and a segment length equal to the length of the input data vector. The spectral estimator set can achieve the maximum frequency resolution that is attainable with the input data length.

• `'Specify frequency resolution'` — The object uses the value specified by the `FrequencyResolution` property to automatically compute the size of the spectral estimator data window.

• `'Specify window parameters'` — The object obtains power measurements with a Welch spectral estimator determined by the `SegmentLength`, `OverlapPercentage`, `Window`, and `SidelobeAttenuation` properties. In this setting, the `FrequencyResolution` property does not apply, but you can use these properties to control also the resolution.

Data Types: `char` | `string`

Segment length for the spectral estimator in samples, specified as a positive integer. The segment length enables you to make tradeoffs between frequency resolution and variance in the spectral estimates. A long segment length results in better resolution. A short segment length results in more averaging and a decrease in variance.

#### Dependencies

To enable this property, set the `SpectralEstimation` property to ```'Specify window parameters'```.

Data Types: `double`

Overlap percentage between segments in the spectral estimator, specified as a numeric scalar in the range [0, 100].

#### Dependencies

To enable this property, set the `SpectralEstimation` property to ```'Specify window parameters'```.

Data Types: `double`

Window function for the spectral estimator, specified as `'Hamming'`, `'Bartlett'`, `'Bartlett-Hanning'`, `'Blackman'`, `'Blackman-Harris'`, `'Bohman'`, `'Chebyshev'`, `'Flat Top'`, `'Hann'`, `'Nuttall'`, `'Parzen'`, `'Rectangular'`, or `'Triangular'`.

The default Hamming window has a sidelobe attenuation of 42.5 dB. This attenuation can mask spectral content below this value, relative to the peak spectral content. Choosing different windows enables you to make tradeoffs between resolution and sidelobe attenuation.

#### Dependencies

To enable this property, set the `SpectralEstimation` property to ```'Specify window parameters'```.

Data Types: `char` | `string`

Sidelobe attenuation for the Chebyshev window function in dB, specified as a nonnegative scalar.

#### Dependencies

To enable this property, set the `SpectralEstimation` property to ```'Specify window parameters'``` and the `Window` property to `'Chebyshev'`.

Data Types: `double`

Frequency resolution of the spectral estimator, specified as a numeric scalar.

• If you set the `NormalizedFrequency` property to `true`, specify the frequency resolution as a normalized value in the range [0, 1].

• If you set the `NormalizedFrequency` property to `false`, specify the frequency resolution in Hz.

#### Dependencies

To enable this property, set the `SpectralEstimation` property to ```'Specify frequency resolution'```.

Data Types: `double`

Number of fast Fourier transform (FFT) points that the spectral estimator uses, specified as one of these values.

• `'Next power of 2'` — The object sets the number of FFT points to the next power of 2 that is greater than `max(SegmentLength,256)`.

• `'Same as segment length'` — The object sets the number of FFT points to the value of the `SegmentLength` property.

• `'Custom'` — The object sets the number of FFT points to the value of the `CustomFFTLength` property.

Data Types: `char` | `string`

Custom number of FFT points, specified as a positive integer.

#### Dependencies

To enable this property, set the `FFTLength` property to `'Custom'`.

Data Types: `double`

Maximum-hold setting control, specified as one of these logical values.

• `0` (`false`) — The object obtains power measurements by using instantaneous power spectral density estimates.

• `1` (`true`) — The object obtains power measurements by comparing two vectors. One vector is the current estimated power spectral density vector (obtained with the current input data frame). The object checks this vector against the previous maximum-hold accumulated power spectral density vector (obtained at the previous call of the object). The object stores the maximum values at each frequency bin and uses these values to compute average power measurements. To clear the maximum-hold spectrum, use the `reset` object function.

Tunable: Yes

Data Types: `logical` | `double`

Power measurement units, specified as one of these values.

• `'dBm'` or `'dBW'` — The object returns ACPR measurements in a dBc scale (the adjacent channel power referenced to the main channel power).

• `'Watts'` — The object returns ACPR measurements in a linear scale.

Data Types: `char` | `string`

Option to enable main channel power measurement output, specified as a logical `0` (`false`) or `1` (`true`). When you set this property to `true`, the object returns the main channel power measurement. The main channel power is the power of the input signal measured in the band specified by the `MainChannelFrequency` and `MainMeasurementBandwidth` properties. The object returns the power measurements in the unit specified by the `PowerUnits` property.

Data Types: `logical` | `double`

Option to enable adjacent channel power measurements output, specified as a logical `0` (`false`) or `1` (`true`). When you set this property to `true`, the object returns a vector containing adjacent channel power measurements. The adjacent channel powers correspond to the power of the input measured in the bands specified by the `AdjacentChannelOffset` and `AdjacentMeasurementBandwidth` properties. The object returns the power measurements in the unit specified by the `PowerUnits` property.

Data Types: `logical` | `double`

## Usage

### Syntax

``adjChPowRatio = acpr(signal)``
``[adjChPowRatio,mainChPow] = acpr(signal)``
``[adjChPowRatio,adjChPow] = acpr(signal)``
``[adjChPowRatio,mainChPow,adjChPow] = acpr(signal)``

### Description

````adjChPowRatio = acpr(signal)` measures the ACPR in input data `signal`. The measurements are at the frequency bands specified by the `MainChannelFrequency`, `MainMeasurementBandwidth`, `AdjacentChannelOffset`, and `AdjacentMeasurementBandwidth` properties.```
````[adjChPowRatio,mainChPow] = acpr(signal)` measures the main channel power, `mainChPow`. To use this syntax, set the `MainChannelPowerOutputPort` property to `true`. The main channel power is measured within the main channel frequency band specified by the `MainChannelFrequency` and `MainMeasurementBandwidth` properties.```
````[adjChPowRatio,adjChPow] = acpr(signal)` measures the adjacent channel powers, `adjChPow`. To use this syntax, set the `AdjacentChannelPowerOutputPort` property to `true`. The adjacent channel powers are measured at the adjacent frequency bands specified by the `AdjacentChannelOffset` and `AdjacentMeasurementBandwidth` properties.```
````[adjChPowRatio,mainChPow,adjChPow] = acpr(signal)` measures the ACPR, the main channel power, and adjacent channel powers. To use this syntax, set the `MainChannelPowerOutputPort` and `AdjacentChannelPowerOutputPort` properties to `true`.```

### Input Arguments

expand all

Input signal, specified as a column vector of complex numbers.

Data Types: `double`
Complex Number Support: Yes

### Output Arguments

expand all

ACPR measurements, returned as a numeric row vector. The length of the vector equals the number of adjacent channels specified by the `AdjacentChannelOffset` property.

Data Types: `double`

Main channel power measurements, returned as a numeric scalar. The `PowerUnits` property specifies the units used for the returned value.

Data Types: `double`

Adjacent channel power measurements, returned as a numeric row vector. The length of the vector equals the number of adjacent channels specified by the `AdjacentChannelOffset` property. The `PowerUnits` property specifies the units used for the returned value.

Data Types: `double`

## Object Functions

To use an object function, specify the System object as the first input argument. For example, to release system resources of a System object named `obj`, use this syntax:

`release(obj)`

expand all

 `step` Run System object algorithm `release` Release resources and allow changes to System object property values and input characteristics `reset` Reset internal states of System object

## Examples

collapse all

Generate data with an alphabet size of 16, and then modulate the data.

```x = randi([0 15],5000,1); y = qammod(x,16);```

Upsample the data by using a rectangular pulse shape.

```L = 8; yPulse = rectpulse(y,L);```

Create an ACPR measurement object.

```acpr = comm.ACPR(... 'SampleRate',3.84e6*8, ... 'MainChannelFrequency',0, ... 'MainMeasurementBandwidth',3.84e6, ... 'AdjacentChannelOffset',[-5e6 5e6], ... 'AdjacentMeasurementBandwidth',3.84e6, ... 'MainChannelPowerOutputPort',true, ... 'AdjacentChannelPowerOutputPort',true);```

Measure the ACPR, main channel power, and adjacent channel powers of the modulated signal.

`[adjChPowRatio,mainChPow,adjChPow] = acpr(yPulse)`
```adjChPowRatio = 1×2 -14.3659 -14.3681 ```
```mainChPow = 38.8668 ```
```adjChPow = 1×2 24.5010 24.4988 ```

## Algorithms

To comply with the Nyquist sampling theorem, these conditions must be satisfied when you set the frequencies and measurement bandwidths of the main and adjacent channels.

`$\begin{array}{l}|\text{MainChannelFrequency}±\text{}\text{\hspace{0.17em}}\frac{\text{MainMeasurementBandwidth}}{2}|<{F}_{\mathrm{max}}\\ |\left(\text{MainChannelFrequency}+\text{}\text{\hspace{0.17em}}\text{AdjacentChannelOffset}\right)±\frac{\text{AdjacentMeasurementBandwidth}}{2}|<{F}_{\mathrm{max}}\end{array}$`

If you set the `NormalizedFrequency` property to `false`, ${F}_{\mathrm{max}}={F}_{s}/2$, where ${F}_{s}$ is the sampling frequency specified by the `SampleRate` property.

If you set the `NormalizedFrequency` property to `true`, ${F}_{\mathrm{max}}=1$.

## Version History

Introduced in R2012a


text:
# k-means clustering - Characterize clusters

I have a data set giving the number of visits for ~20 web pages for a total of ~3000 users. To indetify "similar" users according to the number of visits of each web page, I ran a k-means clustering.

I now know which user belongs to which of the k = 3 (k is irrelevant here) clusters. But how can I characterize the clusters? Is there a way to come to a conclusion similar to "User X belongs to the cluster of users, that like web pages about News and Politics."?

You used a single metric to classify the users into clusters? I'll assume you have additional, descriptive information about these events. One heuristic would be to run a summary of cluster central tendencies (e.g., means, medians, etc.) based on the cluster assignments across the descriptive information. So, if you have k=3 and x=20 (both k and x are irrelevant, x being the number of descriptors or features), then the output would create a 20 (rows) by 3 (columns) summary matrix for analysis. Next, to determine how the clusters differ on each descriptor, create an index based on the cluster value divided by the global value across all users for each descriptor. This index would be like an IQ score where 100 is "normal," 120+ and 80 or less indicating descriptors that are suggesting behaviors that diverge from the norm. 120+ and 80 or less are like "quick and dirty" significance tests for between group (clusters) differences.

• Just to clarify: Indeed I have one single metric, namely the count of visits of a web page. But I have this metric for 20 web pages. Besides this I only know the topic of the pages, like Politics, News, Travel, Culture... – hitchcock's_birds Dec 2 '16 at 14:22
• Do this analysis for your single descriptor. Otherwise, your data is really impoverished. If you can get these two pieces of information, there has to be more as all of the standard website tools extract boatloads of useless metrics and information. Look into extracting more data. If somebody tells you that it doesn't exist or can't be found, they're not to be believed. – Mike Hunter Dec 2 '16 at 14:36

At the risk of sounding trite, you can just use the cluster centroids to characterize the clusters. The centroid of a cluster is literally the average representation of all the cluster elements. So not only are these are the natural output of k-means clustering, but they're also relatively intuitive.

What I think the answer by TrynnaDoStat is saying is that this can be risky because cluster uniformity is not a given. That is, some applications of k-means will result in clusters that are mostly homogeneous internally, and other applications will result in "messy" clusters. There are several ways to quantify the "messiness" of a clustering result: the answers to How to tell if data is "clustered" enough for clustering algorithms to produce meaningful results? contain some excellent suggestions.

This is a often a difficult task because you're trying to abstract meaning from groups that may or may not exist. When you use K-Means, you're asking the algorithm to find $K$ groups regardless if there are $K$ groups! There are also some quite restrictive assumptions on the kinds of groups you're trying to find when using K-means (How to understand the drawbacks of K-means).

Before you try and abstract meaning, I would convince yourself that you're doing a great identifying groups. This means trying different clustering algorithms and being comfortable with your selection of the number of groups while considering the possibility that there's only 1 group (see strategies here). Once you've done that, I would calculate summary statistics on each of the groups (mean vectors, variances, proportions, etc.) and see if you can abstract any meaning.

Use the cluster centers. They correspond to the average user behavior in each group. So treat them as if you have 3 typical users now, and study their differences.

Beware that k-means is very sensitive to noise. So if you have "one of a kind" users, they may ruin your cluster averages. K-means probably is not a very good choice because of this.

To validate your findings: 1. pay attention o cluster sizes, and 2. run k-means multiple times - if you don't get consistent findings (i.e. there is always a cluster much more interested in politics than the others) then it probably did not work well.

format: plain


text:
List Commands Library for 50g
09-30-2017, 09:27 AM (This post was last modified: 09-30-2017 09:27 AM by pier4r.)
Post: #181
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: List Commands Library for 50g
(09-29-2017 09:39 PM)DavidM Wrote:  Wouldn't it be easier to simply keep the keys and values in their own lists? That way you achieve the above with { key or value list } <target> LCNT/MPOS/etc.

Give it some thought. I think you'll find that keeping the keys and values as separate lists has some nice benefits, and KSORT provides some nice flexibility by allowing you to execute a user-supplied program on the bundled list.

Yes, as I said, I did not play around with KSORT. Having the two list separated is ok and has advantages (I can even input the bundled list and then build somehow the separated lists).

(09-29-2017 11:30 PM)John Keith Wrote:  Not to be disagreeable, but I have to vote for 2a for several reasons:

IMHO, version 2a would result in less stack manipulation than version 2b in most cases.

John

Then I change my vote to 2a too. As wrote, I don't mind much, I thought that 2b was the most stack friendly solution but it happens that I am wrong. Thanks for the explanations.

PS: little request. If you (as 'you all', not John) are going to reply generically to a long post (that is, not to specific paragraphs), could you please shorten the quoted part?

Wikis are great, Contribute :)
10-01-2017, 12:56 PM (This post was last modified: 10-01-2017 01:26 PM by pier4r.)
Post: #182
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: List Commands Library for 50g
After a quick look in listExt and goferlist I did not find it, so request (maybe I already requested it, I don't remember).

What about such a command (for list of integers/reals or even just reals):

L3: input list
L2: list positions to increment
L1: increments to apply (same size of the position lists)

example
L3: { 0 0 1 0 2 }
L2: { 1 2 5 }
L1: { 3 2 1 }
---
L1: { 3 2 1 0 3 }

Or is it too better to use the built in ADD ? Like:
L2: { 0 0 1 0 2 }
L1: { 3 2 0 0 1 } (maybe a bit cumbersome to create?)

Of course, given the increment, one then would request for subtractions as well (and in the best case multiplication, division). This let me think that maybe the built in operations are already good, since they are already there.

Also random pick from a list.

One could do:
(short, but maybe not always quick with large lists)

or (way longer but pinpointing)
{list} DUP SIZE RAND * 1 + IP GET

{list} LRPICK
(List random pick)

Pick a random element from the list. Returns:
L2: position of the element
L1: value

{list} n LRPICKM
(List random pick multiple)

Pick randomly 'n' times from the list (so the list can be even smaller than n). Produces in output 2 lists
L2: {positions}
L1: {values}

{list} n LRPICKMU
(List random pick multiple unique)
Pick randomly 'n' times from the list without picking from the same position, so n should be at most the size of the list. Produces in output 2 lists
L2: {positions}
L1: {values}
This one can be approximated with:
{list} LSHUF n LFRST

Approximated because one has no positions.

<Spoiled>I want more high quality commands like the others in listExt that simplify programs and avoid that I write my own little libraries.
</spoiled>
(at the end it is my fault, I could have collected various short and fast programs already while reading the forum. Actually I should do it, to provide myself and others with a valid library for lazy people like me)

Wikis are great, Contribute :)
10-01-2017, 02:21 PM
Post: #183
 John Keith Senior Member Posts: 723 Joined: Dec 2013
RE: List Commands Library for 50g
(10-01-2017 12:56 PM)pier4r Wrote:  or (way longer but pinpointing)
{list} DUP SIZE RAND * 1 + IP GET

{ list } DUP SIZE RAND * CEIL GET is shorter and faster.

To pick multiple random items, use the above code in a loop, combine the random indices with \->LIST, and use the resulting list with LPICK. Or, just use LSHUF followed by SUB.

John
10-01-2017, 03:45 PM
Post: #184
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: List Commands Library for 50g
(10-01-2017 02:21 PM)John Keith Wrote:  { list } DUP SIZE RAND * CEIL GET is shorter and faster.

To pick multiple random items, use the above code in a loop, combine the random indices with \->LIST, and use the resulting list with LPICK. Or, just use LSHUF followed by SUB.

John

Thanks. Anyway it is exactly my point. If I have to do it by myself I do it obviously, but putting it in a library would save (for every user and for every place it is used) development/testing time.

Wikis are great, Contribute :)
10-01-2017, 04:50 PM
Post: #185
 DavidM Senior Member Posts: 824 Joined: Dec 2013
RE: List Commands Library for 50g
(10-01-2017 12:56 PM)pier4r Wrote:  Or is it too better to use the built in ADD ? Like:
L2: { 0 0 1 0 2 }
L1: { 3 2 0 0 1 } (maybe a bit cumbersome to create?)

Of course, given the increment, one then would request for subtractions as well (and in the best case multiplication, division). This let me think that maybe the built in operations are already good, since they are already there.

Reading through your description, I kept having the feeling that there were simply too many potential variations for this to be turned into a generic function. It seemed like you were beginning to come to that same conclusion in your request .

One thing I'd point out, though, is that creating the list identified above as L1 could be done fairly easily from the originals in your example as follows:

Code:
\<<   { 0 0 1 0 2 }   { 1 2 5 }   { 3 2 1 }   PICK3 SIZE   \-> pos val sz   \<<     0 sz NDUPN \->LIST     pos val 2 \<< PUT \>> DOLIST   \>> \>>
(after which you can apply whatever function you need: ADD, -, *, etc.).

(10-01-2017 12:56 PM)pier4r Wrote:  Also random pick from a list. ...

Once again, it seems to me that this type of thing is best left for your own specific uses. There's lots of room for interpretation here, with lots of perspectives. With or without replacement? Should the list be randomized once, or after each selection? ...and more. Each variation may indicate a different approach for implementation.

While the LSHUF command performs reasonably well (especially in the most recent version), it is a "big hammer" in that it shuffles the entire list. You may not actually need all of that shuffling going on to do what you need. If you simply need 3 random elements from a list of 3000, it hardly makes sense to shuffle the entire list just to do 1 3 SUB. And that approach assumes "without replacement", which may or may not be appropriate for any given situation.

(10-01-2017 12:56 PM)pier4r Wrote:  I could have collected various short and fast programs already while reading the forum. Actually I should do it, to provide myself and others with a valid library for lazy people like me)

I think that's a good approach.

(10-01-2017 03:45 PM)pier4r Wrote:  If I have to do it by myself I do it obviously, but putting it in a library would save (for every user and for every place it is used) development/testing time.

But that assumes that the command in question has the same input/output that everyone else would need. I don't see that being the case here.
10-01-2017, 05:32 PM
Post: #186
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: List Commands Library for 50g
(10-01-2017 04:50 PM)DavidM Wrote:  But that assumes that the command in question has the same input/output that everyone else would need. I don't see that being the case here.

well, I tried

Wikis are great, Contribute :)
10-01-2017, 05:48 PM (This post was last modified: 10-01-2017 06:34 PM by Thomas Okken.)
Post: #187
 Thomas Okken Senior Member Posts: 1,369 Joined: Feb 2014
RE: List Commands Library for 50g
(10-01-2017 02:21 PM)John Keith Wrote:
(10-01-2017 12:56 PM)pier4r Wrote:  or (way longer but pinpointing)
{list} DUP SIZE RAND * 1 + IP GET

{ list } DUP SIZE RAND * CEIL GET is shorter and faster.

It’s not equivalent, though. With CEIL it is possible to get 0, and there is a correspondingly slightly lower probability of getting the maximum value. 1 + IP is the way to go; correctness trumps speed.

UPDATE: I just checked the manual (the 48SX manual from the MoHPC documentation set) and it says that RAND returns values in the range 0 <= x <= 1.

If that is true, then neither of the above code sequences are correct, because 1 + IP could return SIZE + 1. Seems weird though, I don’t think I’ve ever seen a random number function with that kind of range, it’s usually 0 <= x < 1 or some range of integers. Is the 48SX (and other RPL calculators?) weird in this regard, or is it a typo in the manual?

UPDATE 2: The Programmer's Reference Manual says 0 <= x <= 1, and the Owner's Manual says 0 <= x < 1.
10-01-2017, 05:57 PM
Post: #188
 DavidM Senior Member Posts: 824 Joined: Dec 2013
RE: List Commands Library for 50g
(10-01-2017 05:32 PM)pier4r Wrote:  well, I tried

Yes, nothing wrong with that.

I think it's fair to say that I'm really starting to think more in terms of refining/finalizing the existing command set now as opposed to expanding it. Unless there's something really compelling, I'm more inclined to defer new commands to some future version so that the existing set can be finalized.

There's a handful of optimizations I still need to do with the existing code base, a couple of which only came to my attention recently. A couple others have been on my TODO list for a while, but kept getting pushed down by higher priority items. There's also a couple of design decisions I'd like to get some feedback on before finalizing things. The first of those will be posted momentarily...
10-01-2017, 06:12 PM
Post: #189
 DavidM Senior Member Posts: 824 Joined: Dec 2013
RE: List Commands Library for 50g
As has been pointed out by Joe Horn and John Keith in another thread, real arguments (as opposed to exact integers) are usually better performers when passed to built-in commands for processing.

This brings up an important point about many of the ListExt commands. Previously, I had been thinking that numeric output for many of the commands should be tied to the current mode of the calculator: Exact mode would have the commands output exact integers, Approximate would cause reals instead. That seemed to be a coherent approach that respected a user's mode preference.

That said, I've also wanted to keep an eye on performance of the library's routines. In that sense, real numbers are almost always going to be the hands-down winners. Just as an example:

In exact mode, 5000 LSEQ returns the result as a list of exact integers in about 8.75 seconds.
In approximate mode, 5000 LSEQ gives the same result as a list of reals in about 1.29 seconds.

Furthermore, subsequent operations you may want to perform using those results will almost always be faster if they are reals.

My current thinking is that I should return reals for commands that aren't already specifically designated to return integers (such as NL→I), regardless of mode. If integers are needed, it's easy enough for the user to use the built-in R→I command on the result list.

Does anyone have a problem with that? Am I overlooking any significant issues with that approach?
10-01-2017, 06:15 PM
Post: #190
 pier4r Senior Member Posts: 2,075 Joined: Nov 2014
RE: List Commands Library for 50g
for me even if the list commands works only (and always) in real mode would be already fine. The fact that the commands are consistent with the input is a very nice feature though (and I wonder how much work is behind that!). If someone is in exact mode, maybe there is a reason (or the user will find out on his own).

Wikis are great, Contribute :)
10-01-2017, 07:50 PM
Post: #191
 rprosperi Senior Member Posts: 5,023 Joined: Dec 2013
RE: List Commands Library for 50g
(10-01-2017 05:48 PM)Thomas Okken Wrote:  UPDATE 2: The Programmer's Reference Manual says 0 <= x <= 1, and the Owner's Manual says 0 <= x < 1.

Both the 48G AUR and the 50g AUR state RAND's results will be in the range 0 <= x < 1. The 50g User Guide and User Manual do not specify the range, just stating 'between 0 and 1'. I'd guess the 48 Programmer's Ref Manual (which was very early and I don't believe was updated) was incorrect and was fixed in later manual versions.

--Bob Prosperi
10-02-2017, 08:58 AM
Post: #192
 Werner Senior Member Posts: 648 Joined: Dec 2013
RE: List Commands Library for 50g
RAND will never return 0 or 1. I remember from many, many winters ago. Alas, that is all I remember. So I had to look it up:

Random thoughts on HP48 random functions

Basically, it boils down to the fact that a whole class of Random Number Generators use

x(n+1) := (x(n)*a + c) mod m

eg. the early Random Number generator used for the 41c used
c=.211327, a=9821, m=1. (This is from memory, but I think I'm right ;-)
Now, the algorithm on the 48 uses c=0, and thus can never return 0.

Cheers, Werner
10-02-2017, 12:10 PM
Post: #193
 Didier Lachieze Senior Member Posts: 1,369 Joined: Dec 2013
RE: List Commands Library for 50g
I’ve looked at the string functions in this library and I have a question about how numbers with a fractional part should be handled.

For example the description of I→NL ( Integer to Number List ) states that: " A real number will be treated as IP(number)", but in the examples 15.8 is rounded to 16: 15.8 I→NL => { 1 6 }

Same for NL→I, which description states that "Fractional parts of numbers are ignored", but in the example 2,718 is rounded to 3: { 3.14 2.718 } NL→I => 33

Same for NL→S which according to the description is working with absolute value of the integer part of the numbers, but in the example 67.6 is converted to "D" (ASCII 68)
10-02-2017, 01:12 PM
Post: #194
 John Keith Senior Member Posts: 723 Joined: Dec 2013
RE: List Commands Library for 50g
The built-in CHAR command rounds to the nearest integer (e.g. 67.6 CHAR returns "D") so I think that is desirable for the Library's string commands.

John
10-02-2017, 01:53 PM
Post: #195
 DavidM Senior Member Posts: 824 Joined: Dec 2013
RE: List Commands Library for 50g
(10-02-2017 12:10 PM)Didier Lachieze Wrote:  I’ve looked at the string functions in this library and I have a question about how numbers with a fractional part should be handled. ...

Thanks for pointing out the error in the documentation! The commands previously used a truncation approach, but in order to match how most built-in commands work, they were changed to use a "nearest integer" approach instead. I apparently only changed the examples in the documentation without changing the descriptive text. I've added this to my list for updates.
10-03-2017, 07:13 PM
Post: #196
 DavidM Senior Member Posts: 824 Joined: Dec 2013
RE: List Commands Library for 50g
LSPLT/LRSPL

I'm moving forward now with the assumption that option 2a was the consensus for how the result should be presented for LSPLT and LRPSL.

Reals vs. Exact Integers in results

Also, having only received 1 confirming response to my question about always returning real results (as opposed to exact integers while in Exact mode), I'm moving forward with changing all affected commands to only return real results for indexes, counts, and char codes (there's quite a few that this applies to).

These changes will be in the next release, which I'm now thinking will be a "beta" as opposed to "release candidate" due to the nature and quantity of changes that the library is undergoing.
10-03-2017, 07:34 PM (This post was last modified: 10-03-2017 07:34 PM by HP67.)
Post: #197
 HP67 Senior Member Posts: 654 Joined: Dec 2013
RE: List Commands Library for 50g
(10-01-2017 05:48 PM)Thomas Okken Wrote:  UPDATE 2: The Programmer's Reference Manual says 0 <= x <= 1, and the Owner's Manual says 0 <= x < 1.

I have an SX put away. If I have to I can run a program indefinitely until it produces a 1 or drains the batteries

It ain't OVER 'till it's 2 PICK
10-03-2017, 08:31 PM
Post: #198
 Joe Horn Senior Member Posts: 1,774 Joined: Dec 2013
RE: List Commands Library for 50g
(10-03-2017 07:34 PM)HP67 Wrote:
(10-01-2017 05:48 PM)Thomas Okken Wrote:  UPDATE 2: The Programmer's Reference Manual says 0 <= x <= 1, and the Owner's Manual says 0 <= x < 1.

I have an SX put away. If I have to I can run a program indefinitely until it produces a 1 or drains the batteries

No need to do that. As Werner explained above, the RPL RAND function CANNOT return either 0 or 1, ever, guaranteed. Even the 50g AUR manual is wrong about this.

<0|ɸ|0>
-Joe-
10-04-2017, 01:06 AM
Post: #199
 brickviking Senior Member Posts: 336 Joined: Dec 2014
RE: List Commands Library for 50g
(10-03-2017 08:31 PM)Joe Horn Wrote:  ... As Werner explained above, the RPL RAND function CANNOT return either 0 or 1, ever, guaranteed. Even the 50g AUR manual is wrong about this.

Hm. So how do I actually GET a value between 0 and 1 inclusive from a random function, at least in my 50G? I'm even more surprised that the venerable AUR has an error!

(Post 109)

Regards, BrickViking
HP-50g |Casio fx-9750G+ |Casio fx-9750GII (SH4a)
10-04-2017, 04:22 AM (This post was last modified: 10-04-2017 04:23 AM by Thomas Okken.)
Post: #200
 Thomas Okken Senior Member Posts: 1,369 Joined: Feb 2014
RE: List Commands Library for 50g
(10-02-2017 08:58 AM)Werner Wrote:  eg. the early Random Number generator used for the 41c used
c=.211327, a=9821, m=1. (This is from memory, but I think I'm right ;-)

You're absolutely right, and I know that one from memory as well. :-D

That is also the RNG that I use in Free42. This thread got me thinking, though: maybe I should replace that RNG? Even if its properties are generally OK, the RNG in the real HP-42S generates numbers with 12 significant digits, while the one from the HP-41C manual generates numbers with only 6 significant digits.

And now I discover that the HP-42S RAN function behaves exactly like RAND in the 48G! Give it the same seed, and the same numbers pop out.

The behavior for seed 0 is different, but still, it looks like I've stumbled upon another way to make Free42 a bit truer to the original. Neat!
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)


text:
# Tag Info

## Hot answers tagged beam

19

While not an ideal situation, it is common enough that this type of cut/reduction of the beam as it comes to its support actually has a name. This is more often referred to as a coped or dapped steel I beam. There are various ways to transition from the full depth of the beam to the depth you may require at your support. Some examples are: Sometimes the ...

16

This is a textbook example of what not to do. We don't get into stress concentration at the cut off of the corner of the beam, or the fact that the two very different stiffnesses of the beams are a constant cause of differential deflection and vibration. The thin edge of the web sitting on the column cap is an unstable mechanism waiting to either kick the CC ...

6

If the white beam on the left is adequate, the one on the right is much bigger than it needs to be, so hacking a piece out of it might not matter. In general this idea is a horrible example of engineering "design". Still, if you follow the sticker on the wall and "maintain social distancing," that will reduce the number of deaths when it ...

5

TL;DR: Since we can't see how the beam is supported on the other end, its not clear whether its structurally safe. Still, I don't believe this configuration can transfer safely any substantial structural load.. When I first saw the image, my first thought was that this is the one end of a simply supported beam. I thought is was an accident waiting to happen. ...

4

I would recommend you have your boys wear a helmet while playing. Also cover the landing area with 8 inch deep bed of mulch or some soft material like foam sheets covered by a mat. With all due respect to the enviably beautiful job your husband has done, 5 feet cantilever swing is the ideal unbalanced pendulum, overtime working its way to loosen up the nails ...

4

Let's start talking not about hinges, but supports. Specifically, why do supports generate the forces (including bending moments, if applicable) they do (or don't)? Think of a simply supported beam under a downward force. Its supports generate upward reaction forces. Why? Because if they didn't, the system would be unbalanced, and we wouldn't have a ...

4

For a rectangular simply supported plate with length $a$ and width $b$ (Roark's Formulas for stress and strain): $$\sigma_{max} = \sigma_b= \frac{\beta qb^2} {t^2}$$ $\beta$ ranges from 0.287 for a=b to 0.75 for a very long and narrow beam. 0.75 would make it equal to a beam. At a=5b ,$\beta$ is 0.74. Approximately at $a> 5b$ the plate behaves very ...

4

What is really proportional to the distance from the neutral axis (let's denote it $z$) is the strain. For pure bending and a symmetric cross-section the equation for strain is given by $$\epsilon(z) = \frac{z}{\rho}$$ where: $\rho$ or $R$ is the radius of curvature of the beam Because in the linear region the constitutive equation is $\sigma(z) = E\cdot \... 3 Shear buckling of beam web happens when the shear at a section of the beam under consideration surpasses the controlling combination of factored shear. The following three equations are the LFRD method for: no web instability Inelastic web buckling Elastic web buckling These depend on the ratio$h/t$of the web. If this ratio is bigger than 260 web ... 3 For clarity, it's helpful to make the distinction between talking generally about "H-shaped" and "I-shaped" members, which is somewhat vague, versus the actual designations of standardized rolled shapes. The AISC Steel Construction Manual includes section information for standard W, S, HP, and M rolled shapes that will be fairly commonly ... 2 Usually continuity is to be maintained between all joints - wall/slab/beam, and side wall/side wall, or sidewalls/column, to provide water tightness. So, yes, moments due to the pool water (horizontally and vertically) need to be considered. 2 You seem to be mixing up the conditions on the forces and moments acting across the hinge, and the displacements and slopes there. There is no bending moment transmitted across the hinge, but there can be equal and opposite shear forces on each side, and the two slopes can be different non-zero values. The fact that the slopes can be non-zero should be ... 2 Two concepts are in play here: Calculation of moment of inertia for a composite section. Calculation of elastic beam stresses. First, the calculation of$I_{total}$for the wide flange section. Your equation for$I_{total}$via the parallel axis theorem is correct, but the execution went awry. $$I_{total} = \sum (I + A \cdot d^2)$$ Since the section is ... 2 Here,$y'(L)$, i.e., the slope at$x=L$cannot be determined beforehand. However, moment is prescribed at$x=L$. So, the boundary condition will be$EI\frac{d^2y}{dx^2}|_{x=L} = M$. 2 What you want to look for is Shear buckling or Web buckling. It is quite an advanced subject though. In order to determine mode of failure, critical loads etc, you need to specify explicity the boundary conditions, and then solve the problem for the dimensions. In case that you want to determine the permissible load of the member outside the context of a ... 2 In general what you are doing is ok. Assuming you have small enough deflections (either through bending or torsional), you can independently solve the problems. I.e.: Calculate the Force required to obtain the bending exactly as you have done. $$F = \frac{3 \delta \pi d^4 E}{32l^3}$$ Calculate the magnitude of the shear stress. Caveats However, from that ... 2 The short answer would be no, or at least not reliably. In case of an actual static load there is no time dependency, hence no acceleration and thus no signal to integrate. You could try to use the transient response of the beam being loaded and try to integrate that twice in order to determine the deflection. Typically, it is difficult to accurately ... 2 The lower flanges resists a downward bending force that puts tensile stress on the lower flanges. Removing a short section of the lower flange lowers its bending strength but because of the very short lever arm at the cut , bending stresses are relatively very low ; So a clever solution. The shear strength is also reduced but from the visual sizes ,the black ... 2 First of all the bending moment, according to the usual convention (and the one you are presenting here) is positive. However, the problem originates when you add the area of the shear force. (Probably without realising it), what you are doing is you integrate the shear force over dx$\int_0^L V(x)dx$. I am using the mathematical notation because it is ... 2 Your best bet is to rig the planer with a couple of carpenter's horses or something on the sides. However, if we want to go your way need to check the following. Overturning moment on the fully extended setting with 44" cantilevered rollers. Torque on the joint between the two drawer slides. Let's say your machine and its base weigh 40# and the base ... 2 This is a case of a variable-cross-section beam. What you need to do in these cases is separate the cantilever into two parts: near the support it has one cross-section, near the free end, another. The analysis can then be done by hand, but it's a pain and I honestly wouldn't recommend it. Just use some analytical software to get the solution. You also ... 1 Call both the engineer and the builder, strong enough is one thing but meeting specifications ie building regs is another. If the engineer won’t sign it off then you have a problem. 1 Double integration of acceleration over time Double integration with an accelerometer would not yield any useful results under static loading. Alternative approach What you could do instead is the following (the longer the beam the better - a bridge would be ideal for this): place a few accelerometers along one side of the beam (if you can place on top and ... 1 Disclaimer: As a parent myself, I understand your anxiety to keep your boys safe. I have completed this calculation to the best of my knowledge, however I need to point out that I don't feel confident working with US units, nor do I have any experience in wooden structures. One thing to note is the loads on this swing. I'll just point out, outright that I'll ... 1 If we assume a single degree of freedom vibration of the beam as a spring and mass system and substitute beam with half of its mass concentrated at its center, which is not grossly wrong and we also assume no damping, the beam will vibrate under its natural frequency and a rough estimate of its vibration amplitude can be substituted for its deflection. We ... 1 Circular beam I ,$I_{xx}=\pi/4(R^4-R_i^4)\rightarrow I_x= 1.1687in^4M=300*10=3000 ft.lbs$We use 2.5 as factor of safety due to dynamic gust loading. M=3000*2.5=7500lbs.ft$\sigma= My/I<25000 alum= (7500*1.5*12)/1.1687=115512.9psi $We are by far underdesigned. testing for a 4in pipe.$1155512.9*3/4^2=64976.04psi>25000$no good. It would be better ... 1 Using the properties you mentioned, the equation for bending stress is $$\sigma = \frac{M}{I_{xx}}\cdot y_{max}$$ where :$M=F\frac{l}{2}=0.5kNm$(that's a lot)$I_{xx} $= 1800mm4$y_{max} = \frac{thickness}{2}=3[mm]\$ The results is a whopping 833.[MPa], so it will fail. Assuming you use a solid beam (same material), you can estimate the minimum ...

1

It depends on the material and slack of the wire. A wire strong enough and pulled tight can impose large tension forces on the beam. Say the wire is pulled straight and under 50kg deflects only 1cm. The tension force or horizontal component of its reaction at beam will be Fx = 280/2(1)50 = 7000 kg. Which is impractically too large. And causes a huge moment ...

1

The floorboards functions are supporting and distributing loads on beams. Another function is to brace the beams. In the design of the beams we only consider the rectangle section beam, not I section. As you described in the question, the floorboards are nailed to the beam. Thus, if you cut the section of the beam, the connection between the boards and the ...

1

You are on the right track but your equation is wrong on some places and there's some misinterpretation. First error your drawing doesn't show that the midle piece thickness is 5mm (for this type of beam usualy the web and flange thickness is different). Just note some numbers aren't fully in cientific notation. I've done this to stick with your precision ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
Using real-time quantitative PCR, cell-free EBV DNA was detectable in the plasma of 96% (55 of 57) of nasopharyngeal carcinoma (NPC) patients (median concentration, 21058 copies/ml) and 7% (3 of 43) of controls (median concentration, 0 copies/ml). Advanced-stage NPC patients had higher plasma EBV DNA levels than those with early-stage disease. At 1 month after completion of radiotherapy, plasma EBV DNA was undetecTable in 7 of 15 subjects (47%) but remained high in the remaining 8 subjects (53%). Clinical examination revealed that all of the former seven subjects had complete tumor regression, whereas six of the eight latter subjects exhibited evidence of disease persistence or had developed distant metastases. These results suggest that quantitative analysis of plasma EBV DNA may be a useful clinical and research tool in the screening and monitoring of NPC patients.

NPC3 is an important cancer in Southern China and Southeast Asia (1). In Hong Kong, nearly all NPC cases are undifferentiated or poorly differentiated squamous cell carcinoma and harbor EBV in tumor tissues (1). The demonstration that tumor-derived DNA is detectable in the plasma and serum of cancer patients (2, 3) raises the possibility that noninvasive detection and monitoring of NPC may be feasible by EBV DNA PCR analysis of plasma or serum samples. This possibility was realized by Mutirangura et al.(4), who reported that EBV DNA is detectable in the serum of 31% of NPC patients. However, little quantitative information is available regarding the levels of tumor-derived DNA in cancer patients in general and the levels of plasma EBV DNA in NPC patients in particular. To further understand the biological, temporal, and clinical parameters governing the liberation of EBV DNA into the circulation of NPC patients, we developed a real-time quantitative PCR assay (5, 6) for EBV DNA and used this tool to analyze plasma samples from NPC patients.

### Patients.

Fifty-seven patients with histologically confirmed NPC under the care of the Department of Clinical Oncology at the Prince of Wales Hospital were recruited, and informed consent was obtained. All were investigated uniformly with an endoscopic examination of the nasopharynx and computed tomography and staged according to the American Joint Committee on Cancer Staging criteria (7). Blood samples for EBV DNA analysis were taken before the commencement of radiotherapy. An additional blood sample taken 1 month after the completion of radical radiotherapy (≥66 Gy over a 6.6–8.6-week period) was available in 15 of these patients. The mean time interval between blood sampling at presentation and after radiotherapy was 3.5 months. At the time of the second blood sampling, clinical and fiber-optic nasopharyngoscopic examinations and nasopharyngeal biopsies were carried out. The control group consisted of 43 subjects attending a screening clinic for relatives of patients with NPC. These subjects had all undergone examination of the nasopharynx and neck and had been followed-up for a minimum of 1 year with no evidence of NPC development. The study was approved by the Ethics Committee of The Chinese University of Hong Kong.

### DNA Extraction from Plasma Samples.

Peripheral blood (5 ml) was collected from each subject into an EDTA tube for the isolation of plasma. Blood samples were centrifuged at 1600 × g, and plasma was carefully removed from the EDTA-containing tubes and transferred into plain polypropylene tubes. The samples were stored at −20°C until further processing. DNA from plasma samples was extracted using a QIAamp Blood Kit (Qiagen, Hilden, Germany) using the blood and body fluid protocol as recommended by the manufacturer (2). Plasma samples (130–800 μl/column) were used for DNA extraction. The exact amount was documented for the calculation of the target DNA concentration. A final elution volume of 50 μl was used.

### DNA Extraction from Nasopharyngeal Biopsy Samples.

Pre- and postradiotherapy nasopharyngeal biopsy specimens from two NPC patients (TM6 and TM42) were studied. Fifteen paraffin-embedded sections, each of which was 5-μm thick, were made from each biopsy specimen. DNA was extracted with a QIAamp Tissue Kit (Qiagen) using a protocol recommended by the manufacturer. A final elution volume of 50 μl was used.

### Real-Time Quantitative PCR.

Real-time quantitative PCR is based on the continuous optical monitoring of the progress of a fluorogenic PCR reaction (5, 6). In this system, in addition to the two amplification primers used in conventional PCR, a dual-labeled fluorogenic hybridization probe is also included (8). One fluorescent dye serves as a reporter (FAM), and its emission spectra is quenched by a second fluorescent dye (TAMRA). During the extension phase of PCR, the 5′ to 3′ exonuclease activity of Taq DNA polymerase (9) cleaves the reporter from the probe, thus releasing it from the quencher and resulting in an increase in fluorescence emission at 518 nm.

Two real-time quantitative PCR systems were developed for EBV DNA detection: (a) one toward the BamHI-W region; and (b) the other toward the EBNA-1 region (10). The BamHI-W system consisted of the amplification primers W-44F (5′-CCCAACACTCCACCACACC-3′) and W-119R (5′-TCTT AGGAGCTGTCCGAGGG-3′) and the dual-labeled fluorescent probe W-67T [5′-(FAM)CACACACTACACACACCCACCCGTCTC(TAMRA)-3′]. The EBNA-1 system consisted of the amplification primers EBNA-1162F (5′-TCATCATCATCCGGGTCTCC-3′) and EBNA-1229R (5′-CCTACAGGGTGGAAAAATGGC-3′) and the dual-labeled fluorescent probe EBNA-1186T [5′-(FAM)CGCAGGCCCCCTCCAGGTAGAA(TAMRA)-3′]. The fluorescent probes contained a 3′-blocking phosphate group to prevent probe extension during PCR. Primer/probe combinations were designed using Primer Express software (Perkin-Elmer Corp., Foster City, CA). Sequence data for the EBV genome were obtained from the GenBank Sequence Database (accession number V01555). Real-time quantitative PCR for the β-globin gene consisted of primers and probe, as described previously (6), and was used as a control for the amplifiability of plasma DNA. For DNA extracted from paraffin-embedded nasopharyngeal biopsy samples, the β-globin gene quantitative PCR results were used to normalize the EBV DNA quantity.

Fluorogenic PCR reactions were set up in a reaction volume of 50 μl using components (except for the fluorescent probes and amplification primers) supplied in a TaqMan PCR Core Reagent Kit (Perkin-Elmer Corp.). Fluorescent probes were custom-synthesized by Perkin-Elmer Applied Biosystems. PCR primers were synthesized by Life Technologies, Inc. (Gaithersburg, MD). Each reaction contained 5 μl of 10× buffer A; 300 nm of each of the amplification primers; 25 nm (for the EBV probes) or 100 nm (for the β-globin probe) of the corresponding fluorescent probe; 4 mm MgCl2; 200 μm each of dATP, dCTP, and dGTP; 400 μm dUTP; 1.25 units of AmpliTaq Gold; and 0.5 unit of AmpErase uracil N-glycosylase. Extracted plasma DNA or nasopharyngeal tissue DNA (5 μl) was used for amplification. DNA amplifications were carried out in a 96-well reaction plate format in a Perkin-Elmer Applied Biosystems 7700 Sequence Detector. Each sample was analyzed in duplicate. Multiple negative water blanks were included in every analysis.

A calibration curve was run in parallel and in duplicate with each analysis, using DNA extracted from the EBV-positive cell line Namalwa (American Type Culture Collection CRL-1432; Ref. 11) as a standard. Namalwa is a diploid cell line (12) that contains two integrated viral genomes/cell (13). A conversion factor of 6.6 pg of DNA/diploid cell was used for copy number calculation (14). Concentrations of circulating cell-free EBV DNA were expressed as copies of EBV genome/ml plasma. For nasopharyngeal biopsies, results were expressed as a ratio of the copy number of the EBV genome:the copy number of the β-globin gene.

An identical thermal profile was used for the EBV BamHI-W and EBNA-1 PCR systems. Thermal cycling was initiated with a 2-min incubation at 50°C for the uracil N-glycosylase to act, followed by an initial denaturation step of 10 min at 95°C, and then 40 cycles of 95°C for 15 s and 56°C for 1 min were carried out. Conditions for the human β-globin PCR system were as described previously (6).

Amplification data collected by the 7700 Sequence Detector and stored in a Macintosh computer (Apple Computer, Cupertino, CA) were then analyzed using the Sequence Detection System software developed by Perkin-Elmer Applied Biosystems. The mean quantity of each duplicate was used for further concentration calculation. The plasma concentration of EBV DNA or the β-globin gene (expressed in copies/ml) was calculated using the following equation:

$C\ {=}\ Q\ {\times}\ \frac{\mathit{V}_{DNA}}{\mathit{V}_{PCR}}\ {\times}\ \frac{1}{\mathit{V}_{ext}}$

in which C represents the target concentration in plasma (copies/ml), Q represents the target quantity (copies) determined by a sequence detector in a PCR, VDNA represents the total volume of DNA obtained after extraction (typically 50 μl/Qiagen extraction), VPCR represents the volume of DNA solution used for PCR (typically 5 μl), and Vext represents the volume of plasma/serum extracted (typically 0.13–0.80 ml).

### Development of Real-Time Quantitative PCR.

To determine the dynamic range of real-time quantitative PCR, serial dilutions of Namalwa DNA were made and subjected to analysis by the two EBV real-time quantitative PCR systems. Fig. 1 A shows the results obtained using the BamHI-W region PCR system. The amplification curve shifted to the right as the input target quantity was reduced. This was expected because reactions with fewer target molecules required more amplification cycles to produce a certain quantity of reporter molecules than reactions with more target molecules. The system was sensitive enough to detect 5 copies of EBV DNA. Similar results and the detection limit were obtained using the EBNA-1 PCR system (data not shown).

Fig. 1 B shows a plot of the threshold cycle (CT) of the EBV BamHI-W region PCR against the input target quantity, with the latter plotted on a common logarithmic scale. The CT was set at 10 SDs above the mean baseline fluorescence calculated from cycles 1–15 and was proportional to the starting target copy number (logarithmic scale) used for amplification (5). The linearity of the graph demonstrates the large dynamic range and the accuracy of real-time quantitative PCR. Similar results were obtained using the EBNA-1 system (data not shown).

The reproducibility of DNA extraction from plasma and EBV quantitative PCR systems was tested by performing 10 replicate extractions from pooled plasma samples from NPC individuals. These replicate extractions were then subjected to real-time quantitative PCR using the EBV PCR systems. The coefficients of variation of CT values of these replicate analyses were 0.83% for the EBV BamHI-W region PCR and 0.55% for the EBNA-1 PCR.

### Quantitative Analysis of Cell-free EBV DNA in NPC and Control Subjects.

Plasma DNA samples from 57 NPC patients on presentation and 43 control subjects were analyzed using the two EBV real-time quantitative PCR systems. The BamHI-W region PCR measured median plasma EBV DNA concentrations of 21,058 copies/ml (interquartile range, 4,279–93,589 copies/ml) in NPC subjects and 0 copies/ml (interquartile range, 0–0 copies/ml) in control subjects (Fig. 2). Similar results were obtained using the EBNA-1 PCR that showed a strong correlation with the BamHI-W region PCR data (Spearman rank order correlation, correlation coefficient = 0.918; P < 0.0005). The differences in EBV DNA levels between the NPC and control groups using both the BamHI-W region PCR (Mann-Whitney rank-sum test, P < 0.001) and the EBNA-1 PCR (Mann-Whitney rank-sum test, P < 0.001) were highly significant. All plasma DNA samples (NPC and controls) were amplifiable using β-globin PCR, thus confirming the quality of the plasma-extracted DNA.

### Correlation of Plasma Cell-free EBV DNA Levels with Staging in NPC Patients.

Of the 57 NPC cases, 22 were classified as early-stage disease (stages I and II) and 35 were classified as advanced-stage disease (stages III and IV). Plasma cell-free EBV DNA levels in advanced NPC cases (median, 47,047 copies/ml; interquartile range, 17,314–133,766 copies/ml) were significantly higher than those in early-stage NPC cases (median, 5,918 copies/ml; interquartile range, 279–20,452 copies/ml; Mann-Whitney rank-sum test, P < 0.001).

### Change in Plasma EBV DNA Levels after Radiotherapy.

Fifteen NPC patients with no clinical evidence of distant metastases on presentation were further studied at 1 month after the completion of radiotherapy. All 15 patients had detectable plasma cell-free EBV DNA at presentation (Fig. 3). After the completion of radiotherapy, 47% (7 of 15) of the patients had no detectable plasma EBV DNA by both EBV PCR assays. The remaining eight subjects (53%) continued to have detectable plasma EBV DNA (Fig. 3). The change in the proportion of individuals with detectable cell-free EBV DNA after radiotherapy is statistically significant (Fisher’s exact test, P = 0.006). As a control for the quality of plasma DNA, all pre- and postradiotherapy samples were shown to be amplifiable using the β-globin PCR.

At the time of postradiotherapy blood sampling, clinical evaluation showed that all seven patients with undetectable EBV DNA had complete regression of the tumor, whereas six of the eight patients with detectable EBV DNA levels had incomplete regression of the tumor or had developed distant metastases. The difference in the proportions of cases with these clinical outcomes is statistically significant (Fisher’s exact test, P = 0.007).

The pre- and postradiotherapy nasopharyngeal biopsies from the two subjects (TM6 and TM42; Fig. 3) without clinical evidence of tumor persistence who had detectable plasma EBV DNA after radiotherapy were analyzed by real-time quantitative PCR. For subject TM6, the copy number ratios of EBV DNA:β-globin gene pre- and postradiotherapy were 14.3 and 0.18, as determined by the BamHI-W fragment quantitative PCR system. For subject TM42, the corresponding figures were 33.6 and 0.16, respectively. These results represent a reduction of the EBV DNA level in the nasopharyngeal tissue samples of 79.4-fold (subject TM6) and 210-fold (subject TM42) after radiotherapy. The results obtained using the EBNA-1 quantitative PCR system were highly concordant and demonstrated a reduction in EBV DNA level in the nasopharyngeal tissue samples of 118.6-fold (subject TM6) and 275-fold (subject TM42) after radiotherapy.

In this study, we have developed real-time quantitative PCR assays for two regions of the EBV genome, the BamHI-W and the EBNA-1 regions. When these assays were used to analyze plasma DNA extracted from NPC patients, circulating cell-free EBV DNA was detected in 55 of 57 patients (96%). Plasma EBV DNA was detected in 3 of 43 controls (7%). In addition, the levels of plasma EBV DNA in the NPC patients were much higher than those in controls, including the three control subjects with detectable EBV DNA (Fig. 2). These data suggest that quantitative plasma EBV DNA analysis may be useful as a screening method for NPC in high-risk areas. Real-time quantitative PCR is highly suitable for this application due to its rapidity and accuracy.

The clinical significance of the presence of plasma EBV DNA in the three control subjects without clinical evidence of NPC is unclear at present. We are carrying out long-term follow-up of these individuals to monitor any clinical signs of NPC and any change in their plasma EBV DNA levels.

We have taken special precautions to maximize the sensitivity of our system, including the use of prospectively collected samples that were promptly processed after venesection. We chose to use plasma instead of serum because previous work has indicated that DNA is liberated during the clotting process, which results in an increase in human DNA background when serum DNA is used (6). Our use of the real-time PCR method using multiple primer/probe combinations also contributed to the sensitivity and robustness of detection. We believe that these technical improvements have combined to result in a much greater sensitivity in detecting plasma EBV DNA in NPC subjects than the previously reported figure of 31% (4).

Our quantitative approach allowed us to correlate the levels of plasma cell-free EBV DNA with disease staging. Our data indicate that the plasma EBV DNA levels were approximately eight times higher in advanced NPC (stages III and IV) than in early-stage disease (stages I and II). One explanation for these results is that the liberation of EBV DNA into the blood may be related to the tumor load. This contention is supported by our findings on follow-up of patients after radiotherapy.

By analyzing plasma samples from NPC patients before and 1 month after radiotherapy, we demonstrated that 47% (7 of 15) of NPC patients did not have detectable EBV DNA in the plasma by 1 month postradiotherapy. These seven patients had complete regression of the tumor. In contrast, among the eight patients with detectable plasma EBV DNA after radiotherapy, six had incomplete regression of the tumor or had developed distant metastases. These results suggest that plasma EBV DNA measurement may be useful in identifying patients at increased risk of disease persistence after radiotherapy who may benefit from more aggressive treatment such as combined chemotherapy and radiotherapy (15).

To obtain more information on the two patients (subjects TM6 and TM42) without clinical evidence of tumor persistence who still had detecTable plasma EBV DNA after radiotherapy, we analyzed the pre- and postradiotherapy nasopharyngeal biopsies from these individuals. The preradiotherapy nasopharyngeal biopsies from these subjects showed histological evidence of NPC and demonstrated high levels of EBV DNA by quantitative PCR analysis. Large reductions in tissue EBV DNA levels were observed in the postradiotherapy biopsies of both of these individuals. In subject TM42, this reduction in the tissue level of EBV DNA was paralleled by a reduction in plasma EBV DNA levels (Fig. 3). On the contrary, in subject TM6, the plasma EBV DNA level showed an additional increase after radiotherapy (Fig. 3), suggesting that the nasopharyngeal biopsy might have missed residual foci of disease or that occult lymph node or distant metastases might have occurred. We are currently following-up these and other individuals with NPC in an attempt to further understand the relationship between plasma EBV DNA levels and patient survival.

Our data raise the possibility that quantitative measurement of tumor-derived DNA in other cancers may also have clinical and biological value. The most direct extension of our findings would be for the analysis of other viral-associated cancers such as hepatocellular carcinoma and cervical cancer, in which associations with hepatitis B virus (16) and human papillomavirus have been found (17). Real-time quantitative PCR can be readily adapted for quantifying hepatitis B virus and human papillomavirus DNA in plasma DNA.

The mechanism of liberation of cell-free EBV DNA into the plasma of NPC patients is currently unclear. Fournie et al.(18) suggested that plasma DNA may be a marker of cell death. In this regard, apoptosis in tumor tissues has been demonstrated to correlate with the presence of EBV DNA in the serum of NPC patients (4). Our quantitative EBV assays may allow investigation of the mechanism of EBV DNA release by studying viral DNA levels under different clinical conditions, e.g. immediately after radiotherapy or biopsy. Apart from improving our understanding of the biology of NPC, these future studies may also increase our knowledge regarding the biology of plasma tumoral DNA in general.

The costs of publication of this article were defrayed in part by the payment of page charges. This article must therefore be hereby marked advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate this fact.

1

Supported in part by grants from the Hong Kong Research Grants Council.

3

The abbreviations used are: NPC, nasopharyngeal carcinoma; FAM, 6-carboxy- fluorescein; TAMRA, 6-carboxy-tetramethylrhodamine.

Fig. 1.

Detection of EBV DNA by real-time quantitative PCR for the BamHI-W region. A amplification plot of fluorescence intensity against the PCR cycle. Each plot corresponds to a particular input target quantity marked by a corresponding symbol. The X axis denotes the cycle number of a quantitative PCR reaction. The Y axis denotes the ΔRn, which is the fluorescence intensity over the background (5). B plot of the threshold cycle (CT) against the input target quantity (common log scale). The input target quantity was expressed as copies of EBV DNA. The correlation coefficient is 0.994.

Fig. 1.

Detection of EBV DNA by real-time quantitative PCR for the BamHI-W region. A amplification plot of fluorescence intensity against the PCR cycle. Each plot corresponds to a particular input target quantity marked by a corresponding symbol. The X axis denotes the cycle number of a quantitative PCR reaction. The Y axis denotes the ΔRn, which is the fluorescence intensity over the background (5). B plot of the threshold cycle (CT) against the input target quantity (common log scale). The input target quantity was expressed as copies of EBV DNA. The correlation coefficient is 0.994.

Close modal
Fig. 2.

Comparison of plasma cell-free EBV DNA in NPC and control subjects. The categories (NPC and control subjects) are plotted on the X axis. Results from NPC and control subjects are indicated by ○ and ⋄, respectively. The Y axis denotes the concentration of cell-free EBV DNA (copies of EBV DNA/ml of plasma) detected by the BamHI-W region PCR system.

Fig. 2.

Comparison of plasma cell-free EBV DNA in NPC and control subjects. The categories (NPC and control subjects) are plotted on the X axis. Results from NPC and control subjects are indicated by ○ and ⋄, respectively. The Y axis denotes the concentration of cell-free EBV DNA (copies of EBV DNA/ml of plasma) detected by the BamHI-W region PCR system.

Close modal
Fig. 3.

Plasma cell-free EBV DNA in NPC subjects before and after radiotherapy. The X axis marks each of the 15 subjects studied. The Y axis denotes the amount of cell-free EBV DNA (expressed as copies of EBV DNA/ml of plasma) detected by the BamHI-W region PCR system. Data before and after radiotherapy are plotted as ▪ and ▨, respectively. For visual clarity, the seven cases with no detectable EBV DNA after radiotherapy are grouped together on the left of the graph. These cases are followed by the eight cases with detectable levels of EBV DNA after radiotherapy.

Fig. 3.

Plasma cell-free EBV DNA in NPC subjects before and after radiotherapy. The X axis marks each of the 15 subjects studied. The Y axis denotes the amount of cell-free EBV DNA (expressed as copies of EBV DNA/ml of plasma) detected by the BamHI-W region PCR system. Data before and after radiotherapy are plotted as ▪ and ▨, respectively. For visual clarity, the seven cases with no detectable EBV DNA after radiotherapy are grouped together on the left of the graph. These cases are followed by the eight cases with detectable levels of EBV DNA after radiotherapy.

Close modal

We thank Dr. K. F. To for help during the course of this study.

1
Rickinson A. B., Kieff E. Epstein-Barr virus 3rd ed. Fields B. N. Knipe D. M. Howley P. M. eds. .
Fields Virology
,
:
2397
1996
.
2
Chen X. Q., Stroun M., Magnenat J-L., Nicod L. P., Kurt A-M., Lyautey J., Lederrey C., Anker P. Microsatellite alterations in plasma DNA of small cell lung cancer patients.
Nat. Med.
,
2
:
1033
-1035,
1996
.
3
Nawroz H., Koch W., Anker P., Stroun M., Sidransky D. Microsatellite alterations in serum DNA of head and neck cancer patients.
Nat. Med.
,
2
:
1035
-1037,
1996
.
4
Mutirangura A., Pornthanakasem W., Theamboonlers A., Sriuranpong V., Lertsanguansinchi P., Yenrudi S., Voravud N., Supiyaphun P., Poovorawan Y. Epstein-Barr viral DNA in serum of patients with nasopharyngeal carcinoma.
Clin. Cancer Res.
,
4
:
665
-669,
1998
.
5
Heid C. A., Stevens J., Livak K. J., Williams P. M. Real time quantitative PCR.
Genome Res.
,
6
:
986
-994,
1996
.
6
Lo Y. M. D., Tein M. S. C., Lau T. K., Haines C. J., Leung T. N., Poon P. M. K., Wainscoat J. S., Johnson P. J., Chang A. M. Z., Hjelm N. M. Quantitative analysis of fetal DNA in maternal plasma and serum: implications for noninvasive prenatal diagnosis.
Am. J. Hum. Genet.
,
62
:
768
-775,
1998
.
7
Beahrs O. H. Henson D. E. Hutter R. V. P. Kennedy B. J. eds. .
Manual for Staging of Cancer
,
:
31
1997
.
8
Livak K. J., Flood S. J., Marmaro J., Giusti W., Deetz K. Oligonucleotides with fluorescent dyes at opposite ends provide a quenched probe system useful for detecting PCR product and nucleic acid hybridization.
PCR Methods Appl.
,
4
:
357
-362,
1995
.
9
Holland P. M., Abramson R. D., Watson R., Gelfand D. H. Detection of specific polymerase chain reaction product by utilizing the 5′-3′ exonuclease activity of the Thermus aquaticus DNA polymerase.
,
88
:
7276
-7280,
1991
.
10
Baer R., Bankier A. T., Biggin M. D., Deininger P. L., Fallell P. J., Gibson T. J., Hatfull G., Hudson G. S., Satchwell S. C., Seguin C., Tuffnell P. S., Barrell B. G. DNA sequence and expression of the B95-8 Epstein-Barr virus genome.
Nature (Lond.)
,
310
:
207
-211,
1984
.
11
Klein G., Dombos L., Gothoskar B. Sensitivity of Epstein-Barr virus (EBV) producer and non-producer human lymphoblastoid cell lines to superinfection with EB virus.
Int. J. Cancer
,
10
:
44
-57,
1972
.
12
Whitaker A. M. The chromosomes of the Namalwa cell line.
J. Biol. Stand.
,
13
:
173
-175,
1985
.
13
Lawrence J. B., Villnave C. A., Singer R. H. Sensitive, high-resolution chromatin and chromosome mapping in situ: presence and orientation of two closely integrated copies of EBV in a lymphoma line.
Cell
,
52
:
51
-61,
1988
.
14
Saiki R. K., Gelfand D. H., Stoffel S., Scharf S. J., Higuchi R., Horn G. T., Mullis K. B., Erlich H. A. Primer-directed enzymatic amplification of DNA with a thermostable DNA polymerase.
Science (Washington DC)
,
239
:
487
-491,
1988
.
15
Chan A. T. C., Teo P. M. L., Leung W. T., Johnson P. J. Role of chemotherapy in the management of nasopharyngeal cancer.
Cancer (Phila.)
,
82
:
1003
-1012,
1998
.
16
Beasley R. P. Hepatitis B virus: the major etiology of hepatocellular carcinoma.
Cancer (Phila.)
,
61
:
1942
-1946,
1988
.
17
Villa L. L. Human papillomaviruses and cervical cancer.
,
71
:
321
-341,
1997
.
18
Fournie G. J., Courtin J. P., Laval F., Chale J. J., Pourrat J. P., Pujazon M. C., Lauque D., Carles P. Plasma DNA as a marker of cancerous cell death. Investigations in patients suffering from lung cancer and in nude mice bearing human tumours.
Cancer Lett.
,
91
:
221
-227,
1995
.


text:
An Almost Linear Time Approximation Algorithm for the Permanen of a Random (0-1) Matrix

```@inproceedings{Frer2004AnAL,
title={An Almost Linear Time Approximation Algorithm for the Permanen of a Random (0-1) Matrix},
author={Martin F{\"u}rer and S. Kasiviswanathan},
booktitle={FSTTCS},
year={2004}
}```
• Published in FSTTCS 2004
• Computer Science, Mathematics
We present a simple randomized algorithm for approximating permanents. The algorithm with inputs A, ∈ > 0 produces an output X A with (1-∈)per(A) 0, and almost all (0-1) matrices the algorithm runs in time O(n 2 ω), i.e., almost linear in the size of the matrix, where w = w(n) is any function satisfying ω(n) → ∞ as n → ∞. This improves the previous bound of O(n 3 ω) for such matrices. The estimator can also be used to estimate the size of a backtrack tree.

Figures and Topics from this paper

Approximating the Permanent with Deep Rejection Sampling
• Computer Science
• ArXiv
• 2021
We present a randomized approximation scheme for the permanent of a matrix with nonnegative entries. Our scheme extends a recursive rejection sampling method of Huber and Law (SODA 2008) by replacingExpand
FPRAS Approximation of the Matrix Permanent in Practice
• Computer Science
• ArXiv
• 2020
An implementation and detailed runtime analysis of one such Markov Chain Monte Carlo (MCMC) based Fully Polynomial Randomized Approximation Scheme (FPRAS) for the matrix permanent is presented. Expand
Relating counting complexity to non-uniform probability measures
A family of probability distributions over the set of solutions of a problem in TotP are presented, and it is proved that sampling and approximating the normalizing factor is easy; counting is equivalent to computing their normalizing factors. Expand
Approximately Counting Perfect Matchings in General Graphs
• Mathematics, Computer Science
• ALENEX/ANALCO
• 2005
This work presents a much simpler algorithm based on determinants that has an excellent performance for random graphs, another one might be a candidate for a good worst case performance and an experimental analysis of one of its variants. Expand
Scalingmatrices and counting the perfectmatchings in graphs
We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general undirected graphs. Our approach is based on assigning probabilities toExpand
Approximation algorithms for graph problems
This thesis studies approximation algorithms for two fundamental problems arising in graph theory: counting copies of one graph in another graph and estimating distances in geometric graphs. In theExpand
Approximately Counting Embeddings into Random Graphs†
• Computer Science, Mathematics
• Combinatorics, Probability and Computing
• 2014
This paper presents the first general subcase of the subgraph isomorphism counting problem, which is almost always efficiently approximable, and presents a simple randomized algorithm for the counting problem that can be applied to proving many more similar results. Expand
Approximately Counting Embeddings into Random Graphs
• Mathematics, Computer Science
• APPROX-RANDOM
• 2008
This paper presents the first general subcase of the subgraph isomorphism counting problem which is almost always efficiently approximable and presents a simple randomized algorithm for the counting problem. Expand
Solution Counting Algorithms for Constraint-Centered Search Heuristics
• Mathematics, Computer Science
• CP
• 2007
This paper proposes new search heuristics based on solution counting information at the level of individual constraints, and describes efficient algorithms to evaluate the number of solutions of two important families of constraints: occurrence counting constraints, such as alldifferent, and sequencing constraints,such as regular. Expand
Solution counting algorithms for constraint-centered search heuristics
• Mathematics, Computer Science
• Constraints
• 2008
This paper proposes new search heuristics based on solution counting information at the level of individual constraints, and describes efficient algorithms to evaluate the number of solutions of two important families of constraints: occurrence counting constraints, such as alldifferent, and sequencing constraints,such as regular. Expand

References

SHOWING 1-10 OF 20 REFERENCES
Approximating the Permanent
• Mathematics, Computer Science
• SIAM J. Comput.
• 1989
A randomised approximation scheme for the permanent of a 0–1s presented, demonstrating that the matchings chain is rapidly mixing, apparently the first such result for a Markov chain with genuinely c... Expand
An analysis of a Monte Carlo algorithm for estimating the permanent
• M. Jerrum
• Computer Science, Mathematics
• IPCO
• 1993
It is shown that polynomially many trials suffice to approximate the permanent of any dense 0,1-matrix, i.e., one in which every row- and column-sum is at least (1/2+α)n, for some constant α>0. Expand
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Mathematics, Computer Science
• JACM
• 2004
A polynomial-time randomized algorithm for estimating the permanent of an arbitrary n × n matrix with nonnegative entries computes an approximation that is within arbitrarily small specified relative error of the true value of the permanent. Expand
Approximating the Permanent: A Simple Approach
An efficient and very simple unbiased estimator for the enumeration of square (0–1) matrices is presented and it is proved that this estimator runs in time polynomial in the size of the input matrix for almost all matrices. Expand
Clifford algebras and approximating the permanent
• Mathematics, Computer Science
• STOC '02
• 2002
The first main result shows how to compute in polynomial time an estimator with the same mean and variance over the 4-dimensional algebra (which is the quaternions, and is non-commutative); in addition to providing some hope that the computations can be performed in higher dimensions, this quaternion algorithm provides an exponential improvement in the variance over that of the 2-dimensional complex version studied by Karmarkar et al. Expand
A Monte-Carlo Algorithm for Estimating the Permanent
• Mathematics, Computer Science
• SIAM J. Comput.
• 1993
A Monte-Carlo algorithm is described that produces a “good in the relative sense” estimate of the permanent of A and has running time \${\operatorname{poly}(n)2^{{n / 2}} \$, where \${\ operatornam{poly}}( n)\$ denotes a function that grows polynomially with n. Expand
A new approach to the minimum cut problem
• Mathematics, Computer Science
• JACM
• 1996
A randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability with a significant improvement over the previous time bounds based on maximum flows. Expand
Tree Size by Partial Backtracking
• P. Purdom
• Mathematics, Computer Science
• SIAM J. Comput.
• 1978
The efficiency of Knuth's method can be greatly improved by occasionally following more than one path from a node, which results in an improvement which increases exponentially with the height of the tree. Expand
Random Generation of Combinatorial Structures from a Uniform Distribution
• Computer Science, Mathematics
• Theor. Comput. Sci.
• 1986
It is shown that exactly uniform generation of ‘efficiently verifiable’ combinatorial structures is reducible to approximate counting (and hence, is within the third level of the polynomial hierarchy). Expand
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• Computer Science, Mathematics
• STOC '01
• 2001
We present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries.