texts: Finding optimal element with two criteria

texts:
Let there be a (unsymmetric, directed, weighted) graph ( $\mathbb{G}$, capacity $m$ ) and an array ( $\mathbb{A}$, fixed capacity $n$) of objects ($m>>n$). The array contains references to a number of vertices. The problem is to pick a single vertex ($\mathbb{V}$) from the graph, that is not in the array, fulfilling the following condition: $\mathbb{V}$ has the minimal $\psi$ of all the vertices in $\mathbb{G}$ and $\psi$ is defined as $\psi(\mathbb{V})=S(\mathbb{V})\cdot\tau(\mathbb{V})$. (for tie-breaker conditions see below)

$S(\mathbb{V})$ is the sum of the weights of the edges of $\mathbb{V}$ to all the vertices that are in $\mathbb{A}$.
Example: if $\{ g_1,g_2,g_3,g_4\}\in\mathbb{G}$ and $\{ g_2,g_3\}\in\mathbb{A}$, given that $W(g_1, g_2)=5$, $W(g_1, g_3)=3$, $W(g_1, g_4)=1$, $W(g_2, g_1)=2$, $W(g_2, g_3)=1$, $W(g_2, g_4)=8$, $W(g_4, g_1)=9$, $W(g_4, g_2)=2$, $W(g_4, g_3)=1$, then $S(g_1) = W(g_1, g_2) + W(g_1, g_3) = 8$ and $S(g_4) = W(g_4, g_2) + W(g_4, g_3) = 3$.

Each vertex in $\mathbb{G}$ has a time-decay property (100-1), $\tau(\mathbb{V})$, that is updated at discrete moments. The value is reset to the maximum once it is removed from $\mathbb{A}$ and is periodically lowered until it reaches the minimal value (at which point it stops decreasing)  or is again picked and placed in $\mathbb{A}$.

tie-break: if $\psi(\mathbb{V}_1)=\psi(\mathbb{V}_2)$, advantage is given in the following order: lower $S(\mathbb{V})$, lower $\tau(\mathbb{V})$, any of the two (e.g. the first that was picked).

My approach was the following algorithm:

get the current number of elements in $\mathbb{A}$, $a$
create a new array $\mathbb{A}_2$ of size $a(m-a)$
populate $\mathbb{A}_2$ with the weight of each edge ($W(g_x, g_y)$ where $g_x \in \mathbb{G}$ and $g_y \in \mathbb{A}$)
apply the time-decay to each element of $\mathbb{A}_2$ (i.e. multiply the weight with the time-decay)
return the vertex with the minimal value in $\mathbb{A}_2$

