text:
# Unicorns break into RTS: analyzing the OpenRA source code

This article is about the check of the OpenRA project using the static PVS-Studio analyzer. What is OpenRA? It is an open source game engine designed to create real-time strategies. The article describes the analysis process, project features, and warnings that PVS-Studio has issued. And, of course, here we will discuss some features of the analyzer that made the project checking process more comfortable.

## OpenRA

The project chosen for the check is a game engine for RTS in the style of games such as Command & Conquer: Red Alert. More information can be found on the website. The source code is written in C# and is available for viewing and using in the repository.

There were 3 reasons for choosing OpenRA for a review. First, it seems to be of interest to many people. In any case, this applies to the inhabitants of GitHub, since the repository has reached the rating of more than 8 thousand stars. Second, the OpenRA code base contains 1285 files. Usually this amount is quite enough to hope to find interesting warnings in them. And third… Game engines are cool.

## Redundant warnings

I analyzed OpenRA using PVS-Studio and at first was encouraged by the results:

I decided that among so many High level warnings, I could definitely find a whole lot of different sapid errors. Therefore, based on them, I would write the coolest and most intriguing article :) But no such luck!

One glance at the warnings and everything clicked into place. 1,277 of the 1,306 High level warnings were related to the V3144 diagnostic. It gives messages of the type "This file is marked with a copyleft license, which requires you to open the derived source code". This diagnostic is described in more detail here.

Obviously, I wasn't interested in warnings of such kind, as OpenRA is already an open source project. Therefore, they had to be hidden so that they didn't interfere with viewing the rest of the log. Since I used the Visual Studio plugin, it was easy to do so. I just had to right-click on one of the V3144 warnings and select "Hide all V3144 errors" in the opening menu.

You can also choose which warnings will be displayed in the log by going to the "Detectable Errors (C#)" section in the analyzer options.

To go to them using the plugin for Visual Studio 2019, click on the top menu Extensions->PVS-Studio->Options.

## Check results

After the V3144 warnings were filtered out, there were significantly fewer warnings in the log:

Nevertheless, I managed to find worthy ones among them.

### Meaningless conditions

Quite a few positives pointed to unnecessary checks. This may indicate an error, because people usually don't write this code intentionally. However, in OpenRA, it often looks as if these unnecessary conditions were added on purpose. For example:

public virtual void Tick()
{
....

Active = !Disabled && Instances.Any(i => !i.IsTraitPaused);
if (!Active)
return;

if (Active)
{
....
}
}

Analyzer warning: V3022 Expression 'Active' is always true. SupportPowerManager.cs 206

PVS-Studio quite rightly notes that the second check is meaningless, because if Active is false, it won't execute. It might be an error, but I think it was written intentionally. What for? Well, why not?

Perhaps, what we have here is a temporary solution, which was supposed to be refined later. In such cases, it is quite convenient that the analyzer will remind a developer of such shortcomings.

Let's look at another just-in-case check:

Pair<string, bool>[] MakeComponents(string text)
{
....

if (highlightStart > 0 && highlightEnd > highlightStart)  // <=
{
if (highlightStart > 0)                                 // <=
{
// Normal line segment before highlight
var lineNormal = line.Substring(0, highlightStart);
}

// Highlight line segment
var lineHighlight = line.Substring(
highlightStart + 1,
highlightEnd - highlightStart – 1
);
line = line.Substring(highlightEnd + 1);
}
else
{
// Final normal line segment
break;
}
....
}

Analyzer warning: V3022 Expression 'highlightStart > 0' is always true. LabelWithHighlightWidget.cs 54

Again, it is obvious that re-checking is completely pointless. The value of highlightStart is checked twice, right in neighbouring lines. A mistake? It is possible that in one of the conditions wrong variables are selected for checking. Anyway, it's hard to say for sure what's going on here. One thing is definitely clear — the code should be reviewed and corrected. Or there should be an explanation if additional check is still needed for some reason.

Here is another similar case:

public static void ButtonPrompt(....)
{
....
var cancelButton = prompt.GetOrNull<ButtonWidget>(
"CANCEL_BUTTON"
);
....

if (onCancel != null && cancelButton != null)
{
cancelButton.Visible = true;
cancelButton.OnClick = () =>
{
Ui.CloseWindow();
if (onCancel != null)
onCancel();
};

if (!string.IsNullOrEmpty(cancelText) && cancelButton != null)
cancelButton.GetText = () => cancelText;
}
....
}

Analyzer warning: V3063 A part of conditional expression is always true if it is evaluated: cancelButton != null. ConfirmationDialogs.cs 78

cancelButton can be null indeed, because the value returned by the GetOrNull method is written to this variable. However, it stands to reason that by no means will cancelButton turn to null in the body of the conditional operator. Yet the check is still present. If you don't pay attention to the external condition, you happen to be in a very strange situation. First the variable properties are accessed, and then the developer decides to make sure if there is null or not.

At first, I assumed that the project might be using some specific logic related to overloading the "==" operator. In my opinion, implementing something like this in a project for reference types is a controversial idea. Not to mention the fact that unusual behavior makes it harder for other developers to understand the code. At the same time, it is difficult for me to imagine a situation where you can't do without such tricks. Although it is likely that in some specific case this would be a convenient solution.

In the Unity game engine, for example, the "==" operator is redefined for the UnityEngine.Object class. The official documentation available by the link shows that comparing instances of this class with null doesn't work as usual. Well, the developer probably had reasons for implementing this unusual logic.

I didn't find anything like this in OpenRA :). So if there is any meaning in the null checks discussed earlier, it is something else.

PVS-Studio managed to find a few more similar cases, but there is no need to list them all here. Well, it's a bit boring to watch the same triggers. Fortunately (or not), the analyzer was able to find other oddities.

### Unreachable code

void IResolveOrder.ResolveOrder(Actor self, Order order)
{
....
if (!order.Queued || currentTransform == null)
return;

if (!order.Queued && currentTransform.NextActivity != null)
currentTransform.NextActivity.Cancel(self);

....
}

Analyzer warning: V3022 Expression '!order.Queued && currentTransform.NextActivity != null' is always false. TransformsIntoTransforms.cs 44

Once again, we have a pointless check here. However, unlike the previous ones, this is not just an extra condition, but a real unreachable code. The always true checks above didn't actually affect the program's performance. You can remove them from the code, or you can leave them – nothing will change.

Whereas in this case, the strange check results in the fact that a part of the code isn't executed. At the same time, it is difficult for me to guess what changes should be made here as an amendment. In the simplest and most preferable scenario, unreachable code simply shouldn't be executed. Then there is no mistake. However, I doubt that the programmer deliberately wrote the line just for the sake of beauty.

### Uninitialized variable in the constructor

public class CursorSequence
{
....

public CursorSequence(
FrameCache cache,
string name,
string cursorSrc,
string palette,
MiniYaml info
)
{
var d = info.ToDictionary();

Start = Exts.ParseIntegerInvariant(d["Start"].Value);
Palette = palette;
Name = name;

if (
(d.ContainsKey("Length") && d["Length"].Value == "*") ||
(d.ContainsKey("End") && d["End"].Value == "*")
)
Length = Frames.Length - Start;
else if (d.ContainsKey("Length"))
Length = Exts.ParseIntegerInvariant(d["Length"].Value);
else if (d.ContainsKey("End"))
Length = Exts.ParseIntegerInvariant(d["End"].Value) - Start;
else
Length = 1;

Frames = cache[cursorSrc]
.Skip(Start)
.Take(Length)
.ToArray();

....
}
}

Analyzer warning: V3128 The 'Frames' field is used before it is initialized in constructor. CursorSequence.cs 35

A nasty case. An attempt to get the Length property value from an uninitialized variable will inevitably result in the NullReferenceException. In a normal situation, it is unlikely that such an error would have gone unnoticed – yet the inability to create an instance of the class is easily detected. But here the exception will only be thrown if the condition

(d.ContainsKey("Length") && d["Length"].Value == "*") ||
(d.ContainsKey("End") && d["End"].Value == "*")

is true.

It is difficult to judge how to correct the code so that everything is fine. I can only assume that the function should look something like this:

public CursorSequence(....)
{
var d = info.ToDictionary();

Start = Exts.ParseIntegerInvariant(d["Start"].Value);
Palette = palette;
Name = name;
ISpriteFrame[] currentCache = cache[cursorSrc];

if (
(d.ContainsKey("Length") && d["Length"].Value == "*") ||
(d.ContainsKey("End") && d["End"].Value == "*")
)
Length = currentCache.Length - Start;
else if (d.ContainsKey("Length"))
Length = Exts.ParseIntegerInvariant(d["Length"].Value);
else if (d.ContainsKey("End"))
Length = Exts.ParseIntegerInvariant(d["End"].Value) - Start;
else
Length = 1;

Frames = currentCache
.Skip(Start)
.Take(Length)
.ToArray();

....
}

In this version, the stated problem is absent, but only the developer can tell to what extent it corresponds to the original idea.

### Potential typo

public void Resize(int width, int height)
{
var oldMapTiles = Tiles;
var oldMapResources = Resources;
var oldMapHeight = Height;
var oldMapRamp = Ramp;
var newSize = new Size(width, height);

....
Tiles = CellLayer.Resize(oldMapTiles, newSize, oldMapTiles[MPos.Zero]);
Resources = CellLayer.Resize(
oldMapResources,
newSize,
oldMapResources[MPos.Zero]
);
Height = CellLayer.Resize(oldMapHeight, newSize, oldMapHeight[MPos.Zero]);
Ramp = CellLayer.Resize(oldMapRamp, newSize, oldMapHeight[MPos.Zero]);
....
}

Analyzer warning: V3127 Two similar code fragments were found. Perhaps, this is a typo and 'oldMapRamp' variable should be used instead of 'oldMapHeight' Map.cs 964

The analyzer detected a suspicious fragment associated with passing arguments to the function. Let's look at the calls separately:

CellLayer.Resize(oldMapTiles,     newSize, oldMapTiles[MPos.Zero]);
CellLayer.Resize(oldMapResources, newSize, oldMapResources[MPos.Zero]);
CellLayer.Resize(oldMapHeight,    newSize, oldMapHeight[MPos.Zero]);
CellLayer.Resize(oldMapRamp,      newSize, oldMapHeight[MPos.Zero]);

Oddly enough, the last call passes oldMapHeight, not oldMapRamp. Of course, not all such cases are erroneous. It is quite possible that everything is written correctly here. But you will probably agree that this place looks unusual. I'm inclined to believe that there is an error for sure.

Note by a colleague Andrey Karpov. I don't see anything strange in this code :). It's a classic last line mistake!

If there is no error, then one should add some explanation. After all, if a snippet looks like an error, then someone will want to fix it.

### True, true and nothing but true

The project revealed very peculiar methods, the return value of which is of the bool type. Their uniqueness lies in the fact that they return true under any conditions. For example:

static bool State(
S server,
Connection conn,
Session.Client client,
string s
)
{
var state = Session.ClientState.Invalid;
if (!Enum<Session.ClientState>.TryParse(s, false, out state))
{
server.SendOrderTo(conn, "Message", "Malformed state command");
return true;
}

client.State = state;

Log.Write(
"server",
"Player @{0} is {1}",
conn.Socket.RemoteEndPoint,
client.State
);

server.SyncLobbyClients();

CheckAutoStart(server);

return true;
}

Analyzer warning: V3009 It's odd that this method always returns one and the same value of 'true'. LobbyCommands.cs 123

Is everything OK in this code? Is there an error? It looks extremely strange. Why haven't the developer used void?

It's not surprising that the analyzer finds such a place strange, but we still have to admit that the programmer actually had a reason to write this way. Which one?

