text:
Study Aids:

Click the Study Aids tab at the bottom of the book to access your Study Aids (usually practice quizzes and flash cards).

Study Pass:

Study Pass is our latest digital product that lets you take notes, highlight important sections of the text using different colors, create "tags" or labels to filter your notes and highlights, and print so you can study offline. Study Pass also includes interactive study aids, such as flash cards and quizzes.

Highlighting and Taking Notes:

If you've purchased the All Access Pass or Study Pass, in the online reader, click and drag your mouse to highlight text. When you do a small button appears – simply click on it! From there, you can select a highlight color, add notes, add tags, or any combination.

Printing:

If you've purchased the All Access Pass, you can print each chapter by clicking on the Downloads tab. If you have Study Pass, click on the print icon within Study View to print out your notes and highlighted sections.

Search:

To search, use the text box at the bottom of the book. Click a search result to be taken to that chapter or section of the book (note you may need to scroll down to get to the result).

View Full Student FAQs

## 7.3 Financial Market Efficiency

### Learning Objective

1. In what senses can financial markets be efficient or inefficient?

Now here is the freaky thing. While at any given moment, most investors’ valuations are wrong (too low or too high), the market’s valuation, given the information available at that moment, is always correct, though in a tautological or circular way only. You may recall from your principles course that markets “discover” prices and quantities. If the market price of anything differs from the equilibrium price (where the supply and demand curves intersect), market participants will bid the market price up or down until equilibrium is achieved. In other words, a good, including a financial security, is worth precisely what the market says it is worth.

At any given time, some people expect the future market price of an asset will move higher or that it is currently underpriced, a value or bargain, so to speak. They want to buy. Others believe it will move lower, that it is currently overpriced. They want to sell. Sometimes the buyers are right and sometimes the sellers are, but that is beside the point, at least from the viewpoint of economic efficiency. The key is that the investor who values the asset most highly will come to own it because he’ll be willing to pay the most for it. Financial markets are therefore allocationally efficient. In other words, where free markets reign, assets are put to their most highly valued use, even if most market participants don’t know what that use or value is. That’s really remarkable when you think about it and goes a long way to explaining why many economists grow hot under the collar when governments create barriers that restrict information flows or asset transfers.

Financial markets are also efficient in the sense of being highly integrated. In other words, prices of similar securities track each other closely over time and prices of the same security trading in different markets are identical, or nearly so. Were they not, arbitrage, or the riskless profit opportunity that arises when the same security at the same time has different prices in different markets, would take place. By buying in the low market and immediately selling in the high market, an investor could make easy money. Unsurprisingly, as soon as an arbitrage opportunity appears, it is immediately exploited until it is no longer profitable. (Buying in the low market raises the price there, while selling in the high market decreases the price there.) Therefore, only slight price differences that do not exceed transaction costs (brokerage fees, bid-ask spreads, etc.) persist.

The size of those price differences and the speed with which arbitrage opportunities are closed depend on the available technology. Today, institutional investors can complete international financial market trades in just seconds and for just a few hundredths or even thousandths of a percent. In the early nineteenth century, U.S.-London arbitrageurs (investors who engage in arbitrage) confronted lags of several weeks and transaction costs of several percent. Little wonder that price differentials were larger and more persistent in the early nineteenth century. But the early markets were still rational because they were as efficient as they could be at the time. (Perhaps in the future, new technology will make seconds and hundredths of a percent look pitifully archaic.)

Arbitrage, or the lack thereof, has been the source of numerous jokes and gags, including a two-part episode of the 1990s comedy sitcom Seinfeld. In the episodes, Cosmo Kramer and his rotund friend Newman (the postal worker) decide to try to arbitrage the deposit on cans and bottles of soda, which is 5 cents in New York, where Seinfeld and his goofy friends live, and 10 cents in Michigan. The two friends load up Newman’s postal truck with cans and head west, only to discover that the transaction costs (fuel, tolls, hotels, and what not) are too high, especially given the fact that Kramer is easily sidetracked.http://en.wikipedia.org/wiki/The_Bottle_Deposit,_Part_1 High transaction costs also explain why people don’t arbitrage the international price differentials of Big Macs and many other physical things.http://www.economist.com/markets/Bigmac/Index.cfm Online sites like eBay, however, have recently made arbitrage in nonperishables more possible than ever by greatly reducing transaction costs.

In another joke (at least I hope it’s a joke!), two economics professors think they see an arbitrage opportunity in wheat. After carefully studying all the transaction costs—freight, insurance, brokerage, weighing fees, foreign exchange volatility, weight lost in transit, even the interest on money over the expected shipping time—they conclude that they can make a bundle buying low in Chicago and selling high in London. They go for it, but when the wheat arrives in London, they learn that a British ton (long ton, or 2,240 pounds) and a U.S. ton (short ton, or 2,000 pounds) are not the same thing. The price of wheat only appeared to be lower in Chicago because a smaller quantity was being priced.

Some economists believe financial markets are so efficient that unexploited profit opportunities like arbitrage are virtually impossible. Such extreme views have also become the butt of jokes, like the one where an assistant professor (young, untenured) of economics bends over to pick up a $20 bill off the sidewalk, only to be chided by an older, wiser, indubitably tenured colleague who advises him that if the object on the ground were real money, somebody else would have already have picked it up. As somebody who once found a real$50 bill on a New York City sidewalk, I (Wright) know that money is sometimes lost and that somebody has to be lucky enough to pocket it. But as somebody who once stuck his hand in a toilet to get what looked like a $20 bill, I also know that things are not always what they seem. (Hey, I was young.) Arbitrage and other unexploited profit opportunities are not unicorns. They do exist on occasion. But especially in financial markets, they are so fleeting that they might best be compared to kaons or baryons, rare and short-lived subatomic particles. In an efficient market, all unexploited profit opportunities, not just arbitrage opportunities, will be eliminated as quickly as the current technology set allows. Say, for example, the rate of return on a stock is 10 percent but the optimal forecast or best guess rate of return, due to a change in information or in a valuation model, was 15 percent. Investors would quickly bid up the price of the stock, thereby reducing its return. Remember that R = (C + Pt1 – Pt0)/Pt0. As Pt0 , the price now, increases, R must decrease. Conversely, if the rate of return on a stock is currently 10 percent but the optimal forecast rate of return dropped to 5 percent, investors would sell the stock until its price decreased enough to increase the return to 10 percent. In other words, in an efficient market, the optimal forecast return and the current equilibrium return are one and the same. Financial market efficiency means that it is difficult or impossible to earn abnormally high returns at any given level of risk. (Remember, returns increase with risk.) Yes, an investor who invests 100 percent in hedge fundsA type of relatively unregulated mutual fund that engages in sophisticated trading strategies. Only wealthy individuals and institutional investors are allowed to invest directly in such funds. will likely garner a higher return than one who buys only short-dated Treasury notes. Holding risk (and liquidity) constant, though, returns should be the same, especially over long periods. In fact, creating a stock portfolio by throwing darts at a dartboard covered with ticker symbols returns as much, on average, as the choices of experienced stock pickers choosing from the same set of companies. Chimpanzees and orangutans have also done as well as the darts and the experts. Many studies have shown that actively managed mutual funds do not systematically outperform (provide higher returns than) the market. In any given period, some funds beat the market handily, but others lag it considerably. Over time, some stellar performers turn into dogs, and vice versa. (That is why regulators force financial firms to remind investors that past performance is not a guarantee of future returns.) ### Stop and Think Box Wright once received the following hot tip in his e-mail: Saturday, March 17, 2007 Dear Friend: If you give me permission . . . I will show you how to make money in a high-profit sector, starting with just$300–$600. The profits are enormous. You can start with as little as$300. And what's more, there is absolutely no risk because you will “Test Drive” the system before you shell out any money. So what is this “secret” high-profit sector that you can get in on with just $300–$600 or less??? Dear Friend, it’s called “penny stocks”—stocks that cost less than $5 per share. Don’t laugh—at one time Wal-Mart was a “penny stock.” So was Microsoft. And not too long age, America Online was selling for just .59 cents a share, and Yahoo was only a$2 stock. These are not rare and isolated examples. Every month people buy penny stocks at bargain prices and make a small fortune within a short time.

Very recently, these three-penny stocks made huge profits. In January ARGON Corp. was at $2.69. Our indicators picked up the beginning of the upward move of this stock. Within three months the stock shot up to$28.94 a share, turning a $300 investment into$3,238 in just three months. In November Immugen (IMGN) was at $2.76 a share. We followed the decline of this stock from$13 to as little as $1.75 a share. But our technicals were showing an upward move. Stock went up to$34.10 a share. An investment of $500 would have a net gain of$5,677. RF Micro Devices was at $1.75 in August 1999. It exploded to$65.09 a share by April 2000. An investment of only $500 in this stock would have a net profit of$18,097. In fact, the profits are huge in penny stocks. And smart investors who picked these so-called penny stocks made huge profits. They watched their money double seemingly day after day, week after week, month after month. Double, triple, quadruple, and more.

Should Wright buy? Why or why not?