This is a very expensive approach, both in terms of time and space complexity.
Are there any provably better algorithms for this problem?
Is there a specification for my kind of problem, based on which I could do further research? My current searches regarding sorting/searching, graphs and optimization problems have not yielded any tangible results.
Additional information
The size of $\mathbb{A}$ is fixed. Vertices can be added/removed from $\mathbb{G}$.The program logic takes elements from $\mathbb{G}$ and places them in $\mathbb{A}$, where they are part of some processing that is not related with this algorithm. It is important to note that vertices are repeatedly subjected to this processing and that, as a side effect of this processing, the weights of the vertices in $\mathbb{A}$ are updated.
Once that processing is completed, a vertex is removed from $\mathbb{A}$ (note that that doesn't necessarily imply that the vertex is removed from $\mathbb{G}$ as well, in fact, adding/removal of vertices is very rare). The now vacant slot needs to be filled, which is were the algorithm applies. $S(\mathbb{V})$ ensures that the choice is optimal in regards of internal metrics (i.e. the weights of the edges), while $\tau(\mathbb{V})$ is supposed to prevent starving. All vertices in $\mathbb{G}$ need to participate in the processing, otherwise only the "best" elements would iterate through $\mathbb{A}$, while those with bad metrics would never get processed.
Therefore, there is a mechanism in place which at discreet moments goes through every vertex in $\mathbb{G}$ and updates their respective idle time property (i.e. applies time-decay). This value is reset once the appropriate vertex is removed from $\mathbb{A}$.
Finally, the algorithm takes as input $\mathbb{G}$ and $\mathbb{A}$. Its task is to fill the vacant slot in $\mathbb{A}$. This is done by finding the minimal $\psi$ (take tie-breaks into account). The output of the algorithm is this particular vertex.


texts: How to prove that every regular language can be obtained by some FA?

texts: I have seen this definition almost everywhere, but I don't know the underlying proof behind this definition.


texts: The meaning of "set" in NP-complete problem

texts:
Garey and Johnson describe in their book many NP-complete problems which are based on sets, for example Hitting Set, Minimum Test Set, Set Packing, Set Splitting, and many more.

The traditional mathematical definition of a set does not allow duplicates; when multiplicities count, the object is called a multiset.

Are the sets in the NP-complete problems described by Garey and Johnson allowed to contain duplicates?


texts: Finding the height of all nodes in a forest

texts:
I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges to traverse in reverse to reach a vertex of height 0.

I also know that the average degree of a node is a small constant, say 2 or so. To find the height of all vertices, I can think of two algorithms:

Walking Algorithm

Go through and mark $h=0$ for vertices with no incoming edges.
For each vertex with $h=0$, follow the outgoing edges, updating the height of each encountered vertex if it's previous height is smaller.

Frontier Algorithm

Go through and mark $h=0$ for vertices with no incoming edges, and mark these as the frontier.
For every frontier vertex, see if it's parent has children at or below the frontier, If it does, mark the parent as having $1$ plus the largest height among its children. Mark the parent as being on the frontier.
Repeat 2 until there is nothing beyond the frontier.

My questions:

Is there a name for this problem, and a well known fastest solution?
I tend to think simply walking up from all the $h=0$ vertices is the fastest solution. Am I right?


texts:
In this set of notes, they claim that there is a size $O(2^{\sqrt n})$ depth-3 circuit (OR -AND -OR) that implements XOR.

I tried for a little bit to figure out how to do this, but couldn't find such a construction. How do you do this?


texts: PL: How can I prove the type of something using "Inversion for Typing"?

texts:
I'm currently going through this book about programming languages, and in section 4.2, Lemma 4.2 it says this:

Lemma 4.2 (Inversion for Typing). Suppose that $\Gamma \vdash e : \tau$. If $e = \texttt{plus}(e_1;e_2)$, then $\tau = \texttt{num}$, $\Gamma \vdash e_1 : \texttt{num}$, and $\Gamma \vdash e_2 : \texttt{num}$ ...
Proof. These may all be proved by induction on the derivation of the typing judgment $\Gamma \vdash e : \tau$.

I understand that this is obviously true, but I don't understand how I might explicitly write out the proof for this (e.g., what does "induction on the derivation of the typing judgment" mean?)
This is my current understanding:
The derivation of the typing judgement is simply the sequence of rules applied to figure out the type of some expression (in this case, $e$).
For example, if I have $e_1 : \texttt{num}$ and $e_2 : \texttt{num}$, and I wish to find the type of $\texttt{plus}(e_1;e_2)$, I could derive it as follows in one step according to the rules of the language:
$$\frac{\Gamma \vdash e_1 : \texttt{num}, \Gamma \vdash e_2 : \texttt{num}}{\Gamma \vdash \texttt{plus}(e_1;e_2) : \texttt{num}}$$
But I don't know what it means to use induction "on the derivation".


texts: Knapsack problem 0/1 with even number of items

texts:
So I need to solve the knapsack problem, but I need to make sure that the end solution consists of an even number of items.

I found this on an already existing question:

You can keep two tables with $n$ rows and $C$ columns:

$DP_{even}$ that saves the best knapsack solution with an even number of itens.
$DP_{odd}$ that saves the best knapsack solution with an odd number of itens.

To fill $DP_{even}$ you look at the previous best solution of $DP_{odd}$ plus a new item, or of $DP_{even}$ if you don't take the item:
  $$DP_{even}[i, j] = max(DP_{odd}[i - 1,j - c[i]] +  v[i], DP_{even}[i - 1, j]) $$
The same idea goes for $DP_{odd}$
$$DP_{odd}[i, j] = \max(DP_{even}[i - 1,j - c[i]] +  v[i], DP_{odd}[i - 1, j]) $$

Your solution will be in $DP_{even}[n, C]$

But how do I initialize both arrays, since when I intitialize them with 0 in the first row both arrays are going to be the same? Or am I making a false conclusion?

Edit: I already know how to solve the knapsack problem normally, so you don't need to explain that.


texts: Converting Boolean Expression for NAND Gate Implementation - DeMorgan's Law

texts:
If I have the sum-of-products expression B~CD + ACD how would I convert this so it could be implemented using 3-input NAND gates through DeMorgan's Law? Would this not generate the expression: ~(~(B~CD) ^ ~(ACD))?

It would seem I could implement this and use a 3-input NAND gate with 3-C inputs to act as a NOT gate but this seems wrong.

If this isn't the right place for such a question, let me know and direct me elsewhere if possible, I'll remove it.


texts: What's the highest 'order' data structure

texts:
Not sure exactly how to define this but here's the basis of the question (very loosely)

All lists can be contained in tree's
all trees can be contained in a graph
all graphs can be contained in a multi graph,
and all multigraphs can be contained in a hypergraph (never actually heard of a hypergraph before searching for an answer to this, so may not have it quite right)

So there's a containment hierarchy of 'complexity' of data structures. Is Hypergraph the highest one, is there a proof of this, and is there a name for the study of whatever this is.

By highest one, I mean all structures can be represented as a hypergraph if I chose to. So in any code I could represent all the structures by using a number of hypergraphs (not that I would). tia

[Update] Perhaps an alternative way to ask it is, for any arrangement of data structures consisting of nodes and edges. Does there exist a structure that can't be contained in a hypergraph.

Then there is a second question - is there any data structure which can't be represented using nodes and edges.


texts: Code measurements in emperical software engineering: how to plan measurements?

texts:
I am talking about a measurement plan for software metrics and I am looking for references.

In emperical software engineering there are code level measurements ("software metrics" that measure, e.g., some property like a paprameter for the redundancy of the code and possibly also a parameter of coupling and cohesion of a large software system.

I have a finished paper with software measurements, but the feedback to me was that the way the measurements parameters are derive can be more, say "systematic" or better put in relationship with the research goals. I am interested to improve my approach for my "future work" (My English is not native, so perhaps I don't use the right terms.)

Are there references on a "measurement plan for software metric" that helps to systematically derive measurement parameters from research goals? (Similar to the goal question metric but more focused at academia?) I would like to


texts: If f(n) = Θ(g(n)) then what all can one say about f(h(n)) and Θ(g(h(n))

texts:
I was going across some problems which translated the fact that $\log (n!) = \Theta(n\log n)$ to give
$$\log(\lceil\log n\rceil!) = \Theta(\lceil\log n\rceil \log \lceil\log n\rceil)$$
and therefore $\log(\lceil \log n\rceil!) =  \omega(\lg n)$.

Now I just have this intuition that this sort of conversions shouldn't and wouldn't be always right.

Would it be right to think that.

Any justification as to why am I wrong in thinking that and guidance to what I should have a look at, what texts I should go through to understand it better for myself are very much appreciated.

Thank you.


texts: Why can I look at a graph and immediately find the closest point to another point, but it takes me O(n) time through programming?

texts:
Let me clarify:

Given a scatterplot of some given number of points n, if I want to find the closest point to any point in the plot mentally, I can immediately ignore most points in the graph, narrowing my choices down to some small, constant number of points nearby.

Yet, in programming, given a set of points n, in order to find the closest point to any one, it requires checking every other point, which is ${\cal O}(n)$ time.

I am guessing that the visual sight of a graph is likely the equivalent of some data structure I am incapable of understanding; because with programming, by converting the points to a more structured method such as a quadtree, one can find the closest points to $k$ points in $n$ in $k\cdot\log(n)$ time, or ammortized ${\cal O}(\log n)$ time.

But there is still no known ${\cal O}(1)$ ammortized algorithms (that I can find) for point-finding after data restructuring.

So why does this appear to be possible with mere visual inspection?


texts:
I am attempting a textbook question about asymptotic analysis. The question goes:
**
The number of operations executed by algorithms A and B is 8nlogn and
2n^2, respectively. Determine n0 such that A is better than B for n ≥ n0.
**
So far my approach has been to draw a log-log graph with both lines and find the meeting point, I am thinking that this meeting point is at log(n0) so I can find n0 from it, the one that they are looking for, but things get strange here because the two lines never meet!
Here is the picture of my graph. https://drive.google.com/file/d/1eUFkawKXCWiRBV6BV34Acs5SK4mBHMN4/view?usp=sharing
Any help with this problem will be much appreciated.


texts: Finding all (weighted) cycles through a given vertex

texts:
For a connected undirected graph $G$, given a particular vertex $v$, is there a known (efficient) algorithm to find all simple cycles in $G$ that contain $v$?

In my case, I have weights for every edge.  Ideally I'd like to be able to compute, for every $v \in V(G)$, the product of the edge weights over all cycles that go through $v$. Doing this to some level of approximation would still be very helpful.

Is this a known result?  Any pointers would be very helpful.


texts: When using the Pumping lemma, how do I deal with different cases of y?

texts:
I want to prove L is not regular:$$L={\{www|w \in \Sigma^*\}}$$ $$\Sigma=\{a,b\}$$

I am sure I can do so using pumping lemma. I used  $$ab^pab^pab^p$$as my chosen string but I am stuck. I do not know how to handle different cases of y in pumping lemma.


texts: Does a pushdown automata exists for the following language?

texts:
I have came across a question stating that language $L = a^n b^n c^{2n}$ is not a context free language and hence, no PDA can be constructed for it. But what I am wondering is that, if I add another alphabetical comparison to the above language as

$L_1= a^n b^n c^{2n} d^n$
$L_2= a^n b^{2n} c^n d^{2n}$

And a mixture of above will lead to cfg. Because now we have two comparison so not only we can push the symbol but with the help of other symbol we can pop it so as to empty the stack implies to acceptance of the strings.
my question is I do not know that whether my assertion to the modification of the language is right or wrong so please if you can tell me where iam wrong or right it would be helpful.
One more thing if iam right, then please show the  cfg production to derive them as I can make PDA for them( if iam right) but finding hard to assign production the accepts the above cgl language ( if its then)
Thanks


texts: Shortest common supersequence with Genetic Algorithm

texts:
I'm trying to solve the shortest common supersequence with Genetic Algorithm.
I found it a little bit hard to reduce the size of the chromosomes in each generation.

I know that the maximum size of the chromosome is the total length of the strings.
Even if we create a "naive" genetic algorithm:
Totally random strings (with different length) as initial population, mutation that replace a character, fitness that return how much strings that chromosome contains etc.
How the crossover can reduce the size of the chromosome length?
If we choose n-points crossover, the length of the children cannot be smaller than the shorter parent.

So how genetic algorithm can solve such problems that need the shortest chromosome length? How crossover can reduce the chromosome length?


texts: Allocating tasks among two people equitably

texts:
Given that we have 2 people, and 2n tasks, find the minimum time to complete the tasks. Both persons should solve exactly n tasks each and any task j has to be solved before task j+1. Required time complexity is O(nlogn).
E.g- given this input:

A B

5 3

2 1

3 2

1 2

the intended output is 8, because A solves the second and fourth task, and B solves the first and second.


texts: Finding two languages satisfying conditions

texts:
Let $$E_{TM} = \left \{ \langle M\rangle \mid L(M) = \emptyset \right\}$$

  Prove that there are two languages $L_1, L_2$ such that

  $L_1, L_2 $ are infinite.
  $L_1 \cup L_2 = E_{TM}$
  $L_1 \cap L_2 = \emptyset$
  $L_1$ is decidable, $L_2$ is not recognizable.

I'm finding it really hard to find two languages that satisfy these conditions.

Especially the second condition, which two language unify to $E_{TM}$?


texts: Is this a valid heuristic for Dots and Boxes to reduce the branching factor of the search tree?

texts:
I am implementing an AI based on the MiniMax algorithm that plays the game Dots and Boxes. I would like to reduce the branching factor of the search tree, by introducing a heuristic rule that limits the number of successor states. However, I am not sure whether there exist any situations, where this rule would exclude the optimal move and make the AI play worse.

In the game 2 players take turns, until one of them captures a box, after which they have to make another move, possibly capturing another box etc. For this purpose, I define successor states of $S$ to be all states, where the opponent gets the move, or the terminal state. If a player made a capture and still has to make another move, then the current state is not yet a successor state of $S$ - the player has to continue making moves until they're unable to.

My rule is as follows:

Assume a player makes a series of captures from a starting state $S$ and ends it with a move $m$, after which the turn goes to the opponent. Then it's always better or at least not worse for the player to have made as many captures as possible before finishing the sequence with $m$.

This means that any state $S$ always has less successors, then there are legal moves. All successors where the player captures $n$ boxes and finishes with move $m$ are discarded, unless $n$ is the maximum number of boxes that can be captured such that $m$ can still be a finishing move. For example, in the following state:

immediately capturing the 4 boxes leads to a loss, while dividing them into 2 small chains, 2 boxes each, with the move (2,2)-(2,3) leads to a victory. The optimal strategy is consistent with the rule, as it would not be possible to finish with the move (2,2)-(2,3), if any of the boxes were captured. The rule excludes all successors, where the player captures 1 or 2 boxes, from being considered.


texts: Using rotate to balance a red-black tree?

texts:
You have a Black-Red Tree of height h that has two childs:

  Left child is a full binary tree of height h-1
  Right child is a full binary tree of height h-3

  Balance the tree so both childs of root are of the same height (you don't have to keep the other nodes balanced, just the root).

From Wikipedia I understood that:

  When a subtree is rotated, the subtree side upon which it is rotated
  increases its height by one node while the other subtree decreases its
  height. This makes tree rotations useful for rebalancing a tree.

So the solution would be to right-rotate the root, and then the left and right childs' heights will become h-2.

However it doesn't work well:

The left child node height did decrease by one, but the right child node increased by two!

Why is it happening? Is wikipedia wrong?
How can I do it otherwise?


texts: Tips for creating “Context Free Grammar”

texts:
I am new to CFG's, Can someone give me tips in creating CFG that generates some language

For example

$L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$, where  $w^R$ is the reverse of
     string $w$.

I'm having trouble understanding the language .. I want to build DFA to convert it


texts: In Operating Systems, I can't understand why deadlock happens, why does a process not let go of a resource when it is done using it?

texts: I know deadlock occurs when Process A has resource R1 and is waiting for resource R2, while process B has resource R2 and is waiting for resource R1, however why don't both processes just let go of the resource they are currently owning before/while waiting for the other resource? How does A keep holding on to R1 even though it is waiting for R2.


texts: 3✕n chessboard with holes - maximum number of knights not attacking each other

texts:
I'm trying to to create an algorithm (working in polynomial time) to solve the following problem:

What maximum number of knights that any two of them don't attack each other can be placed on a 3✕n chessboard with holes (knight can't be placed on a hole).
Width of the chessboard (n) and positions of holes are given. Besides the maximum number of knights that can be placed, the algorithm should return their positions.

I think some dynamic programming techniques can be used here but I have no idea how to get a solution for bigger chessboard having a solution for a smaller one. What I make out about the problem so far is:

the chessboard is a bipartite graph, where nodes are the normal (not holes) fields and edges are legal knight moves (white fields in the "left" set and the black ones in the "right" set)
the maximum degree of a node is 4 (knight can move to maximum 4 fields because the width of chessboard equals 3).


texts:
I am trying to figure out the process of generating code (set of instructions, implementation language specifics dont matter at this time) from an automaton.

The description of my intent is vague because although I am an electrical engineer, with extensive coding experience, I have no theoretical CS background and I am struggling to even articulate what I mean. The issue at hand is related to a digital circuit that I am working with. At this point I am not even aware of what I need to start looking into. Another way of describing my intent is, say I got a transition model of a process with the data requirements that are associated with the states. Knowing that, can I generate a program that will implement that model? Is there a field of study that deals with problems like this? Or should I just develop some logic to solve a limited interpretation of the model?

I believe I am using incorrect or misleading terms from a CS standpoint but I will appreciate if I can get some guidance on how to formulate my intent and then try to understand the possible solutions, if any.

Thanks!


texts:
I have pretty simple question, but still can't find an answer just googling it.

I'm trying to understand Chomsky Normal Form (CNF). There are three production rules:

$A \to BC$
$A \to \alpha$
$S \to \epsilon$

First two I understand. But last one $\epsilon$ doesn't makes sense for me. Why do we need this rule? What is use of having this?


texts: residual graph and augmenting path in max flow

texts: I thought I understood max flow perfectly until I got to the exam and we got this. I know how to compute a maximum flow by means of the Ford-Fulkerson algorithm, specify the residual network and augmenting path. But here they gave us a graph where some of the capacities were already full (if you can tell from the picture) and I couldn't find a new augmenting path. Is there another way to solve this?


texts: Greedy algorithm to find Minimum Dominating Set in a tree

texts: Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?


texts: Looking for some more details on "Turing" devices

texts:
I've been reading a lot of computer science literature in the recent past but haven't ran across an explanation of Turing machines, the different types, and why they seem to come up so often (I understand they are a sort of a basis for CS topics).

I've also seen comments by some members mentioning turing-completeness (Particularly when dealing with programming languages) and was just looking for some clarification.

I did search around before posting this and haven't been able to find a similar post or a website that describes this in terms that I have been able to understand or decipher.  Thanks.


texts:
I'm struggling to understand this question:

  Give an encoding of the Turing machine with lowest index that accepts anything but the empty set.

I know what an encoding of a Turing Machine is. But my professor didn't explain what the index of a Turing machine is and how I know that it is lower or higher? Can someone explain what lowest index is and how would I go about this problem?


texts: Context-free grammar for complement of $\{ab \mid b=\mathrm{complement}(a)\}$

texts:
I want to construct a context-free grammar for
$$L=\Sigma^*-\{ab \mid b=\mathrm{complement} (a)  , a,b \in \{0, 1\}^*\}$$
and prove the correctness of answer. The complement of a string is obtained by switching $0$s and $1$s. For example, $\mathrm{complement}(001) = 110$.
I'm trying to decompose the language but I'm not sure about the different cases I should consider. For example, I know that $L$ contains all strings with odd length. But what else do I have to consider? Also, I can't make sure that the language of constructed grammar equals the given language, so a proof is needed.


texts: I'm lookin for a method to construct a particular grammar?

texts:
I'm looking for an algorithm to construct a grammar which, given a set of words which can have multiple identical symbols, represents a compressed version of this set, that is, I can generate only the words of the set but the grammar will take less memory than the set himself.

Besides, I'm looking for an algorithm which can update the grammar when I want to remove a word of the set.

What type of algorithm is able to do that ?

I give a concrete example:

Consider a string S="abcdefghij", and then consider the finite set of words "cdhij", acdef", "fghi", "bcfgij", "defi".

I would like to construct a grammar which generates only this set of words (words which can be viewed as concatenation of various substrings of any length from the original string S).

Finally I would like to remove a word in the set and update subsequently the grammar.

Thank you.


texts: Finding max value algorithm with subset comparison

texts:
I have a set of $N$ different values, and my goal is to find the biggest one in the least number of comparisons. Comparing subsets (using the sum of each) is also allowed, and counts as one comparison.

The intuitive algorithm would be comparing them linearly: compare two items, compare the biggest with the next one, repeat. That would give us a total of $N-1$ comparisons.

Since I couldn't come up with anything, I want to know if there is some algorithm to do this more efficiently (making fewer comparisons), taking advantage of subset comparison being allowed.


texts: How many different strongly connected graphs can be created given n nodes?

texts:
Given some fixed number of nodes $n$, which we will number 1 to $n$ in order to tell them apart, how many different strongly connected graphs can be created? Multiple edges with the same starting and ending nodes should be considered redundant and not contribute to the total.

For example, if $n$ is 2, we can create only one strongly connected graph, (the 2-cycle.) But if $n$ is 3 then we can create 18 different graphs: 2 with 3 edges, 9 with 4 edges, all 6 with 5 edges and the complete 3-graph.

Is there a known general formula for computing this number for a given $n$?


texts: Determine number of values less than mean in one pass through list

texts:
The problem statement is as follows:

  Can we determine precisely the number of elements less than the mean in a list $A$ of $n$ numbers in only one pass through the array (starting at $A_1$ and ending at $A_n$) with only constant memory?

By "constant memory" I mean a constant number of $O(m \log_2 n)$ bit words where $m$ is the number of bits to represent the largest value in $A$. Some other things to consider:

Assume $m$ is non-constant and $m \geq \log_2 n$. If $m$ were constant, we could not even count $n$ as Yuval mentioned.
Assume values in $A$ are integers, but does it affect the problem if they are rational, or real valued?
Assume values in $A$ are uniform random. It helps if they are uniform random because we can get a tight confidence bound with a constant number of elements. How high of a confidence bound can we get?
Time complexity does not matter. You can spend as much time as you want on a particular $A_i$ if that helps, but once you move to $A_{i+1}$ you cannot go back unless you have stored $A_i$ in one of your constant memory words.
What if the values in $A$ are non-uniform random with distribution is unknown? What if the distribution is known?
What if we are not constrained to going from $A_1$ to $A_n$, perhaps we could randomly sample and get a tight confidence bound even if the distribution is non-uniform?
What if instead of mean, we wanted values less than median? Does this help at all?

It's clear with 2 passes through the array we can get this value precisely with no probability involved. With one pass through the array this seems not be possible, but I am not sure. You could create an adversary that waits until the last element to give it an extreme value and throw off all previous calculations. However, with a uniform distribution this is limited. Any thoughts on these variations or an answer under the assumptions provided would be appreciated.


texts: Meyniel's theorem + finding a Hamiltonian path for a specific graph family

texts:
Let's say we have a directed graph $G = (V, E)$ for which $(v, w) \in E$ and/or $(w,v) \in E$ holds true for all $v, w \in V$. My feeling is that this graph most definitely is Hamiltonian, and I want to find a Hamiltonian path in it (from any vertex to any other vertex, I don't care where to start or stop).

I wanted to refer to Meylien's theorem for this:

  A strongly connected simple directed graph with $n$ vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to $2n − 1.$

There are two subtleties that I'm not sure about with this theorem:

What is meant by "adjcent vertices". Does the order matter here? Is the pair $(v,w)$ adjacent even if $(w,v) \in E$ but not $(v,w)$ itself? If that is the case and the graph is strongly connected, than it must obviously be Hamiltonian, since there are no non-adjacent pairs of vertices at all.
A graph with the above property is not necessarily strongly connected. I think this is easy to solve: We can just decompose the graph into SCCs. We will still have no non-adjacent pairs of vertices in the components and all of them are Hamiltonian. We can then construct a Hamiltonian path of the whole graph by connecting them in topological order.

Is the above reasoning correct and the theorem applicable? Or is there some other argument we can use to show that there is a Hamiltonian path in the graph?

In the end I want to actually find the Hamiltonian cycles in the SCCs, but haven't had much luck finding a constructive proof of the theorem, let alone an algorithm that solves this. Can it be done in a straightforward way? I feel like some kind of greedy approach could work, where we take the nodes in decreasing order of outdegree or something similar.


texts: Approximation factor of NP-complete problems

texts:
We talked about the following theorem in class but I am still having problems to understand it:

For a NP-complete decision problem "Does a valid solution with a value $\leq K$ exist?" there is no approximation algorithm for the corresponding minimization problem with an approximation factor $\lt 1 + 1/K$.

Why is this necessarily true? And where does that upper bound $1 + 1/K$ come from?


texts: Given an non-deterministic finite automaton, will its determinization always have unreachable states?

texts:
Given an NFA that accepts the regular language L, will its equivalent DFA which accepts the same language L always have unreachable states.
If it does, why?


texts: Complexity analysis of recurrence with multiple variables

texts:
To give background, there's two ways to multiply two complex numbers:

Method A: requires 3 multiplications and 5 additions
Method B: requires 4 multiplications and 2 additions

And it's given that multiplying two $m$ bit numbers is $O(m^2)$ and that adding two $m$ bit numbers is $O(m)$.

Now given a list of complex numbers, we can multiply them together using a divide and conquer algorithm that looks like this:

function divideAndConquer(list, i, j) {
  if (i === j) {
    return list[i]
  }
  const m = i + (j - i) / 2
  return methodA(divideAndConquer(list, i, m), divideAndConquer(list, m + 1, j))
}

My goal is to find the complexity of the divide and conquer algorithm using methods A and B respectively. Using method A as an example, we could say that

List of size 1: $T(1) = 1$
List of size 2: $T(2) = 3am^2 + 5bm$ where $a > 0, b > 0$

because with one number you don't do anything, and with two numbers you do 3 multiplications and 5 additions.

However, now my issue is that I'm not quite sure that for $T(n)$ what I have is right because while it's quite obvious that it'll be something like

$$T(n) = T\left(\frac{n}{2}\right) + f(n)$$

I'm not really sure how to find out what $f(n)$ is because at each level $n$, $m$ will grow as a result of multiplication, meaning that $f(n) = 3am^2 + 5bm$ isn't accurate.

Essentially, the thing that confuses me is that there are two variables in play. The size of the list, $n$, and the size of the numbers in bits, $m$, that you're multiplying. So the heart of my question is really how do I solve a recurrence that has multiple variables? In this case $n$, and $m$.


texts:
Note: Not sure with the tags.

I'm quite new to this area of Computer Science. I was used to just developing software and applications and applying certain algorithms when necessary. However, I am tasked right now with a very complex task. I apologize in advance, although being a Computer Science graduate, I've only been in the industry for at least 2 years. So, this specific requirement is really eating me up.

Consider two time-series data sets:

Data Set 1

Date           Category            Count
11/12/13       A                   30
11/13/13       A                   23
11/14/13       A                   24
11/12/13       B                   53
11/13/13       B                   36
11/14/13       B                   67

Data Set 2

Date           Category            Count
11/12/13       C                   44
11/13/13       C                   12
11/14/13       C                   62
11/12/13       D                   26
11/13/13       D                   73
11/14/13       D                   62

I was tasked to get which Category-pairs from D1 and D2 has the highest correlations. This was simple enough using Pearson or Kendall's

For example (mock correlation values for example):

Category Pair       Correlation
A vs C              0.532222
A vs D              0.742221
B vs C              0.988888
B vs D              0.356666

This was easy enough to do, so I just had to output that list in order from highest to lowest. But the thing is, my boss tells me that I should add an evolutionary algorithm to the program because the current algorithm I am doing to determine the correlation is of brute force where I pair each A to C, then D, and do the same with B. However, my boss tells me that if I use evolutionary algorithm, it will only take randomized pairs which will reduce performance time but still give a somewhat above average result.

I am quite unsure with how to approach this. I've been reading on Evolutionary Algorithms for a while now but I can't seem to wrap my mind on how this time-series data set would fit into the algorithm.

Am I supposed to apply the Evolutionary algorithm after the correlations have been computed? I can't seem to grasp why I need to do an evolutionary algorithm on such data sets?

From my understanding, Evolutionary algorithm is like 'survival of the fittest', keeping the most optimized, and best values in the end.

I am pretty sure my understanding of Evolutionary algorithms are still lacking, please do enlighten me. I am not a native English speaker but I'll try my best to understand. It would also be great if someone can point me to the right direction on how to approach the merging of these two concepts together.


texts: 1 bit register with data flip flop doesn't store bit?

texts:
A 1-bit register:

  Credit:
  Elements of Computing Systems
  by Noam Nisan and Shimon Schocken
  ISBN-13: 978-0262640688

I know that the data flip flop outputs the input at the previous time step.

Based on this, I created this table (not sure if correct):

Note: For the Mux, 1 is for in and 0 is for DFF output.

$$
\begin{array}{|c|c|c|c|}
\hline
\text{In} & \text{DFF In} & \text{Load} & \text{Out} \\ \hline
1 & 1 & 1 & 0 \\ \hline
1 & 0 & 0 & 1 \\ \hline
1 & 1 & 0 & 0 \\ \hline
\end{array}
$$

The output is always alternating, no bit is being stored. It should constantly output 1 while load is 1 because that's what we initially stored.

I know that a register does actually store data, so something is wrong in my understanding of this.


texts: Cover a polygon with least amount of parallelograms

texts:
I am solving the task that is as follows:

Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside.

Goal: to cover it with 2 (at least) or more parallelograms that together are equal to or contain the whole polygon. The following criteria should be met:

There is no point of the polygon that lies beyond parallelograms.
The number of the parallelograms should be the least possible. I.e. we want to find largest parallelograms that cover the polygon.
These parallelograms must not intersect within the polygon.

Question: Is this task solved and if it is solved - how? I am looking for a direction where to start with and what related algorithms/theory to learn.


texts:
I'm currently looking for literature/papers on machine learning techniques to create structures.

In detail, I want to generate finite automata (NFA, DFA), which are useful for student-exercises. So I have a bunch of useful graphs and I want to check, whether there is a possibility to feed that into an ML algorithm and let it construct new graphs.

I could use reinforcement learning, by checking specific properties after the generation to determine the applicability for exercises. For example, an exercise should not contain more than 5 but not less than 3 states, while having a percentage of X transitions, is connected and so forth. The actual criteria depend on the exercise.

I'm not able to find any papers on how one could feed that into an ML approach, s.t. in generates new automata.

Can someone provide some? Thank you :)


texts: If the union and intersection of two NP languages are both in P, prove that the langauges are in co-NP

texts:
Given $L_1, L_2 \in \mathsf{NP}$, $L_1 \cup L_2 \in \mathsf{P}$ and $L_1 \cap L_2 \in \mathsf{P}$,

Prove: $\ L_1, L_2 \in \mathsf{coNP}$

What I've done so far is:

$$ L_1 \cup L_2 \in \mathsf{P} \Rightarrow (L_1 \cup L_2) ^\complement \in \mathsf{P}
   \Rightarrow L_1^\complement \cap L_2^\complement \in \mathsf{P} $$

$$ L_1 \cap L_2 \in \mathsf{P} \Rightarrow (L_1 \cap L_2) ^\complement \in \mathsf{P}
   \Rightarrow L_1^\complement \cup L_2^\complement \in \mathsf{P} $$

How do I proceed from here?


texts:
We take the sequence of integers from $1$ to $n$, and we push them onto a stack one by one in order. Between each push, we can choose to pop any number of items from the stack (from 0 to the current stack size).

Every time we pop a value from the stack, we will print it out.

For example, $1,2,3$ is printed out when we do push, pop, push, pop, push, pop. $3,2,1$ comes from push, push, push, pop, pop, pop.

However, $3,1,2$ is not a possible printout, because it is not possible to have $3$ printed followed by $1$, without seeing $2$ in between.

Question: How can we detect impossible orders like $3,1,2$?

In fact, based on my observation, I have come out a potential solution. But the problem is I can't prove my observation is complete.

The program that I wrote with the following logic:

When the current value minus the next value is larger than 1, a value between current and next cannot appear after next. For example, if current=3 and next=1, then the value between current (3) and next (1) is 2 which cannot appear after next(1), hence $3,1,2$ violates the rule.

Does this cover all cases?


texts: How can I draw a Moore diagram for a given circuit?

texts: I have a circuit and I should draw a moore diagram (state diagram) for that.  The problem is that every state can have 5 inputs and this makes the question hard for me.  I tried about 20 times to draw that diagram and every time I failed.  Can anyone help?


texts: Given a fast and a slow computer, at what sizes does the fast computer running a slow algorithm beat the slow computer running a fast algorithm?

texts:
The source of this question comes from an undergraduate course I am taking, which covers an introduction to the analysis of algorithms. This is not for homework, but rather a question asked in CLRS.

You have a slow machine running at $x$ MIPS, and a fast machine running at $y$ MIPS. You also have two algorithms of the same class, but different running time complexities: one "slow" algorithm runs at $T(n) = c_1n^2$ whereas a "fast" algorithm runs at $T(n) = c_2n \log n$.

You execute the slow algorithm on the fast machine, and the fast algorithm on the slow machine. What is the largest value of n such that the fast machine running the slow algorithm beats the slow machine running the fast algorithm?

My solution so far:

Find the set of all $n$ such that $$\frac{c_2n\log n}{x} > \frac{c_1n^2}{y}$$ where $n$ is a natural number.

This is my work thus far:

$$\{n : \frac{c_2 n \log_2 n}{x} > \frac{c_1 n^2}{y}, n \in \mathbb{N}\} = \{n : n < \frac{c_2 y}{c_1 x} \log_2 n, n \in \mathbb{N}\}$$

The only solution that comes to mind now is to plug-n-chug all values of $n$ until I find the first n where

$$n < \frac{c_2y}{c_1x}\log(n)$$

no longer holds.


texts: How to objectively quantify the simplicity of an algorithm?

texts:
I often ask for a "simple" algorithm that solves some problem and I realized that, almost aways, the answerers's notions of simplicity doesn't match mine's. Often, for example, I notice people using numbers inside a supposedly "simple" answer, ignoring the fact numbers are, themselves, a complex dependency which adds a ton of bytes to the implementation of that algorithm in any language that doesn't have arithmetics (addition, multiplication, division, modulus, etc.) as primitives. Maybe that is partly due to fact most human programming languages have numbers built in, but that is merely an accident due to our obsession with numbers.

When I ask for a "simple" algorithm, I mean one with low Kolmogorov Complexity. That is, I want something that is simple to implement on the average neutral language: it must be simple in Python, in C, in brainfuck or on the untyped lambda calculus. Its simplicity must be inherent, not depend on the specific language. Sadly, I can't ask specifically for that, because the Kolmogorov Complexity of an object is undecidable. Nether less, certain things are just obvious. For example, an implementation of XOR is certainly, inherently less complex than an implementation of SHA256, in any "neutral" language. But then, how could I define a "neutral" language? Those things make it very hard to ask formally for something that is simple, despite the meaning being so obvious to me. I could ask specifically for the size of the program on the binary lambda calculus, but on my experience that just shies people away from my question.

My question, is: how do I properly ask for a "simple" algorithm, given the above notion of simplicity?


texts:
I am having trouble understanding a mapping reduction and I would appreciate your help. Define

$\quad \begin{align}
  A_{TM} &= \{ \langle M, w \rangle \mid M \text{ Turing machine}, w \in \mathcal{L}(M)\} \\
  S_{TM} &= \{ \langle M,w \rangle \mid M \text{ Turing machine}, w \in \mathcal{L}(M) \implies w^R \in \mathcal{L}(M)\} \\
\end{align}$

and consider the reduction of $A_{TM}$ to $S_{TM}$ as follows.

Given $\langle M, w \rangle$ the following Turing machine $M'$ is defined:

M' on input x:
  if x = 01 then accept
  else run M on w and accept x if M accepts w

I don't understand the reduction entirely, this reduction is supposed to solve $S_{TM}$ using $A_{TM}$.  Why do I need to check if x = 01? There is no need to check anything about the reverse of $w$?  How is that covered by the reduction?


texts: Given N sets of disjoint subsets, find a set of disjoint subsets such that it satisfies a criteria

texts:
Given a collection of sets $S_i$ of disjoint subsets $sub_i$ of a set $X$,
find a set $A$ of disjoint subsets $asub$ such that each one of these subsets is subset or equal to at most one subset in each of $S_i$, i.e., for

$S_1$ = $\{sub_11,sub_12,sub_13\}$, where $sub_11$, $sub_12$, $sub_13$ are disjoint,

$S_2$ = $\{sub_21,sub_22\}$, where $sub_21$, $sub_22$ are disjoint

Then find
$A$ = $\{asub1,asub2,asub3\}$, where $asub1$, $asub2$ are disjoint

and

$asub1$ can be a subset of only one of $sub_11$ or $sub_12$ or $sub_13$ but not more than one of them. Same goes for $asub2$ and $asub3$.

Similarly

$asub1$ can be a subset of only of either $sub_21$ or $sub_22$ or but not both of them. Same goes for $asub2$ and $asub3$.

More formally,

$\forall sub_i \in S_i,$
and given a subset $asub \in A,$

If $Asub=\{sub_i\mid asub\subseteq sub_i\}$

$then$
$|Asub|=1$

$Example 1:$

$X = \{e1,e2,e3,e4,e5\}$

$S_1 = \{\{e1,e2\},\{e3,e4\},\{e5\}\}$

$S_2 = \{\{e1\},\{e2,e3,e4\},\{e5\}\}$

$S_3 = \{\{e1,e2,e3,e4\},\{e5\}\}$

$A= \{\{e1\},\{e2\},\{e3,e4\},\{e5\}\}$

$Example 2:$

$X = \{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12\}$
$S_1 = \{\{e1,e2,e11,e12\},\{e3,e4,e5,e6\},\{e7,e8,e9,e10\}\}$
$S_2 = \{\{e1,e2,e3\},\{e4,e5,e6,e7,e8\},\{e9,e10,e11\},\{e12\}\}$

$A= \{\{e1,e2\},\{e3\},\{e4,e5,e6\},\{e7,e8\},\{e9,e10\},\{e11\},\{e12\}\}$

Preferably the algorithm for finding $A$ should take optimal time.

P.S. Forgive me if the mathematical description of the problem is not formal enough or if there are mistakes in it, I am not a mathematician.


texts: Why does packet data don't need trailer/footer while frame needs it?

texts:
Why does packet don't need trailer/footer while frame needs it?

I am trying to understand networking concept regarding OSI & TCP/IP layering. I have googled a bit and it says that the footer in data link layer pdu (frame) is needed as a mark of the end of the pdu.

But why does packet data etc in the layers above it doesn't need footer to mark the end of the pdu as well?


texts:
I am study this lecture The Complexity of Propositional Proofs. Here there is a term size of propositional formula (page 2),

  Every tautology $\tau$ on $n$ variables has an $F$-proof in which thera are at most $2^{O(n)}$ formulas, each of which has size polynomial in the size of $\tau$

but here doesn't define that term. I have googled this term and I have found something similar length of propositional formula, which is defined as

  The function $L(P)$ giving the length of a formula is defined by
  structural induction as follows:

$L(p_i) = 1$, for all atomic formulas $p_i$
$L(P ∧ Q)$ = 1 + $L(P ) + L(Q)$,
$L(P ∨ Q) = 1 + L(P ) + L(Q)$,
$L(¬P) = 1 + L(P)$.

My question is: Is the length and size of a formula the same?


texts: 4-digit 5's complement of a negative number

texts:
Let $n = -13, \ k = -24$

How do I find the 4-digit 5's complement of each number? What would be the result of $n + k$ in complement representation?

I understand how to calculate $n$-digit, 2's complement. I convert it to base 2, invert and add one.

Also, with positive numbers, let's say $n = 13,  \ k = 24$, the 4-digit 5's complement would be $(5542)_{10}$ and $(5531)_{10}$. Correct? What would their addition be?


texts: Can an (extended) regular grammar have multiple nonterminals in its RHS?

texts:
Standard (right) regular grammars have three kinds of rules:

A <- ""
A <- "a"
A <- "a" B

This is OK for a theoretical point of view, but a big inconvenience to be usable in practice. A practical regular grammar should allow us to use commodity operators (|,*,+,?,.,(,)), character sets and group multiple rules in a single one. For example, the following regular grammar describes fractional numbers:

start <- digit+ dot digit* | digit* dot digit+
digit <- [0-9]
dot   <- '.'

The question is, what restrictions must be applied to RHS non-terminals to keep this grammars regular (if it is possible at all)?

NOTE

Q - Why regular grammars instead of regular expressions?

A - Regular expressions are OK for simple languages, but they are write-only for more complex ones. On the other hand, well written extended regular grammars are allot more readable and maintainable and allows us to extend them with captures and rule actions easily.


texts: Is there a #$P$-complete counting problem such that every (valid) instance of its decision version is a Yes-instance?

texts:
I want to know whether there is a decision problem, written EasyProblem, satisfying the follow property:

For every valid instance $x$, $x$ is a Yes-instance for EasyProblem (if we construct EasyProblem as a nature problem). Formally speaking, maybe we can define EasyProblem as a language $L \in \mathrm{DTIME}(n)$ or even $L \in \mathrm{DTIME}(1)$.

The counting version #EasyProblem is in #$P$-complete.

Really what I'm asking is: can we construct a very easy decision problem, but its counting version is too hard? Or can we construct a very hard counting poblem, but its decision version is too easy?


texts: Modify a binary matrix to minimize the sum of values of the rows

texts:
I have a matrix of zeros and ones, i.e., $\mathbf{X}=[x_{ij}]$ with $x_{ij}\in\{0,1\}$ for all $i=1,2,\ldots,m$ and $j=1,2,\ldots,n$. Associated with each row  $i$ of the matrix $\mathbf{X}$ a set of the consecutive number of zeros $S_i$. Row $i$ has a value $v_i=\sum_{k\in S_i}\lfloor k/2\rfloor$.
I would like to modify this matrix such that:

$\sum_{i=1}^mx_{ij}\leq1$ for all $j=1,2,\ldots,n$: keep only a single one in each column; and
$\sum_{i=1}^mv_i$ is as small as possible.

An example.
Let $$\mathbf{X}=\begin{pmatrix}1&0&1&0&0&0&1\\1&0&0&0&0&0&0\\0&0&1&0&1&0&0\\1&0&0&1&0&0&1\\\end{pmatrix}.$$ Here, we have

$S_1=\{1, 3\}$ and $v_1=1$;
$S_2=\{6\}$ and $v_2=3$;
$S_3=\{2, 1, 2\}$ and $v_3=2$; and
$S_4=\{2, 2\}$ and $v_4=2$.

If I make the following modification to $\mathbf{X}$:

$x_{21}=x_{41}=0$;
$x_{13}=0$;
$x_{47}=0$;
I would get the following modified matrix $$\mathbf{X}'=\begin{pmatrix}1&0&0&0&0&0&1\\0&0&0&0&0&0&0\\0&0&1&0&1&0&0\\0&0&0&1&0&0&0\\\end{pmatrix}.$$

We have satisfied the the first constraint of $\sum_{i=1}^mx_{ij}\leq1$ for all $j=1,2,\ldots,n$. Now, we have

$S_1=\{5\}$ and $v_1=2$;
$S_2=\{7\}$ and $v_2=3$;
$S_3=\{2, 1, 2\}$ and $v_3=2$; and
$S_4=\{3, 3\}$ and $v_4=2$.

The value of $\sum_{i=1}^mv_i$ if $9$. If I try all possible combinations of the modifications I end up with the one that gives the best value of $\sum_{i=1}^mv_i$.
Can we solve this problem in polytime?


texts: Why we don't consider cycles in path problems?

texts: I'm working on my research and I found that for directed graphs, there are many algorithms trying to solve shortest path problem(like Dijkstra, Bellman‐Ford algorithm), but few is to get all paths(including circles) in the result. Is it because the complexity is way too expensive? Thanks in advance for your help!


texts: In which pipeline stage are exceptions detected?

texts: Do you immediatly handle an exception when it occurs (for example an overflow exception in the EX stage) or do you wait until the final pipeline stage and then check whether any interrupts had occured?


texts:
It is known that the runtime complexity of sorting is $\Theta (n \log n)$. But what if we have, for every input array of size $n$, an oracle that can sort any array of $k<n$ numbers in constant time?

In this case, the runtime of merge sort becomes $O(n)$. The recursive calls are cheap and the runtime is dominated by the merging step.

Does there exist a more efficient algorithm for sorting, using these oracles? My guess is that the answer is negative, i.e. sorting with recursive oracles has runtime complexity $\Theta(n)$.  Is this correct?

NOTE: this is a special case of the following question from cstheory.SE L https://cstheory.stackexchange.com/questions/27094/are-there-problems-for-which-divide-and-conquer-is-provably-useless


texts: Why Isn't This Outlier Score/Reconstruction Error Not Squared?

texts:
I was looking through a paper called "AI2
: Training a big data machine to defend", and saw this (http://people.csail.mit.edu/kalyan/AI2_Paper.pdf)

$score(X_{i}) = \sum_{j=1}^{p} (|X_{i} − R^{j}_{i}|) × ev(j)
$

Where $ev(j)$ is the percentage of variance.

I was wondering, why isn't the the term $(|X_{i} − R^{j}_{i}|)$  squared like other reconstruction error functions, or at least the ones I saw?

I believe the term $\sum_{j=1}^{p} (|X_{i} − R^{j}_{i}|)$ is a mean absolute error and is used here because it is better than a mean square error because it is better for a time series and is more robust. If I am wrong, please correct me.


texts: How do analogue computers perform logical operations?

texts:
My idea of analogue computers had been that they were the discrete version of digital computers, with fuzzy logic operations returning values in the interval [0, 1] instead of Boolean operations.

However looking at schematics, they seem to be built for directly computing differential equations.

I'm struggling to connect this to dicrete computation. How do analogue computers perform simple logical operations?


texts: I am trying to prove that the problem of having a person at the minimum x number of intersections to be able to see each street is NP-Complete. I think that the street problem is very similar to the Vertex Set problem, and to prove it is NP-Complete I could some form of reduction like 3-SAT to Vertex Set but with my problem in place, to verify the requirement that it is NP-Hard (I can prove it is NP). I'm having an extreme amount of trouble getting started with this however. I've looked many examples of reduction but cannot think how to start my own. How would I show the reduction from 3-SAT to the street problem/Vertex Set?


texts: What data structure might this game use?

texts:
This question is not about game development or about actual implementation details.

I was playing Little Alchemy yesterday.  (Warning: Productivity hazard.)  You start with the four classical Elements of earth, air, fire, and water.  You can combine them to produce other "Elements" (wood, humanity, time, cities, etc.), combine those to produce even more, etc.  All of the relationships are predefined, so the game is less about crafting and more about lateral thinking.

I got curious about how exactly the game could store and query the various combinations optimally.  Whether the developer actually does so under the hood is a different story, and not what I'm asking about.

Consider the following game mechanics:

There is no limit to the number of Elements, but it's decided in advance by the game's designer and thus does not change at runtime.
All Elements are made by combining exactly two other Elements, possibly of the same kind (Fire + Water = Steam).
Even the four base Elements can be created (Fire + Ice = Water).
Some Elements can be created through more than one combination. (Fire + Water = Energy + Water = Steam)
Some combinations produce more than one Element (Human + Cow = Minotaur and Milk)
Some Elements are "final" and cannot be combined to produce any other, though they may in future updates.  (Jedi + Swamp = Yoda)
Order of combination does not matter (e.g. Water + Fire = Fire + Water).

The game presumably needs fast lookup and low memory usage.  More specifically:

Given exactly two elements, look up the result of their combination, if any.  This should be fast.
There is no insertion or removal except by the game's designer in advance.  This can safely be slow.

Given these, what data structure might Little Alchemy use to store the various combinations that can be used to produce elements?

Initial Thoughts

Back-of-the-envelope guess?  A big ass-hash-table that maps (Element, Element) pairs to Element lists. For $n$ Elements, this results in amortized $O(1)$ lookup and $O(n^2)$ memory, because theoretically any combination can produce every other Element at once.  Can we do better?


texts: In a kernel, what are "global constructors"?

texts:
I am a beginner developing kernels (though I have developed several Hello World programs in C and C++). I frequently see reference being made to global constructors (e.g., osdev https://wiki.osdev.org/Calling_Global_Constructors), but I have not been able to find a clear definition or in it.

Could someone please guide me to the correct definition? I know they are called before the kernel, but I am having trouble understanding why.

The kernel of which I take the example, is this:
  https://github.com/AlgorithMan-de/wyoos/commit/7eb9f8a1d5089cf7587e553e601c42db34dc94a2

in the linker.ld file, have this code:

  .data  :
  {
  start_ctors = .;
  KEEP(*( .init_array ));
  KEEP(*(SORT_BY_INIT_PRIORITY( .init_array.* )));
  end_ctors = .;

  *(.data)
  }

in the kernel.c file, have this code:

typedef void (*constructor)();
extern "C" constructor start_ctors;
extern "C" constructor end_ctors;
extern "C" void callConstructors()
{
  for(constructor* i = &start_ctors; i != &end_ctors; i++)
     (*i)();
}


texts: How to detect if objects are on top of each other?

texts: Lets say we know the co-ordinates of each object in a camera co-ordinate systems. How do we find out if some object is on top of each other? My idea is: Compare each object and point with one another.For two different points on different objects check if the X and Z values are the same and the difference between the Y value is within some threshold. What do you guys think?


texts: NP-Completeness and commutative property

texts:
If $X$ is NP-complete and for some $Y, X\leq_p Y$ and $Y\leq_p X$ what can we say about $Y$?

My intuition says that this is only the case when $X=Y$ but I'm not sure how to justify this.


texts: How does a compiler give an immediate compilation error?

texts: I am confused. I know that compilers translate your code one time as a whole into intermediary code, but how come when I type in something improper, the IDE shoots out a compilation error immediately? What am I not understanding? I thought the whole difference between an interpreter and a compiler is that the former translates code line by line and the latter translates your source program as a whole in one go.


texts: Channel coding and Error probability. Where are these probabilities from?

texts:
From where are the following probabilities?

We consider BSCε with ε = 0,1 and block code C = {c1, c2} with the code words c1 = 010 and c2 = 101. On the received word y we use the decoder D = {D1,D2} which decodes the word to the code word which has the lowest hamming distance to y. Determine D1 and D2 and the global error probability
ERROR(D) if the code words have the same probability.
Hint: To an output y there exists only one x which gets to a failing decoding.
(Y = 100 will only gets wrong decoded if we sent message is x = c1 = 010.) So the term (1− p(D(y)|y)) is equal to Pr[X = x|Y = y] for a suitable x.

Nun

$$\begin{aligned} &\text { Hamming-Distance: }\\ &\begin{array}{c|cc} \text { Code } & 010 & 101 \\ \hline \hline 000 & 1 & 2 \\ \hline 001 & 2 & 1 \\ \hline 010 & 0 & 3 \\ \hline 011 & 1 & 2 \\ \hline 100 & 2 & 1 \\ \hline 101 & 3 & 0 \\ \hline 110 & 1 & 2 \\ \hline 111 & 2 & 1 \\ \hline \end{array} \end{aligned}$$ $$\left.D_{1}=\{000,010,011,110\} \text { (Decides for } 010\right)$ $\left.D_{2}=\{001,100,101,111\} \text { (Decides for } 101\right)$$ $$\begin{aligned}
E R R O R(D) &=\sum_{y \in \Sigma_{A}^{3}} p(y)(1-p(D(y) | y)) \\
&=\overbrace{2 \cdot p(y)(1-p(D(y) | y))}+\quad \overbrace{6 \cdot p(y)(1-p(D(y) | y))}^{ } \\
&=2 \cdot\left(\frac{729}{2000}+\frac{1}{2000}\right)\left(\frac{7}{250}\right)+6 \cdot\left(\frac{81}{2000}+\frac{9}{2000}\right)\left(\frac{757}{1000}\right)
\end{aligned}$$ How do I get to the probabilities $$ \frac{7}{250}$$ and $$\frac{757}{1000}$$??

I don't get this calculation. It should be right. But I don't get how to get to these probabilities.

Could someone explain me this?


texts: Searching for the biggest area inside 2D matrix

texts:
I have an algorithmic problem where I need to find the biggest area of a certain type of pixels inside a 2D matrix with following conditions:

Each pixel needs to be connected either diagonally or adjacently.
The area is considered coherent only if it is surrounded by the other type of pixel( x-es on the edge are not)

A pixel is considered an object with 3 fields:

int x,y;          //Cordinates of a pixel
String type;      //Type of a pixel
boolean visited;  //Was the pixel visited

The input file is something like this:

oooooooooo
oXXooXXXoo
oooXoooooo
xooooXXXXo
xxooXooooo
xxxooooooo

The output in this example should be an int of value 5.

Is someone able to tell me if the BFS algorithm is a viable solution or should I try a different approach?


texts: If a problem Q is NP complete, is another problem reducible to Q also NP complete?

texts: Let's say $\mathcal{P}$ is a yes/no prolem with an existing reduction to the problem $\mathcal{Q}$ (with time complexity $\mathcal{O}(n^2)$). $\mathcal{Q}$ is NP complete. Does this mean that $\mathcal{P}$ is also NP complete?


texts: Complexity of calculating average across distributed network?

texts: What is the communication complexity of the best known algorithm for computing the average of a set of N*D numbers distributed across N nodes with D values per node? Assume you have full control over the network topology and protocol.


texts: Time complexity of minimizing Boolean expression

texts:
Given any arbitrary boolean expression using AND, OR and NOT gates what is the time complexity of minimizing the expression such that minimum number of gates are used.

The following Wikipedia article only talks about the space complexity of the problem (which is PSPACE), but does not talks about the time complexity.

https://en.wikipedia.org/wiki/Circuit_minimization_for_Boolean_functions


texts: Does a collision occur if two packets are sent at the same time in Slotted AHOLA?

texts:
There's something I don't really understand about the Slotted AHOLA protocol, and I hope you can help me: what happens if a station wants to send two packets at the same time? Will it be considered as a collision? If not, when will the first and second package be sent?

I did some research here but all I found was probability formulas that I haven't seen yet...


texts: context free grammar not closed under relative complement using product construction of pda and dfa

texts:
Hello friends need a bit of help,

I Know that

given: $$L_1 \in L_{cfg}, L_2 \in L_{reg}$$ $$L_2/L_1\notin L_{cfg}$$
because if it was contex free it would imply that $L_{cfg} $ is closed under complement and this is not true.
But at another glance I can build a product construction of pda and dfa that could solve this problem.

Consider this:

product construction of pda and dfa
at any input read the input and at the same time move through the pda and the dfa
the accept states will be all the states where $(q_1, q_2)$ s.t $q_1\notin A_{pda}  $ and $ q_2\in A_{dfa}$

this machine should accept the language of $L_2/L_1$ and this would imply that this language is infect context free.
I know that some-thing is wrong here but it scares me that I cant understand what... please help.


texts: Composition of functions computable in logspace

texts:
The bit-graph of $f\colon \{0,1\}^* \rightarrow \{0,1\}^*$ is the language:

$\text{BIT}_f := \{\langle x,i \rangle : 1\leq i \leq|f(x)| \text{ and the $i$-th bit of } f(x) \text{ is } 1\}$

It is said that $f$ is logspace computable if $\text{BIT}_f$ is decidable in space $O(\log n)$. Decidable means that there exist a Turing Machine $M$ such that:

if $\langle x,i \rangle \in \text{BIT}_f$ then $M(\langle x,i \rangle) = 1$
if $\langle x,i \rangle \notin \text{BIT}_f$ then $M(\langle x,i \rangle) = 0$

Prove that the composition $(f \circ g)(x)=f(g(x))$ of two logspace computable functions $f,g$ is also a logspace computable function.

Any hint on this exercise? What I tried so far is playing with the composition of the two Turing Machines associated with $f$ and $g$, but I didn't succeed because it always end up with a case analysis exercise.


texts: If there is comparison between two variables then language is not regular. Then how the below two languages L1 and L2 Regular? Please Explain

texts: How these two languages be regular.If there is comparison between m and n since (n < m) is the condition to be satisfied.


texts:
First question :

Is the following formula a valid MSO formula?

$\theta(S, r) = \exists (e_1, t_1), ... ,(e_h, t_h) \bigwedge\limits_{(e_i, e_j) \in \rho(S,r)} \mathcal{R}((e_i, t_i), (e_j, t_j))$

So my main concern here is the fact one states there exists $e_1, t_1$ etc. but then goes on to not use these in the actual formula (only using $e_i$ and $e_j$). Is this correct?

Second question :

While browsing around, I found the following :

(found in this post : MSO (Monadic second-order logic) Logic On Words)

My question here is, in MSO, how come one can still use 2-ary relations, such as $S(x,y)$ (as well as $\mathcal{R}((e_i, t_i), (e_j, t_j))$ from the first question), since I thought MSO is supposed to use only 1-ary relations, i.e. sets?

I think I might have found the answer myself, but I would like to verify : is this allowed because one does not quantify over these 2-ary relations?


texts: Why $L=\{Wa^nb^mW^R\mid\:W\in\{a,b\}^+,n>m,m>0\:\}$ is context free?

texts:
Please help me, why the following language is context free?

$L=\{Wa^nb^mW^R\mid\:W\in\{a,b\}^+,n>m,m>0\:\}$


texts:
Say I have a set of numbers, for example {1, 2, 3, 4, 5}. Is there an algorithm that allows these numbers to be put into a consensus ordering based on a ranked vote? For example, if 3 people vote and their votes are [1, 2, 3, 4, 5], [2, 1, 3, 4, 5], and [1, 2, 3, 5, 4], then the consensus ordering would be [1, 2, 3, 4, 5]. Ideally the algorithm would support votes of partial orderings as well, such as [2, 5, 4].

I'm pretty sure I can extend the ranked voting system to produce a complete ordering of the "candidates," but I'm wondering if there's already an algorithm to do this.


texts: $L$ is a context free language so prefix$(L)$ is also context free language

texts: In case $L$ is context free language. $L_1 \setminus L_2 = \{x\in \Sigma ^* : \exists y\in L_2$ s.t $xy\in L_1 \}$ when $L_2$ is regular, is a context free language, thus using $L_1 = L$ ,$L_2 = \Sigma ^*$ one conclude that prefix$(L)$ is context free. However I wish to build a grammar for prefix$(L)$. My attempt so far was as follow: $L$ has a Chomsky's normal form grammar, $(N,T,S,P)$ so I defined the grammar $(N\cup N' , T, S, P\cup P')$ when $N' = \{A' : A\in A\}$ ,$P' = P\cup \{A\rightarrow BC' : A\rightarrow BC \in P \} \cup \{A' \rightarrow t : t\in T, A\rightarrow t \in P\} \cup \{A' \rightarrow \varepsilon\} $ my idea was that the non-tagged terms will be fully producted as in the usual grammar and the tagged terms might product a terminal or an $\varepsilon$. Yet I didn't succeed to prove it's a correct grammar for prefix$(L)$.


texts: Complexity of the V-opt heuristic Traveling Salesman algorithm

texts:
The paragraph on V-opt heuristic TSP algorithms at this site mentions a very effective algorithm due to Lin-Kernigham-Johnson. That page says:

  For many years Lin–Kernighan–Johnson had identified optimal solutions for all TSPs where an optimal solution was known and had identified the best known solutions for all other TSPs on which the method had been tried.

Impressive, so what is the complexity of that algorithm? Does the algorithm often work faster than predicted  based on theoretical complexity (if yes, how much)? Is that algorithm used most often in software that solves the TSP?


texts: Finding a target vector through applications of a binary operator

texts:
Let $\mathbb{X} = \mathbb{N} \cap [0, 255]$. I am given three vectors in $\mathbb{X}^3$ which I will denote by $v_i = [x_i, y_i, z_i]^T$ for $i \in \{1, 2, 3\}$. Now we have a binary operator $\bigoplus$ defined by $w = u \bigoplus v = \lfloor0.9 \cdot u\rfloor + \lfloor0.1 \cdot v\rfloor$, where $u$ and $v$ are in $\mathbb{X}^3$. Given a target vector $t \in \mathbb{X}^3$, the goal is to find a sequence of applications of $\bigoplus$ starting only with vectors $v_1, v_2, v_3$ that yield $t$. We are also given a promise that such a sequence of applications exists. How quickly can I find this sequence? It is worth noting that $\bigoplus$ is non-commutative and closed on $\mathbb{X}^3$. In my case, I am given specific values for $v_1, v_2, v_3,$ and $t$:
$$\begin{align*}v_1 &=[150, 0, 255] \\ v_2 &= [255, 150, 0] \\ v_3 &= [0, 255, 150] \\ t &= [62, 63, 184]\end{align*}$$

The obvious thing to try was a memoization / search approach where we keep a data-structure containing each vector seen so far (initially containing only $v_1, v_2, v_3$) and recursively apply the operator on each pair of vectors stored in my data-structure until the target is found. However this appears to be much to time consuming as the number of possibilities grow super quickly. Is there any better approach that one might try? It doesn't help that there appears to be little structure - For example, starting with our three vectors, there appears to be many combinations that we cannot even form.

I am also interested in knowing what happens if we are not given the promise that $t$ can be obtained from a series of applications of $\bigoplus$ on our three vectors. If we are not given such a promise, is there any easy way to at least determine if such a sequence exists (even though finding it might be difficult)?


texts: Kruskal naive implementation: how to use DFS to detect cycle in MST plus next edge?

texts:
Most discussion of naive (without Union-Find) implementations of Kruskal's algorithm for finding the minimal spanning tree that I see has a handwavy bit: "just use DFS to detect if there is a cycle" and then moves on to more optimised approaches.
I like to understand problems so I'm not interested in just skipping to the union find implementation, but I am struggling with some implementation details:
At each iteration I need to consult the edges from all of the nodes in my MST and find the minimum edge that ends in the unvisited notes, then check if there is a cycle.
To use DFS do I now need a third data structure (graph of MST + new edge) to send to my cycle_detect routine?

it seems like constructing this will be expensive because I'll have to go through my nodes in MST and only copy edges that are in the tree
at other stages of the algorithm I do need to consider edges that are not in the MST, so I can't work with only the MST edges throughout

This is enough to make myself think that I'm missing something about this. Perhaps the problem is my implementation of the rest of Kruskal's algorithm.


texts: I've read that a program can crash if it tries to access addresses with no memory allocated. But, how is it possible that an address has no memory allocated? When does it happen?


texts: How to compare n number of m-dimensional points among one another with minimum time complexity?

texts:
Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all points among one another based on their values in corresponding dimensions ? Aim is to have minimum time complexity . (Practically n >> m ). The mentioned comparison is carried out to check whether points are mutually non-dominated or not. Example :

A(4,1) and B(5,6) -> B dominates A since (5>4) and (6>1) . Therefore, A and B are not mutually non-dominated.
C(4,1) and D(2,3) -> D doesn't dominate C ,since (3>1) but (2<4) . Similarly C also doesn't dominate D ,since (4>2) but (1<3) . Therefore, C and D are mutually non-dominated.

(Note : In general, if (X>=Y) -> X dominates Y )

Goal is to check for non-dominance among all possible combinations of points from the given set of points with minimum time complexity . With four points A, B, C, D possible combinations are AB, AC, AD, BC, BD, CD . If ALL of these six combinations are mutually non-dominated , then it can be concluded that given set of points are mutually non-dominated, else dominated.

Input : Set of points, Task : Check for non-dominance among all possible combination of points from the given set of points , Output : If ALL combinations are mutually non-dominated , print ('set of points are mutually non-dominated') . Else print ('set of points are not mutually non-dominated') .

I have taken a 2-D array for this purpose . For n points which are m-dimensional , I have used a (n * m) matrix and compared each row with every other row to check for non-dominance among rows. Suppose if points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4) , then matrix is : x[4][4] = { {4,1,1,1}, {3,2,1,1}, {2,3,3,3}, {1,4,4,4} } . Here the time complexity is : O(m * n * n).

(Note :In this method , each row of matrix is representing one point )

Is there any better approach which results lesser time complexity ?


texts: Constructing a Turing Machine with Lambda Calculus

texts:
I'm interested in the implementation of a Turing Machine (deterministic) in Lambda Calculus.
How should I proceed to do this?
I am not sure on how to start since I must represent the state and infinite tape somehow.

I hope my question makes sense.
Thanks in advance.


texts: Use the pumping lemma to prove that the following language is not context free

texts:
Can anyone help with the following problem ?

Let $B = \{ a^{n}b^{m}c^{m}d^{2n} | n,m ≥ 0 \}$, use the pumping lemma to prove B is not context-free

Thanks in advance.


texts: Why does Python allow stand-alone expressions?

texts:
In Python, this is a valid program
def PrintWorld():
    print('World')

print('Hello')
0
'beautiful'
True
None
0 < 0
3, 3
lambda c:3
PrintWorld()

All it does is print 'Hello World' on two lines. The expressions are 0, 'beautiful', True, None, 0 < 0, 3, 3, and lambda c:3 are ignored and I'm wondering why.
I realize that this behavior allows Python to treat the function call PrintWorld() like any expression: It is an expression with value None in the course of whose evaluation the function is called. In a sense, this means that both 'beautiful', PrintWorld(), and a hypothetical expression with side effects like PrintWorld() is None could be treated the same on some level.
I also realize that this is related to interactive mode: When you run the Python interactively, giving only a stand-alone expression will result in its value being printed.
Still, why should non-interactive mode accept these expressions (except function calls)? In my eyes they open up the possibility for pointless code without offering anything in return.
And, as a follow-up: If you do allow these stand-alone expressions, why have comments or a pass statement in the language when you could just use a stand-alone expression instead?  Sure, "explicit is better than implicit", but it's also valuable to keep the language small.
As research I googled and searched stack overflow and CS stack exchange. I also looked into the Python language definition.


texts: Allocation of many students to many schools based on capacity

texts:
Say I have a set of schools coordinates (S). I also have a set of neighborhoods centroid coordinates (N).

I know how many kids are in each neighborhood, and they are categorized as either primary, middle or high school. So, in other words,

N = [(locationN1, primary:3, middle:10, high:4), (locationN2, primary:10, middle:17, high:7), ...]

I know how many spots are available in each school, the format being:

S = [(locationS1, primary:20, middle:5, high:2), (locationS2, primary:12, middle:7, high:8), ...]

My goal is to match as many students as possible to a school within a certain radius. It is possible (extremely likely) that in my calculations, some students will be school-less.

What I want: identify which neighborhood have school-less children and how many.

My current plan:

List all the pairings and corresponding distances between schools and neighborhood, within a given radius
Order by distance from lowest to highest
Give priority based on distance
Loop over the neighborhood in order of appearance (each neighborhood can appear several times linked to a given school within defined radius)
Fill corresponding school with children from neighborhood
Remove taken spots from the school capacity
Move to the next neighborhood-school pairing, ...

As an example:

Say you obtain the following ordering:

Order = [(neighborhood_2, school_7, distance1), (neighborhood_5, school_2, distance2), (neighborhood_2, school_2, distance3), (neighborhood_2, school_3, distance4) ...]

Then, school_7 receives children from neighborhood_2. Not all children from neighborhood_2 can be taken in at school_7.

Then, school_2 receives students from neighborhood_5. Now, assume that school_2 is full for middle school capacity.

Then, neighborhood_2 still has students to dispatch, and so tries to send them to school_2. Primary and high school, no problem, they are now all dispatched. But middle school is full.

Then we move on to the next pairing, and school_3 gets the remaining middle school students from neighborhood_2. Note that if distance4 had been higher than the limit radius, these middle school students would have been classified as school-less since no other pairings are available.

Additionally, if neighborhood_4 is oit of the limit radius for any school, all its children are considered school-less.

1) Is my algorithm correct?

2) What is the name of this exact problem? I've come across many to many point matching, capacitated allocation problems, or the "validation" part of facility location problem, but not this particular variant for some reason (likely poor searching skills)

3) How can I make this efficient, or is it pretty reasonable this way? (efficiency is not my primary concern, but easy fixes are welcome)

4) Do I have other options besides distance sorting? Technically, in my case, distance doesn't matter much to give priority, it's more of a random (or should I say fair) allocation based on for example time of received application (unknown data). So my method will show likely 100% allocation for a neighborhood very close to a school amd a bunch of school-less kids in farrher neighborhoods, yet that may not be (is not) true in real life.