I decided to check where this method is called and whether its returned always true value is used. It turned out that there is only one reference to it in the same class – in the commandHandlers dictionary, which has the type

IDictionary<string, Func<S, Connection, Session.Client, string, bool>>

During the initialization, the following values are added to it

{"state", State},
{"startgame", StartGame},
{"slot", Slot},
{"allow_spectators", AllowSpectators}

and others.

Here we have a rare (I'd like to think so) case of static typing that creates problems for us. After all, to make a dictionary in which the values are functions with different signatures… is at least challenging. commandHandlers is only used in the InterpretCommand method:

public bool InterpretCommand(
S server, Connection conn, Session.Client client, string cmd
)
{
if (
server == null ||
conn == null ||
client == null ||
!ValidateCommand(server, conn, client, cmd)
)  return false;

var cmdName = cmd.Split(' ').First();
var cmdValue = cmd.Split(' ').Skip(1).JoinWith(" ");

Func<S, Connection, Session.Client, string, bool> a;
if (!commandHandlers.TryGetValue(cmdName, out a))
return false;

return a(server, conn, client, cmdValue);
}

Apparently, the developer intended to have the universal possibility to match strings to certain operations. I think that the chosen method is not the only one, but it is not so easy to offer something more convenient/correct in such a situation. Especially if you don't use dynamic or something like that. If you have any ideas about this, please leave comments. I would be interested to look at various solutions to this problem:).

It turns out that warnings associated with always true methods in this class are most likely false. And yet… What disquiets me here is this ''most likely'' :) One has to really be careful and not miss an actual error among these positives.

All such warnings should be first carefully checked, and then marked as false if necessary. You can simply do it. You should leave a special comment in the place indicated by the analyzer:

static bool State(....) //-V3009

There is another way: you can select the warnings that need to be marked as false, and click on "Mark selected messages as False Alarms" in the context menu.

### Extra check for null?

static bool SyncLobby(....)
{
{
server.SendOrderTo(conn, "Message", "Only the host can set lobby info");
return true;
}

var lobbyInfo = Session.Deserialize(s);
if (lobbyInfo == null)                    // <=
{
server.SendOrderTo(conn, "Message", "Invalid Lobby Info Sent");
return true;
}

server.LobbyInfo = lobbyInfo;

server.SyncLobbyInfo();

return true;
}

Analyzer warning: V3022 Expression 'lobbyInfo == null' is always false. LobbyCommands.cs 851

Here we have another method that always returns true. However, this time we are looking at a different type of a warning. We have to pore over such places with all diligence, as there is no guarantee that we deal with redundant code. But first things first.

The Deserialize method never returns null – you can easily see this by looking at its code:

public static Session Deserialize(string data)
{
try
{
var session = new Session();
....
return session;
}
catch (YamlException)
{
throw new YamlException(....);
}
catch (InvalidOperationException)
{
throw new YamlException(....);
}
}

For ease of reading, I have shortened the source code of the method. You can see it in full by clicking on the link. Or take my word for it that the session variable doesn't turn to null under any circumstances.

So what do we see at the bottom part? Deserialize doesn't return null, and if something goes wrong, it throws exceptions. The developer who wrote the null check after the call was of a different mind, apparently. Most likely, in an exceptional situation, the SyncLobby method should execute the code that is currently being executed… Actually, it is never executed, because lobbyInfo is never null:

if (lobbyInfo == null)
{
server.SendOrderTo(conn, "Message", "Invalid Lobby Info Sent");
return true;
}

I believe that instead of this "extra" check, the author still needs to use try-catch. Or try another tack and write, let's say, TryDeserialize, which in case of an exceptional situation will return null.

### Possible NullReferenceException

public ConnectionSwitchModLogic(....)
{
....
var logo = panel.GetOrNull<RGBASpriteWidget>("MOD_ICON");
if (logo != null)
{
logo.GetSprite = () =>
{
....
};
}

if (logo != null && mod.Icon == null)                    // <=
{
// Hide the logo and center just the text
if (title != null)
title.Bounds.X = logo.Bounds.Left;

if (version != null)
version.Bounds.X = logo.Bounds.X;
width -= logo.Bounds.Width;
}
else
{
// Add an equal logo margin on the right of the text
width += logo.Bounds.Width;                           // <=
}
....
}

Analyzer warning: V3125 The 'logo' object was used after it was verified against null. Check lines: 236, 222. ConnectionLogic.cs 236

As for this case, I'm sure as hell there is an error. We are definitely not looking at "extra" checks, because the GetOrNull method can indeed return a null reference. What happens if logo is null? Accessing the Bounds property will result in an exception, which was clearly not part of the developer's plans.

Perhaps, the fragment needs to be rewritten in the following way:

if (logo != null)
{
if (mod.Icon == null)
{
// Hide the logo and center just the text
if (title != null)
title.Bounds.X = logo.Bounds.Left;

if (version != null)
version.Bounds.X = logo.Bounds.X;
width -= logo.Bounds.Width;
}
else
{
// Add an equal logo margin on the right of the text
width += logo.Bounds.Width;
}
}

This option is quite simple for comprehension, although the additional nesting doesn't look too great. As a more comprehensive solution, one could use the null-conditional operator:

// Add an equal logo margin on the right of the text
width += logo?.Bounds.Width ?? 0; // <=

By the way, the first version looks more preferable to me. It is easy to read it and triggers no questions. But some developers appreciate brevity quite highly, so I also decided to cite the second version as well :).

### Maybe, OrDefault after all?

public MapEditorLogic(....)
{
var editorViewport = widget.Get<EditorViewportControllerWidget>("MAP_EDITOR");

var gridButton = widget.GetOrNull<ButtonWidget>("GRID_BUTTON");
var terrainGeometryTrait = world.WorldActor.Trait<TerrainGeometryOverlay>();

if (gridButton != null && terrainGeometryTrait != null) // <=
{
....
}

var copypasteButton = widget.GetOrNull<ButtonWidget>("COPYPASTE_BUTTON");
if (copypasteButton != null)
{
....
}

var copyFilterDropdown = widget.Get<DropDownButtonWidget>(....);
copyFilterDropdown.OnMouseDown = _ =>
{
copyFilterDropdown.RemovePanel();
copyFilterDropdown.AttachPanel(CreateCategoriesPanel());
};

var coordinateLabel = widget.GetOrNull<LabelWidget>("COORDINATE_LABEL");
if (coordinateLabel != null)
{
....
}

....
}

Analyzer warning: V3063 A part of conditional expression is always true if it is evaluated: terrainGeometryTrait != null. MapEditorLogic.cs 35

Let's delve into this fragment. Note that each time the GetOrNull method of the Widget class is used, a null equality check is performed. However, if Get is used, there is no check. This is logical – the Get method doesn't return null:

public T Get<T>(string id) where T : Widget
{
var t = GetOrNull<T>(id);
if (t == null)
throw new InvalidOperationException(....);
return t;
}

If the element is not found, an exception is thrown – this is reasonable behavior. At the same time, the logical option would be to check the values returned by the GetOrNull method for equality to the null reference.

In the code above, the value returned by the Trait method is checked for null. Actually it is inside the Trait method where Get of the TraitDictionary class is called:

public T Trait<T>()
{
return World.TraitDict.Get<T>(this);
}

Can it be that this Get behaves differently from the one we discussed earlier? Well, the classes are different. Let's check it out:

public T Get<T>(Actor actor)
{
CheckDestroyed(actor);
return InnerGet<T>().Get(actor);
}

The InnerGet method returns an instance of TraitContainer<T>. The Get implementation in this class is very similar to Get of the Widget class:

public T Get(Actor actor)
{
var result = GetOrDefault(actor);
if (result == null)
throw new InvalidOperationException(....);
return result;
}

The main similarity is that null is never returned here either. If something goes wrong, an InvalidOperationException is similarly thrown. Therefore, the Trait method behaves the same way.

Yes, there may just be an extra check that doesn't affect anything. Except that it looks strange, but you can't say that this code will confuse a reader much. But if the check is needed indeed, then in some cases an exception will be thrown unexpectedly. It is sad.

So in this fragment it seems more appropriate to call, for example, TraitOrNull. However, there is no such method:). But there is TraitOrDefault, which is the equivalent of GetOrNull for this case.

There is another similar case related to the Get method:

public AssetBrowserLogic(....)
{
....
frameSlider = panel.Get<SliderWidget>("FRAME_SLIDER");
if (frameSlider != null)
{
....
}
....
}

Analyzer warning: V3022 Expression 'frameSlider != null' is always true. AssetBrowserLogic.cs 128

The same as in the code considered earlier, there is something wrong here. Either the check is really unnecessary, or one still needs to call GetOrNull instead of Get.

### Lost assignment

public SpawnSelectorTooltipLogic(....)
{
....
var textWidth = ownerFont.Measure(labelText).X;
if (textWidth != cachedWidth)
{
label.Bounds.Width = textWidth;
widget.Bounds.Width = 2 * label.Bounds.X + textWidth; // <=
}

widget.Bounds.Width = Math.Max(                         // <=
teamWidth + 2 * labelMargin,
label.Bounds.Right + labelMargin
);
team.Bounds.Width = widget.Bounds.Width;
....
}

Analyzer warning: V3008 The 'widget.Bounds.Width' variable is assigned values twice successively. Perhaps this is a mistake. Check lines: 78, 75. SpawnSelectorTooltipLogic.cs 78

It seems that if the textWidth != cachedWidth condition is true, widget.Bounds.Width must be written to a specific value for this case. However, an assignment made below, regardless of whether this condition is true, makes the string

widget.Bounds.Width = 2 * label.Bounds.X + textWidth;

pointless. It is likely that the author just forgot to write else here:

if (textWidth != cachedWidth)
{
label.Bounds.Width = textWidth;
widget.Bounds.Width = 2 * label.Bounds.X + textWidth;
}
else
{
widget.Bounds.Width = Math.Max(
teamWidth + 2 * labelMargin,
label.Bounds.Right + labelMargin
);
}

### Checking the default value

public void DisguiseAs(Actor target)
{
....
var tooltip = target.TraitsImplementing<ITooltip>().FirstOrDefault();
AsPlayer = tooltip.Owner;
AsActor = target.Info;
AsTooltipInfo = tooltip.TooltipInfo;
....
}

Analyzer warning: V3146 Possible null dereference of 'tooltip'. The 'FirstOrDefault' can return default null value. Disguise.cs 192

When is FirstOrDefault usually used instead of First? If the selection is empty, First throws an InvalidOperationException. FirstOrDefault doesn't throw an exception, but returns null for the reference type.

The ITooltip interface implements various classes in the project. Thus, if target.TraitsImplementing<ITooltip>() returns an empty selection, null is written to tooltip. Accessing the properties of this object, which is executed next, will result in a NullReferenceException.

In cases where the developer is sure that the selection won't be empty, it is better to use First. If one isn't sure, it's worth checking the value returned by FirstOrDefault. It is rather strange that we don't see it here. After all, the values returned by the GetOrNull method mentioned earlier were always checked. Why didn't they do it here?

Who knows?.. All right, the developer will answer these questions for sure. In the end, it is the code author who will be fixing it :)

## Conclusion

OpenRA somehow turned out to be a project that was nice and interesting to scan. The developers did a lot of work and didn't forget that the source code should be easy to view. Of course, we did find some… controversies, but one can't simply do without them :)

At the same time, even with all the effort, alas, developers remain people. Some of the considered warnings are extremely difficult to notice without using the analyzer. It is sometimes difficult to find an error even immediately after writing it. Needless to say, how hard it is to search for error after a long time.

