texts: Perfect matching in complete, weighted graph

texts:
I'm trying to find pairs in a complete, weighted graph, similar to the one below (weights not shown).

For each possible pair there is a weight and I would like to find pairs for including all vertices, maximizing the weight of those pairs.

Many of the algorithms for finding maximum matchings are only concerned with finding them in bipartite graphs (e.g. Hungarian algorithm). In this case the graph is not bipartite. The only algorithm I found that seems to fit the problem here is Edmond's Blossom algorithm and it's (revised?) Blossom V variant.

As far as I understand the complexity of Blossom is polynomial ($n^3$) and so with bigger graphs complexity increases quickly. I currently don't expect more than 100 vertices which should be manageable unless the $n$ in $n^3$ concerns the number of edges in the graph. In this case I might need to find a way to make the graph less dense.

My questions are:

Is Blossom/Blossom V the only algorithm that should be considered for this problem or did I miss any other contenders while digging into this?
Do you know if in these kinds of algorithms $n$ usually refers to the number of vertices or edges?
Since even with Blossom this might be computationally intensive I was wondering if someone can think of some smart steps to simplify the problem, maybe turning it into another problem that could be easier to solve.


texts:
This is about basic machine learning which I do not understand clearly.

I have 2 Gaussian models $G_1$ and $G_2$ and given a list of data as below.

(1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 18, 23)

I do not know which numbers were generated by which $G_i$ model, but I want to do Expectation Maximization for clustering.

So, what are the hidden variables? and how to perform Expectation and Maximization steps?

Could you show some calculation or short Python code of the likelihood metric? (Perhaps 2 iteration)

I got the basics of EM algorithm from here, but I cannot apply to this question. http://www.nature.com/nbt/journal/v26/n8/full/nbt1406.html


texts:
I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand;
What I would like to ask, if there is a certain way to find out O-Notation? Actually I know that the purpose of O-Notation, it helps us to estimate the effciency of algorithm. But in a specific questions like O(2^n) * O(n^10) I assumed that O(2^n * n^10) as in the worst case but learned that I was false, it should be 2^n and I don't know why? Shouldn't we think that which term would go faster to eternity, and in this case I thought that when I multiply both then it can go faster than 2^n, can't it? Could anyone explain please ? Just short and with beginner sight:)


texts: Remove from black/red tree subtree with red root, red sibling and black parent in $O(\lg n)$

texts:
How can i remove from a red/black tree a subtree whose root and its sibling are red, and their parent is black, in $O(\lg n)$ time, while keeping the red/black properties at the end of the process?

In other words:
I have a black/red tree with $n$ nodes, a given black node $y$, and his two red children $x$ and $z$. How can I delete the subtree of $x$ in $O(\lg n)$ time, while keeping the red/black tree properties at the end of the process?

This is an homework question.


texts: How prefix property of language affects the PDA

texts:
I know that every DPDA (deterministic PDA) is a PDA (more specifically, non-deterministic PDA). But I found it hard to understand, not that every DPDA is an NPDA, but some results that contradict this fact:

In PDA we have two modes of accepting the language, which are "empty stack method" and "final state acceptance method".
Language accepted by both of these modes in PDA (NPDA) are equal, but in DPDA language accepted by "final state method" > "empty stack method" (strictly).
Thirdly we know that those "deterministic context-free language" having prefix property can not be accepted by "empty stack". An example is $L = \{ a^n \mid n>0 \}$. So for these languages, we need final state method of DPDA.

Now my doubt is that if every DPDA is NPDA then the language accepted by both of the modes should be same in DPDA. I think that I am missing something here because individually all of the above result are ok, but when put sequentially they seems to cause a contradiction.


texts: Can one have a condition like this in semidefinite programming?

texts:
Is it possible to have the following condition in a semidefinite programming as a constraint?

$
         M=
            \left[ {\begin{array}{cc}
             a & \sqrt{u} \\
             \sqrt{u} & b \\
                \end{array} } \right]
        \geq 0$

where $\geq 0$ means positive semidefinite.


texts:
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is important that the grammar at hand is correct, that is generates exactly the desired words.

We can often argue on a high-level why the grammar is an adequate representation of the desired language, omitting a formal proof. But what if we are in doubt or need a formal proof for some reason? What are techniques we can apply?

This is supposed to become a reference question. Therefore, please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!


texts:
I am working through Sipser, and I am trying to understand some of the algorithms described in Space Complexity, but I am having a hard time understanding the presentation of the material (especially Savitch's theorem). I have a very strong intuition for time complexity, but I don't understand how space complexity fits into a heirarchy of time complexity, and I think it has to do with the fact that it is all discussed in terms of Turing machines. It is hard to see how space and time are related when I'm wasting time untangling convoluted algorithms described in terms of Turing machines.

Does anyone have any advice on how to think about Turing machines vis-a-vis contemporary computation in general? It is unintuitive to think about algorithms in terms of input strings, tapes, and machines simulating machines. I don't feel like I am leveraging my existing knowledge of computers and programming to more deeply understand the proofs and algorithms being presented.

I think I just need help understanding how space varies based on the data structure of the input. For some input of size $n$, are the bits required to represent each entity of the input negligible? Say our language is a set of objects that are all of a certain type, and each object is massive. How does space usage vary vs. a similar language with very small objects?

Edit: I understand now that space complexity fits in with time complexity because they are both resources used to determine whether some string is a member of a language; Or in other words, whether some element belongs to a particular problem (see here).


texts: What are some of the methods that NLP practitioners use to automatically learn linguistic features from text?

texts:
I am learning about NLP, with an eye to starting some practical NLP projects. I see that many of the algorithms for relation extraction and named entity recognition require you to identify linguistic features like "word comes before a period" or "word is the last word in a verb phrase." This seems like it takes a lot of manual work. You have to look at instances in the text and parse out features.

I also know that in distant supervised relation extraction they generate tons of features from tons of examples -- so it seems like there are ways to extract features automatically. Are there any ways of doing this? For instance, are there ways to grep for known names and then automatically detect the features around those names? Can anyone list the names of some methods that exist for doing this?


texts: Big Oh and Big Omega when $n$ and $\log n$ terms are in $f(n)$

texts:
having problems with big oh and big omega functions when there is a $\log n$ added or subtracted. For example how do I deal with $n+\log n$ or $n-\log n$ when I have to determine whether the function is in $\Omega(n)$ or in $\Omega(n^2)$? For example, is $n-\log n$ in $\Omega(n)$ or in $\Omega(n^2)$?
I cannot ignore the log function and am not sure how to deal with it.  Polynomials and logs when multiplied I find OK. But I have a mental block over this one so help would be appreciated


texts: How to apply Arden's theory to determine a regular expression

texts:
If $P=ab$ and $Q=a^*$,
how do I use Arden's theorem to determine the regular expression $R$.
I'm not sure if I am supposed to just substitute the values of $P$ and $Q$ in the equation $R= Q + RP$. Also how would I use that to check that $R$ satisfies Arden's equation.


texts: If a Triple Graph Grammar rule counts as a Mathematical Proof

texts:
I am intrigued by Triple Graph Grammars (TGG) as a potential for formal mathematical proof.

  Triple Graph Grammars (TGGs) are a technique for defining the
  correspondence between two different types of models in a declarative
  way.

In some systems, proofs are simply trees of rules being applied to transform one syntax tree of terms into another. I don't really have a firm grasp of what that actually means in practice, but I think I understand the gist of it. As such, a proof is a transformation of a into b, so a correspondence between two different models. Some sort of isomorphism.

The diagrams below show (roughly) that there are links between source and target objects, defining how to transform them (bijection). I'm wondering if a TGG rule has enough information in it to allow it to be considered a valid proof of a transformation of isomorphism. That is, and I don't fully understand how to apply TGGs, you define a TGG between two forms of an object (or more generally, between two objects), and that definition is equivalent to a formal proof of the isomorphism between the two objects. Wondering if this is true or if it is close to true. If close / along the lines of the right direction, wondering what it would require to make it into a valid proof.

To summarize, the questions are:

If a TGG counts as a valid proof of transformation (maybe of isomorphism) from $A \to B$.
If a TGG counts as a valid proof of transformation from $B \to A$.
If not, what would be required to make it into a valid proof.

Some more notes are:

  A triple graph $G =(G_S \overset{s_G}{\longleftarrow} G_C \overset{t_G}{\longrightarrow} G_T)$ consists of three graphs $G_S$, $G_C$, and $G_T$, called source, correspondence, and target graphs, together with two graph morphisms $s_G : G_C \to G_S$ and $t_G : G_C \to G_T$. A triple graph morphism $m = (m_S, m_C , m_T) : G \to H$ consists of three graph morphisms $m_S : G_S \to H_S$, $m_C : G_C \to H_C$ and $m_T : G_T \to H_T$ such that $m_S \circ s_G = s_H \circ m_C$ and
  $m_T \circ t_G = t_H \circ m_C$. A typed triple graph $G$ is typed over a triple graph $T_G$ by a triple graph morphism $type_G : G \to T_G$. [source]

A function transforming A into B doesn't keep track of the actual individual steps between transformation, so the information is lost. But the TGG does. The only way to "prove" that A can be transformed to B with a function is to actually apply the function and compare the outputs. But with a mapping defined in a TGG, the "proof" would be the mapping itself, so you don't have to actually perform the transformation (or it seems). So given A and B and R (rule) in TGG context, R is the proof, we don't have to try converting A $\to$ B.

An example of this would be the transform between a parse tree and an abstract syntax tree. The parse tree let's say is the actual individual tokens organized into a tree of symbols and words, where every object in the tree is the same type of object (let's say a "parse node" object). The AST though is a tree of custom objects like "function node" and "variable node". So you convert the parse tree to the AST. How to prove that AST came from the parse tree. A function requires recomputing the output, maybe a TGG rule means it's automatically proven as a "derivation" of the parse tree.

Given I have parse tree A and AST B in memory, I would like to be able to say "A becomes B" without having to recompute it. I would like to say "B came from A" as well, which seems possible because of the bidirectional mapping of TGGs.


texts:
From a database theory point of view, what term can be used to refer to a key that does not violate the rules of the engine within which it is implemented, but fails to conform to any sort of normalisation? For instance, if a timestamp was used as a primary key. Primary keys are supposed to ensure that no two rows refer to the same thing, but as long as the values within the so-called primary key column is unique, the database engine may not detect any violation.

The reason for wanting to obtain a technical or academic term for this is to describe a situation where there is a primary key that has been technically successfully implemented, but is conceptually flawed.


texts:
See title. I'm trying to apply the method from this question. What I have so far is this, but I don't know how to proceed from here on:

T(n) = T(n-1) + n2

