text:
# 9.6. Graphs Revisited: Pattern Matching¶

Even with the growing interest in computer graphics, processing textual information is still an important area of study. Of particular interest here is the problem of finding patterns, often referred to as substrings, that exist in long strings of characters. The task is to perform some type of search that can identify at least the first occurrence of the pattern. We can also consider an extension of the problem that attempts to find all occurrences.

Python includes a built-in substring method called find that returns the location of the first occurrence of a pattern in a given string. For example,

>>> "ccabababcab".find("ab")
2
>>> "ccabababcab".find("xyz")
-1
>>>

shows that the substring "ab" occurs for the first time starting at index position 2 in the string "ccabababcab". find also returns a -1 if the pattern does not occur.

## 9.6.1. Biological Strings¶

Some of the most exciting work in algorithm development is currently taking place in the domain of bioinformatics; in particular, finding ways to manage and process large quantities of biological data. Much of this data takes the form of coded genetic material stored in the chromosomes of individual organisms. Deoxyribonucleic acid, more commonly known as DNA, is a very simple organic molecule that provides the blueprint for protein synthesis.

DNA is basically a long sequence consisting of four chemical bases: adenine(A), thymine(T), guanine(G), and cytosine(C). These four symbols are often referred to as the “genetic alphabet” and we represent a piece of DNA as a string or sequence of these base symbols. For example, the DNA string ATCGTAGAGTCAGTAGAGACTADTGGTACGA might code a very small part of a DNA strand. It turns out that within these long strings, perhaps thousands and thousands of base symbols long, small pieces exist that provide extensive information as to the meaning of this genetic code. We can see then that having methods for searching out these pieces is a very important tool for the bioinformatics researcher.

Our problem then reduces to the following ideas. Given a string of symbols from the underlying alphabet A, T, G, and C, develop an algorithm that will allow us to locate a particular pattern within that string. We will often refer to the DNA string as the “text.” If the pattern does not exist, we would like to know that as well. Further, since these strings are typically quite long, we need to be sure that the algorithm is efficient.

## 9.6.2. Simple Comparison¶

Our first approach is likely the solution that comes immediately to your mind for solving the DNA string pattern-matching problem. We will simply try all possibilities for matching the pattern to the text. Figure 1 shows how the algorithm will work. We will start out comparing the pattern from left to right with the text, starting at the first character in both. If there is a match, then we proceed to check the second character. Whenever a mismatch occurs, we simply slide the pattern one position to the right and start over.

A Simple Pattern-Matching Algorithm

In this example, we have found a match on the sixth attempt, starting at position 5. The shaded characters denote the partial matches that occurred as we moved the pattern. Listing [lst_simplematcher] shows the Python implementation for this method. It takes the pattern and the text as parameters. If there is a pattern match, it returns the position of the starting text character. Otherwise, it returns -1 to signal that the search failed.

def simple_matcher(pattern, text):
i = 0
j = 0

while True:
if text[i] == pattern[j]:  |\label{lst_simplematcher:line_checkmatch}|
j = j + 1
else:
j = 0  |\label{lst_simplematcher:line_patternreset}|
i = i + 1

if i == len(text):  |\label{lst_simplematcher:line_textended}|
return -1
if j == len(pattern):  |\label{lst_simplematcher:line_patternended}|
return i - j

The variables i and j serve as indices into the text and pattern respectively. The loop repeats until either the text or the pattern ends.

Line [lst_simplematcher:line_checkmatch] checks for a match between the current text character and the current pattern character. If the match occurs, pattern index is incremented. If the match fails, we reset the pattern back to its beginning (line [lst_simplematcher:line_patternreset]). In both cases we move to the next position in the text. At every iteration of the loop we check if there is more text to process (line [lst_simplematcher:line_textended]) and return -1 if not. Line [lst_simplematcher:line_patternended] checks to see if every character in the pattern has been processed. If so, a match has been found and we return its starting index.

If we assume that the length of the text is $$n$$ characters and the length of the pattern is $$m$$ characters, then it is easy to see that the complexity of this approach is $$O(nm)$$. For each of the $$n$$ characters we may have to compare against almost all $$m$$ of the pattern characters. This is not so bad if the size of $$n$$ and $$m$$ are small. However, if we are considering thousands, or perhaps millions, of characters in our text, and in addition a large pattern, it will be necessary to look for a better approach.

## 9.6.3. Using Graphs: Finite State Automata¶

It is possible to create a $$O(n)$$ pattern-matcher if we are willing to do some preprocessing with the pattern. One approach is to build what is known as a deterministic finite automaton, or DFA, that represents the pattern as a graph. Each vertex of the DFA graph is a state, keeping track of the amount of the pattern that has been seen so far. Each edge of the graph represents a transition that takes place after processing a character from the text.

Figure 2 shows a DFA for the example pattern from the last section (ACATA). The first vertex (state 0) is known as the “start state” (or “initial state”) and denotes that we have not seen any matching pattern characters so far. Clearly, before processing the first text character, this is the situation.

A Deterministic Finite Automaton

The DFA works in a very simple way. We keep track of our current state, setting it to 0 when we start. We read the next character from the text. Depending on the character, we follow the appropriate transition to the next state, which in turn becomes the new current state. By definition, each state has one and only one transition for each character in the alphabet. This means that for our DNA alphabet we know that each state has four possible transitions to a next state. Note that in the figure we have labeled some edges (transitions) with multiple alphabet symbols to denote more than one transition to the same state.

We continue to follow transitions until a termination event occurs. If we enter state 5, known as the “final state” (the two concentric circles denote the final state in the DFA graph), we can stop and report success. The DFA graph has discovered an occurrence of the pattern. You might note that there are no transitions out of the final state, meaning that we must stop at that point. The location of the pattern can be computed from the location of the current character and the size of the pattern. On the other hand, if we run out of text characters and the current state is somewhere else in the DFA, known as a “nonfinal” state, we know that the pattern did not occur.

Figure 3 shows a step-by-step trace of the example DFA as it works through the text string ACGACACATA looking for the substring ACATA. The next state computed by the DFA always becomes the current state in the subsequent step. Since there is one and only one next state for every current state–current character combination, the processing through the DFA graph is easy to follow.

A Trace of the DFA Pattern-Matcher

Since every character from the text is used once as input to the DFA graph, the complexity of this approach is $$O(n)$$. However, we need to take into account the preprocessing step that builds the DFA. There are many well-known algorithms for producing a DFA graph from a pattern. Unfortunately, all of them are quite complex mostly due to the fact that each state (vertex) must have a transition (edge) accounting for each alphabet symbol. The question arises as to whether there might be a similar pattern-matcher that employs a more streamlined set of edges.

## 9.6.4. Using Graphs: Knuth-Morris-Pratt¶

Recall the simple pattern-matcher presented earlier. Every possible substring of the text was tested against the pattern. In many cases this proved to be a waste of time since the actual starting point for the match was farther down the text string. A possible solution to this inefficiency would be to slide the pattern more than one text character if a mismatch occurs. Figure 4 shows this strategy using the rule that we slide the pattern over to the point where the previous mismatch happened.

Simple Pattern-Matcher with Longer Shifts

In step 1, we find that the first two positions match. Since the mismatch occurs in the third character (the shaded character), we slide the entire pattern over and begin our next match at that point. In step 2, we fail immediately so there is no choice but to slide over to the next position. Now, the first three positions match. However, there is a problem. When the mismatch occurs, our algorithm says to slide over to that point. Unfortunately, this is too far and we miss the actual starting point for the pattern in the text string (position 5).

The reason this solution failed is that we did not take advantage of information about the content of the pattern and the text that had been seen in a previous attempted match. Note that in step 3, the last two characters of the text string that occur at the time of the mismatch (positions 5 and 6) actually match the first two characters of the pattern. We say that a two-character prefix of the pattern matches a two-character suffix of the text string processed up to that point. This is valuable information. Had we been tracking the amount of overlap between prefixes and suffixes, we could have simply slid the pattern two characters, which would have put us in the right place to start step 4.

This observation leads to a pattern matcher known as Knuth-Morris-Pratt (or KMP), named for the computer scientists who first presented it. The idea is to build a graph representation that will provide information as to the amount of “slide” that will be necessary when a mismatch occurs. The KMP graph will again consist of states and transitions (vertices and edges). However, unlike the DFA graph from the previous section, there will be only two transitions leaving each state.

Figure 5 shows the complete KMP graph for the example pattern. First, there are two special states. The initial state, marked “get,” is responsible for reading the next character from the input text. The subsequent transition, marked with an asterisk, is always taken. Note that the start transition enters this initial state, which means that we initially get the first character from the text and transition immediately to the next state (state 1). The final state (state 6), this time labeled with an “F,” again means success and represents a termination point for the graph.

An Example KMP Graph

Each remaining vertex is responsible for checking a particular character of the pattern against the current text character. For example, the vertex labeled “C?” asks whether the current text character is C. If so, then the edge labeled “Y” is used. This means “yes,” there was a match. In addition, the next character is read. In general, whenever a state is successful in matching the character it is responsible for, the next character is read from the text.

The remaining transitions, those labeled “N,” denote that a mismatch occurred. In this case, as was explained above, we need to know how many positions to slide the pattern. In essence, we want to keep the current text character and simply move back to a previous point in the pattern. To compute this, we use a simple algorithm (see Listing [lst_mismatchlinks]) that basically checks the pattern against itself, looking for overlap between a prefix and a suffix. If such an overlap is found, its length tells us how far back to place the mismatch link in the KMP graph. It is important to note that new text characters are not processed when a mismatch link is used.

Here is the example pattern as it is being processed by the mismatch_links method:

>>> mismatch_links("ACATA")
{1: 0, 2: 1, 3: 1, 4: 2, 5: 1}
>>>

The value returned by the method is a dictionary containing key-value pairs where the key is the current vertex (state) and the value is its destination vertex for the mismatch link. It can be seen that each state, from 1 to 5 corresponding to each character in the pattern, has a transition back to a previous state in the KMP graph.

def mismatch_links(pattern):
aug_pattern = "@" + pattern
for k in range(2, len(aug_pattern)):
while s >= 1:
if aug_pattern[s] == aug_pattern[k - 1]:
break
else:

As we noted earlier, the mismatch links can be computed by sliding the pattern past itself looking for the longest matching prefix and suffix. The method begins by augmenting the pattern so that the indices on the characters match the vertex labels in the KMP graph. Since the initial state is state 0, we have used the “0” symbol as a placeholder. Now the characters 1 to $$m$$ in the augmented pattern correspond directly with the states 1 to $$m$$ in the graph.

Line [lst_mismatchlinks:line_initdict] creates the first dictionary entry, which is always a transition from vertex 1 back to the initial state where a new character is automatically read from the text string. The iteration that follows simply checks larger and larger pieces of the pattern, looking for prefix and suffix overlap. If such an overlap occurs, the length of the overlap can be used to set the next link.