Obviously, it is much better to detect an error than its consequences. To do this, you can spend hours rechecking a huge number of new sources manually. Well, and have a bit of a look at the old ones — what if there is an oversight there? Yes, reviews are really useful, but if you have to view a large amount of code, then you stop noticing some things over time. And it takes a lot of time and effort.

Static analysis is just a convenient addition to other methods of checking the quality of source code, such as code review. PVS-Studio will find "simple" (and sometimes tricky) errors instead of a developer, allowing people to focus on more serious issues.

Yes, the analyzer sometimes gives false positives and is not able to find all the errors. But with it you will save a lot of time and nerves. Yes, it is not perfect and sometimes makes mistakes itself. However, in general, PVS-Studio makes the development process much easier, more enjoyable, and even (unexpectedly!) cheaper.

In fact, you don't need to take my word for it — it's much better to make sure that the above is true yourself. You can use the link to download the analyzer and get a trial key. What could be simpler?

Well, that's it for this time. Thanks for your attention! I wish you clean code and an empty error log!
PVS-Studio
Static Code Analysis for C, C++, C# and Java


text:
Post Reopened by Peter K.
Post Closed as "Needs details or clarity" by Peter K.
2 Minor formatting changes

Using a micro-processor of 48MHz, I am trying to output a sine wave from the DAC (digital to analog ), and I am not sure if my Nyquist and calculations are good.

1.I have to output sine in frequencies range of 1KHz to 3MHz

2.I have created an array of a sine samples that has 1000 points(for 1 period )

3.I am running a timer between samples, and the frequency calculation is :

float timerFrequency=sineFrequency*1000; //(timerT*1000=finalSineT)

1. I have to output sine in frequencies range of 1KHz to 3MHz

2. I have created an array of a sine samples that has 1000 points(for 1 period )

3. I am running a timer between samples, and the frequency calculation

float timerFrequency=sineFrequency*1000; //(timerT*1000=finalSineT)

But then I was thinking that for 3MHz sine wave, I will need a timer frequency of 3GHz with this approach(!). (3Mhz signal * 1000 sine samples)

Something here is very wrong with everything, because if I have a processor that is 48MHz, I can probably output a 3MHz , isn't it ?

1.Whats wrong with my approach, and what are my limits with these assumptions ?

2.Can I reduce the sine samples array to lets say 100 ? what would it do to the Nyqvist at 3MHz ?

3.How many samples should my sine array needs? (the min), and my timer frequency?

Thanks!

1. Whats wrong with my approach, and what are my limits with these assumptions ?

2. Can I reduce the sine samples array to lets say 100 ? what would it do to the Nyqvist at 3MHz ?

3. How many samples should my sine array needs? (the min), and my timer frequency?

Using a micro-processor of 48MHz, I am trying to output a sine wave from the DAC (digital to analog ), and I am not sure if my Nyquist and calculations are good.

1.I have to output sine in frequencies range of 1KHz to 3MHz

2.I have created an array of a sine samples that has 1000 points(for 1 period )

3.I am running a timer between samples, and the frequency calculation is :

float timerFrequency=sineFrequency*1000; //(timerT*1000=finalSineT)

But then I was thinking that for 3MHz sine wave, I will need a timer frequency of 3GHz with this approach(!). (3Mhz signal * 1000 sine samples)

Something here is very wrong with everything, because if I have a processor that is 48MHz, I can probably output a 3MHz , isn't it ?

1.Whats wrong with my approach, and what are my limits with these assumptions ?

2.Can I reduce the sine samples array to lets say 100 ? what would it do to the Nyqvist at 3MHz ?

3.How many samples should my sine array needs? (the min), and my timer frequency?

Thanks!

Using a micro-processor of 48MHz, I am trying to output a sine wave from the DAC (digital to analog ), and I am not sure if my Nyquist and calculations are good.

1. I have to output sine in frequencies range of 1KHz to 3MHz

2. I have created an array of a sine samples that has 1000 points(for 1 period )

3. I am running a timer between samples, and the frequency calculation

float timerFrequency=sineFrequency*1000; //(timerT*1000=finalSineT)

But then I was thinking that for 3MHz sine wave, I will need a timer frequency of 3GHz with this approach(!). (3Mhz signal * 1000 sine samples)

Something here is very wrong with everything, because if I have a processor that is 48MHz, I can probably output a 3MHz , isn't it ?

1. Whats wrong with my approach, and what are my limits with these assumptions ?

2. Can I reduce the sine samples array to lets say 100 ? what would it do to the Nyqvist at 3MHz ?

3. How many samples should my sine array needs? (the min), and my timer frequency?

1

# Output a sine wave from samples-limits?

Using a micro-processor of 48MHz, I am trying to output a sine wave from the DAC (digital to analog ), and I am not sure if my Nyquist and calculations are good.

1.I have to output sine in frequencies range of 1KHz to 3MHz

2.I have created an array of a sine samples that has 1000 points(for 1 period )

3.I am running a timer between samples, and the frequency calculation is :

float timerFrequency=sineFrequency*1000; //(timerT*1000=finalSineT)

But then I was thinking that for 3MHz sine wave, I will need a timer frequency of 3GHz with this approach(!). (3Mhz signal * 1000 sine samples)

Something here is very wrong with everything, because if I have a processor that is 48MHz, I can probably output a 3MHz , isn't it ?

1.Whats wrong with my approach, and what are my limits with these assumptions ?

2.Can I reduce the sine samples array to lets say 100 ? what would it do to the Nyqvist at 3MHz ?

3.How many samples should my sine array needs? (the min), and my timer frequency?

Thanks!

format: plain


text:
Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DISCRETE MEMORYLESS CHANNELS:
Reports tagged with discrete memoryless channels:
TR16-033 | 10th March 2016
Suppose Alice holds a uniformly random string $X \in \{0,1\}^N$ and Bob holds a noisy version $Y$ of $X$ where each bit of $X$ is flipped independently with probability $\epsilon \in [0,1/2]$. Alice and Bob would like to extract a common random string of min-entropy at least $k$. In this ... more >>>


text:
## Curve Modelling

Started by 3 years ago7 replieslatest reply 3 years ago142 views

Hi All,

I hope this question is OK here! If not, I'll go away...quickly.

I  want to understand how an estimation for a curve fit polynomial could be created. I'm not asking for one to be made...just how to go about it.

I have a lithium battery, and the data sheet has various curves of temperature for discharge rate of current (x-axis) against voltage (y-axis) . I imagine one way to do it is to create a table and interpolate between those points. It's rudimentary and would be close...but, by the curves, may not be close enough. Unless I enter a lot of points! I can't afford a voltage bump pulling too much current and would be better if I could get it as close as possible.

It would be ideal to pass in the x axis desired current at a specific temperature and see the resultant voltage. I imagine each temperature curve would have it's own cure fit polynomial. So what is the right way to go about this?

Thanks!

[ - ]

Hi Groger, not trying to be unkind here but did you try typing "how to estimate a polynomial curve fit" into box at www.google.com ? If so it would have shown you this link:

www.math.tamu.edu › ~glahodny › Math442 › Curve Fitting

### Curve Fitting and Parameter Estimation - TAMU Math

curve that best fits this data. The most common form of curve fitting is linear least squares regression. 1.1 Polynomial Regression. In order to develop an idea of ...

Which is a wonderful discussion of the techniques using MATLAB. I you don't have a MATLAB license (you can get a demo license for free) you can run gnu OCTAVE which has the same syntax and does the same stuff for free. There are versions for Windows, Linux and MacOS.

My goal here is to get your toolkit buffed with some of the tools you will find useful in day to day explorations of this space! If videos are more your style, watching the curve fitting videos on YouTube from Khan Academy () are also really great and full of all the bits you need with exercises to test your understanding. I can easily recommend them.

[ - ]

If you use Matlab, then I think these 2 very simple lines of code sum up Least Squares polynomial curve fitting very well:

