Number of graphs that satisfies the property that edge weight is maximum of node values on which the edge is incident

I have an undirected weighted graph without multi edges. All the edge weights are whole numbers and known. I want to know in how many ways node values(node values are also whole numbers) can be assigned to the nodes such that the graph satisfies the condition that for every edge its edge weight is exactly equal to maximum of two node values this edge is incident on.

Difficulty in understand the proof of the lemma : “Matroids exhibit the optimal-substructure property”

I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma I give a brief description of the possible prerequisites for the lemma.


Let $ M=(S,\ell)$ be a matroid where $ S$ is the ground set and $ \ell$ is the family of subsets of $ S$ called the independent subsets of $ S$ .

Let us have an algorithm which finds an optimal subset of $ M$ using greedy method as:

$ GREEDY(M,W):$

$ 1\quad A\leftarrow\phi$

$ 2\quad \text{sort $ S[M]$ into monotonically decreasing order by weight $ w$ }$

$ 3\quad \text{for each $ x\in S[M]$ , taken in monotonically decreasing order by weight $ w(x)$ }$

$ 4\quad\quad \text{do if $ A\cup\{x\} \in \ell[M]$ }$

$ 5\quad\quad\quad\text{then $ A\leftarrow A\cup \{x\}$ }$

$ 6\quad \text{return $ A$ }$


I was having a problem in understanding a step in the proof of the lemma below.

Lemma: (Matroids exhibit the optimal-substructure property)

Let $ x$ be the first element of $ S$ chosen by $ GREEDY$ for the weighted matroid $ M = (S, \ell)$ . The remaining problem of finding a maximum-weight independent subset containing $ x$ reduces to finding a maximum-weight independent subset of the weighted matroid $ M’ = (S’, \ell’)$ , where

$ S’ = \{y\in S:\{x,y\}\in \ell\}$ ,

$ \ell’ = \{В \subseteq S – \{x\} : В \cup \{x\} \in \ell\}$ ,

and the weight function for $ M’$ is the weight function for $ M$ , restricted to $ S’$ . (We call $ M’$ the contraction of $ M$ by the element $ x$ .)

Proof:

  1. If $ A$ is any maximum-weight independent subset of $ M$ containing $ x$ , then $ A’ = A — \{x\}$ is an independent subset of $ M’$ .

  2. Conversely, any independent subsubset $ A’$ of $ M’$ yields an independent subset $ A = A’\cup\{x\}$ of $ M$ .

  3. We have in both cases $ w(A) = w(A’) + w(x)$ .

  4. Since we have in both cases that $ w(A) = w(A’) + w(x)$ , a maximum-weight solution in $ M$ containing $ x$ yields a maximum-weight solution in $ M’$ , and vice versa.


I could understand $ (1),(2),(3)$ . But I could not get how the line $ (4)$ was arrived in the proof from $ (1),(2),(3)$ . especially the part in bold-italics. Could anyone please make it clear to me.

PyCrypto based encrypted Property class for Google App Engine standard – is this AES implementation secure

I have a need to encrypt OAuth access and refresh tokens stored in the Google Cloud Datastore.

The goal here is to ensure that if the Datastore entities are accessed independently of the code, the OAuth tokens will be encrypted and thus unusable.

This is not intended to protect against situations where both the code and Datastore are exposed together.

To securely store the data, I have leveraged PyCrypto’s AES implementation, and created a custom property type that automatically encrypts/decrypts the properties when accessing them.

The logic is as follows:

  • To store – I generate a random initialization vector, encrypt the data, then I base64 encode both the initialization vector and the encrypted data, and store them together in a text property.

  • To retrieve – I fetch the text data, slice off the base64 encoded initialization vector, and proceed to decode then decrypt the remaining data.

In addition to securing my own application, I am considering publishing the details and distributing the relevant code for others, so I want to ensure I have a secure or "correct" implementation of this functionality

(Note I have stripped out App Engine specific code and just included relevant encryption code here, for simplicity. The actual implementation allows it to be dropped into existing Datastore models in a backwards-compatible fashion).

 from Crypto.Cipher import AES   from Crypto import Random  from base64 import b64encode,b64decode  from meta_secure import aes_key #aes_key is a 32 digit alphanumeric string (GUID)    #encryption scheme  def encrypt_value(value):     rand = Random.new()     init_vector = rand.read(16)     aes = AES.new(aes_key,AES.MODE_CFB,init_vector)     encrypted = b64encode(aes.encrypt(value))     return '%s%s'%(b64encode(init_vector),encrypted)    def decrypt_value(value):     init_vector = b64decode(value[:24])     aes = AES.new(aes_key,AES.MODE_CFB,init_vector)     decrypted = aes.decrypt(b64decode(value[24:]))     return decrypted     