Figure 6 shows the KMP graph as it is being used to locate the example pattern in the text string ACGACACATA. Again, notice that the current character changes only when a match link has been used. In the case of a mismatch, as in steps 4 and 5, the current character remains the same. It is not until step 6, when we have transitioned all the way back to state 0, that we get the next character and return to state 1.

Steps 10 and 11 show the importance of the proper mismatch link. In step 10 the current character, C, does not match the symbol that state 4 needs to match. The result is a mismatch link. However, since we have seen a partial match at that point, the mismatch link reverts back to state 2 where there is a correct match. This eventually leads to a successful pattern match.

A Trace of the KMP Pattern-Matcher

As with the DFA graph from the previous section, KMP pattern-matching is $$O(n)$$ since we process each character of the text string. However, the KMP graph is much easier to construct and requires much less storage as there are only two transitions from every vertex.


text:
## up [and down] Pöstlingberg

Posted in Mountains, pictures, Running, Travel, University life with tags , , , , , , , , , on September 18, 2014 by xi'an

Early morning today, following my Linz guests’ advice, I went running towards the top of Pöstlingberg, a hill 250m over Linz and the Danube river. A perfect beacon that avoiding wrong turns and extra-mileage, but still a wee climb on a steep path for the last part. The reward of the view from the top was definitely worth the [mild] effort and I even had enough time to enjoy a good Austrian breakfast before my ABC talk

## talk in Linz [first slide]

Posted in Mountains, pictures, Running, University life with tags , , , , , , , , , on September 17, 2014 by xi'an

## independent component analysis and p-values

Posted in pictures, Running, Statistics, Travel, University life with tags , , , , , , , , , , , , , on September 8, 2014 by xi'an

Last morning at the neuroscience workshop Jean-François Cardoso presented independent component analysis though a highly pedagogical and enjoyable tutorial that stressed the geometric meaning of the approach, summarised by the notion that the (ICA) decomposition

$X=AS$

of the data X seeks both independence between the columns of S and non-Gaussianity. That is, getting as away from Gaussianity as possible. The geometric bits came from looking at the Kullback-Leibler decomposition of the log likelihood

$-\mathbb{E}[\log L(\theta|X)] = KL(P,Q_\theta) + \mathfrak{E}(P)$

where the expectation is computed under the true distribution P of the data X. And Qθ is the hypothesised distribution. A fine property of this decomposition is a statistical version of Pythagoreas’ theorem, namely that when the family of Qθ‘s is an exponential family, the Kullback-Leibler distance decomposes into

$KL(P,Q_\theta) = KL(P,Q_{\theta^0}) + KL(Q_{\theta^0},Q_\theta)$

where θ⁰ is the expected maximum likelihood estimator of θ. (We also noticed this possibility of a decomposition in our Kullback-projection variable-selection paper with Jérôme Dupuis.) The talk by Aapo Hyvärinen this morning was related to Jean-François’ in that it used ICA all the way to a three-level representation if oriented towards natural vision modelling in connection with his book and the paper on unormalised models recently discussed on the ‘Og.

On the afternoon, Eric-Jan Wagenmaker [who persistently and rationally fight the (ab)use of p-values and who frequently figures on Andrew's blog] gave a warning tutorial talk about the dangers of trusting p-values and going fishing for significance in existing studies, much in the spirit of Andrew’s blog (except for the defence of Bayes factors). Arguing in favour of preregistration. The talk was full of illustrations from psychology. And included the line that ESP testing is the jester of academia, meaning that testing for whatever form of ESP should be encouraged as a way to check testing procedures. If a procedure finds a significant departure from the null in this setting, there is something wrong with it! I was then reminded that Eric-Jan was one of the authors having analysed Bem’s controversial (!) paper on the “anomalous processes of information or energy transfer that are currently unexplained in terms of known physical or biological mechanisms”… (And of the shocking talk by Jessica Utts on the same topic I attended in Australia two years ago.)

## a day of travel

Posted in pictures, Running, Travel with tags , , , , , , on September 1, 2014 by xi'an

I had quite a special day today as I travelled through Birmingham, made a twenty minutes stop in Coventry to drop my bag in my office, went down to London to collect a most kindly loaned city-bike and took the train back to Coventry with the said bike… On my way from Bristol to Warwick, I decided to spend the night in downtown Birmingham as it was both easier and cheaper than to find accommodation on Warwick campus. However, while the studio I rented was well-designed and brand-new, my next door neighbours were not so well-designed in that I could hear them and the TV through the wall, despite top-quality ear-plugs! After a request of mine, they took the TV off but kept to the same decibel level for their uninteresting exchanges. In the morning I tried to go running in the centre of Birmingham but, as I could not find the canals, I quickly got bored and gave up. As Mark had proposed to lend me a city bike for my commuting in [and not to] Warwick, I then decided to take the opportunity of a free Sunday to travel down to London to pick the bike, change the pedals in a nearby shop, add an anti-theft device, and head back to Coventry. Which gave me the opportunity to bike in London by Abbey Road, Regent Park, and Hampstead, before [easily] boarding a fast train back to Coventry and biking up to the University of Warwick campus. (Sadly to discover that all convenience stores had closed by then… )

## Avernian posts

Posted in Mountains, pictures, Running, Travel with tags , , , , , , , , , , on August 31, 2014 by xi'an

## avernian landscapes (#6)

Posted in Mountains, pictures, Running, Statistics, Travel with tags , , , , , , , , , , , , , , on August 30, 2014 by xi'an

## avernian landscapes (#5)

Posted in Mountains, pictures, Running, Statistics, Travel with tags , , , , , , on August 29, 2014 by xi'an

format: plain


text:
# Stochastic individual-based models with power law mutation rate on a general finite trait space

@article{Coquille2021StochasticIM,
title={Stochastic individual-based models with power law mutation rate on a general finite trait space},
author={Loren Coquille and Ann Kraut and Charline Smadi},
journal={Electronic Journal of Probability},
year={2021}
}
• Published 6 March 2020
• Mathematics
• Electronic Journal of Probability

### A stochastic model for speciation by mating preferences

• Computer Science
Journal of mathematical biology
• 2018
A stochastic model of population where individuals, with type a or A, are equivalent from ecological, demographical and spatial points of view, and differ only by their mating preference, showing that mating preferences by themselves, even if they are very small, are enough to entail reproductive isolation between patches.


text:
This affair started quickly, but I knew it was love when I first saw it. A friend of mine first introduced us.

When Apple first came out with these displays, they were expensive. Each one cost about $3500, and at the time almost no computer had graphics cards powerful enough to actually render the screen properly. So that was another$500, just to use it properly.

Somewhat unsurprisingly, Apple no longer makes these.

There’s no real reason to ever have a 30 inch monitor. The screen size is so large that I can comfortably see text from across my room. No bromide about productivity gains can really justify this.

No.

The only reason to get this is the only one that matters: because you damn well want it. Because information was meant to be displayed in all of its glory, with no small screen hiding any of it.

I don’t have a lot of material needs. I gave up my bed months ago and now sleep on the floor in perfect comfort. I own essentially nothing aside from clothes and a laptop full of books.


text:
# HELP VS8 Command line to IDE?

PROBLEM:

C:\>**cl /LD hellomodule.c /Ic:\Python24\include c:\Python24\libs\python24.lib /link/out:hello.dll**

'cl' is not recognized as an internal or external command, operable program or batch file.

I am using Visual Studio Prof Edi 2008.

1. What PATH should I set for this command to work?
2. How to execute above command using the IDE?

NOTE:I am studying this.

C:\>cl /LD hellomodule.c /Ic:\Python24\include c:\Python24\libs\python24.lib /li
nk/out:hello.dll
'cl' is not recognized as an internal or external command,
operable program or batch file.

C:\>PATH="C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\cl.exe"

C:\>cl
'cl' is not recognized as an internal or external command,
operable program or batch file.

C:\>PATH="C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\cl.exe"

C:\>cl /LD hellomodule.c /Ic:\Python24\include c:\Python24\libs\python24.lib /li
nk/out:hello.dll
'cl' is not recognized as an internal or external command,
operable program or batch file.

C:\>

-
David, if cmeerw answered your question, you should mark it as accepted. This gives him +15 rep, and you +2 rep. Plus, it shows the your question has been fully answered. –  Andy Mar 15 '09 at 18:17

## 3 Answers

You can set up the environment by using

C:\Program Files\Microsoft Visual Studio 9.0\VC\vcvarsall.bat

-
@cmeerw,cool you solveed the problem.(1 up:) ) –  Pratik Deoghare Mar 15 '09 at 18:05

I have a "Visual Studio 2008 Command Prompt" in my Programs menu. Are you using that or the command prompt?

-
I'm using normal windows command prompt. –  Pratik Deoghare Mar 15 '09 at 17:20
Don't. Use the "Visual Studio 2008 Command Prompt". That's what it's for. –  John Saunders Mar 15 '09 at 18:24
@John,How to start VS8 cmd prmpt? I'm noob. –  Pratik Deoghare Mar 15 '09 at 18:30

Can you be a bit more specific with your question? What exactly is not working? Can it not find the program, does the compile fail, etc ...

The only immediate issue I can see is that the command line can't resolve the CL command. Try including the full path to the cl.exe binary. This is the relevant path on my machine.

C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\cl.exe

EDIT

When using the path environment variable, you must set it to a path, not an application. Change your path code to

set PATH=%PATH%;C:\Program Files\Microsoft Visual Studio 9.0\VC\bin

As for the inability to load mspdb80.dll, I'm worried messing with your environment variables may have contributed to this problem. Restart your cmd.exe shell and add the line I specified above and retry. If you still get the error with mspdb80.dll you may need to repair your Visual Studio installation.

EDIT2

Definitely looks like the PATH environment variable is messing up the load path for mspdb80.dll. This thread has a bunch of solutions for this problem

http://social.msdn.microsoft.com/Forums/en-US/Vsexpressinstall/thread/2a3c57c5-de79-43e6-9769-35043f732d68/