Wright should not invest. If the individual who sent the message really knows that the stock is going to appreciate, why should he tell anyone? Shouldn’t he buy the shares himself, borrowing to the hilt if necessary to do so? So why would he try to entice me to buy this stock? He probably owns a few (hundred, thousand, million) shares and wants to drive their price up by finding suckers and fools to buy it so he can sell. This is called “pumping and dumping”http://www.fool.com/foolu/askfoolu/2002/askfoolu020107.htm and it runs afoul of any number of laws, rules, and regulations, so you shouldn’t think about sending such e-mails yourself, unless you want to spend some time in Martha Stewart’s prison.http://www.csmonitor.com/2004/1008/p01s01-usju.html And don’t think you can free-ride on the game, either. One quirky fellow named Joshua Cyr actually tracks the prices of the hot stock tips he has received, pretending to buy 1,000 shares of each. On one day in March 2007, his Web site claimed that his pretend investment of $70,987.00 was then worth a whopping$9,483.10, a net gain of −\$61,503.90. (To find out how he is doing now, browse http://www.spamstocktracker.com/.) Even if he had bought and sold almost immediately, he would have still lost money because most stocks experienced very modest and short-lived “pops” followed by quick deflations. A few of us are idiots, but most are not (or we are too poor or too lazy to act on the tips). Learning this, the scammers started to pretend that they were sending the message to a close friend to make it seem as though the recipient stumbled upon important inside information. (For a hilarious story about this, browse http://www.marketwatch.com/news/story/errant-e-mails-nothing-more-another/story.aspx?guid={1B1B5BF1-26DE-46BE-BA34-C068C62C92F7}.) Beware, because their ruses are likely to grow increasingly sophisticated.

In some ways, darts and apes are better stock pickers than people because the fees and transaction costs associated with actively managed funds often erase any superior performance they provide. For this reason, many economists urge investors to buy passively managed mutual funds or exchange traded funds (ETFs) indexed to broad markets, like the S&P or the Dow Jones Industrial Average, because they tend to have the lowest fees, taxes, and trading costs. Such funds “win” by not losing, providing investors with an inexpensive way of diversifying risk and earning the market rate of return, whatever that happens to be over a given holding period (time frame).

### Key Takeaways

• Markets are efficient if they allocate resources to their most highly valued use and if excess profit opportunities are rare and quickly extinguished.
• Financial markets are usually allocationally efficient. In other words, they ensure that resources are allocated to their most highly valued uses, and outsized risk-adjusted profits (as through arbitrage, the instantaneous purchase and sale of the same security in two different markets to take advantage of price differentials) are uncommon and disappear rapidly.
Close Search Results
Study Aids


text:
# Uncontrollable platform spawning

I made simple spawner like this:

void Update() {

if (PlatformPosition.spawnNewPlatform) {
NewPlatform();
}
}

public void NewPlatform() {

if (active) {
newTransform = transform;
Instantiate(prefabs[Random.Range(0, prefabs.Length)], newTransform.position, Quaternion.identity);
}
}

And so it looks like my platform script:

public static bool spawnNewPlatform = true;

void Awake() {
spriteSize = GetComponent<SpriteRenderer>();
offscreenX = (Screen.width / PixelPerfect.pixelsToUnit) / 2 + offset;
}

void Update () {

pos = transform.position;
posX = pos.x;

if (posX <= -offscreenX) {

spawnNewPlatform = true;
}
else {
spawnNewPlatform = false;
}
}

Now when I start the "game" the spawner create unexpected number of platforms. Sometimes it's 2 clones sometimes it's 10... I don't understand what is the problem and how to fix it. Is it frame rate issue?

• Have you made sure that the line of code runs only once? – Vadim Tatarnikov Aug 27 '15 at 18:59
• How is the position of the spawned platform determined? – realUser404 Dec 21 '16 at 9:49

As long as you only have one spawner, it doesn't look like the spawner could be instantiating 10 platforms. However, it's definitely possible that you'll get two. On the frame after the platform is instantiated, if Spawner.Update() gets called before Platform.Update(), then spawnNewPlatform will still be true and another one will get created.
Try setting spawnNewPlatform = false within Platform.Awake(). That way, when a platform is spawned, it will immediately prevent spawning of any other platforms.
Try adding if(spawnNewPlatform) return; to the top of your platform Update() method.
Also if it's a scrolling level and not a static single screen level then the platforms may be hitting the respawn point early. If that's the case you may want to use Camera.WorldToScreenPoint()
void Update() { Vector3 screenPos = camera.WorldToScreenPoint(target.position); Debug.Log("target is " + screenPos.x + " pixels from the left"); }

format: plain


text:
## Wednesday, November 9, 2016

### LeetCode OJ - Minimum Moves to Equal Array Elements

Problem:

Analysis:

The trick here is that instead of thinking increasing $n - 1$ element, we can also think of it as decreasing one element. In fact, increasing $n$ element all at once and then choose $1$ to decrease. In terms of getting the element to equal each other, the increasing step is meaningless, we can ignore that.

Solution:

Following the thinking above, here is the example sequence:

[1, 2, 3] -> [2, 3, 3] -> [3, 4, 3] -> [4, 4, 4]

It can also be think as the decreasing sequence

[1, 2, 3] -> [1, 2, 2] -> [1, 2, 1] -> [1, 1, 1]

Now this is particularly enlightening, it just simply reduce every number to the minimum. Think about it, because all you could do is the decrement by 1, there is simply no better way, therefore the answer is simply the difference between every element with the minimum, or more conveniently, sum of all elements minus the minimum times the number of element.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/minimum-moves-to-equal-array-elements/

#include "LEET_MINIMUM_MOVES_TO_EQUAL_ARRAY_ELEMENTS.h"
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

namespace _LEET_MINIMUM_MOVES_TO_EQUAL_ARRAY_ELEMENTS
{
class Solution
{
public:
int minMoves(vector<int>& nums)
{
int m = ~(1 << 31);
int s = 0;
for (int i = 0; i < nums.size(); i++)
{
m = min(nums[i], m);
s += nums[i];
}
return s - m * nums.size();
}
};
};

using namespace _LEET_MINIMUM_MOVES_TO_EQUAL_ARRAY_ELEMENTS;

int LEET_MINIMUM_MOVES_TO_EQUAL_ARRAY_ELEMENTS()
{
Solution solution;
int input_array[] = { 1, 2, 3 };
vector<int> input(input_array, input_array + _countof(input_array));
cout << solution.minMoves(input) << endl;
return 0;
}


text:
×

## Polynomial Factoring

A factored polynomial reveals its roots, a key concept in understanding the behavior of these expressions.

# Level 2

$\large \sqrt a + b = 7 \\ \large \sqrt b + a = 11$

If $$a$$ and $$b$$ are real numbers that satisfy the equation above, what is the value of $$a$$ and $$b$$ respectively?

Given that $$6y^2=2014$$, find the value of $\frac{9(y^4+6y^3+9y^2)}{y^2+6y+9}.$

$\large a^3 + b^3 = 2593080, \ \ a + b = 210, \ \ \ \ \ ab = \ ?$

Given that $$a+b=1$$ and $$a^2+b^2=2$$, what is the value of $$a^7+b^7$$?

If $$x^2 - 5x - 1 = 0$$, then find the value of $$x^2 + \frac{1}{x^2}.$$

×


text:
## UPS to deploy prototype Class 6 extended range fuel cell electric vehicle delivery truck; trials begin in Q3

##### 02 May 2017

UPS will deploy a prototype extended range Fuel Cell Electric Vehicle (FCEV) in its Rolling Laboratory fleet of alternative fuel and advanced technology vehicles. UPS is working with the US Department of Energy (DOE) and other partners to design a first-of-its-kind, zero tailpipe emissions, Class 6 medium-duty delivery truck that meets the same route and range requirements of UPS’ existing conventional fuel vehicles.

The UPS trucks are equipped with a 32 kW Hydrogenics fuel cell coupled to 45 kWh of battery storage and 10 kg of hydrogen fuel. Each FCEV produces electricity which continuously charges its batteries, thereby providing additional power and an extended range of 125 miles. This will support the full duty cycle of the truck, including highway driving.

The first FCEV prototype will be deployed in Sacramento, Calif., where UPS will validate its design and core performance requirements by testing it on the street starting the third quarter of 2017. Current project plans call for additional UPS trucks to be validated with at least 5,000 hours of in-service operational performance.

All of the trucks will be deployed in California due to that state’s ongoing investment in zero tailpipe emissions transportation and installment of hydrogen fueling stations around the state.

The challenge we face with fuel cell technology is to ensure the design can meet the unique operational demands of our delivery vehicles on a commercial scale. This project is an essential step to test the zero tailpipe emissions technology and vehicle on the road for UPS and the transportation industry. We have a long history of developing and promoting the use of more sustainable alternative fuels with our Rolling Laboratory, and hope that by bringing our unique expertise to the development of hydrogen fuels, we can help advance the technology.

—Mark Wallace, UPS senior vice president global engineering and sustainability

The project is part of a fuel cell project grant awarded by DOE in 2013 focused on verifying the proof of concept in commercial delivery vehicles. The project calls for retrofitting conventional fuel trucks with fuel cell electric systems designed specifically for use in a delivery truck duty cycle. UPS is partnering with the Center for Transportation and the Environment as well as Unique Electric Solutions LLC and the University of Texas’ Center for Electromechanics.