C = bsxfun(@power, (0:L).', (0:N));
a = pinv(C)*y;

(where 0:L are the sample time indices, and N is the desired polynomial order). The first line simply creates a (L+1 x N+1) matrix, C, whose (n,p)th element is np. The second line forms the Moore-Penrose pseudoinverse of C and multiplies this with the observed data vector, y. The vector a then contains the coefficients of the Least Squares best fit polynomial.

I wrote some notes about this in a blog here but sadly the equation rendering is now broken on that site. I could move it into a blog here at dsprelated if it's of any interest.

[ - ]

Hello Groger, I am not sure to fully appreciate your problem and probably the previous answers would do the job nicely, but what strikes me is that you have a family of fits not only just one. If you want a parcimonious solution may be you should consider a 2-dimensionnal fit. You may consider your family of curves current I versus voltage V indexed by temperature T as the 2 dimensional cuts of a 3D function T(I,V). The interpolation problem may require base functions that differ from polynomials but if they are well chosen they may be very few. I am speculating... the only way to be sure is to look at your data.

Regards

[ - ]
I usually try 1st with Wolfram|Alpha
[ - ]

Hi,

Thanks for all of your answers! Appreciated. This is happening in a microcontroller so I have to derive the equation first and then apply the x-variable (current) for a specific T. The T isn't an issue, since I read that accurately.

I found this method on a youtube video and it seems that it will work good, since I have a set of given points and need only apply the x-variable of interest. It's called "Determine Polynomial equation from given set of data points by Finite Difference"

[ - ]


text:
Chromatic Clustering in High Dimensional Space

# Chromatic Clustering in High Dimensional Space

## Abstract

In this paper, we study a new type of clustering problem, called Chromatic Clustering, in high dimensional space. Chromatic clustering seeks to partition a set of colored points into groups (or clusters) so that no group contains points with the same color and a certain objective function is optimized. In this paper, we consider two variants of the problem, chromatic -means clustering (denoted as -CMeans) and chromatic -medians clustering (denoted as -CMedians), and investigate their hardness and approximation solutions. For -CMeans, we show that the additional coloring constraint destroys several key properties (such as the locality property) used in existing -means techniques (for ordinary points), and significantly complicates the problem. There is no FPTAS for the chromatic clustering problem, even if . To overcome the additional difficulty, we develop a standalone result, called Simplex Lemma, which enables us to efficiently approximate the mean point of an unknown point set through a fixed dimensional simplex. A nice feature of the simplex is its independence with the dimensionality of the original space, and thus can be used for problems in very high dimensional space. With the simplex lemma, together with several random sampling techniques, we show that a -approximation of -CMeans can be achieved in near linear time through a sphere peeling algorithm. For -CMedians, we show that a similar sphere peeling algorithm exists for achieving constant approximation solutions.

## 1 Introduction

Clustering is one of the most fundamental problems in computer science and finds applications in many different areas [3, 4, 6, 2, 9, 11, 12, 14, 16, 7, 10]. Most existing clustering techniques assume that the to-be-clustered data items are independent from each other. Thus each data item can “freely” determine its membership within the resulting clusters, without paying attention to the clustering of other data items. In recent years, there are also considerable attentions on clustering dependent data and a number of clustering techniques, such as correlation clustering, point-set clustering, ensemble clustering, and correlation connected clustering, have been developed [4, 7, 9, 11, 10].

In this paper, we consider a new type of clustering problems, called Chromatic Clustering, for dependent data. Roughly speaking, a chromatic clustering problem takes as input a set of colored data items and groups them into clusters, according to certain objective functions, so that no pair of items with the same color are grouped together (such a requirement is called chromatic constraint). Chromatic clustering captures the mutual exclusiveness relationship among data items and is a rather useful model for various applications. Due to the additional chromatic constraint, chromatic clustering is thus expected to simultaneously solve the “coloring” and clustering problems, which significantly complicates the problem. As it will be shown later, the chromatic clustering problem is challenging to solve even for the case that each color is shared only by two data items.

For chromatic clustering, we consider in this paper two variants, Chromatic -means Clustering (-CMeans) and Chromatic -median Clustering (-CMedians), in space, where the dimensionality could be very high and is a fixed number. In both variants, the input is a set of point-sets with each containing a maximum of points in -dimensional space, and the objective is to partition all points of into different clusters so that the chromatic constraint is satisfied and the total squared distance (i.e., -CMeans) or total distance (i.e., -CMedians) from each point to the center point (i.e., median or mean point) of its cluster is minimized.

Motivation: The chromatic clustering problem is motivated by several interesting applications. One of them is for determining the topological structure of chromosomes in cell biology [10]. In such applications, a set of 3D probing points (e.g., using BAC probes) is extracted from each homolog of the interested chromosome (see Figure 6 in Appendix), and the objective is to determine, for each chromosome homolog, the common spatial distribution pattern of the probes among a population of cells. For this purpose, the set of probes from each homolog is converted into a high dimensional feature point in the feature space, where each dimension represents the distance between a particular pair of probes. Since each chromosome has two (or more as in cancer cells) homologs, each cell contributes (i.e., two or more) feature points. Due to technical limitation, it is impossible to identify the same homolog from all cells. Thus, the feature points from each cell form a point-set with the same color (meaning that they are undistinguishable). To solve the problem, one could chromatically cluster all point-sets into clusters (after normalizing the cell size), with each corresponding to a homolog, and use the mean or median point of each cluster as its common pattern.

Related works: As its generalization, chromatic clustering is naturally related to the traditional clustering problem. Due to the additional chromatic constraint, chromatic clustering could behave quite differently from its counterpart. For example, the -means algorithms in [6, 15] relies on the fact that all input points in a Voronoi cell of the optimal mean points belong to the same cluster. However, such a key locality property no longer holds for the -CMeans problem.

Chromatic clustering falls in the umbrella of clustering with constraint. For such type of clustering, several solutions exist for some variants [5]. Unfortunately, due to their heuristic nature, none of them can yield quality guaranteed solutions for the chromatic clustering problem. The first quality guaranteed solution for chromatic clustering was obtained recently by Ding and Xu. In [10], they considered a special chromatic clustering problem, where every point-set has exactly points in the first quadrant, and the objective is to cluster points by cones apexed at the origin, and presented the first PTAS for constant . The -CMeans and -CMedians problems considered in this paper are the general cases of the chromatic clustering problem. Very recently, Arkin et al. [1] considered a chromatic 2D -center clustering problem and presented both approximation and exact solutions.

### 1.1 Main Results and Techniques

In this paper, we present three main results, a constant approximation and a -approximation for -CMeans and their extensions to -CMedians.

• Constant approximation: We show that given any -approximation for -means clustering, it could yield a -approximation for -CMeans. This not only provides a way for us to generate an initial constant approximation solution for -CMeans through some -means algorithm, but more importantly reveals the intrinsic connection between the two clustering problems.

• -approximation: We show that a near linear time -approximation solution for -CMeans can be obtained using an interesting sphere peeling algorithm. Due to the lack of locality property in -CMeans, our sphere peeling algorithm is quite different from the ones used in [15, 6], which in general do not guarantee a -approximation solution for -CMeans as shown by our first result. Our sphere peeling algorithm is based on another standalone result, called Simplex Lemma. The simplex lemma enables us to obtain an approximate mean point of a set of unknown points through a grid inside a simplex determined by some partial knowledge of the unknown point set. A unique feature of the simplex lemma is that the complexity of the grid is independent of the dimensionality, and thus can be used to solve problems in high dimensional space. With the simplex lemma, our sphere peeling algorithm iteratively generates the mean points of -CMeans with each iteration building a simplex for the mean point.

• Extensions to -CMedians: We further extend the idea for -CMeans to -CMedians. Particularly, we show that any -approximation for -medians can be used to yield a -approximation for -CMedians, where the error comes from the difficulty of computing the optimal median point (i.e., Fermat Weber point). With this and a similar sphere peeling technique, we obtain a -approximation for -CMedians. Note that although is a constant in this paper, a -approximation is still much better than a -approximation.

Due to space limit, many details of our algorithms, proofs, and figures are put in Appendix.

## 2 Preliminaries

In this section, we introduce some definitions which will be used throughout the paper.

###### Definition 1 (Chromatic Partition)

Let be a set of point-sets with each consisting of points in space. A chromatic partition of is a partition of the points into sets, , such that each contains no more than one point from each for .

###### Definition 2 (Chromatic k-means Clustering (k-CMeans))

Let be a set of point-sets with each consisting of points in space. The chromatic -means clustering (or -CMeans) of is to find points in space and a chromatic partition of such that is minimized. The problem is called full -CMeans if .

For both -CMedians and -CMeans, a problem often encountered in our approach is “How to find the best cluster for each point in if the mean or median points are already known?” An easy way to solve this problem is to first build a complete bipartite graph with points in and as the two partites and then compute a minimum weight bipartite matching as the solution, where the edge weight is the Euclidean distance or squared distance of the two corresponding vertices. Clearly, this can be done in a total of time for all ’s. (We call this procedure as bipartite matching.)

## 3 Hardness of k-CMeans

It is easy to see that -means is a special case of -CMeans (i.e., each contains exactly one point). As shown by Dasgupta [8], -means in high dimensional space is NP-hard even if . Thus, we immediately have the following theorem.

###### Theorem 3.1

-CMeans is NP-hard for in high dimensional space.

### 3.1 Is Full k-CMeans Easier?

It is interesting to know whether full -CMeans is easier than general -CMeans, since it is disjoint with -means when . The following theorem gives a negative answer to this question.

###### Theorem 3.2

Full -CMeans is NP-hard and has no FPTAS for in high dimensional space unless P=NP (see Appendix for the proof).

The above theorem indicates that the fullness of -CMeans does not reduce the hardness of the problem. However, this does not necessarily mean that full -CMeans is as difficult as general -CMeans to achieve a -approximation for fixed . Below we show that a -approximation can be relatively easily achieved for full -CMeans through some random sampling technique.

First we introduce a key lemma from [13]. Let be a set of points in space, be a randomly selected subset from with points, and , be the mean points of and respectively.

###### Lemma 1 ([13])

With probability , , where .

###### Lemma 2

Let be a set of elements, and be a subset of such that . If randomly select elements from , with probability at least , the sample contains at least elements from .

###### Proof

If we randomly select elements from , then it is easy to know that with probability , there is at least one element from the sample belonging to . If we want the probability equal to , has to be (by Taylor series and , ). Thus if we perform rounds of random sampling with each round selecting elements, we get at least elements from with probability at least . ∎

Lemma 1 tells us that if we want to find an approximate mean point within a distance of to the mean point, we just need to take a random sample of size . Lemma 2 suggests that for any set and its subset of size , we can have a random subset of with size by randomly sampling directly from points, even if is an unknown subset of . Combining the two lemmas, we can immediately compute an approximation solution for full -CMeans in the following way. First, we note that in full -CMeans, each optimal cluster contains exact points from the total of points in . This means that each cluster has a fraction of points from . Then, we can obtain an approximate mean point for each optimal cluster by (1) randomly sampling points from , (2) enumerating all possible subsets of size to find the set which is a random sample of the unknown optimal cluster, and (3) computing the mean of as the approximate mean point of the optimal cluster. Finally, we can generate the chromatic clusters from the approximate mean points by using the bipartite matching procedure (see Section 2).

###### Theorem 3.3

With constant probability, a -approximation of full -CMeans can be obtained in time.

With the above theorem, we only need to focus on the general -CMeans problem in the remaining sections. Note that in the general case, some clusters may have a very small fraction (rather than ) of points, thus we can not use the above method to solve the general -CMeans problem.

## 4 Constant Approximation from k-means

In this section, we show that a constant approximation solution for -CMeans can be produced from an approximation solution of -means. Below is the main theorem of this section.

###### Theorem 4.1

Let be an instance of -CMeans, and be the mean points of a constant -approximation solution of -means on the points . Then contains at least one -tuple which could induce a -approximation of -CMeans on , where .

To prove Theorem 4.1, we first introduce two lemmas.

###### Lemma 3

Let be a set of points in space, and be the mean point of . For any point , (see Appendix for the proof).

###### Lemma 4

Let be a set of points in space, and be its subset containing points for some . Let and be the mean points of and respectively. Then , where .

###### Proof

Let , and be its mean point. By Lemma 3 we first have the following two equalities.

 ∑p∈P1||p−m||2 = ∑p∈P1||p−m1||2+|P1|×||m1−m||2. (1) ∑p∈P2||p−m||2 = ∑p∈P2||p−m2||2+|P2|×||m2−m||2. (2)

Then by the definition of , we have . Let . By the definition of mean point, we have . Thus the three points are collinear, and and . Combining (1) and (2), we have

 δ2=1|P|(∑p∈P1||p−m1||2+|P1|×||m1−m||2+∑p∈P2||p−m2||2+|P2|×||m2−m||2) ≥1|P|(|P1|×||m1−m||2+|P2|×||m2−m||2)=α((1−α)L)2+(1−α)(αL)2=α(1−α)L.

Thus, we have , which means that . ∎

###### Proof (of Theorem 4.1)

Let be the mean points in , and be their corresponding clusters. Let be the unknown optimal mean points of -CMeans, and be the corresponding optimal chromatic clusters. Let , and be its mean point for .

Since , by pigeonhole principle we know that there must exist some index such that . Thus by fixing , we have the following about (see Figure 1)

 ∑p∈Opti||p−cji||2 = ∑p∈Opti||p−mi||2+|Opti|×||mi−cji||2=∑p∈Opti||p−mi||2+|Opti|×||mi−τiji+τiji−cji||2 (3) ≤ ∑p∈Opti||p−mi||2+|Opti|×(||mi−τiji||+||τiji−cji||)2 ≤ ∑p∈Opti||p−mi||2+|Opti|×2(||mi−τiji||2+||τiji−cji||2),

where the first equation follows from Lemma 3 (note that is the mean point of ), and the last inequality follows from the fact that for any numbers and . By Lemma 4, we have

 ||τiji−mi||2≤1−1k1k(1|Opti|∑p∈Opti||p−mi||2). (4) ||τiji−cji||2≤1−|Γiji||Sji||Γiji||Sji|(1|Sji|∑p∈Sji||p−cji||2). (5)

Plugging (4) and (5) into inequality (3), we have

 ∑p∈Opti||p−cji||2≤∑p∈Opti||p−mi||2+|Opti|×2(||mi−τiji||2+||τiji−cji||2) \vspace−0.05in≤∑p∈Opti||p−mi||2+|Opti|×2(1−1k1k(1|Opti|∑p∈Opti||p−mi||2)+1−|Γiji||Sji||Γiji||Sji|(1|Sji|∑p∈Sji||p−cji||2)) \vspace−0.05in=(2k−1)∑p∈Opti||p−mi||2+2|Opti||Γiji|×(1−|Γiji||Sji|)∑p∈Sji||p−cji||2).

Since , we have . Thus the above inequality becomes

 ∑p∈Opti||p−cji||2≤(2k−1)∑p∈Opti||p−mi||2+2k∑p∈Sji||p−cji||2. (6)

Summing both sides of (6) over , we have

 k∑i=1∑p∈Opti||p−cji||2≤(2k−1)k∑i=1∑p∈Opti||p−mi||2+2kk∑i=1∑p∈Sji||p−cji||2 ≤(2k−1)k∑i=1∑p∈Opti||p−mi||2+2k2k∑j=1∑p∈Sj||p−cj||2, (7)