-
I tried this :( but still same error. –  Pratik Deoghare Mar 15 '09 at 17:17
@david, can you post the full command line when you qualify the path? –  JaredPar Mar 15 '09 at 17:20
@JaredPar,yes its up there. –  Pratik Deoghare Mar 15 '09 at 17:27
@JaredPar,and if I try C:\Program Files\Microsoft Visual Studio 9.0\VC\bin>cl a message box pops up that says "This application has failed to start because mspdb80.dll was not found.Re-installing the application may fix this problem." –  Pratik Deoghare Mar 15 '09 at 17:31
@JaredPar,I tried PATH="C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\". It pops up a box same as in above comment. –  Pratik Deoghare Mar 15 '09 at 17:39


text:
main-content

## Inhaltsverzeichnis

### Force and Visual Control for Safe Human-Robot Interaction

Abstract
Abstract. Unlike the industrial robotics domain where the workspace of machines and humans can be segmented, applications of intelligent machines that work in contact with humans are increasing, which involve e.g. haptic interfaces and teleoperators, cooperative material-handling, power extenders and such high-volume markets as rehabilitation, physical training and entertainment. Force and vision play a fundamental role to increase the autonomy of a robotic system, especially in the presence of humans. Vision provides global information on the surrounding environment to be used for motion planning and obstacle avoidance, while force allows adjusting the robot motion so that the local constraints imposed by the environment are satisfied. In order to avoid dangerous collisions and ensure a safe interaction, suitable control strategies based on force and visual feedback can be used while tracking human motion. This paper surveys such strategies and presents some experimental results in a number of significant case studies.
Bruno Siciliano, Luigi Villani, Vincenzo Lippiello, Agostino De Santis

### 3D Automatic Segmentation of the Hippocampus Using Wavelets with Applications to Radiotherapy Planning

Abstract
During the past half-century, the cornerstone of treatment for brain metastases has been whole brain irradiation (WBI). WBI has multiple salutary effects including rapid relief of neurological signs and symptoms as well as enhanced local control. Unfortunately, WBI may also engender side effects including memory deficits and decrements in quality of life. Since memory control is thought to be mediated by the hippocampus, attention has been turned to whole brain radiotherapeutic techniques that allow sparing of the hippocampus. In order to be able to minimize dose deposition within the hippocampus, clinicians must be able to confidently identify that structure. However, manually tracing out the hippocampus for each patient is time consuming and subject to individual bias. To this end, an automated method can be very useful for such a task. In this paper, we present a method for extracting the hippocampus from magnetic resonance imaging (MRI) data. Our method is based on a multi-scale shape representation using statistical learning in conjunction with spherical wavelets for shape representation. Indeed, the hippocampus shape information is statistically learned by the algorithm and is further utilized to extract a hippocampus from the given 3D MR image. Results are shown on data-sets provided by Brigham and Women’s Hospital.
Yi Gao, Benjamin W. Corn, Dan Schifter, Allen Tannenbaum

### Rigid Registration of 3D Ultrasound and MRI: Comparing Two Approaches on Nine Tumor Cases

Abstract
We present a new technique for registering ultrasound and magnetic resonance (MR) images in the context of neurosurgery. It involves generating a pseudo-ultrasound (pseudo-US) from a segmented MR image and uses cross-correlation as the cost function to register with ultrasound. The algorithm’s performance is compared to a state-of-the-art technique that uses a median filtered MR images to register with a Gaussian-blurred ultrasound using normalized mutual information (NMI). The two methods are tested on nine tumor cases, including both high- and low-grade gliomas. The pseudo-US method yielded significantly better alignment average than that obtained by NMI (p = 0.0009).  If one case where NMI failed is excluded, the mean distance obtained by the pseudo-US approach (2.6 mm) is slightly lower than the one obtained by NMI (2.8mm), but not significantly so (p = 0.16).  We conclude that the pseudo-US method is more robust for these cases.
Laurence Mercier, Vladimir Fonov, Rolando F. Del Maestro, Kevin Petrecca, Lasse R. Østergaard, D. Louis Collins

### A New Approach to Virtual Mirroring for View Integration

Abstract
In this paper, we present an improvement to an image integration technique called Virtual Mirroring (VM). The basis for this approach is formed on the notion that humans are familiar with seeing multiple views of a scene through reflections off various reflective surfaces. VM overlays secondary views of a scene onto virtual mirrors that can be seen by a primary view of the scene, thereby providing more views of a given scene to the observer. We refer to the cameras that capture the secondary and primary views as Secondary (SC) and Principal (PC) Cameras respectively. In our previous approach, the camera setup was constrained to a specific relative position between the cameras. Moreover, the virtual mirrors we created did not respect the laws of reflection. In this new approach, we assume an object plane on the scene in order to be able to determine the world position of each SC image point and subsequently, the corresponding points of reflection through a virtual mirror. By using an object plane, the camera placement is not constrained and the virtual mirrors are created using equations that adhere to the laws of reflection.
Carmen E. Au, James J. Clark

### Designing a Metric for the Difference between Gaussian Densities

Abstract
Measuring the difference between two multivariate Gaussians is central to statistics and machine learning. Traditional measures based on the Bhattacharyya coefficient or the symmetric Kullback-Leibler divergence do not satisfy metric properties necessary for many algorithms. This paper proposes a metric for Gaussian densities. Similar to the Bhattacharyya distance and the symmetric Kullback-Leibler divergence, the proposed metric reduces the difference between two Gaussians to the difference between their parameters. Based on the proposed metric we introduce a symmetric and positive semi-definite kernel between Gaussian densities. We illustrate the benefits of the proposed metric in two settings: (1) a supervised problem, where we learn a low-dimensional projection that maximizes the distance between Gaussians, and (2) an unsupervised problem on spectral clustering where the similarity between samples is measured with our proposed kernel.
Karim T. Abou–Moustafa, Fernando De La Torre, Frank P. Ferrie

### Physical Asymmetries and Brightness Perception

Abstract
This paper considers the problem of estimating the brightness of visual stimuli. A number of physical asymmetries are seen to permit determination of brightness that is invariant to certain manipulations of the sensor responses, such as inversion. In particular, the light-dark range asymmetry is examined and is shown to result, over a certain range, in increased variability of sensor responses as scene brightness increases. Based on this observation we propose that brightness can be measured using variability statistics of conditional distributions of image patch values. We suggest that a process of statistical learning of these conditional distributions underlies the Stevens effect.
James J. Clark

### A Learning-Based Patient Repositioning Method from Limited-Angle Projections

Abstract
This paper presents a novel patient repositioning method from limitedangle tomographic projections. It uses a machine learning strategy. Given a single planning CT image (3D) of a patient, one applies patient-specific training. Using the training results, the planning CT image, and the raw image projections collected at the treatment time, our method yields the difference between the patient’s treatmenttime postition and orientation and the planning-time position and orientation. In the training, one simulates credible treatment-time movements for the patient, and by regression it formulates a multiscale model that expresses the relationship giving the patient’s movements as a function of the corresponding changes in the tomographic projections. When the patient’s real-time projection images are acquired at treatment time, their differences from corresponding projections of the planning-time CT followed by applications of the calculated model allows the patient’s movements to be estimated. Using that estimation, the treatment-time 3D image can be estimated by transforming the planning CT image with the estimated movements,and from this, changes in the tomographic projections between those computed from the transformed CT and the real-time projection images can be calculated. The iterative, multiscale application of these steps converges to the repositioning movements. By this means, this method can overcome the deficiencies in limited-angle tomosynthesis and thus assist the clinician performing an image-guided treatment. We demonstrate the method’s success in capturing patients’ rigid motions with subvoxel accuracy with noise-added projection images of head and neck CTs.
Chen-Rui Chou, C. Brandon Frederick, Sha X. Chang, Stephen M. Pizer

### Image and Video Region Saliency Based on Space and Motion

Abstract
This paper proposes a new bottom-up paradigm for detecting visual saliency in images and videos, which is based on scale space analysis of the log amplitude spectrum of natural images and videos. A salient region is assumed to be any region exhibiting a distinct pattern whose intensity, color, texture and motion is different from the rest of the image. Thus patterns which appear frequently as well as uniform regions are suppressed to produce salient region pop-out. We show that the convolution of the image log amplitude spectrum with a low-pass Gaussian kernel (at the proper scale) is equivalent to such an image saliency detector. A saliency map can then be obtained by reconstructing the 2-D signal using the original phase spectrum and an appropriately filtered log amplitude spectrum to produce pop-out. The optimal scale for each image feature channel (intensity, color, motion) is determined by minimizing the entropy of its saliency map. This produces four maps which are then fused by a weighted linear combination. Significantly, the approach does not require the setting of any parameters. We demonstrate experimentally that the proposed model has the ability to highlight small and large salient regions and to inhibit repeating patterns in both images and videos.
Jian Li, Martin Levine, Xiangjing An, Zhenping Sun, Hangen He

### Generalized PCA via the Backward Stepwise Approach in Image Analysis

Abstract
Principal component analysis (PCA) for various types of image data is analyzed in terms of the forward and backward stepwise viewpoints. In the traditional forward view, PCA and approximating subspaces are constructed from lower dimension to higher dimension. The backward approach builds PCA in the reverse order from higher dimension to lower dimension.We see that for manifold data the backward view gives much more natural and accessible generalizations of PCA. As a backward stepwise approach, composite Principal Nested Spheres, which generalizes PCA, is proposed. In an example describing the motion of the lung based on CT images, we show that composite Principal Nested Spheres captures landmark data more succinctly than forward PCA methods.
Sungkyu Jung, Xiaoxiao Liu, J. S. Marron, Stephen M. Pizer

### Performance of MRF-Based Stereo Algorithms for Cluttered Scenes

Abstract
This paper evaluates the performance of different Markov Random Field (MRF) based stereo algorithms for cluttered scenes. These scenes are generated by randomly placing objects within a 3D volume. The scenes, which model natural cluttered scenes such as forests or bushes, contain many depth discontinuities and monocularly visible pixels. Widely used benchmark datasets do not contain stereo pairs with dense clutter, so we address how well existing stereo algorithms perform for such scenes. We use Expansion, Swap, Max Product Belief Propagation (BPM), Sequential Tree Reweighted Message Passing (TRW-S) and Sequential Belief Propagation (BP-S), all with different forms of data and smoothness terms. The results are compared with the ground truth disparity and energy.We found Expansion, TRW-S, and BP-M with the Potts model to work well for most scenes, in that the correct binocular correspondence is found for most points that are binocularly visible. We also found that the energy for the ground truth is much larger than what is found by the optimizers. This shows that there is room for improving the model for cluttered scenes.
Fahim Mannan, Michael Langer

### Medial Spheres for Shape Approximation

Abstract
We study the problem of approximating a solid with a union of overlapping spheres. We introduce a method based on medial spheres which, when compared to a state-of-the-art approach, offers more than an order of magnitude speed-up and achieves a tighter volumetric approximation of the original mesh, while using fewer spheres. The spheres generated by our method are internal to the object, which permits an exact error analysis and comparison with other sphere approximations. We demonstrate that a tight bounding volume hierarchy of our set of spheres may be constructed using rectangle-swept spheres as bounding volumes. Further, once our spheres are dilated, we show that this hierarchy generally offers superior performance in approximate separation distance tests.
Svetlana Stolpner, Paul Kry, Kaleem Siddiqi

### A Heuristic Algorithm for Slicing in the Rapid Freeze Prototyping of Sculptured Bodies

Abstract
The subject of this paper is a heuristic slicing algorithm for converting STL or PLY CAD data into boundary and fill paths for rapid freeze prototyping (RFP). The algorithm, developed for one commercial robotic system, can also be used to produce toolpaths for other rapid prototyping systems. The algorithm entails five steps: (a) geometry data and other control parameters are imported; (b) the geometry is sliced at several equidistant heights to form bounding paths; (c) contours for the scaffolding material are computed; (d) part and scaffolding paths are buffered in or out to account for deposition path width; and (e) fill paths are computed. A STL file of a 300 mm-high statue of James McGill is used as an example part for demonstrating the capabilities of the algorithm.
Eric Barnett, Jorge Angeles, Damiano Pasini, Pieter Sijpkes

### Robust Design of 2nd Order Terminal ILC Using μ-Analysis and a Genetic Algorithm Approach

Abstract
In the thermoforming industry, the heater temperature setpoints can be automatically tuned with Terminal Iterative Learning Control (TILC). This cycle-to-cycle control is used to adjust the heater temperature setpoints so that the temperature profile at the surface of the plastic sheet converges to the desired temperature. The robustness of a closed-loop system with this TILC algorithm is measured using the μ-analysis approach. A Genetic Algorithm (GA) is used to find the 2nd order TILC controller parameters giving the most robust closed-loop system.
Guy Gauthier, Mathieu Beauchemin-Turcotte, Benoit Boulet

### Development of an Anthropomorphic Saxophone-Playing Robot

Abstract
Our research aims to develop an anthropomorphic saxophone-playing robot; as an approach to understand the human motor control from an engineering point of view. In this paper, we present theWaseda Saxophonist Robot No. 2 (WAS-2) which is composed of 22 degrees of freedom (DOF). In particular, he functioning of the lips, fingers, tongue, oral cavity and lungs have been mechanically simulated to enable WAS-2 to play an alto saxophone. Furthermore, in order to ensure the accuracy of the air pressure control, a feed-forward control system with dead time compensation has been implemented.A set of experimentswere carried out to verify the effectiveness of the proposed system. From the experimental results, the range of sound pressure was increased and the air pressure control was improved.
Jorge Solis, Atsuo Takanishi, Kunimatsu Hashimoto

### Human Safety Algorithms for a Parallel Cable-Driven Haptic Interface

Abstract
A parallel cable-driven haptic interface is designed to allow interaction with any type of virtual object. This paper presents and analyzes computational methods for addressing the issues regarding human safety and control reliability using such an interface, thereby ensuring safe operations inside the virtual world. Four strategies are explored: sensor reliability, mechanical interference management, workspace management and human-robot interaction. This paper focuses mainly on the sensors’ reliability and workspace management algorithms for a parallel cable-driven haptic interface that imposes special requirements on the control architecture design. One challenging task is to develop efficient computational algorithms for hard real-time processes included in haptic display applications which improve safety without compromising performance.
Martin J. -D. Otis, Sylvain Comtois, Denis Laurendeau, Clément Gosselin

### Hybrid Stabilizing Control for the Spatial Double Inverted Pendulum

Abstract
The spatial double inverted pendulum actuated at the hip, but not at the foot, may be considered to be a model of standing creatures and robots. Moving inspace, as opposed to in-plane, poses new control problems which, for the most part, are still open. In this paper, a hybrid approach where an energy-shaping, passivitybased swing-up controller hands off the control to a linear-quadratic-regulator in the vicinity of the unstable upright equilibrium is proposed. A direct approach and a pre-compensated approach are described, discussed, and illustrated by means of examples in simulation.
Xinjilefu, Vincent Hayward, Hannah Michalska

### Closed-Loop Control of Plasma Osmolality

Abstract
In this paper, a closed-loop system to regulate plasma osmolality in patients with central diabetes insipidus is investigated. Using model identification techniques, we obtained a 3 rd -order LTI model of the renal/body fluid system from an 11th-order nonlinear system. A Smith Predictor and an $${\mathcal H}_\infty$$ controller were developed. The effectiveness of the controller to reject a step disturbance in the plasma osmolality is examined. This paper shows the potential use of control theory in the context of central diabetes insipidus.
Kamel Zaarouri, Ahmad Haidar, Benoit Boulet

### Cooperative Exploration, Localization, and Visual Map Construction

Abstract
We examine the problem of learning a visual map of the environment based on discrete landmarks. While making this map we seek to maintain an accurate pose estimate for the mapping robots. Our approach is based on using a team of at least two (heterogeneous) mobile robots in a simple collaborative scheme. In many mapping contexts, a robot moves about the environment collecting data (images, in particular) which are later used to assemble a map; we view the map construction as both a knowledge acquisition and a training process. Without reference to the environment, as a robot collects training images, its position estimate accumulates errors, thus corrupting its estimate of the positions from which observations are taken. We address this problem by deploying a second robot to observe the first one as it explores, thereby establishing a virtual tether, and enabling an accurate estimate of the robot’s position while it constructs the map. We refer to this process as cooperative localization. The images collected during this process are assembled into a representation that allows vision-based position estimation from a single image at a later time. In addition to developing a formalism and concept, we validate our approach experimentally and present quantitative results demonstrating the performance of the method in over 90 trials.
Ioannis M. Rekleitis, Robert Sim, Gregory Dudek

### Sliding-Mode Velocity and Yaw Control of a 4WD Skid-Steering Mobile Robot

Abstract
The subject of this paper is the design and implementation of a robust dynamic feedback controller, based on the dynamic model of the four-wheel skidsteering RobuFAST A robot, undergoing high-speed turns. The control inputs are respectively the linear velocity and the yaw angle. The main objective of this paper is to formulate a sliding mode controller, robust enough to obviate the knowledge of the forces within the wheel-soil interaction, in the presence of sliding phenomena and ground-level fluctuations. Finally, experiments are conduced on a slippery ground to ascertain the efficiency of the control law.
Eric Lucet, Christophe Grand, Philippe Bidaud

### On the Design and Validation of an Intelligent Powered Wheelchair: Lessons from the SmartWheeler Project

Abstract
New-generation, intelligent, powered wheelchairs promise to increase the mobility and freedom of individuals with serious chronic mobility impairments. And while rapid progress continues to be made in terms of the engineering capabilities of robotic wheelchairs, many projects fall short of the target in terms of ease of use, conviviality, and robustness. This paper describes the SmartWheeler, a multifunctional intelligent wheelchair, which leverages state-of-the-art probabilistic techniques for both autonomous navigation and user interaction modeling, to provide a novel robust solution to the problem of assistive mobility. We also discuss the use of standardized evaluation in the development and testing of such technology.
Joelle Pineau, Amin Atrash, Robert Kaplow, Julien Villemure

### Devon Island as a Proving Ground for Planetary Rovers

Abstract
The future of space exploration will be increasingly surface-based and extended-duration. Planetary rovers, both manned and autonomous, will play vital roles in transporting instruments, astronauts, and equipment across rugged and unfamiliar surfaces. To enable this vision, it is advisable to deploy prototype rover vehicles in analog environments on Earth, in order to learn how best to use these tools. Devon Island, in the Canadian High Arctic, has been used as a proving ground for planetary rovers, due to its vast scale, variety of topography/geology, challenging lighting, lack of vegetation, existing infrastructure at the well-established Haughton- Mars Project Research Station, and wealth of interesting scientific mission objectives. In this paper we review the suitability of using Devon Island for the continued testing of planetary rovers; several examples of previously conducted tests are provided. We conclude that despite the typical logistical challenges associated with remote field work, Devon Island should be considered a strong candidate for ongoing rover field deployments.
Timothy D. Barfoot, Paul T. Furgale, Braden E. Stenning, Patrick J. F. Carle, John P. Enright, Pascal Lee

### Leader-Follower Cucker-Smale Type Flocking Synthesized via Mean Field Stochastic Control Theory

Abstract
In this paper we study a controlled Leader-Follower (L-F) flocking model (where the state of each agent consists of both its position and its controlled velocity) by use of the Mean Field (MF) Stochastic Control framework. We formulate the large population stochastic L-F flocking problem as a dynamic game problem. In this model, the agents have similar dynamics and are coupled via their nonlinear individual cost functions which are based on the uncontrolled Cucker and Smale (C-S) flocking algorithm. The cost of each leader is based on a trade-off between moving its velocity toward a certain reference velocity and a C-S type weighted average of all the leaders’ velocities. Followers react by tracking the C-S type weighted average of the velocities of all the leaders and followers. For this nonlinear dynamic game problem we derive two sets of coupled deterministic equations for both leaders and followers approximating the stochastic model in large population. Subject to the existence of unique solutions to these systems of equations we show that: (i) the set of MF control laws for the leaders possesses an $$\displaystyle\epsilon_N$$-Nash equilibrium property with respect to all other leaders, (ii) the set of MF control laws for the followers is almost surely $$\displaystyle \epsilon_N$$-Nash equilibrium with respect to all the other agents (leaders and followers), and (iii) $$\displaystyle \epsilon_N \rightarrow 0$$ as the system’s population size, $$\displaystyle N$$, goes to infinity. Furthermore, we analyze the MF system of equations for the leaders and followers with the linear coupling cost functions to retrieve similar MF equation systems in Linear-Quadratic-Gaussian (LQG) dynamic game problems.
Mojtaba Nourian, Peter E. Caines, Roland P. Malhamé, Minyi Huang

### Dynamic Locomotion with a Wheeled-Legged Quadruped Robot

Abstract
In this paper, we present an overview of the work carried out in the Mechatronic Locomotion Laboratory at McGill University on a quadruped robotic platform, PAW. This robot features four springy legs with rotary actuation at the hips and driven wheels mounted at the distal ends of the legs. The robot was designed to explore hybrid modes of locomotion, where it makes use of both wheels and legs to achieve novel behaviors. As well, the robot’s simple construction allows PAW to exploit the dynamics of a mass-spring system to achieve gaits such as bounding, galloping and jumping. We begin by describing the basic design of the robot and its sensing capabilities. We then discuss several modes of locomotion that have been developed on the robot over the past five years. Specifically, results are presented for inclined turning and sprawled breaking achieved with the robot, as part of exploiting the leg capability in the rolling behaviors. This is followed by the presentation of the bounding gait implemented on the robot: the basic version and the intelligent version. The most recent addition to the robot’s repertoire of behaviors is a dynamic jump. We will discuss the main stages of the jumping maneuver and present the results of the jump. The paper concludes with a summary and discussion of our future goals for PAW.
I. Sharf

### Underactuated Cable-Driven Robots: Machine, Control and Suspended Bodies

Abstract
This paper introduces a novel family of robots that consist of cablesuspended bodies whose motion is not fully constrained. The robots are underactuated and exhibit a pendulum-like behavior. Based on the dynamicmodel, a technique is proposed to allow the planning of point-to-point trajectories with zero-velocity landing by making the robot swing itself similarly to children on playground swings. A three-degree-of-freedom planar robot is studied as an example and a prototype of the robot and its controller are presented. Experimental results clearly demonstrate the effectiveness of the proposed control technique. Underactuated cable-suspended robots have the potential to lead to low-cost solutions in applications that require the performance of point-to-point trajectories in a large workspace.
Clément Gosselin, Simon Lefrançois, Nathaniel Zoso

### Computing the Rigid-Body Acceleration Field from Nine Accelerometer Measurements

Abstract
Among other applications, accelerometer arrays have been used in crashworthiness studies to measure the acceleration field of the head of a dummy subjected to an impact. In previous analyzes, the centripetal component of the rigid-body acceleration was estimated linearly from point-acceleration measurements, that is, by considering the quadratic products of the angular-velocity components as independent variables. Although this assumption greatly simplifies the estimation process, it has two drawbacks: (i) it raises the minimum number of accelerometers from nine to 12, and, when more than the minimum number of accelerometers are available, (ii) it ignores some of the constraints between the kinematic parameters, which would otherwise help in filtering the data. In this paper, we solve the nonlinear problem of estimating the rigid-body acceleration field from point-acceleration measurements. To this end, we partition the associated system of equations into two subsystems, one linear, the other nonlinear. The nonlinear subsystem of three equations in three unknowns represents three quadrics in 3D space, whose intersection contains the rigid-body angular velocity. This intersection is computed using a readily-available technique, which yields eight closed-form solutions to the problem. A criterion for the selection of the proper solution is given. The proposed nonlinear method should prove useful when the number of accelerometers is limited, or to improve the robustness of an array of 12 or more accelerometers by taking into account the constraints between the quadratic terms of the angular velocity.
Philippe Cardou

### Singularity Analysis of a Six-Dof Parallel Manipulator Using Grassmann-Cayley Algebra and Gröbner Bases

Abstract
The subject of this paper deals with the singularity analysis of a sixdof three-legged parallel manipulator for force-feedback interface. To this end, a geometric condition for the manipulator singularities is obtained by means of Grassmann-Cayley algebra; the parallel singularities of the manipulator are computed using Jacobian and Gröbner basis. As a result, the algebraic relations of the singularities satisfied by the orientation variables are reported. Finally, the parallel singularities of the manipulator are plotted in its orientation workspace.
Stéphane Caro, Guillaume Moroz, Thibault Gayral, Damien Chablat, Chao Chen
Weitere Informationen


text:
# Applications of linear systems

#### Everything You Need in One Place

Homework problems? Exam preparation? Trying to grasp a concept or just brushing up the basics? Our extensive help & practice library have got you covered.

#### Learn and Practice With Ease

Our proven video lessons ease you through problems quickly, and you get tonnes of friendly practice on questions that trip students up on tests and finals.

#### Instant and Unlimited Help

Our personalized learning platform enables you to instantly find the exact walkthrough to your specific type of question. Activate unlimited help now!

##### Intros
###### Lessons
1. Applications of Linear Systems Overview:
2. Linear Systems in Economics
• A simple economy with sectors.
• Solving the equilibrium prices
3. Linear Systems with Chemical Equations
• Balancing chemical equations
• Solving for coefficients to balance
4. Linear Systems with Network Flow
• Nodes
• Finding the general solution of the network flow
##### Examples
###### Lessons
1. Economics with Resources
Assume that the economy has 3 sectors: Manufacturing, Services, and Extraction. Manufacturing sells 50% of its output to Services, and 50% to Extraction. Services sells 30% of its output to Manufacturing, 60% to extraction, and keeps the rest. Extraction sells 80% of its output to manufacturing, 10% to services, and keeps the rest. Find a set of equilibrium prices for when the extraction output is 80 units.
1. Balancing a Chemical Equation
Balance the following chemical equation using the vector equations
$Na_3 PO_4+MgCl_2$$NaCl+Mg_3(PO_4)_2$
1. Finding the General Flow Pattern
Find the general solution of the network flow. Assuming that all flows are non-negative, what is the minimum value of $x_1$ and $x_2$?

## Applications of linear systems

So far through our linear algebra course we have been looking into the methodology required while solving systems of linear equations with the use of notation of matrices. For the lesson of today, we will be talking about cases in which applying systems of linear equations is of benefit to resolve problems from varied distinct areas in life which, in our minds, we usually do not relate them much to the use of linear algebra.

But before we can go ahead and check into different applications of systems of linear equations in real life, we need to know how to solve a system of linear equations itself. In other words, let us take a quick review on the methods shown in the past few lessons.

#### How to solve systems of linear equations

For problems solving systems of linear equations in linear algebra, we usually use the method of Gaussian elimination (also named row reduction) to find the values of the variables involved in the system after we have converted such system into a matrix equation of augmented form.

If you remember from our lesson on solving a linear system with matrices using Gaussian elimination, the operations which can be applied to the rows of an augmented matrix in order to reduce it to an echelon form are:
1. Interchanging two rows
2. Multiplying a row by a constant (any constant which is not zero)
3. Adding a row to another row

One can also make combinations of these operations, and the resulting matrix, will be an equivalent simplified matrix which will allow us to see directly the value of each variable in the system. This final matrix is what we call the reduced row echelon form of the initial augmented matrix coming from a system of linear equations.

In our lesson on row reduction and echelon forms we saw the algorithm that needs to be followed to in order to arrive to the reduced echelon form of a matrix:

1. Look for the leftmost non-zero column. This is our pivot column
2. Find a non-zero entry in the pivot column. This is our pivot position. It should be at the very top of the pivot column.
3. Use matrix row reduction to make all the entries below the pivot equal to zero.
4. Ignore the row with the pivot and now operate on the next one to the right. Repeat Step 1-3 again and again until you have worked through all of the columns.
5. Find your rightmost pivot. Row reduce it until is equal to 1.
6. Make all the entries above this pivot equal to 0.
7. Repeat steps 5 and 6 for all the pivots in the reduced matrix.

Once the matrix in reduced echelon form, each row of such matrix will provide the final expression (or value) for the variable corresponding to each column on the matrix.

Such methods have been extensively explained in the past lessons, so we recommend that if you still have a few doubts, you can go back and have a review (as a suggestion of the lessons you will be required to know for this one, you can go ahead and check all of the links we have provided through this reading).

#### Applications of systems of linear equations

On this section we will be looking at real-life problems involving linear algebra. The three types of real-life applications we will be looking at are:
1. Linear systems in Economics
2. Linear systems with Chemical Equations
3. Linear systems with Network Flow

Let us then jump in directly into solving examples of each area, remember: Our goal is to make all of these questions into a matrix and then solve.

#### 1. $\quad$ Linear systems in Economics

A country's economy is usually divided into sectors, a few that come to mind might be: manufacturing, services, energy and fuel, transportation, and other public or private sectors. Each of these sectors has a total output (which we will measure in dollars) for one year. This total output is the total amount of earnings for a year and is represented by the letter p, this particular revenue is then used, some or all of it may be invested by exchanging or buying from the other sectors in the economy.

For all of this trade, there must exist an equilibrium price where each sector has:

Income = expenses (expenditures)

Which means that the total amount of income in a sector must be equal to the total amount of expenses, or in other words, the total amount of income is the most that a sector can spend either buying, trading, or even keeping its own capital.
In economics, we can use linear algebra to determine the equilibrium price of outputs for each sector, take a look at the two examples below:

#### Example 1

Assume that the economy has 2 sectors: Transportation and Manufacturing.
• Transportation sells 60% of its output to Manufacturing and keeps the rest of the output.
• Manufacturing sells 80% of its output to Transportation and keeps the rest.
Create an exchange table for this economy, and find the set of equilibrium prices.

On this exchange table, what you can see in the first two columns are the total outputs measured in dollars for one year for each of the two economic sectors given, in other words, this was their income for their year and how they put it out for others to buy. Notice the quantities have been rewritten down from the percentages provided to their equivalency in decimal notation. The rows for the table represent the expense each sector went through.

Since total output is usually defined as $P$, we call the first column $P_{t}$ (for total output from transportation) and the second $P_{m}$ (for total output from manufacturing) and following the principle of income = expenses we can form the next equations:

0.4$P_{t} \, + \,$0.8$P_{m} = P_{t}$
0.6$P_{t} \, + \,$0.2$P_{m} = P_{m}$

Where the left hand side of each equation represents the income and the right hand side represents the expenses of each economic sector.
Now, since we will be solving this system of equations through matrix notation, we need to convert the system to an augmented matrix, but before we can do that, we need to pass all of the unknown variables ($P_{t}$ and $P_{m}$) to the left side of the equations:

0.4$P_{t} \, + \,$0.8$P_{m} = P_{t} \,$$\, -$0.6$P_{t} \, + \,$0.8$P_{m} = 0$
0.6$P_{t} \, + \,$0.2$P_{m} = P_{m} \,$$\, -$0.6$P_{t} \, - \,$0.8$P_{m} = 0$

We construct the augmented matrix and row reduce it to solve for the unknown variables:

As you can see, $P_{m}$ is a free variable since there is no corresponding pivot for it on the augmented matrix, and so out solutions in parametric form are:

The set of equilibrium prices can be obtained by setting the free variable $P_{m} =$1, therefore:

#### Example 2

Assume that the economy has 3 sectors: Manufacturing, Services, and Extraction.
• Manufacturing sells 50% of its output to Services, and 50% to Extraction.
• Services sells 30% of its output to Manufacturing, 60% to extraction, and keeps the rest.
• Extraction sells 80% of its output to manufacturing, 10% to services, and keeps the rest.
Find a set of equilibrium prices for when the extraction output is 80 units.

Following the same methodology we used in our last problem, we obtain the system of linear equations from the exchange table and move all of the unknowns variables to the left hand side.

0.3$P_{s} \, + \,$0.8$P_{\epsilon} = P_{m} \,$$\, - \, P_{m} \, +\,$0.3$P_{s} \, + \,$0.8$P_{\epsilon} = 0$

0.5$P_{m} \, + \,$0.1$P_{s} \, + \,$0.1$P_{\epsilon} = P_{s} \,$$\,$0.5$P_{m} \, - \,$0.9$P_{s} \, + \,$0.1$P_{\epsilon} = 0$

0.5$P_{m} \, + \,$0.6$P_{s} \, + \,$0.1$P_{\epsilon} = P_{\epsilon} \,$$\,$0.5$P_{m} \, + \,$0.6$P_{s} \, - \,$0.9$P_{\epsilon} = 0$

We construct the augmented matrix and row reduce it to solve for the unknown variables:

As you can see, $P_{\epsilon}$ is a free variable since there is no corresponding pivot for it on the augmented matrix, and so out solutions in parametric form are:

For this particular problem, it is asked to find the set of equilibrium prices when $P_{\epsilon} = 80$ and so:

#### 2. $\quad$ Linear systems with Chemical Equations

In Chemistry, we can use linear algebra to balance chemical equations. Take a look at the next exercise to see the process:

#### Example 3

Having the next chemical reaction equation

$N_{2} + H_{2} \,$$\, NH_{3}$

How do we balance a chemical equation? We use coefficients! The coefficients will allow us to find out the quantity needed of the molecules in the left hand side of the reaction, that would proportionally produce a certain amount of the compound in the right hand side of the reaction. Truly if you think about it, a chemical reaction equation can be looked as an algebraic expression too, where the variables would be the name of the elements, or molecules of compounds you are using throughout the reaction. In here,we have inputted coefficients inside parenthesis to balance equation 10:

$(x_{1}) + N_{2} \, + \, (x_{2}) + H_{2} \,$$\, (x_{3}) + NH_{3}$

How do we create a matrix and solve for the variables? This can be a little tricky, but for each element, element molecule or compound found in the chemical reaction, we construct a vector which lists the number of atoms of each reactant. Look how this is done for the reaction above:

Such column vectors can then be used to create the proper matrix to find the correct values for $x_{1}$, $x_{2}$ and $x_{3}$ which will balance the reaction equation. Thus, having the vectors above we obtain:

Notice how in the very right hand side we have a vector equation similar to those seen on our lesson about linear combinations and vector equations. We know that we can convert such equation into an augmented matrix, which we can later solve using the three types of matrix row operations through Gaussian elimination. But before we do that, we have to put all of the variables in the left hand side of the equation, so out vector equation is now:

And so, the augmented matrix looks as follows:

Using row reduction to obtain the value for each of the unknown variables corresponding to the matrix we obtain:

Where we can clearly see that $x_{3}$ is a free variable. Thus the solutions in parametric form are:

Now, there is something important to consider in here: these cannot be our final solutions because these variables represent the coefficients of reactants in a chemical reaction equation, and thus, they MUST be full numbers (you cannot divide either atoms or molecules without changing their properties, and so, these need to be full numbers). And so, since $x_{3}$ is a free variable, we can set it up to any value we want without changing the proportion within the variables. And so, we set $x_{3} = 2$ since is the smallest value it can have to produce full numbers as values for the rest of the variables. Thus:

So our balanced chemical reaction equation is:

$N_{2} \, + \, 3H_{2} \,$$\, 2NH_{3}$

In summary, we balanced by counting the number of elements in a compound, and turning each coefficient as a variable to solve. Let us work through another example of this below.

#### Example 4

Having the next chemical reaction equation:

$Na_{3} PO_{4} \, + \, MgCl_{2} \;$$\; NaCl \, + \, Mg_{3} (PO_{4})_{2}$

We input the unknown coefficients to be solved for:

$(x_{1})Na_{3} PO_{4} \, + \, (x_{2})MgCl_{2} \;$$\; (x_{3})NaCl \, + \, (x_{4})Mg_{3} (PO_{4})_{2}$

In order to write down the column vectors representing the number of atoms from each element involved, we first have to identify all of the type of elements that appear in the reaction equation. We have written the list as a column vector (to serve as template for each reactant vector) as is shown below:

And so, the column vector for each reactant is:

Putting all of these vectors into a column vector equation we obtain the expressions below.

And transcribing these vector equations into an augmented matrix we obtain:

Now let us row reduce this matrix into its reduced echelon form so we can find the value for each unknown:

And so our final solution in parametric form can be seen as:

Notice that $x_{4}$ is a free variable, and so, we can set it up to any value we want! The simplest value to choose for the free variable is to just make it equal to one:

And the final chemical reaction equation is:

2$Na_{3}PO_{4} \, + \, 3MgCl_{2} \,$$\,$6$NaCl \, + \, Mg_{3}(PO_{4})_{2}$

#### 3. $\quad$ Linear systems with Network Flow

Network flow refers to a connected system, named the network, which has elements going in and going out (thus the term flow). A network in itself has a set of points called nodes which are the connections in a set of branches. In this way, each branch has a flow direction pointing to a node, and each node has flow in and flow out, meaning the elements traveling through the network will be passing through each node and the same amount of elements that arrive to each of them are the same ones that get out and go away (there are no losses).
And so, we can use linear algebra to study the flow of some quantity through a network. Just keep in mind the rule for the nodes:

Flow in = Flow out

#### Example 5

Find the general solution of the network flow. Assuming that all flows are non negative, what is the minimum value of $x_{1}$ and $x_{2}$?

On this example we have three nodes, in order to obtain the equations related to the flow at each of them we first construct the next table with the elements that will be needed:

50$\, + \, x_{3} = x_{1} \, + \,$30$\,$$\, x_{1} \, - \, x_{3} = \text(20)$
$x_{1} = x_{2} \,$$\, x_{1} \, - \, x_{2} = \text(0)$
20$\, + \, x_{2} = x_{3} \, + \,$40$\,$$\, x_{2} \, - \, x_{3} = \text(20)$

Above we have written down the equations coming from the table, and we have put all of the unknown variables to the left hand side of each equation so we can convert the system into the next augmented matrix:

Row reducing the equation in order to find the values for $x_{1}$, $x_{2}$ and $x_{3}$:

And so we have that the values of $x_{1}$ and $x_{2}$ are:

$x_{1} = x_{3} \, + \,$20
$x_{2} = x_{3} \, + \,$20
$x_{3} = x_{3}$

In order to obtain their minimum possible value we can set the free variable $x_{3}$ to our most convenient value for that purpose, in other words, let us choose $x_{3}$!
For that, remember flow cannot have negative elements going into a node, but we can have zero elements going in (basically nothing going in, if you think about it, a negative value would actually mean the elements are going out and since these elements are in the other side of the equation they cannot be taken as negatives). And so, the smallest possible value of $x_{3}$ is zero, therefore, the minimum values of $x_{1}$ and $x_{2}$ are:

$x_{1} =$20$\,$ and $\, x_{2} =$20

And that is our final answer!

***

For even more examples on the applications of systems of equations we recommend you to take a look at these algebra notes, remember that as long as you have a linear system, you can convert it into matrix equations to solve. Also, a very interesting and modern application of linear systems can be studied on this innovating scientific paper published a few years ago about solving systems of linear equations on a quantum computer note how the possibilities are endless when knowing math!

We hope you have enjoyed the lesson of today, see you in the next one!
We will be looking at real-life problems involving linear algebra. The three types of real-life applications we will be looking at are:
1. Linear systems in Economics
2. Linear systems with Chemical Equations
3. Linear systems with Network Flow

In economics, we can use linear algebra to determine the equilibrium price of outputs for each sector. Note that in order to get the equilibrium price, we need to set

Income = expenses (expenditures)

In Chemistry, we can use linear algebra to balance chemical equations like:
$N_2+H_2$$NH_3$

We do so by counting the number of elements in a compound, and turning each coefficient as a variable to solve.

We can also use linear algebra to study the flow of some quantity through a network. Make sure that for each node:
Flow in = Flow out

Our goal is to make all of these questions into matrix, and then solve.


text:
# Tag Info

## Hot answers tagged classical-mechanics

3

"but how can you have a "basis" that changes at every point?" This is really the root of your problem. Mathematically (and physically) speaking, such a basis works fine. You just have a (hopefully temporary) conceptual problem. Maybe try thinking of it this way: How does $\hat{x}$ know to point "to the right" in cartesian coordinates, at an arbitrary ...

2

It is a Taylor expansion. You might be a little freaked out because they are treating $L$ as a function of $v^2$, but that doesn't matter, consider $$L(x + \delta) \sim L(x) + \frac{\partial L}{\partial x} \delta + O(\delta^2)$$ but take $x=v^2$ and $\delta = 2 \boldsymbol{v} \cdot \boldsymbol{\epsilon} + \epsilon^2$, \begin{align*} L(v'^2) &= ... 2 Symmetry of potential alone is not enough to guarantee a symmetric orbit. The initial and boundary conditions must also be symmetric. Also, for non-linear systems, numerical treatment has to be sufficiently accurate. 1 In case anyone is interested I'll post here what I learnt. If anyone has any corrections or comments please let me know. The thing that I was missing was that the metric makes the kinetic energy well defined, i.e. independent of coordinates. Working in \mathbb{R}^2 with standard coordinates (x^1,x^2) we have the induced coordinates (x^1,x^2,v^1,v^2) ... 1 The force that each of the pistons can drive with is given byF=\frac14 \pi d^2 P$$How much lift that produces depends on the exact geometry of the table and in general will be a function of height. In essence if the table moves x_1 when the pistons move x_2 the force will be$$F_{table}=2F_{piston}\frac{x_2}{x_1}