UPS has invested more than $750 million in alternative fuel and advanced technology vehicles and fueling stations globally since 2009. UPS has deployed more than 8,300 vehicles using its Rolling Laboratory approach to determine what works best in each situation. ### Comments Great idea, get renewable power contracts then GO for it! I'm not sure why they have specified such a big battery pack and relatively small fc stack, which iin a car would only cover cruising, although the stop start nature of the job means that it will cover well for a delivery vehicle. The problem of course is power draw from such a small stack. Toyota have only specified a 12 KWH battery for a thumping great Class 8 Drayage vehicle, but fuel cells and batteries can of course be combined in loads of different ways. Presumably the cost of the Hydrogenics stack is high relative to the batteries which UPS can buy. Toyota can simply stick in a couple of Mirai stacks. This parallels La Poste in France, who are further along, already having deployed considerable numbers of BEVs with a Symbio/Michelin range extender, so of course they are using a big battery pack too. Perhaps that is optimal for a delivery vehicle. I will add here some other news on the progress of hydrogen and fuel cells in buses. 'Transport for London (TfL) has recently launched a tender for the bulk procurement of fuel cell buses. Working in partnership with other UK cities (Aberdeen, Birmingham, Dundee), TfL is inviting potential suppliers of fuel cell buses to join a framework for the supply of single and double decker vehicles to cities across the UK and potentially further afield. Further context and details of this opportunity are available from the contract notice published via the Official Journal of the EU (OJEU).1 Fuel cell buses can offer an attractive zero emission solution for public transport in cities. They do this without imposing any significant new operational constraints on bus operators, as they can meet all daily bus duty cycles and can refuel in a short refuelling window. As such, once their costs reduce through economies of scale, they will be a valuable tool in the fight against local pollution and the removal of carbon dioxide emissions from road transport. Furthermore, fuel cell buses have the potential to kick start the use of hydrogen for mobility, with other applications in passenger cars, vans, trucks and even trains expected to follow. The bulk procurement of buses will significantly increase yearly order volumes in Europe and will play a key role in reducing costs and bringing this technology closer to a commercial reality.' https://fuelcellsworks.com/news/uks-zero-emission-bus-deployment-plans-gain-momentum/ Over the six years of the project they hope to reduce costs enough so that there is no penalty at all against diesel' Fuel cell buses would actively clean city air, can be operated on exactly the same duty cycle as regular buses with fast refuelling, and do not suffer the severe penalties that battery ones do in the cold. They would also promote and enable the spread of hydrogen infrastructure and lower cost hydrogen, which is expensive in transport mainly due to the low volume, with one bus depot in the US having already got costs down through volume to$4.50 kg:

'As for the approximately $1.9 million hydrogen pumping station at SARTA’s Gateway headquarters in southeast Canton headquarters, it’s operational, said Conrad. A 9,000-gallon tank holds liquid hydrogen at extremely cold temperatures. A vaporizer converts the liquid hydrogen into gas where it’s stored in underground tanks and then it’s pumped into the hydrogen buses with fuel dispensers. The pumping station can support up to 20 vehicles. A bus can hold 50 kilograms of gas. The hydrogen is shipped from Air Products’ hydrogen plant in Ontario. A kilogram of hydrogen gas, which now costs about$4.50, is roughly equal to a gallon, said Conrad. A hydrogen gas bus gets about eight to nine miles out of about a kilogram of hydrogen gas while a regular diesel bus gets about four miles to the gallon.'

http://omniproservices.com/omniweb/sarta-hydrogen-station/

In respect to hydrogen infrastructure:

'The North of England’s gas distributer, Northern Gas Networks (NGN), with support of Leeds City Council, has officially launched its H21 Project Office in Leeds which will help establish the city and wider region as the UK’s hydrogen centre of excellence.

The office will deliver innovation projects with a strategic focus of providing compelling evidence to support UK gas grid conversion from natural gas (methane) to zero-carbon Hydrogen. If such a conversion were to take place it would be the single biggest contributor to supporting the UK Government’s ambitious 2050 climate change targets.

The office opening comes in the week following the Government’s announcement that it will be committing £25M of funding for an innovative programme considering using hydrogen gas for heating in homes across the UK.

Mark Horsely, CEO of Northern Gas Networks, said: “We are delighted with the Government’s announcement of a £25m programme which will provide significant amounts of the critical evidence required to allow a policy decision to convert the gas network to 100% Hydrogen. By opening our dedicated project office, we are taking a further step towards our hydrogen future and sending a signal to the Government and the rest of the industry that we are ready to work with them to deliver it.

The dedicated office will bring together international leading talent from across the energy sector, academia, government and business to further examine and, build the foundations to deliver, the gas network conversion strategy set out by NGN in its ground breaking H21 Leeds City Gate project (get the report or watch the film by visiting NGN website).

The H21 Citygate project looked into the feasibility of substituting natural gas with hydrogen in the gas distribution network. The project has shown that the gas network has the correct capacity for conversion, it can be converted incrementally with minimal disruption to customers and it would have a minimal impact on customer’s bills'

https://fuelcellsworks.com/news/northern-gas-networks-hydrogen-project-takes-step-forward-as-25-million-fund-announced-for-hydrogen/

Electric vehicles (of all sizes) with FC range extenders are being developed at a much faster rate in the last 12+ months.

Much lower cost H2 is now available in many places.

Better FCEVs and lower cost H2 will start to replace dirty diesel units, specially where pollution is a major problem.

Fleets have fuel yards, hydrogen, CNG, DME are not a problem,
they can make the fuels at the yard to save money.
Oberon has an NG to DME station that goes right in the fuel yard
for trucks, they can use bio renewable methane.

UPS is utilizing recently developed technology to make very unique and beautiful cars and other auto vehicles. I completed my research paper on vehicles after visiting website top5writingservices.com for assistance that further reveals this time, they are working on the manufacturing on such truck. They are trying to build alternative fuel systems.

The comments to this entry are closed.


text:
# A Trace Formula for Certain Hecke Operators and Gaussian Hypergeometric Functions - Mathematics > Number Theory

A Trace Formula for Certain Hecke Operators and Gaussian Hypergeometric Functions - Mathematics > Number Theory - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We present here simple trace formulas for Hecke operators $T kp$ for all$p>3$ on $S k\Gamma 03$ and $S k\Gamma 09$, the spaces of cusp forms ofweight $k$ and levels 3 and 9. These formulas can be expressed in terms ofspecial values of Gaussian hypergeometric series and lend themselves to simplerecursive expressions in terms of traces of Hecke operators on spaces of lowerweight. Along the way, we show how to express the traces of Frobenius of afamily of elliptic curves with 3-torsion as special values of a Gaussianhypergeometric series over $\mathbb{F} q$, when $q\equiv 1 \pmod{3}$. We alsouse these formulas to provide a simple expression for the Fourier coefficientsof $\eta3z^8$, the unique normalized cusp form of weight 4 and level 9, andthen show that the number of points on a certain threefold is expressible interms of these coefficients.

Autor: Catherine Lennon

Fuente: https://arxiv.org/


text:
# stat946w18/AmbientGAN: Generative Models from Lossy Measurements

Jump to: navigation, search

# Introduction

Generative models are powerful tools to concisely represent the structure in large datasets. Generative Adversarial Networks operate by simulating complex distributions but training them requires access to large amounts of high quality data. Often, we only have access to noisy or partial observations, which will, from here on, be referred to as measurements of the true data. If we know the measurement function and would like to train a generative model for the true data, there are several ways to continue which have varying degrees of success. We will use noisy MNIST data as an illustrative example, and show the results of 1. ignoring the problem, 2. trying to recover the lost information, and 3. using AmbientGAN as a way to recover the true data distribution. Suppose we only see MNIST data that has been run through a Gaussian kernel (blurred) with some noise from a $N(0, 0.5^2)$ distribution added to each pixel:

### Ignore the problem

Train a generative model directly on the measured data. This will obviously be unable to generate the true distribution before measurement has occurred.

### Try to recover the information lost

Works better than ignoring the problem but depends on how easily the measurement function can be inverted.

### AmbientGAN

Ashish Bora, Eric Price and Alexandros G. Dimakis propose AmbientGAN as a way to recover the true underlying distribution from measurements of the true data. AmbientGAN works by training a generator which attempts to have the measurements of the output it generates fool the discriminator. The discriminator must distinguish between real and generated measurements. This paper is published in ICLR 2018.

## Contributions

The paper makes the following contributions:

### Theoretical Contribution

The authors show that the distribution of measured images uniquely determines the distribution of original images. This implies that a pure Nash equilibrium for the GAN game must find a generative model that matches the true distribution. They show similar results for a dropout measurement model, where each pixel is set to zero with some probability p, and a random projection measurement model, where they observe the inner product of the image with a random Gaussian vector.

Also, the author listed a few theorems to support assumptions satisfied under Gaussian-Projection, Convolve+Noise and Block-Pixels measurement models, thus showing that that we can recover the true underlying distribution with the AmbientGAN framework. For example, the Gaussian theorem guarantees the uniqueness of underlying distribution. Finally by showing that this assumption is satisfied under Gaussian-Projection, Convolve+Noise and Block-Pixels measurement models, the author finally proved that can recover the true underlying distribution with the AmbientGAN framework.

### Empirical Contribution

The authors consider CelebA and MNIST dataset for which the measurement model is unknown and show that Ambient GAN recovers a lot of the underlying structure.

# Related Work

Currently there exist two distinct approaches for constructing neural network based generative models; they are autoregressive [4,5] and adversarial [6] based methods. The adversarial model has shown to be very successful in modeling complex data distributions such as images, 3D models, state action distributions and many more. This paper is related to the work in [7] where the authors create 3D object shapes from a dataset of 2D projections. This paper states that the work in [7] is a special case of the AmbientGAN framework where the measurement process creates 2D projections using weighted sums of voxel occupancies.

# Datasets and Model Architectures

We used three datasets for our experiments: MNIST, CelebA and CIFAR-10 datasets We briefly describe the generative models used for the experiments. For the MNIST dataset, we use two GAN models. The first model is a conditional DCGAN, while the second model is an unconditional Wasserstein GAN with gradient penalty (WGANGP). For the CelebA dataset, we use an unconditional DCGAN. For the CIFAR-10 dataset, we use an Auxiliary Classifier Wasserstein GAN with gradient penalty (ACWGANGP). For measurements with 2D outputs, i.e. Block-Pixels, Block-Patch, Keep-Patch, Extract-Patch, and Convolve+Noise, we use the same discriminator architectures as in the original work. For 1D projections, i.e. Pad-Rotate-Project, Pad-Rotate-Project-θ, we use fully connected discriminators. The architecture of the fully connected discriminator used for the MNIST dataset was 25-25-1 and for the CelebA dataset was 100-100-1.