T(n-1) = T(n-2) + (n-1)2 = T(n-2) + n2 - 2n + 1

T(n-2) = T(n-3) + (n-2)2 = T(n-3) + n2 - 4n + 4

T(n-3) = T(n-4) + (n-3)2 = T(n-4) + n2 - 6n + 9

Substituting the values of T(n-1), T(n-2) and T(n-3) into T(n) gives:

T(n) = T(n-2) + 2n2 - 2n + 1

T(n) = T(n-3) + 3n2 - 6n + 5

T(n) = T(n-4) + 4n2 - 12n + 14

Now I have to find a pattern but I don't really know how to do that. What I got is:

T(n) = T(n-k) + kn2 - ...???


texts: What is the relation between P vs. NP and Nature's ability to solve NP problems efficiently?

texts:
I was thinking about how nature can efficiently compute ridiculous (i.e. NP) problems with ease. For example, a quantum system requires a $2^n$ element vector to represent the state, where $n$ is just the number of particles. Nature doesn't need any extra time despite the exponential nature of "solving" this $n$-particle system.

This may not be a wholly valid assumption, but the action principle in physics makes me think that nature always wants to do things the easiest way. If that's not true, then this question is probably moot.

If we found that nature was NOT capable of solving some problems efficiently, does this mean we are doomed in terms of being able to solve NP problems in polynomial time? Are the laws of physics a strong enough weapon for tackling P vs. NP? Is the converse of the first question/assertion also true (if nature can do it, then there must be a way for us to as well)?


texts: Advances in recent time in Von-neumann self replication idea

texts:
I have read about Von-neumann self replication from  Theory of Self-reproducing automata, which are lecture notes reconstructed from lectures in book of the same name. Theory of Self-reproducing automata

  Its looks really interesting that neumann has formalize this even far before the discovery of DNA. I'm looking the work now from biological perspective and the work by Jeremy England his paper on Statistical Physics of Self-Replication and other similar work in irreversible biological process.

The work that Von-neumann did was around 50's. Is there any recent relevant work in this field based on the neumann's work. One that i could see is Enhancing the Robustness of
Self-Replication Processes

Thank You.


texts:
Let $C$ be a $[n,k]$ cyclic code over $\mathbb{F}_q$ with $(n,q)=1$.

I want to show that $(1, \dots, 1)$ is a codeword iff $X-1 \nmid g(X)$.

$g(x)$ is the generator polynomial.

We suppose that $(1, \dots, 1)$ is a codeword.

We consider the following correspondence

$$\pi: \mathbb{F}_q^n \to \mathbb{F}_q[x] / x^n-1, (a_0, a_1, \dots, a_{n-1}) \mapsto a_0+ a_1 x+ \dots+ a_{n-1} x^{n-1}$$

Then $(1, \dots, 1) \mapsto 1+ x+ \dots+ x^{n-1}$.

We want to show that $X-1 \nmid g(X)$.

Then $g(X)=b(X)(X-1)$ for some polynomial $b(X)$. How can we get a contradiction?

How can we show that if $X-1 \nmid g(X)$ then $(1, \dots, 1)$ is a codeword?


texts: How does a dual core microprocessors run so many programs?

texts: I have a laptop with Intel dual core and it runs, the OS windows, and many application from Opera, age of empires, word, excel etc open at once just fine. If it only has 2 cores, how can so many programs work? How exactly does it manage to do all these? Does operating system have something to with it?


texts: Polylogarithmic value-bounded concurrent data structures such as max register, counter, and monotone circuit