where the second inequality follows from the inequality , which implies that .

It is obvious that the optimal objective value of -means is no larger than that of -CMeans on the same set of points in . Thus, . Plugging this inequality into inequality (7), we have

 k∑i=1∑p∈Opti||p−cji||2≤(2ck2+2k−1)k∑i=1∑p∈Opti||p−mi||2.

The above inequality means that if we take the -tuple as the approximate mean points for -CMeans, we have a -approximation solution, where the chromatic clusters can be obtained by the bipartite matching procedure. Thus, the theorem is proved. ∎

Running Time: In the above theorem, the bipartite matching procedure takes time for one -tuple. Since there are in total such -tuples, the total running time is for computing a -approximation of -CMeans from a -approximation of -means. As is assumed to be a constant in this paper, the running time is linear.

## 5 (1+ϵ)-Approximation Algorithm

This section presents our -approximation solution to the -CMeans problem. We first introduce a standalone result, Simplex Lemma, and then use it to achieve a -approximation for -CMeans. The main idea of the algorithm is to use a sphere peeling technique to generate the chromatic clusters iteratively, where the Simplex Lemma helps to determine a proper peeling region.

### 5.1 Simplex Lemma

Simplex Lemma is mainly for approximating the mean point of some unknown points set . The only known information about is a set of points with each of them being an approximate mean point of a subset of . The following Simplex lemmas show that it is possible to construct a simplex of and find the desired approximate mean point of inside the simplex.

###### Lemma 5 (Simplex Lemma \@slowromancapi@)

Let be a set of points in with a partition of and for any . Let be the mean point of , and be the mean point of for . Further, let , and be the simplex determined by . Then for any , it is possible to construct a grid of size inside such that at least one grid point satisfies the inequality .

###### Proof

We will prove this lemma by mathematical induction on .

Base case: For , since , . Thus, the simplex and the grid are all simply the point . Clearly satisfies the inequality.

Induction step: Assume that the lemma holds for any for some (i.e., Induction Hypothesis). Now we consider the case of . First, we assume that for each . Otherwise, we can reduce the problem to the case of smaller in the following way. Let be the index set of small subsets. Then, , and . By Lemma 4, we know that , where is the mean point of . Let be the variance of . Then, we have . Thus, if we replace and by and respectively, and find a point such that , we have (where the last inequality is due to the fact ). This means that we can reduce the problem to a problem with point set and a smaller (i.e., ). By the induction hypothesis, we know that the reduced problem can be solved (note that the simplex would be a subset of determined by ), and therefore the induction step holds for this case. Thus, in the following discussion, we can assume that for each .

For each , since , by Lemma 4, we know that . This, together with triangle inequality, implies that for any , . Thus, if we pick any index , and draw a ball centered at and with radius , the whole simplex will be inside . Note that since , also locates inside . This indicates that we can construct in the -dimensional space spanned by , rather than the whole space. Also, if we build a grid inside with grid length , the total number of grid points is no more than . With this grid, we know that for any point inside , there exists a grid point such that . This means that can find a grid point inside , such that . Thus, the induction step holds.

With the above base case and induction steps, the lemma holds for any . ∎

In the above lemma, we assume that the exact positions of are known (see Fig. 3). However, in some scenario (e.g., the exact partition of is not given, as is the case in -CMeans), it is possible that we only know the approximate position of each mean point (see Fig. 3). The following lemma shows that an approximate position of can still be similarly determined.

###### Lemma 6 (Simplex Lemma \@slowromancapii@)

Let , , , and, be defined as in Lemma 5. Let be points in such that for and , and be the simplex determined by . Then for any , it is possible to construct a grid of size inside such that at least one grid point satisfies the inequality .

### 5.2 Sphere Peeling Algorithm

This section presents a sphere peeling algorithm to achieve a -approximation for -CMeans.

Let be an instance of -CMeans with (unknown) optimal chromatic clusters , and be the mean point of the cluster for . Without loss of generality, we assume that .

Algorithm overview: Our algorithm first computes a constant -approximation solution (by Theorem 4.1) to determine an upper bound of the optimal objective value , and then search for a good approximation of in the interval of . At each search step, our algorithm performs a sphere peeling procedure to iteratively generate approximate mean points for the chromatic clusters. Initially, the sphere peeling procedure uses random sampling technique (i.e., Lemma 1 and 2) to find an approximate mean point for . At -th iteration, it already has approximate mean points for respectively. Then it draws peeling spheres, , centered at the approximate mean points respectively and with a radius determined by the approximation of . Denote the set of unknown points as . Our algorithm considers two cases: (a) is large enough and (b) is small. For case (a), since is large enough, we can first use Lemma 2 to find an approximate mean point of , and then construct a simplex determined by and . For case (b), it directly constructs a simplex determined just by . For either case, our algorithm builds a grid inside the simplex (i.e., using Lemma 6) to find an approximate mean point for (i.e., ). Repeat the sphere peeling procedure times to generate the approximate mean points.

Algorithm -CMeans
Input: , , and a small positive value .
Output: -approximation solution for -CMeans on .

1. Run the PTAS of -means in [15] on , and let be the obtained objective value.

2. For to do

1. Set , and run the Sphere-Peeling-Tree algorithm.

2. Let be the output tree.

3. For each path of every , use bipartite matching procedure to compute the objective value of -CMeans on . Output the points from the path with the smallest objective value.

Algorithm Sphere-Peeling-Tree
Input: , , .
Output: A tree of height with each node associating with a point .

1. Initialize with a single root node associating with no point.

2. Recursively grow each node in the following way

1. If the height of is already , then it is a leaf.

2. Otherwise, let be the height of . Build the radius candidates set . For each , do

1. Let be the points associated with nodes on the root-to- path.

2. For each , , construct a ball centered at and with radius .

3. Take a random sample from with size . Compute the mean points of all subset of the sample, and denote them as .

4. For each , construct the simplex determined by . Also construct the simplex determined by . Build a grid inside each simplex with size .

5. In total, there are grid points inside the simplices. For each grid point, add one child to , and associate it with the grid point.

###### Theorem 5.1

With constant probability, Algorithm -CMeans yields a -approximation for -CMeans in time.

### 5.3 Proof of Theorem 5.1

Let , and , where is the mean point of . Clearly, (by assumption) and . Let .

We prove Theorem 5.1 by mathematical induction. Instead of directly proving it, we consider the following two lemmas which jointly ensure the correctness of Theorem 5.1.

###### Lemma 7

Among all the trees generated in Algorithm -CMeans, with constant probability, there exists at least one tree, , which has a root-to-leaf path with each node at level , , on the path associating a point and satisfying the inequality

Before proving this lemma, we first show its implication.

###### Lemma 8

If Lemma 7 is true, Algorithm -CMeans yields a -approximation for -CMeans.

###### Proof

We first assume that Lemma 7 is true. Then for each , we have

 ∑p∈Optj||p−pvj||2 = ∑p∈Optj||p−mj||2


text:
# Interference in Thin Films?

premed

## Homework Statement

Light of wavelength $$\lambda$$ strikes a pane of glass of thickness T and refractice index n, as shown in figure(I attached a diagram I made). Part of the beam is reflected off the upper surface of the glass, and part is transmitted and then reflected off the lower surface of the glass. Destructive interference between these two beams will occur if :
a) T = $$\lambda$$ / 2
b) 2T = $$\lambda$$ / 2
c) T = $$\lambda$$ / 2n
d) 2T = $$\lambda$$ / 2n

## Homework Equations

2T= m$$\lambda$$

## The Attempt at a Solution

According to this equation, destructive interference occurs when 2T = $$\lambda$$ /2. Right? Since $$\lambda$$ = $$\lambda$$ $$_{0}$$ / n, then 2T= $$\lambda$$ / 2n right? The correct answer is C though. I got answer D. What am i doing wrong. Thanks

#### Attachments

• diagram1.doc
24.5 KB · Views: 171

Homework Helper
Hi premed,

In section 3 you have remarked that destructive interference occurs when $2 T = \lambda/2$. How did you find this? In your relevant equations section, you had already stated that the conditions for destructive interference was given by $2 T = m \lambda$.

In that equation, m is an integer (with appropriate restrictions) and $\lambda$ is the wavelength in the film; I don't think you can get $2 T = \lambda/2$ from that unless m=1/2 which is not allowed.

premed
Sorry. I'll clarify. The book gives the equation for constructice interfence as 2T=m$$\lambda$$ where m is an integer. For destructice interference 2T = (m+1/2)$$\lambda$$ . that's why i put in 2T = $$\lambda$$ /2. The m in this case doesn't matter as long as 2T is not an integral multiple of $$\lambda$$ because it is destructive interference. I set m = 0 so that's how I got 2T = $$\lambda$$ /2. Does that make sense?

Homework Helper
Hi premed,

With thin film interference you have two things you have to keep track of: the effects of the path length difference of the two light rays, and the effects of reflection on the phase of the light rays.

When a light ray reflects off a material with a higher index of refraction, it experiences a phase reversal. Whether $2T = m\lambda_n$ (where $\lambda_n$ is the wavelength in the film) is the constructive or destructive condition depends on how many phase reversals there are in the problem (0, 1 or 2).

So how many phase reversals occur? What does that by itself do to the relative phase of the light rays? Once you have that information, then the condition

$$2 T = m \lambda_n$$

will leave their relative phase (from the reflection effects) unchanged, and

$$2 T = (m+\frac{1}{2}) \lambda_n$$

moves them out of phase an additional 180 degrees.


text:
# Why aren't there more numbers like $e$, $\pi$, and $i$? This is based on looking through the Handbook of Mathematical Functions and online.

This is kind of a big picture question. I just counted up all the symbols used in normal mathematics and, give or take, there are probably around 150 of them, tops. And that's really stretching things. I am including:

• the transpose symbol in linear algebra,
• the gamma function symbol,
• the direct sum symbol for two vector spaces,
• the tensor product symbol,
• ...

I am including a lot of seemingly esoteric stuff! Even so, no matter what formula spits out of Wolfram Alpha, or no matter where you look in the Handbook of Mathematical Functions, for practical applied math purposes there really aren't that many symbols. That got me to thinking: we have these famous numbers $$e$$, $$i$$, and $$\pi$$. They are related by the famous Euler formula which blows everybody's mind when they first see it, except for, reportedly, Gauss.

$$\pi$$ relates to the circle. $$e$$ relates to rate of change -- relates to integration and differentiation somehow. $$i$$ gives us an extra number dimension to solve problems.

Question: Why aren't there more of these numbers? Is it the case that $$99$$% of all important mathematics in practice is covered by the rationals, operations like taking rational roots, the vast swath of anonymous, non-name-worthy irrational & transcendental reals, and $$e$$, $$i$$ and $$\pi$$?

What is it about these three numbers that makes them, in effect, practically the only important numbers in mathematics other than those that can be expressed in terms of regular numbers? Is it because this circle relationship, this extra dimension thing with $$i$$, and this rate of change thing with $$e$$, covers all the really important relationships between the dimensions? I really want someone to break this down for me and tell me why this is the case.