texts: Minimum weight Hamiltonian path on a weighted (0 and 1) tournament graph

texts:
Suppose we have a weighted tournament graph. (A directed graph in which every pair of distinct vertices is connected by a single directed edge.)

The weights are constrained to be 0 and 1.

I know that every tournament contains atleast one hamiltonian path and can be found in time complexity $O(n^2)$.

However, I have two questions:

a) Is there a way to find the minimum weight hamiltonian path if we know that all weights are constrained to be either 0 or 1?

b) Is there an efficient algorithm to find ALL hamiltonian paths in a tournament graph?? This would solve a) automatically if true.


texts:
I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is same as $L_1$.

I thought so far that I can describe $L_2$ with a Turing machine. So I can next find the intersection Turing machine of both.

I do not know what to do about the last part of the problem.  Maybe I can say that $L_2$ is decidable (because it is regular) and $L_1 \cap L_2$ is a subset of that. So it is also decidable.

I am not sure whether my approach is correct  or not. Please help me.


texts: As a Teacher: Choosing a suitable programming language

texts:
I'm not sure if it's the right place for this question. Sorry if going a bit off-topic.

Choosing a suitable Language for the first programming course is one of the most important things that every related teacher/lecturer should bear in mind; especially if the students are young or having a limited math knowledge.