1

It seems like a very arbitrary question. It would be much easier if you could just elaborate on one given "specific" and well defined scenario, that you wish to solve, then one can help. From which then you would analogously try to solve other similar scenarios. From what you've asked thus far, your starting point should be Conservation of momentum. Since ...

1

The answer is quite simple. You can't see it because you've forgotten that you make an unphysical simplification when considering "tied to an immovable wall" type situations. What's unphysical about the situation is quite simple : there's no such thing as an immovable wall. Let's say the rocket is tied to the earth. To say where the lost chemical potential ...

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


text:
# Cutpoints in a maze

A maze is given as a matrix of 0s (walls) and 1s (walkable space) in any convenient format. Each cell is considered connected to its 4 (or fewer) orthogonal neighbours. A connected component is a set of walkable cells all transitively connected to each other. Your task is to identify the cutpoints - walkable cells which, if turned into walls, would change the number of connected components. Output a boolean matrix with 1-s only at those locations. The goal is to do it in the fewest bytes of code.

The input matrix will consist of at least 3 rows and 3 columns. At least one of its cells will be a wall and at least one will be walkable. Your function or program must be able to process any of the examples below in under a minute on TIO (or on your own computer, if the language is not supported by TIO).

in:
11101001
11011101
00000001
11101111
11110101
00011111
10110001
11111111
out:
01000000
00001001
00000001
00000101
00110000
00010000
00000000
11100000