• First, mathematics is hardly about numbers anymore. Second, if you are not a professional mathematician how can you tell which symbols are esoteric? – Asaf Karagila Jan 19 '13 at 8:11
• Asaf, re math not being about numbers anymore, I am not sure I understand that statement completely. Don't all the letters ultimately represent sets of numbers, in the end? On the second point, I am sure I am wrong about calling anything "esoteric", maybe a bad choice of words. So I withdraw that adjective. It is just really interesting to me that so few numbers are so important and I wonder if anyone has a perspective on why that is the case. – user58450 Jan 19 '13 at 8:27
• Mathematics is about numbers as much as linguistics and literature are about letters. – Asaf Karagila Jan 19 '13 at 8:33
• If you're just counting symbols, there are not that many because it's hard to invent a new symbol when it's not available in standard fonts/keyboards/etc. Even if you're inventing something new, it's easier to just re-use an existing symbol and explain the meaning. – Ted Jan 19 '13 at 8:48

Have a look at http://en.wikipedia.org/wiki/Mathematical_constants where you will find any number of important mathematical constants which have no known expression in terms of $e$, $i$, and $\pi$. The Euler-Mascheroni constant, $\gamma$, is a biggie in analytic number theory. $\zeta(3)$ was immortalized by Apery. Feigenbaum's constant $\delta$ is super-important in dynamical systems and transition to chaos. Khinchin's constant $K$ is big in continued fractions. And so on.


text:
### Still have math questions?

Trigonometry
Question

An anchor is dropped from a cruise ship at port. The length of the  anchors chain is $$30 m$$ below the water. The angle of elevation from the anchor to the ship is $$39$$ degrees. How many meters did the anchor drop? Round your answer to the nearest tenth.

$$18.8 m$$

$$24.2 m$$

$$47.7 m$$

$$22.5$$

$$d= 30\sin39= 18.8$$