I'm currently teaching a group of highly enthusiastic young people (about 16 to 17 years old) with a medium knowledge of math. They're attending High School at 10th grade class right now. I'm going to start teaching a programming language for the upcoming semester.

They're a group of handpicked students throughout the city with a extraordinary level of creativity and diligence, so i see that working with a real programming language would not be a hard task for them. So, choosing simple graphical and drag'n'drop solutions like Turtle Art, Scratch, and Tynker are not considered as options.

There are a few factors that should be checked before making a choice:

Simplicity: Most of them probably have not experienced any kind of real coding action before.
Simplicity, Again: One of the main ideas is teaching how to think algorithmic. Having a sophisticated or hardly-syntaxed language will divert them out of the path.
Generality: It's better that the language not be designed for special development cases. Take PHP and MATLAB as examples which are respectively designed for Web Development and Calculation/Modeling.
Minimum Objective stuff: No forced OO programming (like Java). Or at least with the minimum dependency to OO concepts.
Platform: It's important to have Windows as a supported dev environment, as neary all of them are on Windows.
Easy to Set-up: It's better to have a straightforward way of setting up the dev environment.
Industry preference: Not a serious problem. But it should be at least a currently-active language allowing students to reach nearly-real dev experiences.
Hardware Portability: It's important (but not required) that the language be flexible enough to be used on Hardware programming. (I'm not speaking of Hardware Description languages like Verilog and VHDL.) The aim is programming for more simple processor-based hardware like AVR Microprocessors or Raspberry Pi GPIO interface.