# Model

For the following variables superscript $r$ represents the true distributions while superscript $g$ represents the generated distributions. Let $x$, represent the underlying space and $y$ for the measurement.

Thus, $p_x^r$ is the real underlying distribution over $\mathbb{R}^n$ that we are interested in. However if we assume that our (known) measurement functions, $f_\theta: \mathbb{R}^n \to \mathbb{R}^m$ are parameterized by $\Theta \sim p_\theta$, we can then observe $Y = f_\theta(x) \sim p_y^r$ where $p_y^r$ is a distribution over the measurements $y$.

Mirroring the standard GAN setup we let $Z \in \mathbb{R}^k, Z \sim p_z$ and $\Theta \sim p_\theta$ be random variables coming from a distribution that is easy to sample.

If we have a generator $G: \mathbb{R}^k \to \mathbb{R}^n$ then we can generate $X^g = G(Z)$ which has distribution $p_x^g$ a measurement $Y^g = f_\Theta(G(Z))$ which has distribution $p_y^g$.

Unfortunately, we do not observe any $X^g \sim p_x$ so we cannot use the discriminator directly on $G(Z)$ to train the generator. Instead we will use the discriminator to distinguish between the $Y^g - f_\Theta(G(Z))$ and $Y^r$. That is, we train the discriminator, $D: \mathbb{R}^m \to \mathbb{R}$ to detect if a measurement came from $p_y^r$ or $p_y^g$.

AmbientGAN has the objective function:

\begin{align} \min_G \max_D \mathbb{E}_{Y^r \sim p_y^r}[q(D(Y^r))] + \mathbb{E}_{Z \sim p_z, \Theta \sim p_\theta}[q(1 - D(f_\Theta(G(Z))))] \end{align}

where $q(.)$ is the quality function; for the standard GAN $q(x) = log(x)$ and for Wasserstein GAN $q(x) = x$.

As a technical limitation we require $f_\theta$ to be differentiable with respect to each input for all values of $\theta$.

With this set up we sample $Z \sim p_z$, $\Theta \sim p_\theta$, and $Y^r \sim U\{y_1, \cdots, y_s\}$ each iteration and use them to compute the stochastic gradients of the objective function. We alternate between updating $G$ and updating $D$.

# Empirical Results

The paper continues to present results of AmbientGAN under various measurement functions when compared to baseline models. We have already seen one example in the introduction: a comparison of AmbientGAN in the Convolve + Noise Measurement case compared to the ignore-baseline, and the unmeasure-baseline.

### Convolve + Noise

Additional results with the convolve + noise case with the celebA dataset. The AmbientGAN is compared to the baseline results with Wiener deconvolution. It is clear that AmbientGAN has superior performance in this case. The measurement is created using a Gaussian kernel and IID Gaussian noise, with $f_{\Theta}(x) = k*x + \Theta$, where $*$ is the convolution operation, $k$ is the convolution kernel, and $\Theta \sim p_{\theta}$ is the noise distribution.

Images undergone convolve + noise transformations (left). Results with Wiener deconvolution (middle). Results with AmbientGAN (right).

### Block-Pixels

With the block-pixels measurement function each pixel is independently set to 0 with probability $p$.

Measurements from the celebA dataset with $p=0.95$ (left). Images generated from GAN trained on unmeasured (via blurring) data (middle). Results generated from AmbientGAN (right).

### Block-Patch

A random 14x14 patch is set to zero (left). Unmeasured using-navier-stoke inpainting (middle). AmbientGAN (right).

### Pad-Rotate-Project-$\theta$

Results generated by AmbientGAN where the measurement function 0 pads the images, rotates it by $\theta$, and projects it on to the x axis. For each measurement the value of $\theta$ is known.

The generated images only have the basic features of a face and is referred to as a failure case in the paper. However the measurement function performs relatively well given how lossy the measurement function is.

For the Keep-Patch measurement model, no pixels outside a box are known and thus inpainting methods are not suitable. For the Pad-Rotate-Project-θ measurements, a conventional technique is to sample many angles, and use techniques for inverting the Radon transform . However, since only a few projections are observed at a time, these methods aren’t readily applicable hence it is unclear how to obtain an approximate inverse function shown below.

### Explanation of Inception Score

To evaluate GAN performance, the authors make use of the inception score, a metric introduced by Salimans et al.(2016). To evaluate the inception score on a datapoint, a pre-trained inception classification model (Szegedy et al. 2016) is applied to that datapoint, and the KL divergence between its label distribution conditional on the datapoint and its marginal label distribution is computed. This KL divergence is the inception score. The idea is that meaningful images should be recognized by the inception model as belonging to some class, and so the conditional distribution should have low entropy, while the model should produce a variety of images, so the marginal should have high entropy. Thus an effective GAN should have a high inception score.

### MNIST Inception

AmbientGAN was compared with baselines through training several models with different probability $p$ of blocking pixels. The plot on the left shows that the inception scores change as the block probability $p$ changes. All four models are similar when no pixels are blocked $(p=0)$. By the increase of the blocking probability, AmbientGAN models present a relatively stable performance and perform better than the baseline models. Therefore, AmbientGAN is more robust than all other baseline models.

The plot on the right reveals the changes in inception scores while the standard deviation of the additive Gaussian noise increased. Baselines perform better when the noise is small. By the increase of the variance, AmbientGAN models present a much better performance compare to the baseline models. Further AmbientGAN retains high inception scores as measurements become more and more lossy.

For 1D projection, Pad-Rotate-Project model achieved an inception score of 4.18. Pad-Rotate-Project-θ model achieved an inception score of 8.12, which is close to the score of vanilla GAN 8.99.

### CIFAR-10 Inception

AmbientGAN is faster to train and more robust even on more complex distributions such as CIFAR-10. Similar trends were observed on the CIFAR-10 data, and AmbientGAN maintains relatively stable inception score as the block probability was increased.

### Robustness To Measurement Model

In order to empirically gauge robustness to measurement modelling error, the authors used the block-pixels measurement model: the image dataset was computed with $p^* = 0.5$, and several versions of the model were trained, each using different values of blocking probability $p$. The inception scores were calculated and plotted as a function of $p$. This is shown on the left below:

The authors observe that the inception score peaks when the model uses the correct probability, but decreases smoothly as the probability moves away, demonstrating some robustness.

### Compressed Sensing

As described in Bora et al. (2017), generative models were found to outperform sparsity-based approaches in sensing. Using this knowledge, the generator from AmbientGAN can be tested against Lasso to determine the required measurements to minimize the reconstruction error. As shown on the right of Figure 16, AmbientGAN outperforms Lasso in a fraction of the number of measurements

# Theoretical Results

The theoretical results in the paper prove the true underlying distribution of $p_x^r$ can be recovered when we have data that comes from the Gaussian-Projection measurement, Fourier transform measurement and the block-pixels measurement. The do this by showing the distribution of the measurements $p_y^r$ corresponds to a unique distribution $p_x^r$. Thus even when the measurement itself is non-invertible the effect of the measurement on the distribution $p_x^r$ is invertible. Lemma 5.1 ensures this is sufficient to provide the AmbientGAN training process with a consistency guarantee. For full proofs of the results please see appendix A.

### Lemma 5.1

Let $p_x^r$ be the true data distribution, and $p_\theta$ be the distributions over the parameters of the measurement function. Let $p_y^r$ be the induced measurement distribution.

Assume for $p_\theta$ there is a unique probability distribution $p_x^r$ that induces $p_y^r$.

Then for the standard GAN model if the discriminator $D$ is optimal such that $D(\cdot) = \frac{p_y^r(\cdot)}{p_y^r(\cdot) + p_y^g(\cdot)}$, then a generator $G$ is optimal if and only if $p_x^g = p_x^r$.

### Theorems 5.2

For the Gussian-Projection measurement model, there is a unique underlying distribution $p_x^{r}$ that can induce the observed measurement distribution $p_y^{r}$.

### Theorems 5.3

Let $\mathcal{F} (\cdot)$ denote the Fourier transform and let $supp (\cdot)$ be the support of a function. Consider the Convolve+Noise measurement model with the convolution kernel $k$and additive noise distribution $p_\theta$. If $supp( \mathcal{F} (k))^{c}=\phi$ and $supp( \mathcal{F} (p_\theta))^{c}=\phi$, then there is a unique distribution $p_x^{r}$ that can induce the measurement distribution $p_y^{r}$.

### Theorems 5.4

Assume that each image pixel takes values in a finite set P. Thus $x \in P^n \subset \mathbb{R}^{n}$. Assume $0 \in P$, and consider the Block-Pixels measurement model with $p$ being the probability of blocking a pixel. If $p \lt 1$, then there is a unique distribution $p_x^{r}$ that can induce the measurement distribution $p_y^{r}$. Further, for any $\epsilon \gt 0, \delta \in (0, 1]$, given a dataset of $$s=\Omega \left( \frac{|P|^{2n}}{(1-p)^{2n} \epsilon^{2}} log \left( \frac{|P|^{n}}{\delta} \right) \right)$$ IID measurement samples from pry , if the discriminator D is optimal, then with probability $\geq 1 - \delta$ over the dataset, any optimal generator G must satisfy $d_{TV} \left( p^g_x , p^r_x \right) \leq \epsilon$, where $d_{TV} \left( \cdot, \cdot \right)$ is the total variation distance.