text:
[This article was first published on r – Appsilon | End to End Data Science Solutions, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

## Line Charts with R

Are your visualizations an eyesore? The 1990s are over, pal. Terrible-looking visualizations are no longer acceptable, no matter how useful they might otherwise be. Luckily, there’s a lot you can do to quickly and easily enhance the aesthetics of your visualizations. Today you’ll learn how to make impressive line charts with R and the ggplot2 package.

Want to learn how to make stunning bar charts with R? Here’s our complete guide.

This article demonstrates how to make an aesthetically-pleasing line chart for any occasion. After reading, visualizing time series and similar data should become second nature. Today you’ll learn how to:

## Make your first line chart

R has a gapminder package you can download. It contains data on life expectancy, population, and GDP between 1952 and 2007. It’s a time-series dataset, which is excellent for line-based visualizations.

Here’s how to load it (and other libraries):

library(dplyr)
library(ggplot2)
library(gapminder)

head(gapminder)

Calling the head() function outputs the first six rows of the dataset. Here’s how they look:

Image 1 – Head of Gapminder dataset

R’s widely used package for data visualization is ggplot2. It’s based on the layering principle. The first layer represents the data, and after that comes a visualization layer (or layers). These two are mandatory for any chart type, and line charts are no exception. You’ll learn how to add additional layers later.

Your first chart will show the population over time for the United States. Columns year and pop are placed on X-axis and Y-axis, respectively:

usa <- gapminder %>%
filter(continent == "Americas", country == "United States")

ggplot(usa, aes(x = year, y = pop)) +
geom_line()

Here’s the corresponding visualization:

Image 2 – Population growth over time in the United States

The visualization is informative but as ugly as they come. The following sections will show you how to tweak the visuals.

## Change Color, Line Type, and Add Markers

Keeping the default styling is the worst thing you can do. With the geom_line() layer, you can change the following properties:

• color – line color
• size – line width
• linetype – maybe you want dashed lines?

Here’s how to make a thicker dashed blue line:

ggplot(usa, aes(x = year, y = pop)) +
geom_line(linetype = "dashed", color = "#0099f9", size = 2)

Image 3 – Changing line style, width, and color

Better, but not quite there yet. Most line charts combine lines and points to make the result more appealing. Here’s how to add points (markers) to yours:

ggplot(usa, aes(x = year, y = pop)) +
geom_line(color = "#0099f9", size = 2) +
geom_point(color = "#0099f9", size = 5)

Image 4 – Line chart with markers

Now the charts are getting somewhere – but there’s still a lot to do.

## Titles, Subtitles, and Captions

You can’t have a complete chart without at least a title. A good subtitle can come in handy for extra information, and a caption is a good place to cite your sources. The most convenient way to add these is through a labs() layer. It takes in values for title, subtitle, and caption

Here’s how to add all three, without styles:

ggplot(usa, aes(x = year, y = lifeExp)) +
geom_line(color = "#0099f9", size = 2) +
geom_point(color = "#0099f9", size = 5) +
labs(
title = "Average life expectancy in US",
subtitle = "Data from 1952 to 2007",
caption = "Source: Gapminder dataset"
)

Image 5 – Title, subtitle, and caption with default styles

But there’s more to this story. You can customize all three in the same way – by putting styles to the theme() layer. Here’s how to center title and caption, left align and italicize the caption, and make the title blue:

ggplot(usa, aes(x = year, y = lifeExp)) +
geom_line(color = "#0099f9", size = 2) +
geom_point(color = "#0099f9", size = 5) +
labs(
title = "Average life expectancy in US",
subtitle = "Data from 1952 to 2007",
caption = "Source: Gapminder dataset"
) +
theme(
plot.title = element_text(color = "#0099f9", size = 20, face = "bold", hjust = 0.5),
plot.subtitle = element_text(size = 13, face = "bold", hjust = 0.5),
plot.caption = element_text(face = "italic", hjust = 0)
)

Image 6 – Styling title, subtitle, and caption

That’s all great, but what about the axis labels? Let’s see how to tweak them next.

## Edit Axis Labels

Just take a look at the Y-axis for the previous year vs. population charts. The ticks look horrible. Scientific notation doesn’t help make things easier to read. The following snippet puts “M” next to the number – indicates “Millions”:

library(scales)

ggplot(usa, aes(x = year, y = pop)) +
geom_line(color = "#0099f9", size = 2) +
geom_point(color = "#0099f9", size = 5) +
scale_y_continuous(
labels = unit_format(unit = "M", scale = 1e-6)
)

Image 7 – Changing axis ticks

But what if you want a bit more space on top and bottom? You can specify where the axis starts and ends. Here’s how:

ggplot(usa, aes(x = year, y = pop)) +
geom_line(color = "#0099f9", size = 2) +
geom_point(color = "#0099f9", size = 5) +
expand_limits(y = c(125000000, 325000000)) +
scale_y_continuous(
labels = unit_format(unit = "M", scale = 1e-6)
)

Image 8 – Changing limits of the axis

The labs() layer takes in values for x and y – these determine the text shown on the X and Y axes, respectively. You can tweak the styles for axis labels the same way you did with the title, subtitle, and caption. The snippet below shows how:

ggplot(usa, aes(x = year, y = pop)) +
geom_line(color = "#0099f9", size = 2) +
geom_point(color = "#0099f9", size = 5) +
scale_y_continuous(
labels = unit_format(unit = "M", scale = 1e-6)
) +
labs(
x = "Year",
y = "Population"
) +
theme(
axis.title.x = element_text(color = "#0099f9", size = 16, face = "bold"),
axis.title.y = element_text(color = "#0099f9", size = 16, face = "italic")
)

Image 9 – Changing X and Y axis labels

And that’s it for styling axes! Let’s see how to show multiple lines on the same chart next.

## Draw Multiple Lines on the Same Chart

Showing multiple lines on a single chart can be useful. We’ll use it to compare average life expectancy between major North American countries – the United States, Canada, and Mexico.

To display multiple lines, you can use the group attribute in the data aesthetics layer. Here’s an example:

north_big <- gapminder %>%
filter(continent == "Americas", country %in% c("United States", "Canada", "Mexico"))

ggplot(north_big, aes(x = year, y = lifeExp, group = country)) +
geom_line(aes(color = country), size = 2)

Image 10 – Average life expectancy among major North American countries

In case you’re wondering how to add markers to multiple lines – the procedure is identical as it was for a single one. Take a look at the code snippet and image below:

ggplot(north_big, aes(x = year, y = lifeExp, group = country)) +
geom_line(aes(color = country), size = 2) +
geom_point(aes(color = country), size = 5)

Image 11 – Adding markers to multiple lines

There’s a legend right next to the plot because of multiple lines on a single chart. You wouldn’t know which line represents what without it. Still, it’s position on the right might be irritating for some use cases. Here’s how to put it on the top:

ggplot(north_big, aes(x = year, y = lifeExp, group = country)) +
geom_line(aes(color = country), size = 2) +
geom_point(aes(color = country), size = 5) +
theme(legend.position = "top")

Image 12 – Changing the legend position

You’ve learned a lot until now, but there’s still one important topic to cover – labels.

If there aren’t too many data points on a line chart, it can be useful to add labels showing the exact values. Be careful with them – they can make your visualization messy fast.

Here’s how to plot average life expectancy in the United States and show text on top of the line:

ggplot(usa, aes(x = year, y = lifeExp)) +
geom_line(color = "#0099f9", size = 2) +
geom_point(color = "#0099f9", size = 5) +
geom_text(aes(label = lifeExp))

A couple of problems, though. The labels are a bit small, and they are positioned right on top of the markers. The code snippet below makes the text larger and pushes them a bit higher:

ggplot(usa, aes(x = year, y = lifeExp)) +
geom_line(color = "#0099f9", size = 2) +
geom_point(color = "#0099f9", size = 5) +
geom_text(
aes(label = lifeExp),
nudge_x = 0.25,
nudge_y = 0.25,
check_overlap = TRUE,
size = 5
)

Image 14 – Styling text

Showing text might not be the cleanest solution every time. Maybe you want text wrapped inside a box to give your visualization a touch more style. You can do that by replacing geom_text() with geom_label(). That’s the only change you need to make:

ggplot(usa, aes(x = year, y = lifeExp)) +
geom_line(color = "#0099f9", size = 2) +
geom_point(color = "#0099f9", size = 5) +
geom_label(
aes(label = lifeExp),
nudge_x = 0.25,
nudge_y = 0.25,
check_overlap = TRUE
)

Image 15 – Replacing text with labels

And that’s all you really need to know about labels and line charts for today. Let’s wrap things up.

## Conclusion

Today you’ve learned how to make line charts and how to make them aesthetically pleasing. You’ve learned how to change colors, line width and type, titles, subtitles, captions, axis labels, and much more. You are now ready to include line charts in your reports and dashboards. You can expect more basic R tutorials weekly (usually on Sundays) and more advanced tutorials throughout the week. Fill out the subscribe form below so you never miss an update.

Are you completely new to R but have some programming experience? Check out our detailed R guide for programmers.


text:
# Dispa-SET for the EU28¶

## Description¶

Warning

The Dispa-SET for the EU28 is currently in developmend and will be released soon

This is input data of the Dispa-SET model, applied to the EU28 member states

The power plants in the model are represented as a cluster of units powered by the same fuel type and technology. They can be modelled together with a large number of RES units with separate hourly distribution curves.

## Features¶

The model is expressed as an optimization problem. Continuous variables include the individual unit dispatched power, the shedded load and the curtailed power generation. The binary variables are the commitment status of each unit. The main model features can be summarized as follows:

• Minimum and maximum power for each unit
• Power plant ramping limits
• Reserves up and down
• Minimum up/down times
• Curtailment
• Pumped-hydro storage
• Non-dispatchable units (e.g. wind turbines, run-of-river, etc.)
• Start-up, ramping and no-load costs
• Multi-nodes with capacity constraints on the lines (congestion)
• Constraints on the targets for renewables and/or CO2 emissions
• Yearly schedules for the outages (forced and planned) of each units
• CHP power plants and thermal storage

The demand is assumed to be inelastic to the price signal. The MILP objective function is therefore the total generation cost over the optimization period.

## Quick start¶

git clone https://github.com/energy-modelling-toolkit/Dispa-SET.git
cd Dispa-SET
conda env create  # Automatically creates environment based on environment.yml
source activate dispaset # in Windows: activate dispaset
pip install -e . # Install editable local version

The above commands create a dedicated environment so that your anconda configuration remains clean from the required dependencies installed.

To check that everything runs fine, you can build and run a test case by typing:

dispaset -c ConfigFiles/ConfigTest.xlsx build simulate

Make sure that the path is changed to local Dispa-SET folder in folowing scripts (the procedure is provided in the scripts):

build_and_run.py

## Documentation¶

The general documentation of the Dispa-SET model and the stable releases are available on the main Dispa-SET website: http://www.dispaset.eu

## Licence¶

Dispa-SET is a free software licensed under the “European Union Public Licence” EUPL v1.2. It can be redistributed and/or modified under the terms of this license.

## Main developpers¶

• Sylvain Quoilin (University of Liège, KU Leuven)
• Konstantinos Kavvadias (European Commission, Institute for Energy and Transport)
• Matija Pavičević (KU Leuven)

## References¶

More details regarding the model and its implementation are available in the following publications


text:
# ReactionNetworks -- create chemical reaction networks and corresponding steady-state and conservation equations

## Description

The ReactionNetworks package provides functions for creating the steady-state and conservation equations corresponding to a given reaction network. Included are some basic building-block motifs, which can be joined together to create specific reaction network. Examples are provided illustrating elimination and degeneration with removal of a species or a reaction and the corresponding effect on the solutions of the system.

Basic Functions:

$\bullet$ reactionNetwork

$\bullet$ isDeficient

$\bullet$ isWeaklyReversible

$\bullet$ steadyStateEquations

$\bullet$ conservationEquations

$\bullet$ glue

Motifs:

$\bullet$ oneSiteModificationA

$\bullet$ oneSiteModificationB

$\bullet$ oneSiteModificationC

$\bullet$ oneSiteModificationD

$\bullet$ twoSiteModificationE

$\bullet$ twoSiteModificationF

$\bullet$ twoSiteModificationG

$\bullet$ modificationOfTwoSubstratesH

$\bullet$ modificationOfTwoSubstratesI

$\bullet$ twoLayerCascadeJ

$\bullet$ twoLayerCascadeK

$\bullet$ twoLayerCascadeL

$\bullet$ crossLinkingModelCelldeath (missing documentation)

$\bullet$ clusterModelCellDeath

$\bullet$ wnt

$\bullet$ nSiteProcessiveModification

$\bullet$ nSiteDistributiveModification

$\bullet$ nSiteImmuneReaction

$\bullet$ nSiteDiffusion

$\bullet$ nSitePoreForming

$\bullet$ nSiteSequestration

$\bullet$ nSiteAutocatalytic

Examples

The following example demonstrates how to compute the degree and dimension of the ideal cut out by the steady-state and conservation equations.

 i1 : N = reactionNetwork "A <--> 2B, A + C <--> D, B + E --> A + C, D --> B+E" o1 = A-->2B 2B-->A A+C-->D D-->A+C D-->B+E B+E-->A+C o1 : ReactionNetwork i2 : R = createRing(N, QQ) o2 = R o2 : PolynomialRing

After creating the reaction network and the corresponding ring, we create the steady state equations and substitute random values for the reaction rates; this will allows us to compute the degree of the ideal.

 i3 : SS = flatten entries steadyStateEquations N 2 o3 = {xx kk - xx xx kk + xx xx kk - xx kk + xx kk B {1, 0} A C {2, 3} B E {4, 2} A {0, 1} D {3, ------------------------------------------------------------------------ 2 , - 2xx kk - xx xx kk + 2xx kk + xx kk , - 2} B {1, 0} B E {4, 2} A {0, 1} D {3, 4} ------------------------------------------------------------------------ xx xx kk + xx xx kk + xx kk , xx xx kk - xx kk A C {2, 3} B E {4, 2} D {3, 2} A C {2, 3} D {3, ------------------------------------------------------------------------ - xx kk , - xx xx kk + xx kk } 2} D {3, 4} B E {4, 2} D {3, 4} o3 : List i4 : K = toList(apply(0..length N.ReactionRates-1, i-> random(QQ))) 9 1 9 1 3 o4 = {-, -, -, -, 1, -} 2 2 4 2 4 o4 : List i5 : Rr = toList(apply(0..length N.ReactionRates-1, i-> value(N.ReactionRates#i))) o5 = {kk , kk , kk , kk , kk , kk } {0, 1} {1, 0} {2, 3} {3, 2} {3, 4} {4, 2} o5 : List i6 : P = toList(apply(0..length Rr-1, i-> Rr#i=>sub(K#i,R))) 9 1 9 1 o6 = {kk => -, kk => -, kk => -, kk => -, kk => {0, 1} 2 {1, 0} 2 {2, 3} 4 {3, 2} 2 {3, 4} ------------------------------------------------------------------------ 3 1, kk => -} {4, 2} 4 o6 : List i7 : F' = toList apply(0..length SS-1, i-> sub(SS#i,P)) 1 2 9 3 9 1 2 3 o7 = {-xx - -xx xx + -xx xx - -xx + -xx , - xx - -xx xx + 9xx + xx , - 2 B 4 A C 4 B E 2 A 2 D B 4 B E A D ------------------------------------------------------------------------ 9 3 1 9 3 3 -xx xx + -xx xx + -xx , -xx xx - -xx , - -xx xx + xx } 4 A C 4 B E 2 D 4 A C 2 D 4 B E D o7 : List

Next, we create the conservation equations and assume there is no translation, i.e., the intial conditions are all zero.

 i8 : C = conservationEquations N o8 = {2xx + xx - xx + xx - 2cc - cc + cc - cc , - 2xx - xx + 2xx + A B C D A B C D A B C ------------------------------------------------------------------------ xx + 2cc + cc - 2cc - cc } E A B C E o8 : List i9 : L = {0,0,0,0,0} o9 = {0, 0, 0, 0, 0} o9 : List i10 : Iv = toList(apply(0..length N.InitialValues-1, i-> value(N.InitialValues#i))) o10 = {cc , cc , cc , cc , cc } A B C D E o10 : List i11 : S = toList(apply(0..length Iv-1, i-> Iv#i=>L#i)) o11 = {cc => 0, cc => 0, cc => 0, cc => 0, cc => 0} A B C D E o11 : List i12 : F'' = toList apply(0..length C-1, i-> sub(C#i,S)) o12 = {2xx + xx - xx + xx , - 2xx - xx + 2xx + xx } A B C D A B C E o12 : List

Finally, we join the two sets of equations and create an ideal. Thus, the degree and dimension can be computed.

 i13 : F = join(F',F'') 1 2 9 3 9 1 2 3 o13 = {-xx - -xx xx + -xx xx - -xx + -xx , - xx - -xx xx + 9xx + xx , 2 B 4 A C 4 B E 2 A 2 D B 4 B E A D ----------------------------------------------------------------------- 9 3 1 9 3 3 - -xx xx + -xx xx + -xx , -xx xx - -xx , - -xx xx + xx , 2xx + xx 4 A C 4 B E 2 D 4 A C 2 D 4 B E D A B ----------------------------------------------------------------------- - xx + xx , - 2xx - xx + 2xx + xx } C D A B C E o13 : List i14 : I = ideal F 1 2 9 3 9 1 2 3 o14 = ideal (-xx - -xx xx + -xx xx - -xx + -xx , - xx - -xx xx + 9xx + 2 B 4 A C 4 B E 2 A 2 D B 4 B E A ----------------------------------------------------------------------- 9 3 1 9 3 3 xx , - -xx xx + -xx xx + -xx , -xx xx - -xx , - -xx xx + xx , 2xx D 4 A C 4 B E 2 D 4 A C 2 D 4 B E D A ----------------------------------------------------------------------- + xx - xx + xx , - 2xx - xx + 2xx + xx ) B C D A B C E o14 : Ideal of R i15 : degree I o15 = 5 i16 : dim I o16 = 11

## Authors

• Cvetelina Hill
• Timothy Duff
• Kisun Lee
• Anton Leykin
• Alexandru Iosif

## Version

This documentation describes version 1.0 of ReactionNetworks.

## Source code

The source code from which this documentation is derived is in the file ReactionNetworks.m2. The auxiliary files accompanying it are in the directory ReactionNetworks/.

## Exports

• Types
• ReactionNetwork -- a mutable hash table, stores information about a reaction network
• Functions and commands
• Methods
• "clusterModelCellDeath()" -- see clusterModelCellDeath -- an example of a chemical reaction
• "conservationEquations(ReactionNetwork)" -- see conservationEquations -- creates the conservation equations of a reaction network
• "conservationEquations(ReactionNetwork,Ring)" -- see conservationEquations -- creates the conservation equations of a reaction network
• "createRing(ReactionNetwork)" -- see createRing -- creates a ring with generators species concentrations, reaction rates, initial values
• "createRing(ReactionNetwork,Ring)" -- see createRing -- creates a ring with generators species concentrations, reaction rates, initial values
• "glue(List,ReactionNetwork)" -- see glue -- combine two networks
• "glue(ReactionNetwork,List)" -- see glue -- combine two networks
• "glue(ReactionNetwork,ReactionNetwork)" -- see glue -- combine two networks
• "modificationOfTwoSubstratesH()" -- see modificationOfTwoSubstratesH -- an example chemical reaction motif
• "modificationOfTwoSubstratesI()" -- see modificationOfTwoSubstratesI -- an example chemical reaction motif
• "negativeLaplacian(ReactionNetwork)" -- see negativeLaplacian -- Computes the negative of the Laplacian matrix of a Reaction Network.
• "negativeUndirectedLaplacian(ReactionNetwork)" -- see negativeUndirectedLaplacian -- Computes the negative of the Laplacian matrix of an undirected graph associated with a Reaction Network.
• "negativeWeightedLaplacian(ReactionNetwork)" -- see negativeWeightedLaplacian -- Computes the negative of the weighted Laplacian matrix of a Reaction Network.
• "nSiteAutocatalytic(ZZ)" -- see nSiteAutocatalytic -- A motif for autocatalytic networks
• "nSiteDiffusion(ZZ)" -- see nSiteDiffusion -- an example for a diffusion network
• "nSiteDistributiveModification(ZZ)" -- see nSiteDistributiveModification -- A motif for purely distributive phosphorylation
• "nSiteImmuneReaction(ZZ)" -- see nSiteImmuneReaction -- A motif for an immune response network
• "nSitePoreForming(ZZ)" -- see nSitePoreForming -- an example for a pore forming network
• "nSiteProcessiveModification(ZZ)" -- see nSiteProcessiveModification -- A motif for purely processive phosphorylation
• "nSiteSequestration(ZZ)" -- see nSiteSequestration -- A motif for sequestration networks
• "oneSiteModificationA()" -- see oneSiteModificationA -- an example for chemical reaction motif
• "oneSiteModificationB()" -- see oneSiteModificationB -- an example for chemical reaction motif
• "oneSiteModificationC()" -- see oneSiteModificationC -- an example for chemical reaction motif
• "oneSiteModificationD()" -- see oneSiteModificationD -- an example for chemical reaction motif
• "reactantMatrix(ReactionNetwork)" -- see reactantMatrix -- Computes the reactants matrix of a Reaction Network.
• "reactionNetwork(Ideal)" -- see reactionNetwork -- creates a reaction network
• "reactionNetwork(List)" -- see reactionNetwork -- creates a reaction network
• "reactionNetwork(String)" -- see reactionNetwork -- creates a reaction network
• "stoichiometricConeKer(ReactionNetwork)" -- see stoichiometricConeKer -- Computes a matrix whose columns are the rays of the cone non-negative kernel of the stoichiometric matrix of a Reaction Network.
• "stoichiometricMatrix(ReactionNetwork)" -- see stoichiometricMatrix -- Computes the stoichiometric matrix of a Reaction Network.
• "stoichiometricSubspace(ReactionNetwork)" -- see stoichiometricSubspace -- Computes the stoichiometric space of a Reaction Network.
• "stoichSubspaceKer(ReactionNetwork)" -- see stoichSubspaceKer -- Computes the kernel of the stoichiometric matrix of a Reaction Network.
• substitute(ReactionNetwork,List) -- substitute species names in reaction network
• "twoLayerCascadeL()" -- see twoLayerCascadeL -- an example for chemical reaction motif
• "twoSiteModificationE()" -- see twoSiteModificationE -- an example for chemical rection motif
• "twoSiteModificationF()" -- see twoSiteModificationF -- an example for chemical reaction motif
• "twoSiteModificationG()" -- see twoSiteModificationG -- an example chemical reaction motif
• "wnt()" -- see wnt -- shuttle model for Wnt signaling pathway
• Symbols
• FullEdges (missing documentation)
• Input (missing documentation)
• NullEdges (missing documentation)
• "Complexes" -- see ReactionNetwork -- a mutable hash table, stores information about a reaction network
• "ConcentrationRates" -- see ReactionNetwork -- a mutable hash table, stores information about a reaction network
• "InitialValues" -- see ReactionNetwork -- a mutable hash table, stores information about a reaction network
• "NullIndex" -- see ReactionNetwork -- a mutable hash table, stores information about a reaction network
• "NullSymbol" -- see ReactionNetwork -- a mutable hash table, stores information about a reaction network
• "ReactionGraph" -- see ReactionNetwork -- a mutable hash table, stores information about a reaction network
• "ReactionRates" -- see ReactionNetwork -- a mutable hash table, stores information about a reaction network
• "ReactionRing" -- see ReactionNetwork -- a mutable hash table, stores information about a reaction network
• "Species" -- see ReactionNetwork -- a mutable hash table, stores information about a reaction network

## For the programmer

The object ReactionNetworks is .


text:
Question

# According to the Kinetic theory of gases there are:A. Intermolecular forcesB. Molecules which have considerable volumeC. No intermolecular forces of attractionD. The velocity of molecules decreases for each collision.

Verified
91.5k+ views
Hint:According to the postulates of the Kinetic theory of gases, molecules of a gas are point masses and are identical for the same gas. Therefore, the volume and the size of the gas are negligible.

Also, the momentum of the molecules is conserved. Thus, the velocity remains the same.

Complete step by step solution:
In Kinetic theory of gases, molecules of each gas are identical but different from that of other gases. In actual gases or real gases, there are intermolecular forces. But since the kinetic theory is only applicable for ideal gases, there are no intermolecular forces.

Hence, option (A) is not the correct answer.

Molecules of a gas are point masses. They are rigid and perfectly elastic spheres. The volume of molecules is negligible as compared to the volume of the gas sample. Therefore, the gas molecules do not have a considerable volume.

Hence, option (B) is not the correct answer.

One of the postulates is that the molecules are rigid and perfectly elastic spheres. This means that momentum and Kinetic energy are conserved. The momentum is conserved that means the velocity does not change after the collision.

Since, momentum = $m\upsilon$

where, ‘m’ and ‘$\upsilon$’ are mass and velocities of the molecules respectively.

Thus, option (D) is not correct, as the velocity remains the same for each collision.

Hence, option (C) is the correct answer as there are no intermolecular forces of attraction.

Note:The Kinetic theory of gases is applicable for ideal gases and not for real gases. In this theory of ideal gases, the factors like the intermolecular forces and gravitational attraction are neglected.

The momentum is conserved, provided physical conditions such as pressure and temperature do not change. Increasing the temperature will increase the velocity of molecules and thus the momentum will increase.


text:
# Schubert Polynomials¶

sage.combinat.schubert_polynomial.SchubertPolynomialRing(R)

Returns the Schubert polynomial ring over R on the X basis (i.e., the basis of the Schubert polynomials).

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ); X
Schubert polynomial ring with X basis over Integer Ring
sage: X(1)
X[1]
sage: X([1,2,3])*X([2,1,3])
X[2, 1]
sage: X([2,1,3])*X([2,1,3])
X[3, 1, 2]
sage: X([2,1,3])+X([3,1,2,4])
X[2, 1] + X[3, 1, 2]
sage: a = X([2,1,3])+X([3,1,2,4])
sage: a^2
X[3, 1, 2] + 2*X[4, 1, 2, 3] + X[5, 1, 2, 3, 4]

class sage.combinat.schubert_polynomial.SchubertPolynomialRing_xbasis(R)

EXAMPLES:

sage: X = SchubertPolynomialRing(QQ)
True

Element
class sage.combinat.schubert_polynomial.SchubertPolynomial_class

Bases: sage.modules.with_basis.indexed_element.IndexedFreeModuleElement

divided_difference(i, algorithm='sage')

Return the i-th divided difference operator, applied to self. Here, i can be either a permutation or a positive integer.

INPUT:

• i – permutation or positive integer
• algorithm – (default: 'sage') either 'sage' or 'symmetrica'; this determines which software is called for the computation

OUTPUT:

The result of applying the i-th divided difference operator to self.

If $$i$$ is a positive integer, then the $$i$$-th divided difference operator $$\delta_i$$ is the linear operator sending each polynomial $$f = f(x_1, x_2, \ldots, x_n)$$ (in $$n \geq i+1$$ variables) to the polynomial

$\frac{f - f_i}{x_i - x_{i+1}}, \qquad \text{ where } f_i = f(x_1, x_2, ..., x_{i-1}, x_{i+1}, x_i, x_{i+1}, ..., x_n) .$

If $$\sigma$$ is a permutation in the $$n$$-th symmetric group, then the $$\sigma$$-th divided difference operator $$\delta_\sigma$$ is the composition $$\delta_{i_1} \delta_{i_2} \cdots \delta_{i_k}$$, where $$\sigma = s_{i_1} \circ s_{i_2} \circ \cdots \circ s_{i_k}$$ is any reduced expression for $$\sigma$$ (the precise choice of reduced expression is immaterial).

Note

The expand() method results in a polynomial in $$n$$ variables named x0, x1, ..., x(n-1) rather than $$x_1, x_2, \ldots, x_n$$. The variable named xi corresponds to $$x_{i+1}$$. Thus, self.divided_difference(i) involves the variables x(i-1) and xi getting switched (in the numerator).

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ)
sage: a = X([3,2,1])
sage: a.divided_difference(1)
X[2, 3, 1]
sage: a.divided_difference([3,2,1])
X[1]
sage: a.divided_difference(5)
0

Any divided difference of $$0$$ is $$0$$:

sage: X.zero().divided_difference(2)
0

This is compatible when a permutation is given as input:

sage: a = X([3,2,4,1])
sage: a.divided_difference([2,3,1])
0
sage: a.divided_difference(1).divided_difference(2)
0

sage: a = X([4,3,2,1])
sage: a.divided_difference([2,3,1])
X[3, 2, 4, 1]
sage: a.divided_difference(1).divided_difference(2)
X[3, 2, 4, 1]
sage: a.divided_difference([4,1,3,2])
X[1, 4, 2, 3]
sage: b = X([4, 1, 3, 2])
sage: b.divided_difference(1).divided_difference(2)
X[1, 3, 4, 2]
sage: b.divided_difference(1).divided_difference(2).divided_difference(3)
X[1, 3, 2]
sage: b.divided_difference(1).divided_difference(2).divided_difference(3).divided_difference(2)
X[1]
sage: b.divided_difference(1).divided_difference(2).divided_difference(3).divided_difference(3)
0
sage: b.divided_difference(1).divided_difference(2).divided_difference(1)
0

expand()

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ)
sage: X([2,1,3]).expand()
x0
sage: [X(p).expand() for p in Permutations(3)]
[1, x0 + x1, x0, x0*x1, x0^2, x0^2*x1]

multiply_variable(i)

Returns the Schubert polynomial obtained by multiplying self by the variable $$x_i$$.

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ)
sage: a = X([3,2,4,1])
sage: a.multiply_variable(0)
X[4, 2, 3, 1]
sage: a.multiply_variable(1)
X[3, 4, 2, 1]
sage: a.multiply_variable(2)
X[3, 2, 5, 1, 4] - X[3, 4, 2, 1] - X[4, 2, 3, 1]
sage: a.multiply_variable(3)
X[3, 2, 4, 5, 1]

scalar_product(x)

Returns the standard scalar product of self and x.

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ)
sage: a = X([3,2,4,1])
sage: a.scalar_product(a)
0
sage: b = X([4,3,2,1])
sage: b.scalar_product(a)
X[1, 3, 4, 6, 2, 5]
sage: Permutation([1, 3, 4, 6, 2, 5, 7]).to_lehmer_code()
[0, 1, 1, 2, 0, 0, 0]
sage: s = SymmetricFunctions(ZZ).schur()
sage: c = s([2,1,1])
sage: b.scalar_product(a).expand()
x0^2*x1*x2 + x0*x1^2*x2 + x0*x1*x2^2 + x0^2*x1*x3 + x0*x1^2*x3 + x0^2*x2*x3 + 3*x0*x1*x2*x3 + x1^2*x2*x3 + x0*x2^2*x3 + x1*x2^2*x3 + x0*x1*x3^2 + x0*x2*x3^2 + x1*x2*x3^2
sage: c.expand(4)
x0^2*x1*x2 + x0*x1^2*x2 + x0*x1*x2^2 + x0^2*x1*x3 + x0*x1^2*x3 + x0^2*x2*x3 + 3*x0*x1*x2*x3 + x1^2*x2*x3 + x0*x2^2*x3 + x1*x2^2*x3 + x0*x1*x3^2 + x0*x2*x3^2 + x1*x2*x3^2

sage.combinat.schubert_polynomial.is_SchubertPolynomial(x)

Returns True if x is a Schubert polynomial, and False otherwise.

EXAMPLES:

sage: from sage.combinat.schubert_polynomial import is_SchubertPolynomial
sage: X = SchubertPolynomialRing(ZZ)
sage: a = 1
sage: is_SchubertPolynomial(a)
False
sage: b = X(1)
sage: is_SchubertPolynomial(b)
True
sage: c = X([2,1,3])
sage: is_SchubertPolynomial(c)
True


text:
# Simple complex numbers integral

1. Sep 8, 2008

### elcotufa

1. The problem statement, all variables and given/known data
Integrate using complex numbers
$$\int\limits_0^{2\pi} cos^4(\theta)$$

2. Relevant equations
$$cos^4(\theta)= (\frac{e^{j\theta} + e^{-j\theta}}2)^4$$
3. The attempt at a solution
$$\frac 1{2^4} (e^{j\theta} + e^{-j\theta})^4$$

I got
$$\frac 1{2^4} \int^{2\pi}_0 (e^{4j\theta}+4e^{2j\theta}+4e^{-2j\theta}+e^{-4j\theta}+6)$$

After this I am not sure what to do

The integral of $$\int e^{4j}$$ would be $$\frac{e^{4j\theta}}{4j}$$?

How do I cancel them?

Input appreciated

2. Sep 8, 2008

### Dick

Sure, that's the integral of e^(4j*theta). You'll notice if you evaluate it from 0 to 2*pi the result is 0. The same for all the other exponentials. The only term that contributes is the 6.

3. Sep 8, 2008

thanks man