I want to know that

is there any other factors that i'm missing?
And, what languages do you suggest as choices?


texts: Is there an algorithm to minimize working set during a topological traversal?

texts:
I have a dependency graph of tasks, which forms a DAG. I'm looking for an algorithm to calculate the optimal topological traverse to minimize the "working set". Specifically, I define the current working set as the set of nodes which have been visited, and which have at least one outgoing edge which is untraversed.

Even more useful would be an algorithm to calculate the optimal topological traversal which minimizes the number of cache evictions, given a fixed size cache for the working set.

Is there an algorithm to calculate this topological traversal? I can do it greedily from the topological ordering, but suspect that's suboptimal.


texts: Why are binary numbers sometimes written with one or more leading zeros that don't change the number (quantity) represented?

texts: Binary numbers like '0110', or '00100101' are seen very often in all contexts. What are the leading (left hand side) zeroes for? Why did the writer not write '110' and '100101', respectively?


texts: Is relative regularity distinct from regularity?

texts:
Let $L$ and $G$ be languages over a finite alphabet $\Sigma$.
$L$ is regular relative to $G$ if $L \subseteq G$ and there is a finite automaton that accepts every input in $L$, and rejects every input in $G \setminus L$; the behaviour of the automaton on inputs in $\Sigma^{*}\setminus G$ is not specified.
Here are some simple facts about relative regularity.