in:
1111111111111111
1000000000000001
1111111111111101
0000000000000101
1111111111110101
1000000000010101
1011111111010101
1010000001010101
1010111101010101
1010101111010101
1010100000010101
1010111111110101
1010000000000101
1011111111111101
1000000000000001
1111111111111111
out:
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000

in:
1011010001111010
1111111011101101
1110010101001011
1111001110010010
1111010000101001
0111101001000101
0011100111110010
1001110011111110
0101000011100011
1110110101001110
0010100111000110
1000110111011010
0100101000100101
0001010101100011
1001010000111101
1000111011000010
out:
0000000000111010
1011110001001000
0000000000000011
0000000100010000
0000010000101000
0000001000000100
0000000011000000
1001100000011110
0000000001000010
0110100001000110
0000100101000010
1000100000000000
0100001000000100
0000000100100001
0000010000111000
0000010000000010

• so, find all bridges in all subgraphs – HyperNeutrino Mar 7 '18 at 21:27
• I think that the challenge would benefit from a step-by-step example for a smaller matrix. – Mr. Xcoder Mar 7 '18 at 21:28
• @HyperNeutrino a bridge is something different - it's an edge (not a vertex) whose removal increases the number of connected components – ngn Mar 7 '18 at 21:38
• @HyperNeutrino also, a subgraph is not quite the same as a connected component – ngn Mar 7 '18 at 21:40
• @Notatree You're right. I made a mistake. It's too late to fix it now but I hope it won't spoil the fun. – ngn Mar 8 '18 at 17:55