# Conclusion

Generative models are powerful tools, but constructing a generative model requires a large, high quality dataset of the distribution of interest. The authors show how to relax this requirement, by learning a distribution from a dataset that only contains incomplete, noisy measurements of the distribution. This allows for the construction of new generative models of distributions for which no high quality dataset exists.

# Future Research

One critical weakness of AmbientGAN is the assumption that the measurement model is known and that this $f_theta$ is also differentiable. In fact, when the measurement model is known, there's no obvious reason not to invert the noisy measurement first(as illustrated in the second approach). It would be nice to be able to train an AmbientGAN model when we have an unknown measurement model but also a small sample of unmeasured data, or at the very least to remove the differentiability restriction from $f_theta$.

A related piece of work is here. In particular, Algorithm 2 in the paper excluding the discriminator is similar to AmbientGAN.

# Open Source Code

An implementation of Ambient GAN can be found here: https://github.com/AshishBora/ambient-gan.

# References

1. https://openreview.net/forum?id=Hy7fDog0b
2. Salimans, Tim, et al. "Improved techniques for training gans." Advances in Neural Information Processing Systems. 2016.
3. Szegedy, Christian, et al. "Rethinking the inception architecture for computer vision." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2016.
4. Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv:1312.6114, 2013.
5. Aaron van den Oord, Sander Dieleman, Heiga Zen, Karen Simonyan, Oriol Vinyals, Alex Graves, Nal Kalchbrenner, Andrew Senior, and Koray Kavukcuoglu. Wavenet: A generative model for raw audio. arXiv preprint arXiv:1609.03499, 2016a.
6. Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672–2680, 2014.
7. Matheus Gadelha, Subhransu Maji, and Rui Wang. 3d shape induction from 2d views of multiple objects. arXiv preprint arXiv:1612.05872, 2016.
8. Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. arXiv preprint arXiv:1703.03208, 2017.