If $G$ is regular, then so is any $L$ that is regular relative to $G$.
If $L$ is regular then it is also regular relative to any $G \subseteq \Sigma^{*}$ in which it is contained.
If $L \subseteq G$ and $G \setminus L$ is regular then $L$ is regular relative to $G$.
It is possible that $L$ is regular and regular relative to $G$, but $G$ is not regular.  (Let $\Sigma = \{0,1\}$, $L = \emptyset$ and take $G$ to be some non-regular language such as the palindromes.)
It is possible that $L$ and $G$ are not regular but $L$ is regular relative to $G$.  (Just take $G=L$.)
$L$ is regular relative to $G$ iff $L \subseteq G$ and there is some language $S \subseteq \Sigma^{*}\setminus G$ such that $L \cup S$ is regular.

  If $L$ is regular relative to some $G \subseteq \Sigma^{*}$, and $G \setminus L$ is not a regular language, is $L$ always regular?

That last fact suggests that the answer should be no, but I can't think of a counterexample.

If this is a standard exercise or the concept has a name then I would appreciate a pointer.


texts: Offline scheduling fully determined arbitrary jobs in multiprocessor setting

texts:
Let $\mathcal{J} = \{J_1,...,J_n\}$ be a set of jobs with each $J_i = [a_i,r_i,d_i]$ where the job becomes available at its arrival time $a_i$, requires $r_i$ execution time and needs to be finished at its deadline $d_i$ (hard real time). Assume we have $m$ processors available.