texts:
While reading the research paper Polylogarithmic Concurrent Data Structures from Monotone Circuits [@JACM'2012] by James Aspnes, Hagit Attiya, and Keren Censor-Hillel, I am not sure about some points and need some verification and explanation.

In the first three sections of the paper, the authors presents constructions of useful concurrent data structures, including max register and counters with bounded values, with step complexity that is polylogarithmic in the number of values the object can take or the number of operations applied to it. Specifically (and extremely in brief),

  The max register is an object $r$ supporting both WriteMax(r,t) and ReadMax(r) operations. It is recursively constructed from a tree of increasingly large max registers. The implementation is wait-free and linearizable.

  The counter, supporting an CounterIncrement() operation and a ReadCounter() operation, is structured as a binary tree of max registers. The implementation is also wait-free and linearizable.

My problems are as follows:

  (1) On the max register: What is the space complexity, i.e., the number of base objects of multi-writer multi-reader (MWMR, for short) registers, of the recursive implementation?

[[In my opinion:]] It is $2m - 1$ for there is exactly one MWMR register for each node in the tree. In particular, the tree can be thought of as the logic structure of an underlying array of $2m-1$ MWMR registers.

  (2) Also on the max register: Is it possible to implement a max register with only a single MWMR register? Are there any related work?

[[(EDIT) In my opinion:]] I have found a related paper: Time and Space Lower Bounds for Non-blocking Implementations [@PODC'1996], in which Jayanti et al. show that

  Operations must take $\Omega(n)$ space and $\Omega(n)$ steps in the worst case, for many common data structures, including (unbounded) max registers and (unbounded) counters, where $n$ is the number of concurrent processes.

However, I have not realized similar conclusions concerning about value-bounded data structures.

  (3) On both the max register and the counter: Are there any related work on the max&min register supporting both ReadMax(r) and ReadMin(r)? Similarly, are there any related work on the inc&dec counter supporting both CounterIncrement() and CounterDecrement()?


texts: Closed-form expression for the sums of the rows of the Trinomial triangle

texts:
There is a question in the second chapter of the book that I'm unable to solve, and unfortunately algorist.com does not provide a rigorous enough solution, or maybe I can't quite understand it.
Here is the question:

I've noticed the sums of rows are the powers of 3, and it's intuitively obvious that the sums of rows are multiples of 3, however I can't prove that they are powers of 3.
Any help would be much appreciated.
The Algorithm Design Manual from Steven S. Skiena
You can get it from here.
Also here is the solution I found on algorist.com .


texts: How to compute an optimally cost-effective cache strategy?

texts:
I am looking for advice in the following optimization problem. I have a website (system) that receives database updates. The updated information is later returned in queries made to the same system. In order to speed up the system the obvious solution is to cache data in each location. I have begun to decompose the times it takes to place data in different caches. I will end up with.
Cu = uth computation time
Su = storage required to store result of uth computation
SCn = storage cost using nth storage resource
Wn = storage cache write time for nth storage resource
Rn = storage cache read time for nth storage resource

I am ignoring local microprocessors caching for now. For example I want to make a storage purchasing decision. I can buy plenty of SSD, Spinning drives and/or RAM. But given the amount of possible caching I want to buy what makes most sense.
Here are some considerations for a cost function. Storage can be simplified since there will be an allocated space that will cost X dollars. I am struggling a bit more with timing. Clearly I could minimize only the time it takes to query and update. But that does not address responsiveness, we need servers to be responsive with every request. As opposed to the ability to process every single update and query at once in a couple of days, instead of three. I am constructing a $$ to seconds function. This function would imply, we are willing to pay $X for a computer that responds in Y seconds.
An optimization algorithm is needed, there are a lot out there and I am not sure which could be a good fit for this problem.
I am having a lot of difficulty finding research similar to this description. And I do know I will need to redo this optimization a number of times, so I will end up writing code so I don't have to do this every time.


texts: A variation of the baseball elimination problem

texts:
I suppose you are all familiar with the baseball elimination problem (it is about determining whether some team with particular number of points can finish in the first place, when there are still such and such games to be played by other teams).

The rules there are rather simple - the winner gets a point, while the loser gets nothing. But what if we changed those rules, so that the loser would get -1 point for each game lost. Could it still be brought down to the max-flow problem then? I've been thinking about this, but there's no way to do that in my opinion.


texts: Nearest visible neighbors in a raster image

texts:
I have a raster image with a number of arbitrary shapes (blobs). I am interested to find, for every blob, its immediate neighbors, i.e. those that are visible from it in a straight line. The search can stop after a few neighbors (say 3) have been found, by decreasing closeness.

I imagine that a growing process around every shape (i.e. constructing offset curves of the boundary with increasing offset size) could work, excluding shadow areas created by the obstacles.

I allow myself a computing budget proportional to the image size (number of pixels), not more. So the above procedure will probably not achieve that goal, as the shapes will have "zones of influence" that overlap each other, and the total workload risks to be proportional to the number of shapes as well.

I am looking for suggestions on ways to reduce the processing time. Vectorizing the scene and working with discrete segments is allowed. Approximate solutions are allowed. In particular exact distance computation is not required. The exact visible area on the neighbors is not required, only mutual visibility matters.


texts:
How is out-of-order instruction execution related to superscalar execution?

How is data hazard detection and handling affected by superscalar execution?


texts: How many ways to find a sum totalling n using only certain Integers?

texts:
Using an infinite supply of integers of a set S, how many ways are there to reach a sum of n?

Clarification: The Integers are arbitrary, positive, and may not include 1.

At first I thought it was the coin changing problem without pennies, but it's not because the order is important so coin changing will always be less.

It's also like Leonardo's Leaps but with arbitrary leap sizes, and again possibly without a leap of 1.


texts: The upper bound on a Nondeterministic Finite Automata's configurations number

texts:
In "Engineering: A Compiler" 2nd ed. by Cooper and Torczon,
in 2.4.1 "Nondeterministic Finite Automata" of Chapter 2,
section "Equivalence of NFAs and DFAs"

discusses the upper bound of a NFA's configurations number.

Here

NFA stands for Nondeterministic Finite Automata
DFA stands for Deterministic Finite Automata

NFA is a  is a five-tuple $(S, \Sigma, \delta, s_0 , S_A)$, where

$S$ is the finite set of states in the recognizer, along with an error state $s_e$.
$\Sigma$ is the finite alphabet used by the FA. Typically, $\Sigma$ is the union
of the edge labels in the transition diagram.
$\delta(s,c)$ is the FA's transition function. It maps each state $s ∈ S$
and each character $c \in \Sigma$ into some next state. In state $s_i$ with input
character $c$, the FA takes the transition $s_i \xrightarrow{\text{c}}\delta(s_i ,c)$.
$s_0 \in S$ is the designated start state.
$S_A$ is the set of accepting states, $S_A \subseteq S$.

A configuration of a NFA is defined as follows

  Each time the NFA must make a nondeterministic choice, the NFA clones
  itself to pursue each possible transition. Thus, for a given input
  character, the NFA is in a specific set of states, taken across all of
  its clones.

  In this model, the NFA pursues all paths concurrently. At
  any point, we call the specific set of states in which the NFA is
  active its configuration.

  When the NFA reaches a configuration in
  which it has exhausted the input and one or
  more of the clones has reached an accepting state, the NFA accepts the
  string.

Given the definitions above, the books states

  Consider the state of an NFA when it has reached some point in the
  input string. [...] the NFA has some
  finite set of operating clones.

  The number of these configurations can be bounded;

  for each state, the configuration either includes one or
  more clones in that state or it does not. Thus, an NFA with $n$ states
  produces at most $\lvert\Sigma\rvert^n$ configurations.

My question.

Please explain in as much details as possible, how $\lvert\Sigma\rvert^n$ is derived.

I need help, because while trying to follow the book's reasoning, I get lost right after this sentence

  for each state, the configuration either includes one or
  more clones in that state or it does not.

This sounds like the upper bound on the number of configurations should be $2^n$, but instead the book gives $\lvert\Sigma\rvert^n$ bringing in $\Sigma$ seemingly out of the blue.


texts:
What is an upright rectangle?

I came across the phrase in my homework -

"The bounding box of a set of S points is the smallest upright rectangle containing S. Describe and analyze an algorithm to compute the bounding box of n points in the plane using fewer than 3n comparisons."

Can anyone explain to me what is meant by an upright rectangle?


texts: How to implement graph search to solve Sudoku puzzle

texts:
My teacher pointed out to us during lectures that we could use Graph Search to help us solve Sudoku puzzles which has left me puzzled .

I dont see how this is possible as Graph Search is mostly about getting from Node A to Node B. He mentioned about how its a directed graph where the nodes correspond to partially completed puzzle

What is the general idea behind using Graph Search to solve Sudoku Puzzle


texts: Turing machine Representation for string of 3 letters

texts:
Can someone explain to me what this statement implies? I am assuming that it means that a string consisting of three characters repeated. What I don't understand is if the repeated string is all 0s or all 1s or both?

Give the state diagram of a machine (any Turing-Complete model) that decides the following languages over {0,1}:

{w : w = xxx, x ∈ Σ*}


texts: Polynomial-Time reduction from Partition to MakeSpan

texts:
Partition Problem:

Input: $A:=$ {$a_{1}, ..., a_{n} $}. $a_{i} \in \mathbb{N}$ $\forall i \in$ $\{1, \ldots, n\}$.

Question: Exists a subset $A_{1} \subset A$ with: $\sum_{a_{i} \in A_{1}} a_{i} = \sum_{a_{i} \in A\setminus A_{1}} a_{i}$ ?

Output: Yes or No.

Makespan Problem:

Input: Jobs $J$ and $b \in \mathbb{N}$.

Question: Exists a Schedule $S$ with $\text{FinishTime}(S) \leq b$ ?

Output: Yes or No.

So I have to change the Makespan Problem in a way that the Partition Problem gives me the correct answers for the Makespan Problem. $Partition \leq_{p} Makespan$

First Problem: When the Makespan Problem has $m$ machines and not two, I don't know how I can use Partition for that scenario. I could recursive iterate the jobs (so that I split Makespan in several Partition Problems) but then I had to use the Partition Problem several times and with my understanding, I am only allowed to change the Input for a Polynomial-Time Reduction.

But let's say we have $m= 2$ machines. If Partition has the Output "Yes", I know that there exists an optimal solution for the Makespan, so that I have an optimal Schedule with value= $\dfrac{1}{m} \cdot \sum_{a_{i} \in A}$. If $b \leq \dfrac{1}{m} \cdot \sum_{a_{i} \in A}$, the result for Makespan is also Yes.

Second problem: But what happens if there is no optimal solution? I only receive "No" from Partition but I don't know how bad the Partition result is.

I would be really happy if someone has an idea for this, I don't know how to I could find a solution for this.


texts: what is the difference between "language" and "certificate" in complexity theory?

texts:
Seems like they both are set of strings for which the problem returns "yes" in decision problems.

P class is consists of problems so we can only say a problem is in P. But we sometimes say that a language L is in P. why?


texts: What is the optimal combination of transducers with limited capabilities to a more powerful transducer?

texts:
Assume we have a number of transducers with limited information processing capabilities. Are there theoretical results (proofs) on how these transducers can be combined by some sort of communication into one joint transducer to reach a maximum of information processing capabilities? Does this work for universal transducers or only for certain problems?

Illustrative example: Let's say I have 3 signal-processing computers and need to combine them to steer a self-driving car. The cameras and other sensors provide a lot of information, e.g., x GBit/s. Each single computer would be overwhelmed by the amount of information. But by combining the computers the information processing capabilities might be sufficient. Are there theoretical results on how or how not to do that to make the best use of the available computers?

Background: I recently came across Stafford Beer's "Viable Systems Model". In my interpretation, it claims to be such an optimal architecture for combination. But I have only found anecdotal evidence or reference to common sense for most parts of that claim, no formal proof.


texts: What parts of linear algebra are used in computer science?

texts: I've been reading Linear Algebra and its Applications to help understand computer science material (mainly machine learning), but I'm concerned that a lot of the information isn't useful to CS. For example, knowing how to efficiently solve systems of linear equations doesn't seem very useful unless you're trying to program a new equation solver. Additionally, the book has talked a lot about span, linear dependence and independence, when a matrix has an inverse, and the relationships between these, but I can't think of any application of this in CS. So, what parts of linear algebra are used in CS?


texts:
I'm looking at Wikipedia's pseudocode implementation of A* and found myself wondering about what they call openSet. That is, the neighbours we've seen, but not yet analyzed.

The first part of the outer loop reads:

 current := the node in openSet having the lowest fScore[] value

And this makes sense to me, as I intuitively think of openSet as a heap. So we just pop() and get whatever's most interesting to look at next.

But when looping through the neighbours in the inner loop, this happens:

 if neighbor not in openSet // Discover a new node
                openSet.Add(neighbor)

And obviously, that's not going to go well with a heap. So what I'm wondering is this:

How is this contains() check meant to be carried out? Am I supposed to use something like an AVL tree to get logarithmic performance on both lookup and pop?

Would it make sense to keep a separate hashset to keep track?

Or can I altogether ignore this step?

What would be most effecient?


texts: Are coevolutionary "Free Lunches" really free lunches?

texts:
In their paper "Coevolutionary Free Lunches" David Wolpert and William Macready describe a set of exceptions to the No Free Lunch theorems they proved in an earlier paper. The exceptions involve two-player games in which a player tries to minimize expected search cost given optimal play, or at least good play, by an opponent.

Free lunches are "allowed" in this case because the exact choice of cost function to minimize changes depending on which fitness (i.e. objective) functions previous rounds of play have "ruled out." In other words, given that an opponent already knows something about the game, and chooses responses that minimize the player's expected return, the player can eliminate certain fitness functions without having to evaluate them. To illustrate how this works, W&M provide this chart:

Here, $\langle g \rangle$ represents the search algorithm that pays no attention to the opponent's moves; $\langle g \rangle_{1}$ represents the search algorithm that considers all possible opponent replies to each move; and $\langle g \rangle_{2}$ represents the search algorithm that samples just one possible opponent reply to each move.

This illustrates the character of the free lunch provided: algorithms that take into account information provided by the opponent do better than algorithms that don't, and those that collect as much information as possible from the opponent do better than those that only collect some. W&M amplify this point in their later discussion of opponent intelligence. They show that even when an opponent is not omniscient, but has partial knowledge, the player can exploit its partial knowledge. In the case of total ignorance this won't work because the opponent always replies with a random move. In that case, there appears to be no gain:

  the expected performance of the agent will be the average over the antagonist’s possible responses.

I guess this looks like $\langle g \rangle$ above. But in cases where the opponent has some knowledge, algorithm performance appears to increase monotonically with opponent intelligence.

What confuses me about all this is that the argument appears to boil down to the following trivial-seeming claim: across all problem domains, algorithms that bother to learn from knowledgable opponents do better than algorithms that do not. That is, as long as you don't turn down the free lunch, you can have it.

In effect, lunch is free because the opponent is buying.

If that's true, then couldn't we imagine a whole range of games in which, say, players play cooperative games with oracles, and those that refuse to cooperate perform worse on all problems? That's a free lunch in the same sense, right? But then we haven't explained where the oracle's knowledge comes from.

Does this mean that if we had to model the source of the other player's knowledge, we'd be back in the No Free Lunch zone? Or is the claim really that this sort of competitive play yields better outcomes even when both players start out in total ignorance, as the phrase "free lunch" seems to imply?


texts:
There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars.

Some people don't have the right bills to pay exactly $p_i$, so they come up with the following algorithm.

  First, everyone puts some of their money on the table. Then each individual takes back the money they overpaid.

The bills have a fixed set of denominations (not part of the input).

An example:
Suppose there are two people, Alice and Bob.  Alice owes \$5 and has five \$1 bills.  Bob owes \$2 and has one \$5 bill.  After Alice and Bob put all their money on the table, Bob takes back \$3, and everyone is happy.

Of course, there are times where one doesn't have to put all his money on the table. For example, if Alice had a thousand \$1 bills, it's not necessary for her to put them all on the table and then take most of them back.

I want to find an algorithm with the following properties:

The input specifies the number of people, how much each person owes and how many bills of each denomination each person has.
The algorithm tells each person which bills to put on the table in the first round.
The algorithm tells each person which bills to remove from the table in the second round.
The number of bills put on the table + the number of bills removed from the table is minimized.

If there is no feasible solution, the algorithm just return an error.


texts: Reduction to longest path from longest chain of tiles

texts:
We have some tiles that each tile has 2 number written on it. We can rotate each tile in order to swap the position of numbers. We want to find the longest chain of tiles starting with a certain tile so that adjacent tiles have the same number on their common endpoint. If the tiles were

 7-4, 11-8, 11-11, 4-2, 7-5, 11-10, 10-5

the longest chain starting with tile 11-8 would be:

8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2

I tried to reduce this problem to the longest path problem:

Consider every tile as a vertex.
If two tiles have a common number in them they are adjacent.
create a sink vertex and connect it to every other vertices.

the resulting adjacency list of graph is:

7-4  : 4-2, 7-5, sink
11-8 : 11-11, 11-10, sink
11-11: 11-8, 11-10, sink
4-2  : 7-4, sink
7-5  : 7-4, sink
11-10: 11-8, 11-11, sink
10-5 : 11-10, 7-5, sink

Now for finding the longest chain starting vertex 11-8 you simply have to find the longest simple path form 11-8 to sink which is 8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2.

But I am being told that in order to say that this problem is reducible to longest path problem I have to prove it the other way around. It means I have to prove that every graph can be represented by some configuration of tiles. However I know that some graphs can't be represented by tiles for example the below graph couldn't be represented by any such tiles.

A-----B
|   / |
| /   |
C-----D

So technically my approach is wrong. But I wonder, I have shown that in general you have to solve the longest path problem to find the longest chain of such tiles, why isn't it enough to show that this problem can't be solved in polynomial time? Why is it necessary to show that all the graphs can be represented by a combination of such tiles?


texts: Can a processor without stack pointer registers, have a subroutine calls and interrupts?

texts:
Suppose a processor does not have any stack pointer registers, which of the following statements is true?

It cannot have subroutine call instruction
It cannot have nested subroutines call
Interrupts are not possible
All subroutine calls and interrupts are possible

====================================================================

I think answer is 2.

Reason- Because in nested subroutine calls, we push old subroutines into stack and point most recent call with stack pointer.

Please, explain which is the correct option. According to book the answer is 1.


texts: Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

texts:
So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices.
In general case, it is exponential.
I am trying to determine whether the number of maximal cliques in a $(2C_4, C_5,P_5)$-free graph is linear or polynomial with respect to the number of vertices.
In a $(2C_4, C_5,P_5)$-free graph, the largest induced cycle is of length 4, and no two 4-cycles are edge-disjoint.
Is there a paper that mentions such result?


texts:
In my books it is written that the concept of pipelining can happen only with Harvard structure as CPU can both fetch data from and write back data to memory at the same time my question is how can fetching and writing back be done at the same time when there is only one bus for data just like von Neumann structure? How can using an instruction bus be helpful when it only carries instruction but not data?

So if I want to add 2+5 here 2 and 5 are data but + would be the instruction right?
If I fetch 2 and 5 from data cache and add from instruction cache then execute and again write back the result 7 which would be a data to memory and before the whole process is done fetch another data for example 7 and 6 like in what the book stated according to the picture would it still be fetching (the data 7 and 6) and rewriting the data 7 (result of execution) happen at the same time both these numbers are data and have to be fetched and rewritten using data bus so it still be impossible to fetch and rewrite them at the same time and the instruction bus wouldn't be useful.


texts: Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes?

texts:
When we have only an asymptotic upper bound, we use $O$-notation. For a given function $g(n)$, we denote by $O(g(n))$ (pronounced “big-oh of $g$ of $n$” or sometimes just “oh of $g$ of $n$”) the set of functions
$$O(g(n))= \left\{ f(n):\text{ there exist positive constants }c\text{ and }n_0\text{ such that},\\ 0\leq f(n)\leq cg(n),\text{ for all }n\geq n_0 \right\}$$
This excerpt has been taken from introduction to algorithms 3rd edition. What I fail to understand is that how can algorithms with a linear runtime have an asymptotic upper bound when linear functions don't have asymptotes or is there a loophole in my thinking?


texts: Proof that Dempster-Shafer Normalised rule is Associative

texts:
Hint: I know it is associative and I just need a proof: (m1 ⊕ m2 ) ⊕ m3 = m1 ⊕ (m2 ⊕ m3) that will show that the operation "⊕" is associative. Thank you in advance!

operation "x" in the image is multiplication!


texts:
Is there a relatively simple way of telling if two pieces of text are semantically similar?

Some assumptions that are valid:

It is all english
I have a list of all the important nouns

Are there any strategies that I should pursue? Looking for something that is relatively computationally cheap, though something that could be scaled to improve accuracy at the expense of computational power would be a bonus.

Note:

Assume that there are not enough posts for some type of probabilistic analysis, but some type of NN might be feasible (I think, just don't know enough about it).


texts: how to draw a complement of a Turing Machine?

texts:
I am now pretty confident on how I would turn something into a Turing Machine. Now my question is how do you convert TM into a complement of a Turing Machine. From what I can remember in Finite Automata, complementing it you would just turn a start state into a ending state, also if you have an ending state you would make it into a start state..How would you do complement of a Turing Machine ?

For example here I have a simple TM of a Palindrome and I want a Palindrome'


texts: Why do many floating point numbers appear compact in base16 and base32 representation? (IEEE 754)

texts:
Consider 3 randomly chosen floating point values and their base conversions:
Floating point        Base-16    Base-15
0.5898704528808594  = 0.9701c    0.8cac2d1d9bd5e9
0.21180343627929688 = 0.3638c    0.329c837b2b291b
0.8631706237792969  = 0.dcf8c    0.ce3302d46d553

The same issue occurs with Base-24, and 32: The representation of the float is very compact.
These were found by searching random IEE754 binary64 double numbers, isolating those with the criteria of less than 6 hex digits. To reduce the search, I forced the lower 33 bits of the mantissa to 0 prior to converting to double. I'm not entirely sure why, but this only seems to happen if the lower 33 bits of the mantissa are zero. I ended up with a list of only 1048225 that met the criteria after 2.2 billion numbers, which is strikingly close to 2^20.
In fraction form, these 3 numbers happen to have a denominator of 262144. Others I've found have denominators of 1048576, 65536, 262144, etc. - the denominator always seems to be a power of 2 when this happens.
Is there an explanation for this?


texts: A median of an AVL. How to take advantage of the AVL?

texts:
Here is the source of my question.

  Given a self-balancing tree (AVL), code a method that returns the
  median.

  (Median: the numerical value separating the higher half of a data
  sample from the lower half. Example: if the series is

  2, 7, 4, 9, 1, 5, 8, 3, 6

  then the median is 5.)

I can offer the following solution:

Traverse the given tree, return the number of elements.
Traverse  n / 2 + 1 (if n is odd) the tree again applying an in-order tree walk. The value of the n / 2 + 1th element is the median.

But I can do it with a binary search tree, can't I?
Is there a better algorithm for an AVL?


texts: Consistent theory based on L and not(A->A) is a theorem

texts:
I am working on this problem in which I have a theory $T$ based on language $\mathcal{L}$ and the only information we have is that T is consistent and $\vdash \lnot(A \rightarrow A)$. Given this information, how can I know if this theory is sound, complete and/or decidable?
My only guess is that I can say that $T$ is sound because since $T$ is consistent and we can derive $\lnot(A \rightarrow A)$ from axioms and inference rules, $\lnot(A \rightarrow A)$ is a theorem and because of that we can assume that $T$ is sound (because the premises and conclusions are true).
Am I correct? What else can I say about this theory?
Thank you!


texts:
I am writing code to evaluate the following expression:
    $$ \frac{(a+b+c)!}{a! b! c!} $$
where $a$, $b$ and $c$ are on the range of $10$ to $500$. The result is going
to be a floating point number. I could use a big number package, but the code
will run slowly. I am using 64-bit floating point numbers.

I claim by doing as much of the computation in integer (maybe 64 bit) I will minimize the floating point round off error. Therefore, I claim that if put the integers to be multiplied together in an array, cancel common denominators, and then do the final computation in floating point I will minimize round off error.

Do I have this right?


texts:
There is the exclusive queue problem in The Little Book of Semaphores, which is stated as follows:

Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor. When a leader arrives, it checks to see if there is a follower waiting. If so, they can both proceed. Otherwise it waits. Similarly, when a follower arrives, it checks for a leader and either proceeds or waits, accordingly. Also, there is a constraint that each leader can invoke dance concurrently with only one follower, and vice versa.

The author's solution:

leaders = followers = 0
mutex = Semaphore(1)
leaderQueue = Semaphore(0)
followerQueue = Semaphore(0)
rendezvous = Semaphore(0)

def leader_thread():
   mutex.wait()
   if followers > 0:
      followers--
      followerQueue.signal()
   else:
      leaders++
      mutex.signal()
      leaderQueue.wait()

   dance()
   rendezvous.wait()
   mutex.signal()

def follower_thread():
   mutex.wait()
   if leaders > 0:
      leaders--
      leaderQueue.signal()
   else:
      followers++
      mutex.signal()
      followerQueue.wait()

   dance()
   rendezvous.signal()

However, I think there is a simpler solution:

leader_mutex=Semaphore(1)
follower_mutex=Semaphore(1)
leader_rendezvous=Semaphore(0)
follower_rendezvous=Semaphore(0)

def leader_thread():
   leader_mutex.wait()
   leader_rendezvous.signal()
   follower_rendezvous.wait()
   dance()
   leader_mutex.signal()

def follower_thread():
   follower_mutex.wait()
   follower_rendezvous.signal()
   leader_rendezvous.wait()
   dance()
   follower_mutex.signal()

It is quite obvious and very similar to the queue problem solution mentioned in this book, so I wonder why it was not included in the book. Is there something wrong with my solution? Could you prove that my solution is correct?


texts: Proving NP completeness of maximal length path

texts:
I have this question to answer:

For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the length of edge $e \in E$. For each node $i \in N$, suppose
the set $N(i)$ is partitioned into two subsets, $N^+(i)$ and $N^-(i)$ such that $j \in N^+(i)(j \in N^-(i))$ is referred to as a positive (negative) neighbor of $i$. (Note: Regardless of whether $j$ is a positive or negative neighbor of
$i$, $i$ can be either a positive or negative neighbor of j.) Consider the problem of ﬁnding a maximum-length
path $(s =) i(0)–i(1)–···–i(h)(= t)$ in $G$ between two nodes $s ∈ N$ and $t ∈ N$ subject to the following restriction: For each internal node $i(k)(k \in\{1,...,h − 1\})$ on the path, the set $\{i(k − 1),i(k + 1)\}$ must contain exactly one positive neighbor and one negative neighbor of $i(k)$. Prove NP-completeness of the decision problem and state whether it strongly NP-complete or not.

I wonder about the steps of the proof and whether shall I start from the longest path problem or from another problem instance.


texts:
Statement:
Every $T(n)$ size bounded Boolean circuit family, could be simulated with $(T(n))^2$ time bounded Random Access Turing Machine (RAM).

Could you please supply me with a reference to an article\ book that states the above?

I am willing to attach this statement in my article, without needing to prove it myself


texts:
So, $G$ is a connected claw free graph. How can i prove that if $M$ is a maximum matching in $G$ then $M$ exposes $at$ $most$ one vertex of $G$ ?

Any ideas ?


texts: Understanding deep cutoff in Alpha–beta pruning algorithm

texts:
I am studying the Alpha Beta pruning algorithm here.
function alphabeta(node, depth, α, β, maximizingPlayer) is
if depth = 0 or node is a terminal node then
    return the heuristic value of node
if maximizingPlayer then
    value := −∞
    for each child of node do
        value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
        α := max(α, value)
        if α ≥ β then
            break (* β cutoff *)
    return value
else
    value := +∞
    for each child of node do
        value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
        β := min(β, value)
        if β ≤ α then
            break (* α cutoff *)
    return value

In this slide (pg. 13) I read:

Deep alpha cut-off: . Def: For a node u in a tree and a positive
integer g, Ancestor(g, u) is the direct ancestor of u by tracing the
parent’s link g times. . When the lower bound Vl is produced at and
propagated from u’s great grand parent, i.e., Ancestor(3,u), or any
Ancestor(2i + 1,u), i ≥ 1. . When an upper bound Vu is returned from
the a branch of u and Vl ≥ Vu, then there is no need to evaluate all
later branches of u.

Also here the difference bteween shallow and deep cutoff.
I understand shallow alpha cutoff but I don't understand why deep alpha cutoff works.
UPDATE: I understood the deep cut watching this video:
Animation of deep pruning by the Alpha-Beta Algorithm.


texts: Have any natural complexity classes been proven not to be closed under complement?

texts:
Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be?

I'm sure one could construct some contrived example, but is there any "natural" complexity class that has this property, by which I mean one that has been studied by theoretical computer scientist for reasons other than its lack of closure under complement?

I know that RE has been proven not to be closed under complement, but I don't know of any examples from complexity theory rather than computability theory - i.e. any classes defined in terms of some kind of resource-constrained Turing machine.


texts: Interval Scheduling Problem with Three Resources

texts:
So I am trying to figure out what kind of algorithm I would use if I wanted to implement the ISP with a predefined number of resources.  Consider this example interval scheduling problem.

Say there are n requests for a lecture hall and three lecture halls are available to satisfy these requests. Each request has a starting time and an ending time.
Create an algorithm to get a maximal scheduling.

I am familiar with the process and I know how the ISP would work if I had only one resource.  But how would I apply it in this scenario if I had two, three, or a predefined set of resources.

Any input will be appreciated.


texts: Algorithm to find a line that divides the number of points equally

texts:
I have recently been asked in an interview to devise an algorithm that divides a set of points in a coordinate system so that half of the points lie on one side of the line, and the rest on the other side.

The points are unevenly placed and the line must not pass through any of the points.

Can any one give any approach to solve the problem? Analysis of the algorithm is appreciated.

Hints: Count the points, use medians.

The number of points is assumed to be even.


texts: Interview q: Small possible length of stick from an array of stick lengths

texts:
I was asked this question in a phone interview recently and I bombed it completely. Zero clue how to approach it. I wasn't able to find any similar patterns on google-ing. Thought maybe folks here might be able to help?

Statement: Given m sticks with different lengths. Combine these sticks to form longer sticks with the same length. What’s the smallest possible length of these newly unified sticks?
Conditions:

Must use all sticks
m < 50
max length of single stick less than 20

Example:
Input: 5 2 1 5 2 1 5 2 1
Output: 6
(Process: 1+5, 1+5, 1+5, 2+2+2)

Input: 3 3 3 2 2 5
Output: 9
(Process: 3+3+3, 2+2+5)

Input: 1 2 3 4 5
Output: 5
(Process: 2+3, 1+4, 5)

Input: 1 3 4 5
Output: 13
(Process: 1+3+4+5)


texts: Constructing CFG from instructions where you have an OR

texts:
My question is: What tips or ideas do you have when you're gonna construct a CFG out of these instructions? If we only had 0 < i <= k, it'd be more straight forward if you ask me, but when we have an OR there, how should I approach it?

edit:

I just realized I could rewrite the language and then define the CFG
as S -> L1 | L2 whereas L1 and L2 is the union shown in the image

However, I still am not very sure if this would be the easiest way. Therefore, I'd still be happy if someone could show me an example of how to construct this CFG.


texts: Finding the minimum value of all subsets in a 2D array

texts:
Imagine a N by M 2D array of random positive integers and two coordinates (i1,j1), (i2,j2), which represent the upper-left bound and bottom-right bound of a subarray, respectively.  Is there a efficient algorithm to calculate all the minimum values of each subarray?
[[4, 10, 9, 7],
 [9, 8,  1, 2],
 [1, 21, 3, 1]]

In this example of a 3 by 4 grid, if the two coordinates were (0,1) and (2,2), the minimum in this case would be 1, out of the values 10,9,8,1,21,3.
Other than the naive solution of finding all subsets and calculating the minimum in this subarray, which would be well beyond O(n^4), I have also considered using a method similar to prefix sum by creating a separate 2D array and storing the minimum from (0,0) to (i,j) at the value (i,j), but this issue here is you can't account for the overlap like you do in prefix sums.
Is there a way to account for overlap or another, more efficient algorithm?
Thank you!


texts:
I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also NP-hard. However, I was not able to find a reference for the complexity of the bottleneck TSP problem with repeated nodes for complete graphs.
Also, I am curious if continuously removing the most costly edges until all nodes are not strongly connected actually solves this problem. I think that this method should solve this problem, but I was not sure about it.


texts: Min-coin change problem with limited coins

texts:
I have been assigned the min-coin change problem for homework. I have to calculate the least number of coins needed to make change for a certain amount of cents in 2 scenarios: we have an infinite supply of coins and also where we only have 1 of each coin. I was able to quickly implement the solution for the first scenario using a recursive formula from here but was not able to find a recursive formula for the second case and I instead came up with an iterative solution.

We can just sum every possible combination of coins, check and see if the sum is equal to the target wanted and compare the number of coins used to the current lowest number of coins. I also realized that I can use binary counting to simulate all possible combinations using the bits in the iterator as a coefficient (either 1 or 0) for each coin and then calculate the Hamming Weight to check how many coins was used in the sum.

To visualize an example with 3 coins:

C1 C2 C3 | S                        | W
 0  0  0 | 0 * C1 + 0 * C2 + 0 * C3 | 0
 0  0  1 | 0 * C1 + 0 * C2 + 1 * C3 | 1
 0  1  0 | 0 * C1 + 1 * C2 + 0 * C3 | 1
 0  1  1 | 0 * C1 + 1 * C2 + 1 * C3 | 2
 1  0  0 | 1 * C1 + 0 * C2 + 0 * C3 | 1
 1  0  1 | 1 * C1 + 0 * C2 + 1 * C3 | 2
 1  1  0 | 1 * C1 + 1 * C2 + 0 * C3 | 2
 1  1  1 | 1 * C1 + 1 * C2 + 1 * C3 | 3

Obviously we can omit the case where all the coefficients are 0, but for completeness (when target = 0) and simplicity I've kept it in the solution.

My implementation in Python is:

import math

def least_coins(coins, target):
    least = math.inf

    # loop all 2^n possible sums of coins
    for i in range(2 ** len(coins)):
        sum = 0

        # add all the coins multiplied by their coefficient in this iteration
        for j in range(len(coins)):
            # get the j-th bit in i
            coefficient = i >> j & 1
            sum += coefficient * coins[j]

        if sum == target:
            count = 0
            # calculate the Hamming Weight of i to determine the number of coins used
            while i:
                i &= i - 1
                count += 1
            least = min(least, count)

    return least

coins = [3, 1, 1, 3, 2, 4]
target = 10
print(least_coins(coins, target))
>>> 3
# 3 + 3 + 4 = 10

As you can see the coins are not necessarily unique, but can only be used once. How can I turn this into a recursive formula (if possible and for the reason of possibly being able to optimize it using dynamic programming) or even introduce coefficients other than 0 and 1 so the problem can be more general where we have a certain amount of each coin?


texts: How is Johnson's shortest path weighting function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ proven by the triangular inequility?

texts:
Recap to the Johnson's shortest path algorithm:

By the procedure extending the original graph $G^\prime = (V^\prime, E^\prime), V^\prime = V\ \cup \{s\}, E^\prime = E\ \cup \{(s, v)\ |\ \forall v \in V\}$, and then extend the original weighting function $\forall x \in V,\ w(s, x) = 0.$

Finally define the reweighted function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ where $\forall x \in V,\ h(x) = d(s, x)$ , where $d(s, x)$ is the shortest path from $s$ to $x$.

Problem:

Assume that there is no negative cycle in the graph. The textbook Introduction to Algorithms says that
$w(u, v) + h(u) - h(v)$ is always nonnegative proven by using the triangular inequality theorem to get $w(u, v) + h(u) \ge h(v)$.

This makes me so confused, because I think that there could exist negative weights in the graph and hence triangular inequality can't be applied. (Am I misunderstanding triangular inequality? Or something are skipped I cannot tell?).

Where did I misunderstand about this algorithm? Thanks!


texts: How can a cyclic tag system halt with an output?

texts:
For example, we can say we have a abstract program that, given a finite binary string as input, removes all of the zeros (i.e. 0010001101011 evaluates to 111111), which is definitely a Turing-computable function.

How can a cyclic tag system compute this (which it can, by definition of it being Turing-complete) when it only halts when it reaches the empty string? The Wikipedia article gives an example of converting to a 2-tag system, but it adds an emulated halt that the original system does not have.

I can't find any reference to how a cyclic tag system halts meaningfully. What is its output supposed to be? I've considered things like

Number of steps (but then input restricts possible output without some kind of fancy encoding I can't find)
The last production (but that only has a finite output range)
Fixed points (which can't be detected in this system and only exist with very limited production rules and inputs)

but they don't work, at least not in any way I can see.


texts: Methods for silhouette feature extraction

texts:
Let's suppose I have an image of a person and its corresponding background. Using OpenCV I can relatively easily get a silhouette of the person from the image.

I am doing a project on human recognition using silhouettes and the only things I came up with for feature extraction are so called Granlund coefficients derived from Fourier coefficients and Hu moments which provide me with features I can send to various classifiers I have.

What I am further curious about is what other methods are there, if any, for feature extraction from silhouettes?

EDIT: In accordance with the first commentator, I will expand my question. As I said, I have tried with Granlund coefficients and Hu moments, both of them are well documented standard techniques which you can find in OpenCV documentation and IEEE Xplore digital library (Granlund coefficients).

Also, I didn't say anything specific about the features, I just want to know about various methods for silhouette feature extraction, other than the two mentioned above.


texts: Can the two optimal subproblems of the recurence formula below be reduced to one subproblem given the assumtions stated in the description below

texts:
In CLRS (Intro to algorithms 3rd Edition) on page 362, it says eqn(1) :

Lets Assume that you are given the cost of matrix multiplication for $A_{i}..A_{j}$ is $C[i,j]$   .
$C[i,j]$ is the Number of scalar multiplications of $A_{i}..A_{j}$.
$C[i,j]$ is not necessarily the optimal Number of scalar multiplications but obtained from this  paranthesisation.
i.e $C[i,j]$ is derived from => $(A_{i}(A_{i+1}(A_{i+2}\dots(A_{j-2}(A_{j-1}A_{j}))...)$
Given that $C[i,j]$ has been provided to us. Can $m[i,j]$ be reduced the equation below.
$$
m[i,j] = \begin{cases}
0 & \text{if } i = j, \\
\displaystyle\min_{i\le k\le j} \{C[i,k]+m[k+1,j] + p_{i-1}p_{k}p_{j}\} & \text{if } i \leq j.
\end{cases}
$$
Note $C[i,j]$ could be any parenthesizations so far as we are consistent.
I truly appreciate any help.


texts: Is there a difference between using $n$ and $\Theta(n)$ in recurrences?

texts: Is there a difference between $T(n)=2T(n/2)+n$ and $T(n)=2T(n/2)+Θ(n)$ when using the master theorem? I've seen it both ways and am a little confused. (Looking for the answer $nlogn$).


texts: Does mapping sorted input to unsorted output prove $P\ne NP$

texts:
Consider two sets of the same length that both contain every $n$-bit value. The first set is sorted, but the second set is unsorted and randomly arranged. Since both sets contain all possible $n$-bit values, they each have a size of $n*2^n$ bits. Now the task is to find what value in the sorted set, $a_i$, corresponds to the given value in the unsorted set, $b_i$. Linear search would need to be performed on the unsorted set resulting in a worst-case of $O(2^n)$. However, if we are given a possible solution, $a_i$, that needs to be verified, then binary search could be used on the sorted set to find $b_i$ and compare the result. This would be $O(n)$. Also, it can be assumed that finding $a_i$ and $b_i$ given $i$ is $O(1)$.

Am I wrong in letting $n$ be the input size rather than the size of sets themselves? Thank you in advance.


texts: Is there a bounded-time algorithm for Envy-free cake-cutting?

texts: I am engineering student,i have doubts regarding the topic can anyone help me to find solution.


texts: Probability that all indices divisible by 100 in a hash table with linear probing are occupied

texts:
I am trying to solve this question on Sedgewick's and Wayne's Algorithms book:

  Suppose that a linear-probing table of size 10^6 is half full, with occupied positions chosen at random. Estimate the probability that all positions with indices divisible by 100 are occupied.

So we had 500.000 inserts on the hash table and need to check the probability of positions 0, 100, 200, ..., 99900 being occupied. So far I thought about calculating the events one by one:
On the first insert there are 10^4 / 10^6 probability of inserting in an index divisible by 100. On the second, we have to consider that the first index divisible by 100 was chosen, so there is a 9.999 / 10^6 probability.

And since we have more inserts (500.000) than indices divisible by 100, I thought about computing the probability of 10.000 inserts occupying the indices divisible by 100 and then multiplying this probability by 50, since we could "try" this insert pattern 50 times.

P = (10.000 / 10^6 * 9.999 / 10^6 * ... * 1 / 10^6) * 50

Is this line of thought correct?
Also, the tricky part here is that we are talking about a linear-probing hash table. So if we insert an element on index 99 twice, the second element will occupy index 100. This also means that inserting an element on index 1 100 times will mean that index 100 is occupied.
I am not sure how to deal with this extra requirement. Any ideas?


texts: Which is more efficient? lg(n+10^n) higher than 2^lgn

texts: Based on the order by asymptotic growth rate which is more efficient?


texts: Is L={0,1}* without strings that start with 00 decidable?

texts: Say you have a language L = "{0,1}* without strings that start with 00". How do you prove this is decidable?  I'm drawing a blank on this one.


texts: primitive recursion in the lambda calculus

texts:
I am having trouble finding out what a primitive subset of the lambda calculus would look like. I reference primitive recursion as shown here: "https://en.wikipedia.org/wiki/Primitive_recursive_function".

These are the three base axioms:

Constant function: The 0-ary constant function 0 is primitive recursive.
Successor function: The 1-ary successor function S, which returns the successor of its argument (see Peano postulates), is primitive recursive. That is, S(k) = k + 1.
Projection function: For every n≥1 and each i with 1≤i≤n, the n-ary projection function Pin, which returns its i-th argument, is primitive recursive.

Here is my confusion. In the LC zero is represented as (λfx. x).
Next the successor functions is defined as (λnfx. f (n f x)). Because they are both axioms both of these functions can be classified as primitive. But when I apply the function suc to zero I get the encoding of the number one. Which is represented as the function (λf.(λx.(f x))).  Now this number is neither zero or the suc function but the result of application. As such I do not see how this result function (value of 1) fits into the rule set. But very clearly a program with the number 1 in it is still primitive recursive. What am I not understanding here? While 1 is the suc to zero, once suc is applied it is neither suc, nor zero.


texts: Average number of full nodes in a binary search tree

texts:
Let $f(N)$ be the average number of full nodes (nodes with two children) in an $N$-node binary search tree.

Determine the values of $f(0)$ and $f(1)$.

Given that for $N > 1$,
$\qquad \displaystyle f(N) = \frac{N-2}{N} + \frac{1}{N} \sum_{i=0}^{N-1} [f(i) + f(N - i - 1)]$,
show that $f(N) = \frac{N - 2}{3}$.

Using this information, show that the average number of nodes with one child in a binary search tree is $\frac{N + 1}{3}$.

I know that for (1) both values are $0$. I mainly need help proving (2).
I also found some hints for (2) and (3) but I can't figure it out:
(2) The root contributes $\frac{N − 2}{N}$ full nodes on average, because the root is full as long as it does not contain the largest or smallest item. The remainder of the equation is the expected contribution of the subtrees.
(3) The average number of leaves is $\frac{N + 1}{3}$.
Any help would be appreciated, even just pointing me in the right direction. Thanks!


texts:
$L_{4},L_{2}$ are regular languages.

given an expression which we know is regular: $L_{4}\cap \bar{L_{2}}\cap \bar{L_{1}}$

May I assume that the language $L_1$ is regular? using closure properties


texts: Prerequisites of computational complexity theory

texts: what's the prerequisite topics needed for understanding computational complexity theory and analysis of algorithm ...including big-O and Big-theta notations and these staff. I want a mathematical background and good book suggestions for each topic ... thanks


texts:
I've been reading lately about SAT problem, NP and co-NP.

Many sources say that the SAT problem is co NP, though, I can't find a co-NP problem equivalent to SAT.

Does anyone have any idea about this ? (Or could lighten my misunderstandings)


texts: This being used in data bits transmitted by GLONASS Satellites. I am sure it is different from other codes like 'Binary Code' which the search engine throws up


texts: Pumping lemma for regular languages. Proof

texts:
Please help me understand the following
$L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$
To prove: The language $L$ has regular pumping property
My argumentation:
Let $p = 4 $. Let $z$ in $L$, with $z$ $\geq $ $p$. Set $u$ to $\epsilon$. Than $x$ is the first letter, and $w$ the rest.
$x$ $\neq$ $\epsilon$
For all $i$ $\geq $0$: ux^iw$ is in $L$
But if i set i to 0 the word is not in the language? And therefor does not have the regular pumping property? What am i missing? Example $0010$, after pumping $4$ $\geq $ $010$?


texts: Can we enumerate provably non-terminating functions?

texts:
In trying to understand the Halting Problem better, I am trying to come up with classes of provably non-terminating programs.

For example, any program (including input) which leads to a finite-length infinite loop (with perfectly repeating state+tape) should be detectable. That leaves mostly induction/search problems like "get the first non-Goldbach even number above 4" as candidates.

Clearly, some of these halt, and some can be proven non-halting (eg we know "find $n$ such that $n\cdot 0=5$ " and "find a proof that the Poincare Conjecture is false" would not halt). More generally, it seems every non-halting problem corresponds to a Diophantine equation which (provably or not) has no solutions. This leads to a seemingly fairly general algorithm to find many non-halting programs:

Convert Turing machine to corresponding Diophantine equation with one unknown
Feed the equation, along with First-Order Peano Arithmetic, to Prolog/Isabelle/your favorite proof assistant
Assert the existence of a solution
Derive 0=1

So, my questions:

Is there a more natural way to search for such contradictions using the formalism of Turing Machines (or some other more conventional model of computation), without converting to Diophantine equations?
Are there provably non-terminating functions that can be found using some other algorithm, but not this one? What algorithm(s)? Would that require a "stronger" version of arithmetic?
If there are such algorithms, is there any notion of a "biggest" class of provably non-halting programs, or would that somehow lead to solving the Halting Problem (or some other contradiction)?
Are there any good references/keywords for this? I've searched for "provably non-terminating functions", but haven't come up with much

PS Feel free to fix/reformat anything, alert me to obvious theoretical mistakes, or let me know if this is a bad question.

EDIT: Some points to address responses so far:

I know that it's "easy" to prove that a program halts--just run it until it does; the challenge is to prove that a program does not halt, which obviously isn't always possible.
Re: D.W.♦, I know we can't enumerate all non-halting programs, and I know we can come up with many provable examples of non-terminating functions, I'm asking if there's a most general method of finding all non-halting programs that can be found/proven
I am aware of the Curry-Howard correspondance that directly relates programs and mathematical proofs. However, because of the halting problem there can be no type for "non-terminating programs", and it's not immediately obvious how to type "provably non-terminating" either
@chi's answer is exactly what I am looking for. To make sure I understand fully, let me restate my understanding of your enumeration of non-terminating programs, using the simplest possible axioms I can think of:

Start with a basic definition of "strings" in pure First-Order Logic: 0,1,add0,add1,equality
Define Turing machines using a rewrite relation on strings that captures the mechanics of a calculation step (ie, eval)
Define big-step calculation $\rightarrow$ as the transitive closure of one-step eval
Define a halting predicate as the existence of a fixed point
For a given program $x$, prove $\forall y.x\rightarrow y\Rightarrow \exists z\ne y.y\rightarrow z$

So, would the above work? Is it equivalent to my Diophantine equation scheme? Is there a yet simpler version? Would more axioms (eg using naturals under Peano Arithmetic to encode the machines) be able to prove more non-terminating programs than this version, ie is there a more general method?


texts: Does Nand Flash Type Affect the Read Latency Based on Page Content?

texts: In general, we have these types of NAND flash cells: SLC, MLC, TLC, and QLC. Since MLC flash cells can store 2 bits, the content of the cell can be 00, 01, 10, or 11 which are detected using different threshold voltages. Each 4KB flash page includes 32768 bits and, thus, 16384 MLCs. So, the content of a page might be all 1, all 0, or a mixture of 1 and 0. Are these types of page content read with different latencies or not? Is there a distinguishable read latency between the pages containing all 1, all 0, and a mixture of 1 and 0?


texts: DFA that recognizes 0 in every odd position

texts:
I had a question that asked for the DFA that accepts the following language:

{w | every odd position of w is a 0 }

Should this DFA accept the empty string, since it doesn't have an odd position?


texts: terminology for grouping words in a string?

texts:
We commonly create sub-groups of strings in one particular algorithm implementation. I just want to know in CS literature is there any standard name for such kind of grouping. For e.g.

Hello World! This is May from the dairy farm.

Strings with sub-groups of two:

Hello World!
World! This
This is
is May
...


texts: Can the Bell-LaPadula model emulate the Chinese Wall model?

texts: I have been reading on security policies and the question wether Bell-LaPadula can be used to implement Chinese Wall. Does anyone know more about it?


texts:
Resolution allows to generate new clauses for an existing set of clauses.

In many cases, the rule is simple:

{ a, b }     { -a, b }
----------------------
        { b }

But what if the clauses contain multiple literals suitable for resolution?

{ a, b }     { -a, -b }
-----------------------
        { ? }

If we choose a, then the result should be { b, -b } by definition. Is this correct?

If it is, what does this imply? I would assume { b, -b } to always be true as it means $b \lor \lnot b$ which is a tautology. Is this correct, and if it is not, what else does the result imply?


texts: Two languages such that their Kleene closures are equal

texts:
I am trying to solve the following problem:
Find languages S and T over the alphabet $\{a, b\}$ such that $ S \not\subset T $ and $ T \not\subset\ S $ ($S$ is not contained in $T$ and not equal to $T$, $T$ is not contained in $S$ and is not equal to $S$) but $S^* = T^*$.
It might be trivial, but I would appreciate some help.


texts: Showing that the language $L = \{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \}$ is decidable or undecidable

texts:
How would you go about showing that the language $L = \{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \}$ is decidable or undecidable?

Intuitively my thoughts are that you might be able to show that $\bar{L} = \{\langle M, w \rangle\ |\ M$ moves left at most twice while computing $w \}$ is undecidable as you wouldn't ever be able to definitively know if the machine will move left a third time so it would end up looping instead of rejecting. I don't know if that's on the right track though.

Thanks in advance!


texts: Assignment Problem with Non assignable cell

texts:
I have question for you guys. In this question is there something else that I should do ? When i try to solve with the way that my professor thought , its unsolveable. What should i do to solve this ?

'*' means there will be no assignment for that person to that job


texts: Calculate Complexity, loop incremented by log(k)

texts:
I'm preparing for an exam, and I ran across the following algorithm:

for(int j = 1 to n) {
    k=2
    while (k < n) {
        sum+= a[k] * b[k]
        k+= log(k)
    }
}

I'm trying to work on finding the complexity of the algorithm. Here's what I have so far.

The outside loop obviously runs in n steps.
The inside loop gets incremented by log(k), so it should run faster than n as log(n) when n >= 2 is greater than 1. Overall, it looks like the overall complexity is a little faster O(n^2), but by how much? I guess the question boils down to: How do I find the complexity of the inner loop when it is incremented by a function of k? What is the final complexity in this case? I'm assuming O(n^2) is technically correct since it will still be an upper bound, but is there a more accurate answer here?


texts: Different boolean degrees polynomially related-2?

texts:
Essentially similar question to here Different boolean degrees polynomially related? (change being error condition $\epsilon\in(0,1)$).

Let $p$ be the minimum degree (of degree $d_f$) real polynomial that represents boolean function $f$ such that $f(x)=p(x)$.

Let $p_{0,\epsilon}$ be the minimum degree (of degree $d_{0,f,\epsilon}$) real polynomial  that represents boolean function $f$ such that $$f(x)=0\implies p_{0,\epsilon}(x)=0$$$$f(x)=1\implies|p_{0,\epsilon}(x)-f(x)|\leq\epsilon.$$

Let $p_{1,\epsilon}$ be the minimum degree (of degree $d_{1,f,\epsilon}$) real polynomial  that represents boolean function $f$ such that $$f(x)=1\implies p_{1,\epsilon}(x)=1$$$$f(x)=0\implies|p_{1,\epsilon}(x)-f(x)|\leq\epsilon.$$

Is $d_{f}\leq d_{0,f,\epsilon}^{c_0}$ and $d_{f}\leq d_{1,f,\epsilon}^{c_1}$ for some  $c_0$ and $c_1$?

Above holds if $\epsilon\in(0,1)$
Relations among different boolean approximations

There solution considered $0<\epsilon<\frac{1}{2}\leq\delta<1$.
Solution showed relation between $d_{0,f,\epsilon},d_{0,f,\delta}$ is a linear function with constant multiplicative factor as long as we have fixed $\epsilon,\delta$.

This along with solution to another problem in Different boolean degrees polynomially related? shows $d_{f}\leq d_{0,f,\epsilon}^{c_0}$ and $d_{f}\leq d_{1,f,\epsilon}^{c_1}$ for some  $c_0$ and $c_1$ holds if we have fixed $\epsilon,\delta$.

(1) I am most interested in case where we have not fixed $\delta$ and/or $\epsilon$. Say $\delta=1-\frac{1}{h(n)}$, $\epsilon=\frac{1}{g(n)}$ (that is either/both $\delta$ or/and $\epsilon$ changes) with some functions $g(n)$, $h(n)$ of $n$ (logarithmic/polynomial/exponential). I am interested in how fast do degrees (multiplicative factors) grow.

(2) There was a comment on sign degree. I understand sign degree is an useful parameter. However for sign degree as I understand ranges of functions involved are over $\Bbb R\backslash\{0\}$ (Only criteria is approximating function takes same sign as $f$). Here ranges are different.


texts:
i am studying on trapezoidal maps. In the last section, "Analysis" of this paper, it says "The expected query time is indeed O(log n). Again the search structure size can be quadratic in the worst case, but the expected size is O(n)."
Here is what i did not understand well. How it is possible to reach a quadratic size of search structure? For example, if i insert all the segments one by one in a specific order and let their number is 5(5 segments and 10 vertices normally). So there are two possible cases. One is: "The edge falls entirely within an old trapezoid" and the second one is : "The edge crosses over at least one old extension". To understand better i tried to divide the plane into two slabs and realized that the number of the slabs are not the quadratic to the number of segments. What i mean is i expected that if i have 5 segments than i have to have 20 slabs and so the search structure would be quadratic to number of segments either.
Finally, can anyone show that if there exists any set of segments which may yield a search structure which is quadratic with number of segments? If it is possible, is it related with the insertion order?  For my opinion it is directly related with the order of segments.


texts: I came up with a way to modify Dijkstra's Algorithm to handle graphs with negative edge weighs

texts:
Add a constant $c\geq |w_{min}|$ to each edge of $G$, so that each edge now has non-negative weight.
Run Dijkstra's algorithm

Can anyone tell me if this is viable or if it fails?


texts: Covering the unit square by smaller squares of variable sizes

texts:
I'm trying to find whether a property $\mathcal{P}$ is true for all points of the unit square (in 2D). At each step I can query for a point of my choice. An oracle then answers me by either:

telling me $\mathcal{P}$ doesn't hold for this point and thus the problem is solved: the property doesn't hold for all points in the unit square.
tells me $\mathcal P$ holds for not only my query point but also for a small square containing my point. Thus I don't need to query for other points in this small square.

The problem is the small squares returned by the oracle are of variables sizes. What data structure and algorithm can I use to store the small squares returned? How can I track efficiently whether I have enough small squares to cover the unit square (and can thus stop the algorithm since I know the property holds for the whole unit square)? Or compute new points to query?

Edit: Okay, I realized my description of the problem is over-complicated. Basically this is the problem:

I have a certain number of squares of variable sizes and positions. How do I check whether they completely cover the unit square, or if not, how do I obtain the coordinates of a point of the unit square not covered ? PS: The problem is online.


texts: Can we test whether two vertices are connected in time linear in the number of nodes?

texts:
Consider the problem:

  Given an undirected graph and two of its vertices, is there a path between them?

I often read that this problem can be solved in linear time in the number of vertices! I am not sure why this claim holds.

Can this really be done in linear time (not amortized) without preprocessing?


texts: Why minimum vertex cover problem is in NP

texts:
I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23):

Is the size of the minimum vertex cover in $G$ at most $k$?

and right after this definition, the author states that this problem is in NP.
My question: What would be a yes certificate?
Indeed, our non-deterministic algorithm could guess a subset of vertices, denoted by $V'$, and we can verify if $V'$ is a vertex cover of some cardinality in polynomial time, but how could we possibly show that $V'$ is minimum in polynomial time?


texts: Does UDP always deliver packets inorder to the application layer

texts:
I was reading about UDP and TCP. TCP is a stream-oriented, connection-oriented protocol and always delivers the segments in order to the application layer.

But UDP being connectionless, does it also always deliver the datagrams to the application layer in order?


texts: Is it possible for a language and its complement to both be unrecognizable?

texts:
Given some unrecognizable language $L$, is it possible for its complement $\overline{L}$ to also be unrecognizable?

If some other language $S$ and its complement $\overline{S}$ are both recognizable, then $S$ and $\overline{S}$ are decidable. If $\overline{S}$ is unrecognizable, then then $S$ is undecidable but still recognizable. Why do we ignore the idea that $S$ and $\overline{S}$ may both be unrecognizable? This implies that $\exists! s \in S \cup \overline{S} = \Sigma^*$ on which no machine halts, otherwise I don't see why we cannot have $x,y \in \Sigma^*$ and $x \neq y$ such that no machine halts on $x$ or $y$, where $x \in S$ and $y \in \overline{S}$.

Perhaps I am making a false assumption somewhere?


texts: Cont: NP-hard or not: partition with irrational input or parameter

texts:
Please take a look at NP-hard or not: partition with irrational input or parameter first.

In  Will irrational parameters make a problem not well-defined on complexity, I got an answer of "No". Then I checked that some well-defined problems  indeed have irrational paprameters(e.g., In the sum of square root problem, it has square roots).

Now I want to use this "property" (irrational parameters donot make a problem ill-defined on complexity) to modify method 1 such that determining the complexity of original problem is well-defined in some cases and it is NP-complete.

More concretely, suppose that $x_*$ in  method 1 is actually $0.52+\sqrt{2}\times 10^{-10}$.  Then we ask such a problem:

  Given a set $N=\{a_1,...,a_{n+2}\}$ with $n+2$ numbers where

  $a_1,...,a_{n+2}$ are positive and rational,

  find a set $S\subseteq N$, such that $f(S)=0.52+\sqrt{2}\times 10^{-10}$, where
  $f(S)=\sum_{i=1}^n a_i \textbf{I}_{i \in S} + (0.51+\sqrt{a_{n+1}}\times 10^{-10})\textbf{I}_{n+1 \in S}+  (0.47-\sqrt{a_{n+2}}\times 10^{-10})\textbf{I}_{n+2 \in S}$ and $\textbf{I}$ is an indicator function.

Then for such a problem, we can argue that it is NP-complete, since there is one instance  with rational inputs satisfying

  $\sum_{i=1}^n a_i = 0.02$ and $a_{n+1}=a_{n+2}=2$.

Is this correct?


texts: proving " if $k\log(k) = \theta (n)$ then $k = \theta (\frac{n}{\log(n)})$"

texts:
First i began with the definition of $\theta$ as below:
$c_1n \leq k \log(k) \leq c_2n  \implies c_1\frac{n}{logk} \leq k \leq c_2\frac{n}{logk}$
and we also know if $k\log(k) = \theta (n)$ then $k = O(n)$ then $k \leq cn$ thus $c\frac{n}{logn} \leq c_1\frac{n}{logk}\leq k $ and thus $k = \omega(\frac{n}{\log(n)})$.
In in this manner, i have to prove that $ c_2\frac{n}{logk} \leq  c\frac{n}{logn}$ too to show that $k = O(\frac{n}{\log(n)})$ . But it ($ c_2\frac{n}{logk} \leq  c\frac{n}{logn}$) seems false! Is this really false and there is a better solution, or is there any proving tricks for $ c\frac{n}{logn} \leq c_1\frac{n}{logk}$?


texts: Recursive Call Inside Argument List (C++)

texts:
So, my professor asked me to implement recursion in different ways to compute $a^n$ (a and n being integers) and rank them according to their space efficiency. Now, here is one of the methods I came up with:

  int Power (int a, int n)
 { if ( n == 0 )
  return 1;
   if ( n % 2 == 0)
  return Power(Power(a, n/2), 2);
   else return Power(Power(a, n/2), 2)*a;
  }

The code compiles well, but leads to a segmentation fault. On debugging, I came to the conclusion that recursive call within the argument list is not acceptable. That is, something like

  return Power(Power(a, n/2), 2)

or

  int m = Power(a, n/2);
  return Power(m, 2);

is not allowed but

  int m = Power(a, n/2);
  return m*m;

is allowed. Why is this the case? Is this true only in C++, or is it a general phenomenon?


texts: How to prove $T(n) = 2T(n/2) + n/\log(n)$ can't be solved using the Master Theorem?

texts:
I have read (in this question) that this recursion can't be solved via Master Theorem.
But I couldn't find exact and complete proof why the Master Theorem does not apply.


texts: Difference between Dominant strategy and Winning Strategy

texts:
I am a little bit confused by the definition of dominant strategy and winning strategy, what's the difference between them.

Following are the definitions taken from wikipedia, below every definition I added some thoughts. If you fell that my thoughts are not correct or ambigues please let me know.

  Dominant strategy.In game theory, dominant strategy (commonly called simply dominance) occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play. Many simple games can be solved using dominance.

The first interesting note is that the term dominant strategy is applied only to two different strategies, and more precisely it's should be defined as "A is dominant strategy over B", actually the notion "dominant strategy" might be relevant to the game itself in this case the dominant strategy A dominates over all other strategies of the player.

  Winning strategy.A strategy is winning if the player following it must necessarily win, no matter what his opponent plays.

This notion sounds like stronger notion than dominant strategy, because having winning strategy its guaranteed that the player wins if he follows the strategy no matter what the opponent does, on the other hand dominant strategy does not guaranteed the win, it only says that dominant strategy guarantees the best possible outcome for the player over all possible player's strategies and no matter what the opponent does.

I would to emphasize one common property for the dominant strategy and the winning strategy they both determined by the outcome of the game and don't depend on the strategy of the opponent.

In my opinion, winning strategy is always a dominant strategy, but vice verse is not always true.

Do you agree with the intuitive understand and thought?


texts: What's the usage of $S$ in Dijkstra shortest path algorithm in the book Introduction to Algorithms?

texts:
I don't understand how the $S$ is needed in dijkstra shortest path algorithm. For each node $v$ in $G.V$, the $v.\pi = previous\_node$ is used to denote it previous node in the shortest path to the current node, and $\rm{}INITIALIZE\rm{-}SINGLE\rm{-}SOURCE(G,s)$ also initialize all $v.\pi=NIL,$ so if it's impossible to reach some node, a simple check $$\textrm{if }v.\pi==NIL$$ is enough. So why the $S$ is needed? If all node can be reached then $S=G.V$ and it will be useless...

Edit: I add the book statement, but I wonder since that the priority queue has been used, the description becomes inconsistent with the pseudocode follows, no need to refer to $V-S$, which will slow down the algorithm?

Edit2: I suspect that priority queue is not a requirement of dijkstra SP algorithm, it's just a technique to speed up it, so the pseudocode in my another question on Dijkstra's SP algorithm is correct?

Edit3: Now I got stuck on my own comment, I suspect it's not correct:

I tried to make use of $S$, so I tried $G.Adj[u]\color{blue}{-S}$ and thought it will speed up the updating, but what if the following happen that the edge $(\color{red}{v,u})$ will not be selected since $\color{blue}S$ is already subtracted?

Book: Introduction to Algorithm 3ed. page 658, (forget about the679 is just pdf reader page #.)


texts: Operating System: replace the process's memory space with a new program

texts: What does it mean that "replace the process's memory space with a new program"? So who's memory space will be replaced by whom?


texts: The trick used in the proof of the doubly exponential complexity of Presburger arithmetics

texts:
I posted this on MathUnderflow but got no answers, so thought I'd try it here,

I am reading Rabin and Fischer's old paper [will post a link when possible] where among other things, the doubly exponential complexity of Presburger arithmetics is proven.

The proof relies on the existence of a formula $I_{n}(x)$ informally asserting "$x < 2^{2^{kx+1}}$" with $|I_{n}| \in O(n)$. Though the construction of this formula is not given in the paper, which was a surprise to me considering that it is presumably highly nontrivial, given that bound and the fact that we only have addition at our disposal!¹

I later learned that the construction of this formula relies on a "trick", previously discovered by Fischer, and independently by Volker Strassen, but I have not managed to track down a paper describing this trick in detail!

So if anyone knows about the paper I am talking about and can either point me in its direction or even describe the trick to me...

This post from Lipton's blog contains a link to the paper as well as mentions [and provides a rough, unfortunately insufficient for me, sketch of] said trick, BTW.

¹ I know that this is a vague description. Though, a sufficiently detailed description would be way too long for a SX post, so I just hope that someone that already knows about the paper in question - and thus can make do with that brief sketch - bumps into this and is able to help me.


texts: Mating board members with gangsters algorithm

texts:
I have a list of board members of all companies in the city. In the city lives three gangsters. Every company needs to have at least two gangsters among the friends of board members but every board member can know at most one gangster. Member can be a board member in multiple companies.

What is the name of this problem? What topic should I explore to solve it?


texts: Why is the Shannon entropy 0.94 in this example?

texts:
Suppose I have a decision tree in which there is a label $L$ under which is the attribute $A$ as shown below. I am given that the Shannon entropy of label $L$ is $H(L) = 0.95$.

I must find the Shannon entropy of $L$ given $A$ ($H(L \mid A)$). Here's what I have tried.

\begin{eqnarray}
H(L \mid A) &=& -(\frac{6}{8} \log_2 \frac{4}{6} + \frac{2}{8} \log_2 \frac{1}{2}) \\
 &\approx& 0.69
\end{eqnarray}

However, $H(L \mid A) \approx 0.94$. Where did I err? Is my formula for Shannon entropy accurate?


texts: Delete rows or columns of matrix containing invalid elements, such that a maximum number of valid elements is kept

texts:
Originally posted in Stack Overflow but was told to post here.
Context: I am doing a PCA on a $M \times N \, (N \gg M)$ matrix with some invalid values located in the matrix. I cannot infer these values, so I need to remove all of them, which means I need to delete the whole corresponding row or column. Of course I want to keep the maximum amount of data. The invalid entries represent ~30% of data, but most of it is completely filled in a few lines, few of it is scattered in the rest of the matrix.
Some possible approaches:

Similar to this problem, where I format my matrix such that valid data entries are equal to 1 and invalid entries to a huge negative number. However, all proposed solutions are of exponential complexity and my problem is simpler.

Computing the ratio (invalid data / valid data) for each row or column, and deleting the highest ratio(s). Recompute the ratios for the sub-matrix and remove the highest(s) ratios. (not sure how many lines or columns we can remove safely in one step), and so on until there is no invalid data left. It seems like an okay solution, but I am unsure it always gives the optimal solution.

My guess is that it is a standard data analysis problem, but surprisingly I could not find a solution online.


texts: Explain $\log_2(n)$ squared asymptotic run-time for naive nested parallel CREW PRAM mergesort

texts:
On from Page 1 of these lecture notes it is stated in the final paragraph of the section titled CREW Mergesort:

  Each such step (in a sequence of $\Theta(\log_2\ n)$ steps) takes
  time $\Theta(\log_2\ s)$ with a sequence length of $s$. Summing these, we
  obtain an overall run time of $\Theta((\log_2\  n)^2)$ for $n$
  processors, which is not quite (but almost!) cost-optimal.

Can anyone show explicitly how the sum mentioned is calculated and the squared log result arrived at?


texts: What is the type of linked list where order doesn't matter

texts:
I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about linked listed implementation:

  Insertion into a singly-linked list is a nice exercise in pointer
  manipulation, as shown below. Since we have no need to maintain the
  list in any particular order, we might as well insert each new item in
  the simplest place. Insertion at the beginning of the list avoids any
  need to traverse the list, but does require us to update the pointer
  (denoted l) to the head of the data structure.

I'm wondering what kind of list is that because I can't use it for index based access. All other basic implementations I've seen provide index based access.

When searching for an item, their implementation shows direct object comparison:

list *search_list(list *l, item_type x)
{
    if (l == NULL) return(NULL);
    if (l->item == x)
        return(l);
    else
        return( search_list(l->next, x) );
}

So I'm thinking maybe they didn't account for index based access.

This book also distinguishes Container and Dictionary categories of DS:

  We use the term container to denote a data structure that permits
  storage and retrieval of data items independent of content. They are
  distinguished by the particular retrieval order they support (LIFO,
  FIFO). By contrast, dictionaries are abstract data types that retrieve
  based on key values or content.

It seems that the linked listed implementation at hand falls into a container category with the object reference as the key, something alike a map DS.

Is this assumption valid?


texts: Calculating sums of floating point numbers by hand

texts:
how do you calculate the sum of 2.6125 * 10^1 and 4.150390625 * 10-1
by hand, assuming A and B are stored in the 16-bit half precision.
i cant figure out how to do this by hand with out losing most of the precision or getting it just plain wrong any help would be appreciated.