Have I used PyCrypto and AES correctly for the goal as stated above?

Does the heap property in the definition of binary heaps apply recursively?

The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property, the key stored in each node is either greater than or equal to or less than or equal to the keys in the node’s children.

Binary tree

In the above tree, the node with value 70 is greater than its parent 10 breaking the heap property. However, 70 is also greater than 40 and lies in the subtree of 40. Will we say that the heap property is also breaking at 40, even though 40 is greater than its two children 10 and 2?

How to find lines of matrix that has the property of being zero everywhere except for 1 entry?

I am interested in finding the lines where all entries are equal to zeros except for one.

Example: Given the follwoing matrix:

\begin{bmatrix}0 &0 &3 & 8\ 0 & 4 & 0 & 0 \ 0 &1 & 0 & 1\end{bmatrix}

Only the second line verify this property.

Of course, the brute force way is to go over the entries and check them one by one. But I am wondering if there is another most efficient way I don’t know about.

Unity toggleable shader property misbehaves when set by code?

I’ve added a toggle to my shader:

[Toggle(ENABLE_COLOR_BLEND)] _EnableColorBlend ("Enable Color Blend", Int) = 0 

In the Subshader:

#pragma shader_feature ENABLE_COLOR_BLEND 

And in the fragment shader:

#ifdef ENABLE_COLOR_BLEND     color = lerp(_DryColor, _WetColor, _ColorBlend); #endif 

And there it is in the inspector, and when I toggle it, color blending is turned on and the material is rendered as it should be. if I turn it off, it’s off.

But if I try to set it like this in code:

Renderer.material.SetInt("_EnableColorBlend", 1); 

The material is rendered like if EnableColorBlend is off.

In the inspector it’s ticked, and as soon as I turn it off, it gets ticked again. (I set it in an Update) But for some reason, it’s still rendered like color blending is off.

And if I remove the SetInt above, and set it by hand, everything works fine.

Why?

Idea: If I set it by hand, there is a smooth transition (don’t know why) instead of an instant change in shade. Maybe by setting it constantly to 1, it always just starts the transition, but can’t finish it?

EDIT: Just checked it with a guard, and it still behaves the same.

if (Renderer.material.GetInt("_EnableColorBlend") == 0) Renderer.material.SetInt("_EnableColorBlend", 1); 

Order of operations for Aurora property Lasers

Laser weapons cannot do damage to invisible creatures. The Aurora property negates invisibility for 1 minute on a hit. At the moment I am assuming that a) you can still make attacks against an invisible target with a laser and b) it will still apply non-damage effects (correct me if these are incorrect). This would mean that a laser with aurora (such as via a Mechanic’s prototype weapon) would still negate invisibility for future shots.

If I fire a laser weapon with the Aurora property, does the (lack of) damage occur before their invisibility is removed, or after?

Relevant rules text:

Laser weapons emit highly focused beams of light that deal fire damage. These beams can pass through glass and other transparent physical barriers, dealing damage to such barriers as they pass through. Barriers of energy or magical force block lasers. Invisible creatures don’t take damage from lasers, as the beams pass through them harmlessly. Fog, smoke, and other clouds provide both cover and concealment from laser attacks. Lasers can penetrate darkness, but they don’t provide any illumination.

When an aurora weapon strikes a target, the creature glows with a soft luminescence for 1 minute. This negates invisibility effects and makes it impossible for the target to gain concealment from or hide in areas of shadow or darkness.

Rice theorem, the proof of the part when the empty language belongs to the property

I was going through the classic text “Introduction to Automata Theory, Languages, and Computation” by Hofcroft, Ullman and Motwani where I came across the proof the Rice theorem as shown.

$ L_u$ => Language accepted by universal turing machine

$ P$ => property of a regular language

$ L_P$ => set containing the codes of the turing machines which accept those languages in $ P$

Theorem : (Rice’s Theorem) Every nontrivial property of the RE languages is undecidable.