Given the above, what scheduling algorithms are available to deal with this? I'm aware of a publication by Horn that gives a solution using flows; since that was in 1974 and flows are comparatively slow, I tried to find faster algorithms for this setting, but couldn't find any. The book on scheduling by Pinedo suggested in this answer on CS.SE mentions the setting and that it can be solved using flows, but unfortunately nothing else. Apart from these two sources, I have been unsuccessful.

Are there known algorithms to solve the above problem that are faster than flow networks on $\Theta(n)$ nodes?


texts: Writing a program to find polynomial $f(x)$ from $f(1)$ and $f(f(1))$

texts:
Let $f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n$, where $a_i\ge0$ and $a_i$ is integer.

Given $f(1)=p$ and $f(f(1))=q$, we have to find $a_0$, $a_1$, $a_2$, $a_3$, $\dots$, $a_n$, where such $f(x)$ exists. Or we have to confirm if such $f(x)$ exists or if the polynomial is ambiguous e.g. for $p=1$ and $q=2$, no such $f(x)$ exists but for $p=1$ and $q=1$, $f(x)=1$, $f(x)=x^2$ both can be solution.

I have to write a program to do that. What should be my procedure?


texts:
You and a friend lost each other on the line to a concert, and neither is sure which of you is further ahead. Formally, each is at some integer coordinate and may only walk towards a higher coordinate or stay in place.