# Stax, 40 bytes

Çóê↓â.Φ}╞│*w<(♦◙¼ñ£º█¢,Dì♥W4·☺╛gÇÜ♠╗4D┬

Run and debug test cases

This program takes input as a space separated string containing rows. The output is in the same format. Here's the unpacked ascii representation.

{2%{_xi48&GxG=-}_?m}{'1'2|e{"12|21".22RjMJguHgu%

The fundamental operation for counting an island works like this.

1. Replace the first '1' with a '2'.
2. Regex replace '12|21' with '22'.
3. Split on spaces.
4. Transpose matrix.
5. Repeat from 2. until a string is repeated.
6. Repeat from 1. until there is no longer a '1' in the string. The number of repetitions is the number of islands.

.

{               start map block over input string, composed of [ 01]
2%            mod by 2. space and 0 yield 0. 1 yields 1. (a)
{             start conditional block for the 1s.
_           original char from string (b)
xi48&       make copy of input with current character replaced with 0
xG          counts islands in original input (d)
=           are (c) and (d) equal? 0 or 1 (e)
-           b - e; this is 1 iff this character is a bridge
}             end conditional block
_?            execute block if (a) is 1, otherwise use original char from string
m               close block and perform map over input
}               goto target - count islands and return
{               start generator block
'1'2|e        replace the first 1 with a 2
{             start generator block
"12|21".22R replace "12" and "21" with "22"
jMJ         split into rows, transpose, and rejoin with spaces
gu            generate values until any duplicate is encountered
H             keep the last value
gu              generate values until any duplicate is encountered
%               count number of iterations it took

Bonus 44 byte program - this version inputs and outputs using the grid format.

• does it process the second example in under a minute on your computer? – ngn Mar 8 '18 at 12:34
• @ngn: It does all three examples in 41s on this mid-range laptop in Chrome. Also, I just fixed the main link. I accidentally left it set to an older non-working version. – recursive Mar 8 '18 at 14:33

# MATL, 26 bytes

n:"GG0@(,w4&1ZIuz]=~]vGZye

The input is a numerical matrix, using ; as row separator.

### Explanation

n           % Implicit input: matrix. Push number of elements, N
:           % Range: gives [1 2 ... N]
"           % For each k in [1 2 ... N]
GG        %   Push input matrix twice
0@(       %   Write 0 at position k (in column-major order: down, then across).
%   The stack now contains the original matrix and a modified matrix
%   with 0 at position k
,         %   Do twice
w       %     Swap
4       %     Push 4. This specifies 4-element neighbourhood
&1ZI    %     Label each connected component, using the specified
%     neighbourhood. This replaces each 1 in the matrix by a
%     positive integer according to the connected component it
%     belongs to
u       %     Unique: gives a vector of deduplicate elements
z       %     Number of nonzeros. This is the number of connected components
]         %   End
=~        %   Are they different? Gives true of false
]           % End
v           % Concatenate stack into a column vector
GZye        % Reshape (in column-major order) according to size of input matrix.
% Implicit display

# Perl 5, -p0105101969390 89 bytes

Uses b instead of 1 in the input.

Make sure the matrix on STDIN is terminated with a newline

#!/usr/bin/perl -p0
s%b%$_="$z$'";s:|.:/ />s#(\pL)(.{@{-}}|)(?!\1)(\pL)#$&|a.$2.a#se&&y/{c/z />0:seg&/\B/%eg  Try it online! Uses 3 levels of substitution! This 87 byte version is both in input and output format easier to interpret, but is not competing since it uses 3 different characters in the output: #!/usr/bin/perl -0p s%b%$_="$z$'";s:|.:/
/>s#(\w)(.{@{-}}|)(?!\1)(\w)#$&|a.$2.a#se&&y/{c/z />0:seg&/\B/%eg

Try it online!

It's easy to save another byte (the regex s modifier) in both versions by using some different (non-alphanumeric) character as row terminator (instead of newline), but that makes the input quite unreadable again.

# How it works

Consider the substitution

s#(\w)(.{columns}|)(?!1)(\w)#c$2c#s  This will find two letters that are different and next to each other horizontally or vertically and replace them by c. In a maze whose paths consist of entirely the letter b nothing will happen since the letters are the same, but as soon as one of the letters is replaced by another one (e.g. z) that letter and a neighbor will be replaced by c and repeated application is a flood-fill of the connected component with c from seed z. In this case I however don't want a complete flood-fill. I want to fill only one of the arms neighboring z, so after the first step I want the z gone. That already works with the c$2c replacement, but I later want to restart a flood-fill along another arm starting from the same point and I don't know which of the cs was originally z anymore. So instead I use

s#(\w)(.{columns}|)(?!\1)(\w)#$&|a.$2.a#se

b | a is c, b | c is c and z | a is {. So in a maze with paths made up of b and a seed z in the first step b will get replaced by c and z will get replaced by { which is not a letter and does not match \w and so will not cause further fills. The c however will keep a further flood-fill going and one neighbor arm of the seed gets filled. E.g. starting from

  b                      c
b                      c
bbzbb       becomes    bb{bb
b                      b
b                      b

I can then replace all c by some non letter (e.g. -) and replace { by z again to restart the flood-fill:

  -                      -
-                      -
bbzbb       becomes    cc{bb
b                      b
b                      b

and repeat this process until all neighbors of the seed have been converted. If I then once more replace { by z and flood-fill:

  -                      -
-                      -
--z--       stays      --z--
-                      -
-                      -

The z remains behind at the end because there is no neighbor to do a transformation with. That makes clear what happens in the following code fragment:

/\n/ >

Find the first newline. The starting offset is now in @-

s#(\w)(.{@{-}}|)(?!\1)(\w)#$&|a.$2.a#se

The regex discussed above with @{-} as number of columns (since plain @- confuses the perl parser and doesn't properly substitute)

&&

The /\n/ always succeeds and the substitution is true as long as we can still flood-fill. So the part after && is executed if the flood-fill of one arm is done. If not the left side evaluates to an empty string

y/{c/z / > 0

Restart the flood-fill and return 1 if the previous flood-fill did anything. Else return the empty string. This whole piece of code is wrapped inside

s:|.: code :seg

So if this is executed on a starting string $_ with a z at the seed position the piece of code inside will be executed many times mostly returning nothing but a 1 every time a neighbor arm gets flood-filled. Effectively $_ gets destroyed and replaced by as many 1s as there are connected components attached to z. Notice that the loop needs to be executed up to sum of component sizes + number of arms times but that is OK since it will "number of characters including newlines * 2 + 1" times.

The maze gets disconnected if there are no 1's (empty string, an isolated vertex) or if there are more than 1 arms (more than 2 1s). This can be checked using the regex /\B/ (this gives 0 instead of 1 on older perl versions. It's arguable which one is wrong). Unfortunately if it doesn't match this will give an empty string instead of 0. However the s:|.: code :seg was designed to always return an odd number so by doing an & with /\B/ this will give 0 or 1.

All that is left is walking the whole input array and at each walkable position seed with z and count connected arms. That is easily done with:

s%b%$_="$z\$'"; code %eg

The only problem is that in the non-walkable positions the old value is retained. Since we need 0s there that means the original input array must have 0 in the non walkable positions and 0 matches \w in the original substitution and would trigger flood-fills. That's why I use \pL instead (only match letters).

# Java 8, 503489459 455 bytes

int R,C,v[][];m->{int c[][]=new int[R=m.length][C=m[0].length],r[][]=new int[R][C],i=R*C,t,u;for(;i-->0;)c[t=i/C][u=i%C]=m[t][u];for(;++i<R*C;r[t][u]=i(c)!=i(m)?1:0,c[t][u]=m[t][u])c[t=i/C][u=i%C]=0;return r;}int i(int[][]m){int r=0,i=0,t,u;for(v=new int[R][C];i<R*C;)if(m[t=i/C][u=i++%C]>v[t][u]){d(m,t,u);r++;}return r;}void d(int[][]m,int r,int c){v[r][c]=1;for(int k=-3,t,u;k<4;k+=2)if((t=r+k/2)>=0&t<R&(u=c+k%2-k/2)>=0&u<C&&m[t][u]>v[t][u])d(m,t,u);}

-18 bytes thanks to @ceilingcat.

Explanation:

Try it online.

int R,C,                    // Amount of rows/columns on class-level
v[][];                  // Visited-matrix on class-level

m->{                        // Method with int-matrix as both parameter and return-type
int c[][]=new int[R=m.length][C=m[0].length],
//  Create a copy-matrix, and set R and C
r[][]=new int[R][C],  //  Create the result-matrix
i=R*C,                //  Index-integer
t,u;                  //  Temp integers
for(;i-->0;)              //  Loop i over each cell:
c[t=i/C][u=i%C]=m[t][u];//   And copy the values of the input to the copy-matrix
for(;++i<R*C              //  Loop over the cells again:
;                     //    After every iteration:
r[t][u]=i(c)!=i(m)?  //     If the amount of islands in c and m are different
1                   //      Set the current cell in the result-matrix to 1
:                    //     Else:
0,                  //      Set it to 0
c[t][u]=m[t][u])     //     And set the copy-value back again
c[t=i/C][u=i%C]=0;      //   Change the current value in the copy-matrix to 0
return r;}                //  Return the result-matrix

// Separated method to determine the amount of islands in a matrix
int i(int[][]m){
int r=0,                  //  Result-count, starting at 0
i=0,                  //  Index integer
t,u;                  //  Temp integers
for(v=new int[R][C];      //  Reset the visited array
i<R*C;)               //  Loop over the cells
if(m[t=i/C][t=i++%C]    //   If the current cell is a 1,
>v[t][u]){           //   and we haven't visited it yet:
d(m,i,j);             //    Check every direction around this cell
r++;}                 //    And raise the result-counter by 1
return r;}               //  Return the result-counter

// Separated method to check each direction around a cell
void d(int[][]m,int r,int c){
v[r][c]=1;                //  Flag this cell as visited
for(int k=-3,u,t;k<4;k+=2)//  Loop over the four directions:
if((t=r+k/2)>=0&t<R&(u=c+k%2-k/2)>=0&u<C
//   If the cell in the direction is within bounds,
&&m[t][u]            //   and it's a path we can walk,
>v[t][u])          //   and we haven't visited it yet:
d(m,i,j);}            //    Do a recursive call for this cell

# Python 2, 290 bytes

lambda m:[[b([[C and(I,J)!=(i,j)for J,C in e(R)]for I,R in e(m)])!=b(eval(m))for j,c in e(r)]for i,r in e(m)]
def F(m,i,j):
if len(m)>i>=0<=j<len(m[i])>0<m[i][j]:m[i][j]=0;F(m,i,j+1);F(m,i,j-1);F(m,i+1,j);F(m,i-1,j)
b=lambda m:sum(F(m,i,j)or c for i,r in e(m)for j,c in e(r))
e=enumerate

Try it online!

-11 bytes thanks to Rod
-11 bytes thanks to Lynn

• It's shorter to use F(m,i,j) for each element, saving 11 bytes – Rod Mar 7 '18 at 22:07
• for q in((i,j+1),(i,j-1),(i+1,j),(i-1,j)): -> for q in(i,j+1),(i,j-1),(i+1,j),(i-1,j): - rm outer parens – ngn Mar 7 '18 at 22:28
• Since F implicitly returns None, you can use F(m,i,j)or c instead of [F(m,i,j)]and c. – Lynn Mar 7 '18 at 22:54
• Also, and m[i][j] can be >0<m[i][j], and [q[:]for q in m] can be eval(m). – Lynn Mar 7 '18 at 22:58
• @Lynn you mean eval('m')? wouldn't that return the same list instance? – ngn Mar 7 '18 at 23:09

# Wolfram Language (Mathematica), 118 bytes

(r=ReplacePart)[0#,Cases[#~Position~1,p_/;(c=Max@MorphologicalComponents[#,CornerNeighbors->1<0]&)@r[#,p->0]>c@#]->1]&

Try it online!

# Javascript 122 bytes

Input/output as a multiline string.

m=>m.replace(/./g,(v,p,m,n=[...m],f=p=>n[p]==1&&(n[p]=0,v=f(p-1)+f(p+1)+f(p-w)+f(p+w)-1?1:0,1))=>(f(p),v),w=~m.search\n)

For each walkable cell, put a block and try to fill the 4 neighbor cells. If the current cell is not a cut point, then starting from any open neighbor will fill all of them. Else, I will need more than one fill operation to reach all neighbor cells.

Less golfed

m=>{
w = m.search('\n') + 1; // offset to the next row
result = [...m].map( // for each cell
( v, // current value
p  // current position
) => {
n = [...m]; // work on a copy of the input
// recursive fill function from position p
// returns 1 if managed to fill at least 1 cell
fill = (p) => {
if (n[p] == 1)
{
n[p] = 0;
// flag will be > 1 if the fill from the current point found disjointed areas
// flag will be 0 if no area could be filled (isolated cell)
var flag = fill(p+1) + fill(p-1) + fill(p+w) + fill(p-w);
// v is modified repeatedly, during recursion
// but I need the value at top level, when fill returns to original caller
v = flag != 1 ? 1 : 0;
return 1; // at least 1 cell filled
}
else
return 0; // no fill
}
fill(p)
return v // orginal value or modified by fill function
})
}

Test

var F=
m=>m.replace(/./g,(v,p,m,n=[...m],f=p=>n[p]==1&&(n[p]=0,v=f(p-1)+f(p+1)+f(p-w)+f(p+w)-1?1:0,1))=>(f(p),v),w=~m.search\n)

var test=in:
11101001
11011101
00000001
11101111
11110101
00011111
10110001
11111111
out:
01000000
00001001
00000001
00000101
00110000
00010000
00000000
11100000

in:
1111111111111111
1000000000000001
1111111111111101
0000000000000101
1111111111110101
1000000000010101
1011111111010101
1010000001010101
1010111101010101
1010101111010101
1010100000010101
1010111111110101
1010000000000101
1011111111111101
1000000000000001
1111111111111111
out:
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000
0000000000000000

in:
1011010001111010
1111111011101101
1110010101001011
1111001110010010
1111010000101001
0111101001000101
0011100111110010
1001110011111110
0101000011100011
1110110101001110
0010100111000110
1000110111011010
0100101000100101
0001010101100011
1001010000111101
1000111011000010
out:
0000000000111010
1011110001001000
0000000000000011
0000000100010000
0000010000101000
0000001000000100
0000000011000000
1001100000011110
0000000001000010
0110100001000110
0000100101000010
1000100000000000
0100001000000100
0000000100100001
0000010000111000
0000010000000010
.match(/\d[10\n]+\d/g);
for(i = 0; test[2*i]; ++i)
{
input = test[2*i]
check = test[2*i+1]
result = F(input)
ok = check == result
console.log('Test '+ i + ' ' + (ok?'OK':'FAIL'),
'\n'+input, '\n'+result)
}


text:
# How to sample from parameter distribution within specific range

I want to be incorporate dynamic effects in a multilevel model and therefore I want to incorporate the term \rho y_{t-1} in my model. Because of stationarity restrictions \rho has to be on the interval [-1,1].

Therefore I model \rho as \rho = 2*\rho_{raw} -1, with rho_{raw} \in [0,1]. Or in stan code:

parameters{
real<lower=0,upper=1> delta_raw;
}
transformed parameters{
real delta = delta_raw * 2 - 1;
}

Now, I want to be \delta to be in the range [-0.9,0.9]. Can I now just use real<lower=0.05,upper=0.95> delta_raw; in the transformed parameters part? I tried this, but the results of my model are not any different from real<lower=0.05,upper=0.95> delta_raw;. Can someone explain this?

Next to that, I want to model an individual specific \delta_i in my model using the non-centered parameterization approach which would look like this:

parameters {
...
real delta_raw;
real u_delta_raw[Nk];// Nk number of individuals i
real<lower=0> sigma_u_delta
...
}
transformed parameters{
real u_delta[Nk];
for(i in 1:Nk){//number of individuals i
u_delta[i] = sigma_u_delta*u_delta_raw[i];
}

for(k in 1:Nk){//number of individuals i
delta[k] = delta_raw + u_delta[k];
}
}
model {
...
u_delta_raw ~ normal(0, 1);
sigma_u_delta~normal(0,1);
...
}

However, I do not know how to keep \delta_i on the interval [-1,1]. Does someone know how to do this?

This seems needlessly convoluted. Why not just directly use “real<lower=-1.0, upper=1.0> rho” in your parameter declaration?

Because I read in a Stan tutorial that Stan did not support variables on such intervals

Which tutorial was this? I suspect that you have misunderstood, because I have never seen such a limitation documented.

It is in a tutorial written by Andrew Gelman about minimizing the number of cockroach compliants and it says exactly the following: Stan doesn’t implement any densities that have support on $[−1,1]$. We can use variable transformation of a raw variable defined on [0,1][0,1] to to give us a density on $[−1,1]$

But maybe this is already old information. However, do you maybe also know how this works in a multilevel setting mentioned above?

I think that you misunderstood what Gelman meant by “Stan doesn’t implement any densities that have support on [−1,1].” If you look at the section in the Stan Functions Reference on continuous distributions, you indeed won’t find any functions in Stan that define probability densities with support exactly on [-1,1]. However, there is a uniform density, which does have support over the interval [a,b] where a and b are arbitrary (except of course for the condition a < b). Furthermore, that is the prior density that a variable with explicitly specified upper and lower bounds will automatically have.

Thanks for the explanation!

However in my multilevel setting I get initialization errors because I define my \delta_i with <lower = -1, upper = 1> but I get errors because my delta_raw and u_delta[k] do not have such restrictions. Do you maybe know how to handle this?

Either put constraints on delta_raw and u_delta[k] or rewrite your model so that you don’t need delta_raw and u_delta[k].

I’m unsure what purpose delta_raw and u_delta[k] serve. Initially, you seemed to use delta_raw because you appeared to think that you couldn’t set lower to -1.0, but now it seems that delta_raw and u_delta are used for a different reason.

In this case, I am using non-centered parameterization for estimating \delta_i and now I estimate it using \delta_i = \delta_{raw} + u_{\delta}. However, putting constraints on both delta_raw and u_delta[k] does not necessarily mean that delta is also constrained on the given interval, right? (in my case [-1,1]). Rewriting my model not using non-centered parameterization causes a lot of divergent transitions so I have to use non-centered parameterization.

That depends on your choice of constraints for delta_raw and u_delta[k].

Your choices for the priors of u_delta_raw and sigma_u_delta, which can range from (-\infty,\infty), are inconsistent with the goal of a finite range for delta[k].

Could you maybe give an example of constraints that will do the trick in my case or prior distributions which are constrained on the interval [-1,1]?

If you have a = b + c, where b \in [b_l, b_h] and c \in [c_l,c_h], then a \in [b_l + c_l, b_h + c_h], right?


text:
# Chapter 3 - Mass Relationships in Chemical Reactions - Questions & Problems: 3.84

20.96g $H_{2}SO_{4}$

#### Work Step by Step

a. $2NH_{3}(aq)+1H_{2}SO_{4}(aq)$ -> $1(NH_{4})_{2}SO_{4}(aq)$ b. Mass of $NH_{3}$ = $\frac{(20.3g(NH_{4})_{2}SO_{4})\times((NH_{4})_{2}SO_{4})\times(2molNH_{3})\times(17.04molNH_{3})}{(132.17g(NH_{4})_{2}SO_{4})\times(1mol(NH_{4})_{2}SO_{4})\times(1molNH_{3})}$ = 5.23 g $NH_{3}$ Mass of $H_{2}SO_{4}$= $\frac{(20.3g(NH_{4})_{2}SO_{4})\times(1mol(NH_{4})_{2}SO_{4})\times(1mol(NH_{4})_{2}SO_{4})\times(1molH_{2}SO_{4})\times(98.09gH_{2}SO_{4})}{(132.17g(NH_{4})_{2}SO_{4})\times(1mol(NH_{4})_{2}SO_{4})\times(1molH_{2}SO_{4})}$ = 15.07 g 15.07 + 5.89 = 20.96g $H_{2}SO_{4}$

After you claim an answer you’ll have 24 hours to send in a draft. An editor will review the submission and either publish your submission or provide feedback.