PROOF: Let $ P$ be a nontrivial property of the $ RE$ languages. Assume to begin that $ \phi$ , the empty language, is not in $ P$ . we shall return later to the opposite case. Since $ P$ is nontrivial, there must be some nonempty language $ L$ that is in $ P$ . Let $ M_L$ be a $ TM$ accepting $ L$ . We shall reduce $ L_u$ to $ L_P$ , thus proving that $ L_P$ is undecidable, since $ L_u$ is undecidable. The algorithm to perform the reduction takes as input a pair $ (M,w)$ and produces a $ TM$ $ M’$ . The design of $ M’$ is suggested by Fig; $ L(M’)$ is $ \phi$ if $ M$ does not accept $ w$ , and $ L(M’)$ = $ L$ if $ M$ accepts $ w$ .

Construction of M' for the proof of Rice's Theorem

$ M’$ is a two-tape $ TM$ . One tape is used to simulate $ M$ on $ w$ . Remember that the algorithm performing the reduction is given $ M$ and $ w$ as input, and can use this input in designing the transitions of $ M’$ . Thus, the simulation of $ M$ on $ w$ is “built into” $ M’$ ; the latter $ TM$ does not have to read the transitions of $ M$ on a tape of its own. The other tape of $ M’$ is used to simulate $ M_L$ on the input $ x$ to $ M’$ , if necessary. Again, the transitions of $ ML$ are known to the reduction algorithm and may be “built into” the transitions of $ M’$ . The $ TM$ $ M’$ is constructed to do the following:

  1. Simulate $ M$ on input $ w$ . Note that $ w$ is not the input to $ M’$ rather, $ M’$ writes $ M$ and $ w$ onto one of its tapes and simulates the universal $ TM$ $ U$ on that pair. If $ M$ does not accept $ w$ , then $ M’$ does nothing else. $ M’$ never accepts its own input, $ x$ , so $ L(M’) = \phi$ . Since we assume $ \phi$ is not in property $ P$ , that means the code for $ M’$ is not in $ L_P$ .

  2. If $ M$ does not accept $ w$ , then $ M’$ does nothing else. $ M’$ never accepts its own input, $ x$ , so $ L(M’) =\phi$ . Since we assume $ \phi$ is not in property $ P$ , that means the code for $ M’$ is not in $ L_P$ .

  3. If $ M$ accepts $ w$ , then $ M’$ begins simulating $ M_L$ on its own input $ x$ . Thus, $ M’$ will accept exactly the language $ L$ . Since $ L$ is in $ P$ , the code for $ M’$ is in $ L_P$ .

Constructing $ M’$ from $ M$ and $ w$ can be carried out by an algorithm. Since this algorithm turns $ (M,w)$ into an $ M’$ that is in $ L_P$ if and only if $ (M,w)$ is in $ L_u$ , this algorithm is a reduction of $ L_u$ to $ L_P$ , and proves that the property $ P$ is undecidable.

We are not quite done. We need to consider the case where $ \phi$ is in $ P$ . If so, consider the complement property $ \overline P$ , the set of $ RE$ languages that do not have property $ P$ . By the foregoing, $ \overline P$ is undecidable. However, since every $ TM$ accepts an $ RE$ language, $ \overline {L_P}$ , the set of (codes for) Turing machines that do not accept a language in P is the same as $ L_{\overline P}$ , the set of TM’s that accept a language in $ \overline P$ . Suppose $ L_P$ were decidable. Then so would be $ \overline {L_P}$ , because the complement of a recursive language is recursive.

I could not understand the last paragraph in bold.

Breaking request validation where requestValidationMode property is set to 2.0

I’m trying to understand something I came accross when looking through documentation for HttpRuntimeSection.RequestValidationMode property.

In ASP.NET 4.0 and later, to disable the built in request validation two things have to happen:

  • Familiar validateRequest has to be set to false
    <system.web>         <pages validateRequest="false" />     </system.web> 
  • RequestValidationMode has to be set to 2.0
    <system.web>         <httpRuntime requestValidationMode="2.0" />     </system.web> 

Below is the explanation what happens if we set RequestValidationMode = 2.0 (From my first link above)

2.0. Request validation is enabled only for pages, not for all HTTP requests. In addition,the request validation settings of the element (if any) in the configuration file or of the @ Page directive in an individual page are used to determine which page requests to validate.

and the default 4.5…

4.5 (the default). In this mode, values are lazily loaded, that is, they are not read until they are requested.

Since 2.0 does protect HTTP requests from pages only, what are some examples of where 2.0 setting would fail but the default setting would not?