Assuming you and your friend are following the exact same algorithm (and no, you may not say "if (name=="R B") do something :) ), and the initial distance between the two of you was $x$ (which is not known to you).

  What is the algorithm which minimizes the expected walking distance till you and your friend meet?

You may assume both your friend and yourself are moving in the same constant speed.

An example simple algorithm would be something like:

  At stage $n$ (starting from $0$):

  Walk $3^n$ steps to the right w.p. $\frac{1}{2}$ or wait $3^n$ time units otherwise.

To see this algorithm makes the friends meet with probability 1 consider what happens at stage $(\log_3 x+1)$. Even if the friend that was $x$ step ahead always walked and the other always stayed in place, the distance between the two would be:
$$x+1+3+9+\ldots+3^{\log_3 x}=2x+\frac{x-1}{2}\leq 3x$$

Therefore, at the $\log_3 x+1$ iteration, the friend which chooses to walk will cover distance of $3^{\log_3 x+1}=3x$, hence with probability $\frac{1}{4}$, the friend which is behind will catch up and they will meet.

A simple optimization (to reduce walking distance) would be, instead of walking $3^x$ steps, walking $c^x$ steps, where $c$ is given by:
$$2+\frac{1}{c-1}=c$$

Hence the optimal $c$ for this algorithm is $c=\frac{3+\sqrt 5}{2}\approx 2.618$

Unfortunately, while this algorithm guarantees that the friends will meet with probability 1, the expected walking distance is infinite, which is something I'd like to avoid if possible.

  Is there a more efficient algorithm?


texts:
What would be the fastest way of doing this (from an algorithmic perspective, as well as a practical matter)?

I was thinking something along the following lines.

I could add to the end of an array and then use bubblesort as it has a best case (totally sorted array at start) that is close to this, and has linear running time (in the best case).

On the other hand, if I know that I start out with a sorted array, I can use a binary search to find out the insertion point for a given element.

My hunch is that the second way is nearly optimal, but curious to see what is out there.

How can this best be done?


texts:
In the exercise I have a 32 bit processor with a 2-way set associative cache. I have 32 bit addresses: 31-14 tag, 13-5 index, 4-0 offset.
Calculate:
1) Cache line size in number of words (1 word = 4 bytes)
2) Total cache size in bits

In the presence of the following sequence of accesses in memory, considering the initially empty cache, indicate for each access if it is hit, miss, or replace:
17920 17948 149024 83488 17952 148998 149012 17964 148648 17848

I think answer at the first part should be:
1) 2^5 = 32byte --> 32/4 = 8words
2) 32byte = 256bit --> size = 256 * (4096 + 18 + 1)

Is it correct? And I'm not sure on how to complete the second part of the exercise


texts: Graph theory: determining maximum number of edges

texts: Based on the question below, can someone please explain to me the reasoning behind why the maximum number of edge is 5/2|V|? I don't find the particular reasoning in the solution to be that helpful for why the maximum number is 5/2|V|.


texts: Shortest travelling cost if we have bunch of points in 2D plane

texts:
I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane and any two of them were Source and Destination. I was asked to calculate the least cost to travel all the points starting from the source and ending on Destination point. The cost to travel between any two points is |x1 - x2| + |y1 - y2|.

So, what I thought of doing was construct a cost matrix and apply Dijkstra since I thought constructing the shortest path tree must be the solution.

But I couldn't think on how to construct this cost matrix. What is the best approach for this?


texts: What would a language look like in which precise GC was implementable as a library?

texts:
Suppose you have some programming language with manual memory management. What features does this language need to have in order to be able to implement precise garbage collection as a library, and not as a fundamental language construct?

By a precise GC I mean one where only pointers to the heap are traversed to ascertain which variables are or are not live.

Some additional considerations:

C and C++ have the Boehm garbage collector, but I don't count this since it's not a precise GC. The Boehm collector assumes that anything on the stack that could be a pointer, based purely on memory alignment requirements, is a pointer. For example, any integer k such that (k % 4) == 0 looks at a bit level like a pointer, since pointers must be 4-byte aligned.
magpie transforms existing C code to use a precise garbage collector. The generated C code has a lot of stubs for garbage collection, i.e. stuff for registering any stack pointers into the heap with the collector. I don't count this because no one could ever be expected to write code that way; it's more of a compilation target for other languages.

I imagine that such a language would need to have:

Macros or some form of metaprogramming, for encapsulating all of the extra code needed to do things like register GC roots.
Some reflective mechanism that allows you to inspect structs or unions; you need to determine which members are pointers.
Some reflective mechanism that allows you to examine the stack frame layout. This sounds a lot harder than 2.

I hope this isn't too vague or opinion-based but I've been wondering about it for a while.


texts: Are these production rules for a formal grammar?

texts:
I have a question on if production rules of a formal grammar are being specified correctly.  Wikipedia defines the syntax of grammars as the following finite set of production rules, where it states each rule has the form:
$(\Sigma \cup N)^{*}N(\Sigma \cup N)^{*} \implies (\Sigma \cup N)^{*}$
How can each rule have this form when each rule is a subset of the above arguments to the implication symbol?  Should quantification and the $\in$ symbol be used to specify each rule?  Thanks


texts: converting for loop into mathematical notation

texts:
I am a bit confused with a problem that I am having.I am trying to do an amoritized analysis and I am able to represent the function that I want to use using code. I coded the function as follows:

sum = 1;
for(i = 1;i < n;i++){
    sum = ceil(1.5 * sum);
}

The code is suppose to represent $\lceil....\lceil\lceil\lceil1.5 \times 1\rceil\times 1.5\rceil\times1.5\rceil...\times1.5\rceil$ and is suppose to keep going $n$ times. How would I represent this mathematically.

Thanks.

Edit: So I am trying to do an amoritized analysis on an array that grows by a factor of 1.5. So what I am trying to do is mathematically write what the code does.

What the code is suppose to represent is it is doing $\lceil...\lceil\lceil 1.5 \times 1\rceil \times 1.5\rceil...\times1.5\rceil$ The ... is suppose to represent the function multiplying by 1.5 $n$ times.

Also as an example if you post the following into desmos it will give you ceil(...ceil(ceil(1.5 * 1))...) 8 times.

\operatorname{ceil}\left(\operatorname{ceil}\left(\operatorname{ceil}\left(\operatorname{ceil}\left(1\cdot1.5\right)\cdot1.5\right)\cdot1.5\right)\cdot1.5\right)

I want to be able to have the behaviour of what is represented above mathematically so I can use it in an analysis. If anything is unclear again please comment.


texts: Changing binary counter structure such that increament and decreament methods will work in O(1) amortized

texts:
Just trying to solve the second part of a question with two parts.
First part was to prove that you can't add decrement method to a standart binary counter without hurting the amortized complexity and change it to be more than O(1).
This part i have done with no problems.
Solution in a nutshell - after some method you are going to be in a dead end when you have a number like this: 100...0 so when you decrease by 1 you will get 0111...1 and then when you will increase by 1 you will get again 100...0 and those decreasment and increament are cost n and you will do them m times so its not O(1) amortized.
The second part, is to tell how you can change the structure such that it will support decreament and increase methods and the amortized complexity will stay O(1).
I never saw something like this and it really confusing me what they want me to do.
Their solution is that anytime you want to change 0 to 1 you change it to minus 1.
Problem is, i can't understand what they meant, i mean, on which stracture you are inserting this change and how does it improved the complexity (if you change to -1 you stil going to the same dead end).


texts: Why polynomial time is called "efficient"?

texts:
Why in computer science any complexity which is at most polynomial is considered efficient?

For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms that run in time, say, $n^{80}$, but the first is considered inefficient while the latter is efficient. Where's the logic?!

(a) Assume, for instance, the number of atoms in the universe is approximately $10^{80}$.


texts:
The city council would like to place trash bins around the city and has a list of suitable spots (street crossroads, supermarkets etc.) but the number of these spots is greater than the number of available bins. The council's goal is to place the limited number of bins so that the distance from each house to a bin is at most 100 m. Prove that the problem k containers are sufficient is NP-hard using reduction from a known NP-hard problem.

I came up with vertex cover (could we alternatively use dominating set?). We then need to transform an instance of vertex cover $(V, E, k)$ to an instance of this problem. It's not clear to me how. This is how I thought I would represent the k containers are sufficient problem by a graph:

My first step would be to create a graph where the set of nodes contains both the spots for containers and all the houses. I would then connect each spot node with all the house nodes that it is close enough to (100 m). This seems quite close to vertex cover except that there are 2 types of nodes:

The house nodes cannot be used as a part of the vertex cover set since bins cannot be placed in front of houses but they need to be covered by the vertex cover set.
The bin spots can be used as a part of the vertex cover set but do need to be covered at all by it.

How could I deal with this in the reduction? I thought about using some vertex to edge transformation to represent these relationships but came up short.


texts:
I have an online homework assignment that is asking me for the tag and index in a direct-mapped cache, for a series of memory addresses. The cache is specified to have 16 one word blocks.

One of the first memory addresses given is 134.

My attempt goes as follows:

134 = 10000110

16 = 2^4

so, I get that:

index  = 10000110 mod 16 = 0110

and

tag = 1000 (the leftover part)

Apparently this is wrong. Could someone please help me to see why?


texts: Is there a name for complement of recursively enumerable set?

texts:
If there is a recursive function
$$
f(x) =
\begin{cases}
1 & \text{if $x \notin A$}\\
\text{undefined} & \text{if $x \in A$}\\
\end{cases}
$$

Is there a special name for the class of sets like $A$?