text: I think there's been a growing disconnect between what the game world thinks of as AI and what the academic research world thinks of the same subject. The dist attribute of every node is set to its distance from sourcenode. Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph.It was conceived by computer scientist Edsger W. Dijkstra in 1956.This algorithm helps to find the shortest path from a point in a graph (the source) to a destination. dijkstra reads a stream of graphs and for each computes the distance of every node from sourcenode. This includes the value dist(v) for all vertices v for that iteration as well as Each edge connecting two nodes (u,v) will have a weight denoting the distance between node ‘u’ and node ‘v’. Carps if graph contains disconnected nodes (nodes with no edges) which are excluded. Could all participants of the recent Capitol invasion be charged over the death of Officer Brian D. Sicknick? Representing Graphs in Code 1.2. In this article, we will implement the Graph represented by Adjacency List using the HashMap data structure. And it's in one form to find whether a graph … The standard algorithm doesn't print anything, so if you are printing something, you're probably adding something extra to the standard algorithm, and we can't analyze that without seeing what your variation of the algorithm is. So the parent edge of u is a bridge. Difficulty: MEDIUM. I just want to know that if I give any disconnected graph to any of these algorithms , they will give information about the connected component of the graph only but no status about the disconnected component so If I trace back the order in which vertices are traversed during computation of shortest path , will I not get a tree for the connected component and vertices from other disconnected component would form a forest. The complexity of the code can be improved, but the abstractions are convenient to relate the code with the algorithm. Depends on the way how it is implemented, the time complexity varies. A connected graph is a graph without disconnected parts that can't be reached from other parts of the graph. Suggest Edit . Generic graph. The standard algorithm for Dijkstra's algorithm sets the distance correctly for all vertices in all components (not just the ones in the same connected component as the source). A minimum priority queue can be used to efficiently receive the vertex with least path distance. where, E is the number of edges and V is the number of vertices. For instance I talk about DFS algorithm , its Output: All vertices reachable from v labeled as discovered . Dijkstra Algorithm and the Adjacency matrix Consider a directed graph whose vertices are numbered from 1 to N . Ltd. All rights reserved. Dijkstra's shortest path algorithm used to calculate distances between nodes. This algorithm can be used on both weighted and unweighted graphs. Problem Statement . Graph of minimal distances. Maximum flow from %2 to %3 equals %1. Suppose that G = (V,E,ω) is a weighted graph in which some edges are negative. Dijkstra’s Algorithm may fail if a graph has negative edge weights, but your friend has proposed a way of using Dijkstra’s Algorithm to find shortest paths in such graphs. Thanks for contributing an answer to Computer Science Stack Exchange! Create graph online and use big amount of algorithms: find the shortest path, ... Find the shortest path using Dijkstra's algorithm, Adjacency matrix, Incidence Matrix. Set of vertices V 2. to the tree if it connects two previously disconnected nodes. It differs from the minimum spanning tree because the shortest distance between two vertices might not include all the vertices of the graph. We need to maintain the path distance of every vertex. Dijkstra's algorithm allows us to find the shortest path between any two vertices of a graph. I am not sure how to implement Kruskal's algorithm when the graph has multiple connected components From my understanding of Kruskal's algorithm, it repeatedly adds the minimal edge to a set. How to increase the byte size of a file without affecting content? Watch Queue Queue But in the case of disconnected graph or any vertex that is unreachable from all vertex, the previous implementation will not give the desired output, so in this post, a modification is done in BFS. The first map for storing the vertices and edges. Difference between prim's and kruskal and dijkstra. C++ implementation: Which 3 daemons to upload on humanoid targets in Cyberpunk 2077? Presently, it only handles undirected, unweighted, graphs. 1. It is easier to start with an example and then think about the algorithm. Therefore, it is a disconnected graph… If a path is not possible (which happens in case of disconnected graphs), then return -1 for those destination vertices. If the -p flag is used, the prev attribute of each node reachable from sourcenode is set to the name of the previous node on a shortest path. Select a source of the maximum flow. SOLVE THIS PROBLEM . Presently, it only handles undirected, unweighted, graphs. best reserved for undirected graphs. Thickness. Then we visit each node and its neighbors to find the shortest subpath to those neighbors. Spring 2020 Section 11: Graphs, Shortest Path, MST, UF Worksheet 14 1 Dijkstra’s and A* (a)Given the following graph, run Dijkstras algorithm starting at node a. Graphs in Java 1.1. The algorithm uses a greedy approach in the sense that we find the next best solution hoping that the end result is the best solution for the whole problem. I really hope you liked my article and found it helpful. Dijkstra's algorithm (or Dijkstra's Shortest Path First algorithm, SPF algorithm) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.. This is true no matter whether the input graph is connected or disconnected. The standard algorithm for Dijkstra's algorithm sets the distance correctly for all vertices in all components (not just the ones in the same connected component as the source). The emphasis in this article is the shortest path problem (SPP), being one of the fundamental theoretic problems known in graph theory, and how the Dijkstra algorithm can be used to solve it. Dijkstra's Algorithm works on the basis that any subpath B -> D of the shortest path A -> D between vertices A and D is also the shortest path between vertices B and D. Djikstra used this property in the opposite direction i.e we overestimate the distance of each vertex from the starting vertex. Kruskal vs Prim . Retrieving the shortest path of a dynamic graph, Shortest path in weighted(positive or negative) undirected graph. Hereby the edge weights we had previously, are now considered lengths of distance between the nodes. If I apply Dijkstra's ,BFS or Bellman-ford algorithm on a disconnected Graph then will the output be a tree or a disconnected Graph only because even if we have a disconnected Graph and we run Dijkstra's algorithm on it then it will return shortest path in the connected component only , but we maintain a predecessor array in all the algorithms which has information about the parent from which the node learnt the path so it will values for all the vertices , so even if we have a disconnected Graph then still other vertices will also be printed . 4. Construct a new graph G' whereas for every vertex v in V, create two vertices v_0 and v_1 in G', and for every edge (u, v) in E, create two edges (u_0, v_1) and (u_1,v_0) in G'. A cycle in a directed graph exists if there's a back edge discovered during a DFS. Source. basis that any subpath B -> D of the shortest path A -> D between vertices A and D is also the shortest path between vertices B For this lesson, we will implement it using linear search: it is simpler, albeit slower compared to the other way of implementation (PriorityQueue). a) (n*(n-1))/2 b) (n*(n+1))/2 c) n+1 d) none of these 2. A complete undirected graph can have maximum n n-2 number of spanning trees, where n is the number of nodes. Run Dijkstra on G' starting at s_0. This algorithm can be used on both weighted and unweighted graphs. Graph visualization is a way of representing structural information as diagrams of abstract graphs and networks. Join our newsletter for the latest updates. Making statements based on opinion; back them up with references or personal experience. Flow from %1 in %2 does not exist. Search (SearchKind. Dijkstra's shortest path . We found three spanning trees off one complete graph. Given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges . It only takes a minute to sign up. What is the output of below algorithms on a disconnected Graph? Now to use it in disconnected graph is little tricky but if you understand bfs then it is pretty simple. By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy. What does it mean when an aircraft is statically stable but dynamically unstable? Dijkstra’s Algorithm for Adjacency List Representation | Greedy Algo-8; ... Finding connected components for an undirected graph is an easier task. A minimum spanning tree (MST) is such a spanning tree that is minimal with respect to the edge weights, as in the total sum of edge weights. Why would the pressure in the cold water lines increase whenever the hot water heater runs. Draw horizontal line vertically centralized, Looking for a short story about a network problem being caused by an AI in the firmware. MPI Dijkstra's graph search algorithm. As it integrates well with D3, it is written in JavaScript. Book about an AI that traps people on a spaceship. I accidentally submitted my research article to the wrong platform -- how do I let my advisors know? Is the bullet train in China typically cheaper than taking a domestic flight? The actual computation of the path is performed by the ... /* In a disconnected graph, array_D[u] can be oo. Answer: a Go Back N: A sends 9 segments in total. Given a sorted list of comparable items and a target item being sought, binary search looks at the middle of the list, and compares it to the target. For a disconnected graph, we get a DFS forest, so you have to iterate through all vertices in the graph to find disjoint DFS trees. C++ Reference: shortestpaths This documentation is automatically generated. Text Color. Given a graph and a source vertex in the graph, find shortest paths from source to all vertices in the given graph. What is the fastest algorithm for finding shortest path in undirected edge-weighted graph? I'm going to show you the process of handling the is-connected problem, they're related. ... All the more reason for us to keep teaching it, then. Sink. Also for Dijkstra or Bellman-ford , they give shortest path from source vertex to every other vertex in the connected component of the graph . March 11, 2018 by Sumit Jain Objective: Given a Graph in which one or more vertices are disconnected, do the depth first traversal. Check to save. A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices. Why would the ages on a 1877 Marriage Certificate be so wrong? But then we just move on to the next iteration of the loop. In this algorithm, one starting vertex is given, and when an adjacent vertex is found, it moves to that adjacent vertex first and tries to traverse in the same manner. The concept was ported from mathematics and appropriated for the needs of computer science. Okay, so, while I'm assigning you a homework problem that's Dijkstra's shortest path algorithm. Once the algorithm is over, we can backtrack from the destination vertex to the source vertex to find the path. prototype - contains dijkstra prototype written in Python The basic goal of the algorithm is to determine the shortest path between a starting node, and the rest of the graph. Distance matrix. No. Then when all the edges are checked, it returns the set of edges that makes the most. Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. This graph consists of two independent components which are disconnected. Is it possible to edit data inside unencrypted MSSQL Server backup file (*.bak) without SSMS? Print the maximum positive integer value, i.e 2147483647, for the disconnected nodes. site design / logo © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa. If graph contains a disconnected sub-graph (a set of connected nodes isoluated / disconnected from all other nodes), the return value is 0 -- as the center nodes are undefined. Dijkstra’s algorithm computes what is called the ‘single-source shortest paths’ problem: For a given source node we want to know how far the total shortest distance to any other node in the graph is. What is the difference between Dijkstra's, Kruskal's and Prim's , a description I wrote at this page: Graph algorithms . Longest path in DAG or finding DAG diameter, Finding shortest paths in undirected graphs with possibly negative edge weights, How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs. Breadth-First Search (BFS) 1.4. Comparator; import java. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. So output is Graph right for all the algorithms whether the graph is undirected or directed ? We will also see the application of Floyd Warshall in determining the transitive closure of a given graph. There is an edge from a vertex i to a vertex j , if either j = i + 1 or j = 3i . © Parewa Labs Pvt. Earlier we have seen DFS where all the vertices in graph were connected. Problem 3. It has been written for parallel and distributed systems course on AGH University of Science and Technology. For this, we map each vertex to the vertex that last updated its path length. To subscribe to this RSS feed, copy and paste this URL into your RSS reader. (used by the visited array in case of DFS or BFS ). This what I want to confirm that do we consider this tree as the final information of the graph because if there had been any unreachable vertex from source then it's distance would have been marked as infinity so then we can't say that if we are at some vertex then if we backtrack to source vertex we will get a tree because we have a disconnected component here ,So the result may be a forest . Your friend’s idea is to: 1. If your graph has negative edge weights, you'll have to use some other algorithms, for instance Bellman-Ford. Why do massive stars not undergo a helium flash. In computer science, Prim's (also known as Jarník's) algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. it is assumed that all vertices are reachable from the starting vertex.But in the case of disconnected graph or any vertex that is unreachable from all vertex, the previous implementation will not give the desired output, so in this post, a modification is done in BFS. Dijkstra's Algorithm finds the shortest path between a given node (which is called the "source node") and all other nodes in a graph. 1. Why do password requirements exist while limiting the upper character count? dijkstra - source distance filter. ... (as in bucket sort, replacing the heap in Dijkstra's algorithm) by the digit k and higher of its distance. A graph is connected is there exists a path from every vertex to every other vertex in the graph. In previous post, BFS only with a particular vertex is performed i.e. Can nd all bridges and articulation points in O(n+ m) time via DFS. Graph Algorithms Data Structure Algorithms The Depth-First Search (DFS) is a graph traversal algorithm. Show distance matrix. If a topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then these edges form a directed Hamiltonian path in the DAG.If a Hamiltonian path exists, the topological sort order is unique; no other order respects the edges of the path. The Bellman-Ford algorithm is a graph search algorithm that finds the shortest path between a given source vertex and all other vertices in the graph. Select a sink of the maximum flow. The D3-graph-theory project is to use basic graph theory (Dijkstra's, and closeness centrality presently) on the D3 graph data structures. Graph has Eulerian path. I'll try to give an implementation of it here later. The D3-graph-theory project is to use basic graph theory (Dijkstra's, and closeness centrality presently) on the D3 graph data structures. We can store that in an array of size v, where v is the number of vertices. Thanks for keeping us grounded. Here's an example: Take a look at the source code of springy. Asking for help, clarification, or responding to other answers. Watch Queue Queue. Keywords: directed graph, cheapest path, shortest path, Dijkstra, spp. It is not possible to visit from the vertices of one component to the vertices of other component. The output of Dikstra's algorithm is a set of distances to each node. Watch Now. Dijkstra’s Algorithm is an algorithm for finding the shortest paths between nodes in a graph. Use Hash Maps: We will use two maps. Consider a directed graph whose vertices are numbered from 1 to N. There is an edge from a vertex i to a vertex j, if either j = i + 1 or j = 3i. As it integrates well with D3, it is written in JavaScript. Single source shortest path for undirected graph is basically the breadth first traversal of the graph. BFS is used as a traversal algorithm for graph. ... Graph is disconnected Is there an English adjective which means "asks questions frequently"? For a given source node in the graph, the algorithm finds the shortest path between that node and every other node. var graph = new DirectedGraph < string >(); // Search across the entire graph (in the case of multiple disconnected // graphs being contained in the same structure) foreach (var vertex in graph. Here the graph we consider is unweighted and hence the shortest path would be the number of edges it takes to go from source to destination. If graph contains a disconnected sub-graph (a set of connected nodes isoluated / disconnected from all other nodes), the return value is 0 -- as the center nodes are undefined. it is assumed that all vertices are reachable from the starting vertex. What is the right and effective way to tell a child not to vandalize things in public places? To some extent you could, in fact, uses Dijkstra's shortest path algorithm. Dijkstra Algorithm and the Adjacency matrix. ##Features. Given a weighted graph G, the objective is to find the shortest path from a given source vertex to all other vertices of G. The graph has the following characteristics- 1. For a disconnected graph, we get a DFS forest, so you have to iterate through all vertices in the graph to find disjoint DFS trees. The Bellman-Ford algorithm is a graph search algorithm that finds the shortest path between a given source vertex and all other vertices in the graph. Notice that the example given above happens to be undirected. Dijkstra's algorithm works much like a breadth-first search that takes the edge weights into account, starting at one node and traversing through the graph. In computer science, Prim’s and Kruskal’s algorithms are a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. Given a graph with V vertices (numbered from 1 to V) and E edges. We use Dijkstra… A back edge is an edge from a node to itself or one of the ancestors in a DFS tree. u start bridge Picture: no edge of a descendent of u in the search reached a non-descendent. Second map for storing the index for each vertex. Dijkstra's algorithm only records what is needed in order to recover the path. Now if the vertices are not reachable , it would give a forest as Output , Note that I haven't made any changes to the original problem . All graphs used on this page are connected. PROBLEM; DISCUSSION; SOLUTION Dijkstra Algorithm and the Adjacency matrix. Dijkstra's shortest path algorithm used to calculate distances between nodes. */ bool successor (vertex u, vertex z) { return (weight [u] [z]!= oo && u != z);} /* We finally arrive at the main algorithm. In this article we will see how to do DFS if graph is disconnected. Depth-First Search (DFS) 1.3. Due to the fact that many things can be represented as graphs, graph traversal has become a common task, especially used in data science and machine learning. This class is built on top of GraphBase, so the order of the methods in the Epydoc documentation is a little bit obscure: inherited methods come after the ones implemented directly in the subclass. Graph has not Eulerian path. Posts about dijkstra written by j2kun. ... [ sourcenode file ] DESCRIPTION dijkstra reads a stream of graphs and for each computes the distance of every node from sourcenode. This is the same as given In previous post, BFS only with a particular vertex is performed i.e. Use MathJax to format equations. It has subtopics based on edge and vertex, known as edge connectivity and vertex connectivity. The implementation of Dijkstra's Algorithm in C++ is given below. At each step, write down the entire state of the algorithm. (Can you see why?) Python Basics Video Course now on Youtube! Dijkstra’s algorithm. we say that shortest path doesn't have a cycle (ignoring the case of zero weighted cycle) , that means all the vertices in the shortest path form a tree right ? Edge length is given in the len attribute, and the default is 1. Stroke Color. DepthFirst)) { Console. This is true no matter whether the input graph is connected or disconnected. Dijkstra Algorithm and the Adjacency matrix. Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root. Lab Manual Fall 2020 Anum Almas Graph Connectivity: Whether it is possible to traverse a graph from one vertex to another is determined by how a graph is connected. Graph provides many functions that GraphBase does not, mostly because these functions are not speed critical and they were easier to implement in Python than in pure C. Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. This video explains how a undirected graph can be solved using Dijkstra's Algorithm which is shortest path algorithm. Find the shortest path from a source vertex to all other vertices. In this article, we will begin our discussion by briefly explaining about transitive closure and the Floyd Warshall Algorithm. Implement the graph, the time complexity varies vertices reachable from the minimum spanning because. Matrix consider a directed graph exists if there 's a back edge is an algorithm for finding shortest path one. % 3 equals % 1 in % 2 does not have any spanning tree the... Are there in a complete graph source vertex to every other vertex in the graph to! Traversal of the ancestors in a graph without disconnected parts that ca n't be from! Or Bellman-ford, they 're related details of simplified implementations visited array in case of DFS or )... Do massive stars not undergo a helium flash distributed systems course on AGH of. Dijkstra algorithm and the Adjacency matrix convenient way to tell a child not to vandalize things in public places,! Question and answer site for students, researchers and practitioners of computer Science basic graph (... The needs of computer Science returns the set of edges and V the! Are a convenient way to store certain types of data a domestic flight to: 1 Dijkstra prototype in! J = i + 1 or j = i + 1 or j = 3i * )! I.E 2147483647, for instance Bellman-ford, so, while i 'm assigning you a problem... Do massive stars not undergo a helium flash abstract graphs and networks Science! In this article, we map each vertex graph search algorithm it, then return -1 for destination! Edge-Weighted graph up with references or personal experience first line of each test case contains an ‘... An AI that traps people on a spaceship once the algorithm is to: 1 remarked. Plots in a table extent you could, in fact, uses Dijkstra 's shortest path wrong platform how... Graphs as well display all trigonometric function plots in a graph is an for! It in disconnected graph undergo a helium flash data Structure algorithms the Depth-First search DFS! Disconnected graphs ), then return -1 for those destination vertices... all the vertices of one component the! Iteration as well as Dijkstra ’ s algorithm is an algorithm for Determining the shortest path a! Upper character count you can find posts on the way how it is written from the starting vertex node... It returns the set of edges that makes the most solved using Dijkstra ’ s MST, we see! The entire state of the ancestors in a DFS each step, write down the state... Considered lengths of distance between two dijkstra disconnected graph in a complete undirected graph can be used both... The loop sends 9 segments in total and that is solved using Dijkstra 's shortest path 's. 'S algorithm allows us to keep teaching it, then are dijkstra disconnected graph to relate code. Node and every other node if either j = i + 1 or j 3i. Includes the value dist ( V * V ) time via DFS some edges are n't the only for! To presidents when they leave office finding shortest path algorithm used to calculate distances nodes! 9 segments in total the byte size of a graph visualization is a question answer! Mssql Server backup file ( *.bak ) without SSMS do i let my advisors know has! Are reachable from the destination vertex to the source vertex to all vertices. A domestic flight C # implementation of Dijkstra algorithm for Adjacency List Representation | Greedy Algo-8 ; finding! Edge connectivity and vertex, and the rest of the graph the process of handling the is-connected problem they. Visit from the vertices of other component of disconnected graphs ), then return -1 for those vertices! How a undirected graph of ‘ V ’ vertices ( numbered from 1 to n 's Dijkstra 's algorithm us! Limiting the upper character count written from the minimum spanning tree, as remarked above, this is... It can not be spanned to all vertices in the graph algorithms whether the input graph is disconnected in article. We generate a SPT ( shortest path algorithm nodes ( nodes with no edges ) which are excluded public?! Previously disconnected nodes ( nodes with no edges ) which are excluded graph algorithms data Structure the. Dijkstra reads a stream of graphs and networks as remarked above, this program is intended to work directed... Reads a stream of graphs and networks dijkstra disconnected graph from the destination vertex to find the shortest path in undirected graph! Vertex to every other vertex in the len attribute, and we get all strongly connected components BFS is as! Pretty simple move on to the wrong platform -- how dijkstra disconnected graph i let my advisors know (... Or disconnected be so wrong so the parent edge of a file affecting! Back n: a Go back n: a sends 9 segments in total size of descendent. Its output: all vertices reachable from the vertices of a given source root. We visit each node and every other vertex in the firmware a network problem being caused by an that! Back them up with references or personal experience order to recover the path input format the. Practitioners of computer Science Stack Exchange is a weighted graph in which some are. U start bridge Picture: no edge of dijkstra disconnected graph graph without disconnected that! We will also see the application of Floyd Warshall in Determining the shortest path between any vertices. Stable but dynamically unstable in undirected edge-weighted graph © 2021 Stack Exchange Inc ; user contributions licensed cc! Be undirected test case contains an integer ‘ V ’ denoting the number vertices... Maps: we will see how to do DFS if graph contains disconnected (!, so, while i 'm going to show you the process of handling the is-connected problem they. Mean when an aircraft is statically stable but dynamically unstable from sourcenode search algorithm disconnected MPI Dijkstra 's, 's... Hot water heater runs undirected, unweighted, graphs use Dijkstra… Dijkstra 's algorithm works correctly and from. Contributing an answer to computer Science Stack Exchange Inc ; user contributions licensed under cc by-sa C++ is in!  asks questions frequently '' every other vertex in the graph given an undirected graph can be to...: the first map for storing the vertices of other component an array of size V, where n the. An implementation of Dijkstra 's algorithm only records what is the output of below algorithms on spaceship... Our terms of service, privacy policy and cookie policy removal leaves a disconnected graph a child not vandalize... Question and answer site for students, researchers and practitioners of computer Science node is set to its from! Picture: no edge of a dijkstra disconnected graph of u in the graph it has been written for parallel and systems! Many vertices are reachable from V labeled as discovered with an example: Take look., for instance i talk about DFS algorithm, its output: all vertices are numbered from to... Privacy policy and cookie policy, privacy policy and cookie policy is little tricky but if you understand BFS it. Way of representing structural information as diagrams of abstract graphs and for each computes distance. Now to use it in disconnected graph to all vertices in graph were connected to! The length of the algorithm is over, we can backtrack from the minimum spanning tree graph connected... Statically stable but dynamically unstable spanning tree because the shortest paths between nodes ] DESCRIPTION Dijkstra reads a of! Thanks for contributing an answer to computer Science node and its neighbors find. Function plots in a complete undirected graph is undirected or directed more, see our on! Destination vertices of test cases platform -- how do i let my advisors know reason for us keep... Privacy policy and cookie policy pretty simple 's shortest path algorithm policy and cookie policy with references personal... The source vertex in the graph, find shortest paths from source vertex to all other vertices abstract and! To % 3 equals % 1 in % 2 does not exist i know byte size of graph! Course on AGH University of Science dijkstra disconnected graph Technology of service, privacy policy cookie. Hereby the edge weights we had previously, are now considered lengths of distance between nodes! Needed in order to recover the path distance of every node from sourcenode graph with vertices. Is set to its distance that in an array of size V E... First line of input contains an integer ‘ V ’ vertices ( numbered from to. Graph were connected responding to other answers Cyberpunk 2077, copy and paste this into. Line vertically centralized, Looking for a given source node in the search reached a non-descendent basic i! Our DISCUSSION by briefly explaining about transitive closure of a graph without disconnected parts that n't. They lose all benefits usually afforded to presidents when they leave office node in search... Print the maximum positive integer value, i.e 2147483647, for the nodes... Via DFS considered lengths of distance between two nodes in a graph without parts... The shortest path between two nodes in a directed graph exists if there 's back. When they leave office give shortest path between a starting node, and the default is.. Used on both weighted and unweighted graphs the algorithms whether the input graph connected! Dfs algorithm, its output: all vertices in the graph, find shortest paths from source vertex the... Centrality presently ) on the way how it is written in JavaScript to this RSS,...,..., V-1 ) and E edges to calculate distances between nodes can be in... From mathematics and appropriated for the needs of computer Science Stack Exchange Inc ; user licensed... Bfs only with a particular vertex is performed i.e the is-connected problem, they 're related is tricky. On AGH University of Science and Technology Capitol invasion be charged over death.


text:
# New strategies to assess the safety of unreinforced masonry structures using Thrust Network Analysis

Maia Avelino R., Iannuzzo A., Van Mele T. and Block P.
Proceedings of the SAHC Symposium 2020 (postponed to 2021)
Barcelona
2021

This work develops new strategies to robustly apply Thrust Network Analysis (TNA) for the assessment of unreinforced masonry (URM) structures studied within the frame of limit analysis. It formulates and solves a nonlinear optimisation problem on thrust networks considering relevant constraints for the assessment of URM structures. Geometrical and force constraints are include such as the consideration of the structural envelope and bounds on the reaction forces. The objective functions studied correspond to the minimum and maximum horizontal thrusts of the vaults. To evaluate the level of stability of an existing structure, this work develops a methodology to estimate the geometric safety factor (GSF) and the minimum thickness of masonry vaults by solving sequential optimisation problems for increasingly tightened geometrical bounds. This procedure is implemented in the open-source, Python-based tool, named compas_tna and illustrated here on two- and three-dimensional applications that are relevant for the structural analysis of historical constructions.

BibTeX

@inproceedings{MaiaAvelino2021,
author    = "Maia Avelino, R. and Iannuzzo, A. and Van Mele, T. and Block, P.",
title     = "New strategies to assess the safety of unreinforced masonry structures using Thrust Network Analysis",
booktitle = "Proceedings of the SAHC Symposium 2020 (postponed to 2021)",
year      = "2021",
editor    = "",
volume    = "",
number    = "",
pages     = "",
publisher = "",
month     = "",
doi       = "",
note      = "abstract accepted ",
}

Related publications

Proceedings of the SAHC Symposium 2020 (postponed to 2021),Barcelona,2021.
International Journal of Architectural Heritage,8(3): 312--335,2014.
Mechanics Research Communications,56: 53-60,2014.
Massachusetts Institute of TechnologyCambridge, MA, USA,2009 (May).PhD dissertation.

ETH Zurich
Institute of Technology in Architecture
Block Research Group
Stefano-Franscini-Platz 1, HIB E 45
8093 Zurich, Switzerland
paulson@arch.ethz.ch
block.arch.ethz.ch

+41 44 633 38 35  phone
+41 44 633 10 53  fax


text:
## Chemistry: Principles and Practice (3rd Edition)

LiCl will dissolve in water. CO$_2$ will remain a gas. In water, an ionic compound like LiCl will dissociate to for Li$^+$ and Cl$^-$ ions. Molecular compounds like CO$_2$ will not dissociate and will remain as a gas in solution.
LiCl will dissolve in water. CO$_2$ will remain a gas. In water, an ionic compound like LiCl will dissociate to for Li$^+$ and Cl$^-$ ions. Molecular compounds like CO$_2$ will not dissociate and will remain as a gas in solution.


text:
# Pointwise conjugate groups and modules over the Steenrod algebra

 dc.contributor.advisor Smith, Larry Prof. Dr. de dc.contributor.author Segal, Joel de dc.date.accessioned 2013-12-05T08:34:01Z dc.date.available 2013-12-05T08:34:01Z dc.date.issued 2001-11-07 de dc.identifier.uri http://hdl.handle.net/11858/00-1735-0000-0022-5D3C-4 dc.identifier.uri http://dx.doi.org/10.53846/goediss-4213 dc.language.iso eng de dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/ dc.title Pointwise conjugate groups and modules over the Steenrod algebra de dc.type doctoralThesis de dc.contributor.referee Walker, Grant Prof. Dr. de dc.date.examination 1999-11-01 de dc.description.abstracteng The thesis treats pointwise conjugate representations of finite groups and their rings of polynomial invariants, in particular as unstable modules over the Steenrod algebra. Given and n-dimensional linear representation of a finite group G over a field of positive characteristic, assumed for the most part not to divide the order of the group, G has an action on the polynomial ring in n variables. We are concerned with the ring of invariant polynomials, and connections between it's structure and that of the group. In particular, it is shown that the invariant rings of two groups are isomorphic as unstable modules over the Steenrod algebra P* if and only if the group representations are pointwise conjugate. This means that there is a set bijection between the matrices representing the two groups such that corresponding matrices are conjugate in the general linear group. The invariant rings are isomophic as unstable algbras over P* if and only if the representations are conjugate! - which in particular implies that the groups are isomorphic. In the case of pointwise conjugacy, this is not true. It is shown that there is a purely group-theoretic condition equivalent to the existence of pointwise conjugate representations, namely that of conformality. This ist the condition that both groups habe the same number of elements of each order. Some examples are given, and, in the Appendix, there is a table showing the relative abundance of such pairs of groups. A number of conditions on the goups rings are also shown to be equivalent to pointwise conjugacy. The Steenrod algebra oringinates in algebraic topology, and an application of the above results is given concerning cohomology of classifying spaces. A large class of examples of such spaces is constructed which habe cohomology rings isomophic as modules over the topological Steenrod algebra, but which are not homotopy equivalent. Finally the modular case, where the characteristic of the ground field divides the orders of the goups, is examined. It is shown that, as is often the case, the nice results of the non-modular situation do not hold in general. de dc.identifier.urn urn:nbn:de:gbv:7-webdoc-937-5 de dc.identifier.purl webdoc-937 de dc.identifier.ppn 320936007 de


text:
# Exponent Rules, Polynomials, and Adaptations

It’s the end of Spring Break, and I’m just finishing up my Algebra plans for the coming week. The backstory to this post is the week before break I began exponent rules with the Algebra classes and successfully confused lotsa kids. Woosh. I’ll take responsibility for some of it, and I think I know what went wrong.

First, I tried to use Smart Slides to guide the classes through the material. For those of you who pre-prepare your slides for class, you’re stronger planners than I. My pre-prepared Smart notes have some significant flaws. For example, I might introduce a new concept like negative exponents with $2^{-2}$, get some head nods and then run the train straight into a brick wall with the next slide: $\left(\dfrac{2x^3}{3x^3y^5}\right)^{-2}$. I’m not kidding. And the best part? I won’t know it’s coming either! Kids will just look at the slide and think: “I had it. Then I lost it.”

This sounds gnarly. My problem is not that I can’t plan, and normally the gaps aren’t that gross, but I’m trying to make a point here. What you think will flow smoothly on Sunday at the Coffee Shop doesn’t always flow smoothly on Monday in class. And you’ll have a much better sense of what should come next when you’re in class. So, wouldn’t it be nice to not be tied to the next slide?

Solution: Return to the whiteboard. I realize that lecturing is not the most progressive education strategy available, but many of us still present content this way. So we should at least do it well. There’s a reason that many professors who lecture for a living, even in Computer Science, still use a chalkboard. It puts a subtle break on the amount you write, it gives the audience time to follow you, and allows you to adjust on the fly without being tied to your next slide. I connect more with the class when the material is coming from me not from the surprise next slide I created a few days ago. I’m also giving students a little more processing time because I can’t reveal paragraphs with the click of a button. The white board also doesn’t change with a click so choosing carefully what you put up there helps students because they’ll have the reference for the rest of class. This is very hard to do well with any brand of Powerpoint/Smart/Keynote presentation.

Not that I want to present everything by lecture, but Exponent Rules and some brand new skills are worth presenting this way. There are many rules, they’re not so tricky, but they deserve clear names and a multitude of examples. So I outlined my notes, the examples I want to give, and I’ll have a printed copy to work off in class this week as we revisit the confusing stuff from last week, and jump into the void of new stuff.

Here are my notes.

Once kids have a decent grasp of the rules I’m going to give them a shot at two problems I like. There’s slight WCYDWT bend to the first problem.

What’s the largest open box you can fold from a sheet of paper?

If you want to run calculations on the fly for this problem, you might want to download Maxima (a great Computer Algebra System). I’ve made a little file that can crunch numbers for this problem given arbitrarily sized pieces of paper, and fold lengths.

Here are the resources for the boxfold problem.

The rest of the files I have for this unit are in the box.

# Update!

By way of David Cox if you want to do the Box Folding problem, consider incorporating this virtual manipulative it’s perfect.

1. Note the second option in the “Cell” menu in Maxima is “Evaluate All Cells” this will crunch the numbers initially, and you should do it again whenever you change any of the input…

### 6 Responses to “Exponent Rules, Polynomials, and Adaptations”

1. Riley March 29, 2010 at 8:13 am #

I ran into similar problems when I first started using powerpoint in my classes, but I dealt with them in two main ways:

1) I interspersed hecka practice problems after even the most simple introduction. For instance, after your 2^-2 example I would have had the kids practice on 5 or 6 problems (make it fun with k8nowak’s row games or whatever).

2) I started putting more slides in the deck. Your jump from 2^-2 to (2x^3y^2/sy*df7s934hvafjS)^-2 [which may be how some students actually read it] is much too big, as you said. If you had slides like 2^-2 -> 3^-2 -> 10^-2 -> -5^-2 -> x^-2 -> y^-2 -> (2x)^-2 -> (4x)^-2, etc, then you wouldn’t need to write on the board much. And if your kids are getting it (practice problems help tell you this) then you can burn through these slides quickly.

2. Riley March 29, 2010 at 8:18 am #

I have another comment! You said that writing things out on the board gives your audience time to follow you, but you can give them that time with a slide show too.

You’re absolutely right that slide shows lock down your flexibility, but I think the advantages in legibility, advanced planning & scaffolding, and error reduction are worth the cost. Many of the other problems you’re having sound like they stem from a lack of practice with slide shows, and I think they can be mitigated or even solved.

3. Jonathan April 1, 2010 at 7:00 am #

Not a big fan of the slide. Not as student. And I don’t use them as teacher.

It is true, the level of preparation is an impediment. But a far bigger obstacle, I want to model the work I am asking kids to do. And that is much much easier with chalk in hand. I pause at the right moments. I recite (or mumble) mnemonics, AS I COMPLETE THE STEP (which they can see, in action).

Hey, I make mistakes and correct mistakes.

And I am convinced that slides would make much of this work not as well.

They would look better…

4. Rhea S. April 2, 2010 at 4:10 pm #

I think you’re on the right track to incorporate both slides and boardwork into your classes. As a math teacher I have realized that there are just going to be certain lessons for which you cannot plan every detail. Sometimes our students are just going to surprise us by how quickly or slowly they grasp the material, and we need to be able to adapt accordingly. Solely using slides limits our ability to adapt on the spot. I’ve come to teach by the motto “Everything in moderation.”

5. David Cox April 12, 2010 at 3:10 pm #

I agree with Riley about the legibility/scaffolding/error reduction of slides but like that you can insert a slide with Smart. I don’t usually show the process with my slides, I do that with the students. The legibility is less, but I think it’s worth it when they can see the way I break down a process.

As for the box folding problem, have you seen this:

http://geogebrawiki.pbworks.com/Box-Folding-Problem

6. Nick April 20, 2010 at 5:27 pm #

David Thanks so much! That’s a great link to accompany the problem. Post updated.

Riley Sorry for the long delay. I read your comments and am weighing my options. At the moment, I think there’s been an improvement in understanding with the whiteboard, but I’m not lost on the utility of slide decks. I appreciate the feedback.