texts:
A decision problem $C$ is $NP$-complete if $C$ is in $NP$, and every problem in $NP$ is reducible to $C$ in polynomial time.

Reduction means transforming an instance of one problem $A$ to an instance of another problem $B$, and by using an algorithm that solves $B$ we can obtain the solution to $A$ for our original instance.

Is there any relationship between the size of instance before and after reduction? If for example the algorithm solving $A$ is $O(n^2)$ and our instance of $A$ of size $n$, what can we say about the instance size after reducing it to $B$, whose algorithm is $O(2^n)$ (the complexity of algorithms actually doesn't matter). Is it $n$ as well? Or maybe it is a polynomial of $n$?

The question is if the fact that a problem $A$ can be reduced to $B$ in polynomial time tells us anything about the size of the resulting instance (of problem $B$) with respect to the size of initial instance of $A$.

Why? It is known that

  If we had a polynomial algorithm for an $NP$-complete problem we could
  solve any other $NP$ problem in polynomial time

right? Because we just reduce $NP$ problem to $NP$-complete problem in polynomial time and solve it in polynomial time.

Let's say problem $A$ is $NP$ and problem $B$ is $NP$-complete. I've found an algorithm for $B$ that is $O(n)$ (polynomial). And let's say the size of our $A$ instance is $k$.  If I reduced it to $B$ in polynomial time and got an instance of $B$ of size $n=2^k$, then the total time of solving it wouldn't be polynomial. So certainly the polynomial time reduction can't give an instance of size $2^k$, because if it could, then the quote above wouldn't be true.


texts:
Is it not always possible to represent a Finite State Machine (FSM) by a Boolean dynamical system?

A Boolean dynamical system is defined by a Boolean map $F\colon B_{0}^n\to B_{0}^n$ (where $B_{0}$ is the-two element Boolean algebra $\{0,1\}$ with operations of $\lor$ (OR), $\land$ (AND) and $\neg$ (NOT)) as

$$x(k+1)=F(x(k)),$$

which is the state update map of the FSM after representing the state space of an FSM as a subset of $B_{0}^n$.


texts: So, this is kind of a long shot, but does anybody here familiar with cellular automata know what type this is? In the game, it starts as a flat pink/red and then becomes this over the course of a few seconds, and when like this it kinda just vibrates. I'm not sure what type or style of cellular automata this is though, other than the game itself is in the retro 8 bit style overall. If I'm asking this in the wrong place, I'm sorry. Looking forward to any answers!


texts: Why proving programs correctness doesn't have the same importance as algorithms analysis or the theory of computation in practice?

texts: What are the major causes that makes "Proving Programs correct", not a widely attractive subject? though from it's name, and from what we know from other disciplines (like mathematics) it looks like it should be on the top of the "must know list". And by the way I'm talking about "the real world", in practice.


texts:
I'm trying to learn buddy allocation and whilst I think I understand the basics of it, there is one problem exercise with which I'm struggling with.

So I have an 8K block and I'm using buddy allocation trying to always allocate to the leftmost free memory area.. and I need to allocate a 5K memory block.

Do I split the 4K block into two 2K blocks, and take (from the left) the 1k, 2k, 2k blocks, or do I split the middle 2k block into two 1k blocks and take the 4k and the first 1k block from the right? Or do i simply take the 2k and 4k blocks that I have now?

Or is this type of allocation simply not possible if I need to make use of the whole 8k block (since the first 1k block is being used)?


texts: Why do computers use binary, instead of ternary, or some other logic system?

texts:
In binary a unit (bit), can store 2 separate values.

if you have ternary, then a unit can store 3 separate values.

why then don't computers use higher bases, for example in ternary you could have 3 different voltages, and even if transistors got a little bigger, wouldn't it still be more efficient?


texts:
There is Lagrange's four-square theorem, which statea that

  Given an integer $N$, we can write $N$ as a sum of four squares
  $A^2+B^2+C^2+D^2=N$.

How can I find a valid solution with time complexity of $O(1)$ or $O(\sqrt N)$? I only have to find one solution.

Here is my $O(1)$ algorithm:

while(count!=4){
     solution = sqrt(N)
     print solution
     N-= solution*solution
     count++
}

But it does not works for all $N$, for example it fails for $N=23$. Is there any other solution?


texts:
I'm having trouble understanding the difference between the Held-Karp $O(n^2 2^n)$ solution and the cutting-plane method pioneered by Dantzig, Fulkerson and Johnson.
Held-Karp is $O(n^2 2^n)$ which result is computational times that are excessive. To quote Cook:

This is disappointing since for $n = 30$ the Held-Karp guarantee
is already quite a large number, and for $n = 100$ it is an impossibly
large number to handle with today's computing platforms.
http://www.math.uwaterloo.ca/tsp/methods/progress/progress.htm

Yet we see, empirically, that solutions can be had in seconds for reasonable $n$'s.
I had initially thought that Dantzig et al. solutions were just "good enough" but Applegate et al write:

The cutting-plane method is the core of nearly all successful
approaches proposed to date for obtaining provably optimal solutions
to the TSP, and it remains the only known technique for solving
instances having more than several hundred cities
http://www.math.uwaterloo.ca/~bico/papers/dfj_mathprog.pdf

Why is one solution different from the other? Why is Held-Karp the best possible solution but Dantzig et al is also "provably optimal" and considerably faster? Given that Dantzig does not seem to have a subexponential time upper bound, why is it so much faster in practice?
In particular, I'm looking for an English explanation, not a math one. I'd like to explain this to my friends.
See Also:
https://www.cs.uleth.ca/~benkoczi/OR/read/tsp-dantzig-fulkerson-johnson-54.pdf


texts: How does one program crashing not crash the entire system?

texts:
In Windows, if you write a random assembly program that has a random jump to an address that doesn't exist, the program crashes and Windows says something went wrong with the program.

Since each computer system is essentially a constant execution of assembly, how does the one program crashing not cause the entire system to crash with it?


texts: Measure the degree of differences between web pages

texts:
I'd like to measure how different two HTML files are from each other.

I refer to the following scenario:

User A visits a website, let's call the website example.com
User A shares the website with User B
User B visits the shared website
User A and User B have installed an add-on that each sends the visited web pages as HTML files to a server C.
The server C should evaluate to what extent the website differs from User A and User B.

I would like to measure the degree of individualization of a website onto the user.

Some websites adapt to each user very strongly, for example the Netflix homepage. Other pages look the same for every user, for example the Terms and Conditions page of Netflix.

My questions are now:

Are there any research or algorithms for this problem?
Which algorithms can be used for this kind of problem?

My thoughts:

http://www.php.net/manual/en/function.similar-text.php
Levenshtein distance
Jaro-Winkler distance
Anything with AI


texts: Turing machines with a finite number of states

texts:
In a class on Turing machines, the lecturer said that the language for a machine with 100 states is both recognizable and decidable.

How can we infer this just from the number of states in the machine?


texts: Recurrence relations and the Master Theorem

texts:
Although it might be a bit of newbie question, my question is, How can I apply the Master theorem to the following relation:
T(n) = 99T(n/100) + log(n!)

I'm trying to learn about algorithms, but I'm not really comfortable with logarithms(haven't studied in school yet), so I'd really appreciate a bit of help.
Thanks.


texts: How many operations at maximum needed to compute powering of a number, i.e. $N^k$?

texts:
Suppose $N$ is $L$-bit long and $k$ is also $L$-bit long.

How to show that it takes at most O$(L^2)$ operations to compute it.

For example $N = 1010$ and $k = 10$. Then $N^k = 6^2 = 100100$. But I am not familiar with how $100100$ comes up without going back to decimal and using the fact that $6*6 = 36$. Therefore, I also find it hard to realize that it takes at most O$(L^2)$ operations to compute the powering of a number.


texts: Gaussian Elimination Minimum Cost Circulation

texts:
In Eva Tardos Strongly polynomial Minimum cost Circulation Algorithm , Step 1 states projecting d, the cost function on a subspace X where flow is 0 for all tight Edges. Also we define an incidence matrix A for all non-tight edges with values{ 1,-1,0} accordingly.
later it is proved that the projection is d(E-T(G))+πA and since it is orthogonal to A we get the following equation:

[d(E-T(G))+πA]A^Transpose=0

How do I compute π using Gaussian Elimination?


texts: Is there a graph product that is multiplicative in independence number?

texts:
I know that Stable set cannot be approximated to constant factor. I saw a simple proof using OR product sometime back. I am unable to recall it. If anyone here knows what I am talking about could help fill my memory, that will be helpful.

Is there a graph product $\cdot$ such that $\alpha(G\cdot G)=\alpha(G)^2$ for all  graphs $G$ and $G\cdot G$ the product of $G$ with itself?

I only need an answer to inapproximability to constant factor and I believe there is a one step proof for this.

If we had such a product, then we have $\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)=\alpha(G)^k$. If $\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)$ can be approximated to constant factor $\sigma>0$, then $\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)=\sigma\hat\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)=\alpha(G)^k$ and since $0<\sqrt[k]{\sigma}<\sigma$, we can get an approximation of $\alpha(G)$ that is better than $\sigma$ by $\sqrt[k]{\sigma\hat\alpha(G\cdot G\cdot\cdots \cdot G\cdot G)}=\alpha(G)$.


texts: Big-O Time Complexity of nested for loops

texts:
My gut tells me the time-complexity of the following code is simply O(n^2).  However, I'm not convinced, thinking it could possibly be O(n^3):

cin >> n;
sum = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n * n; j++)
        sum++;

Can anyone provide a distinction, and why?

Thanks in advance.


texts: converting a triangulated surface to min-max form

texts:
Let $S$ is a triangulated surface, representing a graph of a function z(x,y) in 3D space. According to https://en.m.wikipedia.org/wiki/Piecewise_linear_function
every continuous piecewise linear function can be represented in min-max form $$f(\vec x)=\min_{\Sigma\in\Pi} \max_{(\vec a,b)\in\Sigma} \vec a \vec x+b$$
If anybody knows an algorithm for conversion of the surface from triangulated form to min-max form, please help!


texts: the problems that could exist if halting problem is solved

texts: What problems might exist if halting problem is solved. If there exist an oracle that can compute whether a given machine halts or not then what would be problems that could exists if such oracle is there


texts: What are the other language models of computation similar to lambda calculus?

texts: I hope this question makes sense, but I was wondering if there are other models of computation similar to lambda calculus that you can use to build up axiomatic mathematical and logical fundamentals like numbers, operators, arithmetic functions and such?


texts: All permutations of N numbers with at least K-different positions

texts:
I'm trying to generate all permutations of N numbers where any two permutations are different by at least K positions. I would just like a push in the right direction, the trivial method of memorizing every valid permutation and then just comparing at each step would be impractical for large values of N.

Example:

N=4, K=3

1 2 3 4 - good

1 2 4 3 - skip, only 2 positions differ from the first permutation

1 3 2 4 - skip, only 2 positions differ from the first permutation

1 3 4 2 - good

1 4 2 3 - good

1 4 3 2 - skip, only 2 positions differ from the last permutation

and so on

Any help is highly appreciated.
Thank you.


texts: What are the differences and relations between a type constructor and a type operator?

texts:
What are the definitions of a type constructor and a type operator?
What are their differences and relations?
I think a type operator is a function whose parameters are n types and return is a type. A type constructor also means the same thing.
I use them exchangeably. But some reply used type constructor when my question (I forgot where) used type operator.
In Types and Programming Languages by Pierce, the index says

  type constructors, see type operators

Ch 29 says informally that

  these type-level functions, collectively called type operators, more formally.

Is it correct that type operators/constructors are used only and exactly to create algebraic types, and algebraic types are created only and exactly by type operators/constructors?

Is Ref in Ref T a type operator/constructor? Is Ref T an algebraic type?

Thanks.


texts: How is this defined in an iterative style?

texts:
This is the so-called recursive style:

And this is the so-called iterative style:

It seems like it is defined recursively to me. The function doesn't hide the next call of the function defined in it at all.

(SICP 95)


texts:
I wrote a program to discover how height of the tree is relative to the number of elements in the tree (nodes).

On first test I filled array with 10-50-100-200...-1000 elements of random numbers from 0 to 32k~~ and checked their height and then second array with the same number of elements, however this time keys were picked randomly from 0-9, instead of 0-rand().

And I wonder if I have this right, is this possible height or im just getting some semi-random numbers. Would be grateful for checking that out. For now I don't know how to compare these scores and charts. The scores are very close, but the first array seems to have height slightly lower than second array.


texts:
I'm trying to determine the complexity of the following structure:

for (i = 1; i < n; i++)

for (j = 1; j < o; j++)

for (k = 1; k < p; k++)

print "Hello world!"

Normally, for a triple loop like this, I believe the complexity is O(n^3), but the undefined variables "o" and "p" are throwing a wrench in the works. I've done
some hunting around, and the best I can surmise is that it might be O(n * o * p), depending on what values are assigned to n, o and p. Thanks for taking a look!


texts: How to prove the following xor equation?

texts:
In a test paper, a question is given as :

Let, x1^x2^x3^x4 =0 where x1, x2, x3, x4 are Boolean variables,and ^ is the XOR operator.

Which one of the following must always be TRUE?
(A) x1x2x3x4 = 0
(B) x1x3+x2 = 0
(C)  x1'^x3' = x2'^x4'
(D) x1+x2+x3+x4 = 0

+ is OR and concatenation is AND operator.

Correct answer is C, which I guessed because when all booloean variables are 1, then, neither A,B, or D will hold,But what is the correct way to get to option C?


texts: How to do asynchronous programming with only global variables?

texts:
If a programming language only supports global variables, is it still possible to use asynchronicity, like callbacks, event-driven programming, other kinds of parallelisation?
How can it be done?


texts:
Current chess algorithms go about 1 or maybe 2 levels down a tree of possible paths depending on the player's move's and the opponent's moves. Let's say that we have the computing power to develop an algorithm that predicts all possible movements of the opponent in a chess game. An algorithm that has all the possible paths that opponent can take at any given moment depending on the players moves. Can there ever be a perfect chess algorithm that will never lose? Or maybe an algorithm that will always win?
I mean in theory someone who can predict all the possible moves must be able to find a way to defeat each and every one of them or simply choose a different path if a certain one will effeminately lead him to defeat.....

edit--
What my question really is. Let's say we have the computing power for a perfect algorithm that can play optimally. What happens when the opponent plays with the same optimal algorithm? That also will apply in all 2 player games with finite number (very large or not) of moves. Can there ever be an optimal algorithm that always wins?

Personal definition: An optimal algorithm is a perfect algorithm that always wins... (not one that never loses, but one that always wins


texts:
Given a sequence of N activity durations, the time P of pause between activities, and D, the length of a day (there are no breaks between days, only between activities in a day), what is the minimum sum of the cube loss across all days and how many days are required for the solution. The activities need to be scheduled in order, so the first day will have the first x activities, the second day will have the next y activities, and so on. Between activities that take place in the same day there is a pause time P.

Example:

N = 4

P = 2

D = 7

Activities durations : 3 2 2 5

In this example the minimum total cubed loss would be:

(7 - 3)^3 + (7 - 2 - 2)^3 + 0^3 = 65

The last day doesn't contribute to the total cubed loss (in total the activities are distributed in 3 days). Even if we could have added the second activity to the first day, the total cubed loss would be higher:

(7 - 3 - 2 - 2)^3 + (7 - 2)^3 + 0^3 = 125

I have tried an greedy algorithm but the solution is not optimal. I think the optimal solution can be obtained using a dynamic programming approach. How can I build the solution matrix?

I have tried building a matrix where row i contains the sums of i consecutive activity durations + i - 1 pauses. I am stuck with this approach on how should I traverse the matrix in order to get the optimal result.

Any help is appreciated.


texts: Regular string relations - proof of correctness

texts:
Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows:
$$
R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*
$$
$$
N(T) := Id(\Sigma^* \setminus (\Sigma^* \cdot dom(T) \cdot \Sigma^*)) \cup \{ \langle \epsilon, \epsilon \rangle \}
$$
$N(T)$ is the identity relation of the set of all words that don't contain an infix in $dom(T)$ including the pair $\langle \epsilon, \epsilon \rangle$.
The idea is the following - we have an input string $t \in \Sigma^*$ and $R^{obl}(T)(t)$ will result in the translation of the substrings of $t$ which $\in dom(T)$ via $Т$, and the ones $\notin dom(T)$ via identity.
Example 1: $T = \{ \langle ab, d \rangle, \langle bc, d \rangle \}$, the input text $t = babacbca$ is decomposed as $t = b \cdot ab \cdot ac \cdot bc \cdot a$ and the substrings $\{ b,ac,a \} \subseteq dom(N(T))$, whereas, $\{ab, bc\} \subseteq dom(T)$. So $R^{obl}(T)(t) = b \cdot d \cdot ac \cdot d \cdot a = bdacda$
Example 2: $T = \{ \langle ab, d \rangle, \langle bc, d \rangle \}, t = abcc$. This time we have two possible decompositions due to overlapping. $t = ab \cdot cc = a \cdot bc \cdot c$, therefore, two possible translations $\langle abcc, dcc \rangle \in R^{obl}(T), \langle abcc, adc \rangle \in R^{obl}(T)$.
My questions is - how do we formulate a proof of correctness for such a construction? That it indeed translates the words as described
A bit of a context. I've studying rewrite systems based on regular relations (implemented as finite-state transducers) and more specifically the papers "Regular Models of Phonological Rule Systems" by Kaplan & Kay (1994) and "Directed Replacement" by Karttunnen (1996). They construct complex rewrite relations by using only the regular set and relation algebra, however, the papers do not provide formal proofs that their method is correct. If anyone has experience in this field and can provide some guidance, I'll greatly appreciate it.


texts: Why are processes on the internet not required to use TCP or UDP?

texts:
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 5 (The Network layer), Page 455:
[Fifth, processes on the Internet are not required to use TCP or UDP. If a user on machine A decides to use some new transport protocol to talk to a user on machine B (for example, for a multimedia application), introduction of a NAT box will cause the application to fail because the NAT box will not be able to locate the TCP Source port correctly.]
My question is: in this context. what does "processes" mean? Is it a process of data exchange between routers? And why are processes on the internet not required to use TCP or UDP? Isn't it a part of IP protocol and thus it will be used on the internet?


texts: Theory of message complexity analysis of distributed systems

texts:
Inspired by this post, I thought it would be a good idea to ask an analogous question in the context of distributed systems -

While most of us are familiar with the notion of Time Complexity as a measure of efficiency of algorithms, In the world of distributed systems, another important measure of efficiency plays a preeminent role namely that of Message Complexity.

Specifically, when working in terms of the graph network model(i.e., algorithm instances executing on each node of a network pursuant of a network-level goal), it is the total number of bits of information that are cumulatively sent through each edge/connection of the system over the course of execution of the distributed system. My question is as follows:

What are the usual techniques applied to calculating/bounding the message complexity cost of distributed algorithms?
What is the generalised structure/theory behind these techniques?


texts:
How 2D Cellular Automata rules sequences works?
For example, in elementary cellular automata, when we look at the binary sequence of the rule number, we understand that first bit says if all neighbors are white, and the cell itself is white, the cell in next step is black or white ( depend on the value of the bit ).

But how should I analyze and interpret the binary sequence of rule number? How should I implement the 2D CA when I have the rule number, for example when we have rule number 22369621 with r = 2 ( 25 neighbors ) how can I understand the behavior of this 2D CA to implement that?


texts:
How to prove that BFS directed-graph traversal algorithm terminates?
(I copy the pseudocode from here) Input: A graph G and a root v of G.

  procedure BFS(G,v):
      create a queue Q
      enqueue v onto Q
      mark v
      while Q is not empty:
          t ← Q.dequeue()
          if t is what we are looking for:
              return t
          for all edges e in G.incidentEdges(t) do
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q


texts: Find the shortest path that goes through an even number of red edges

texts:
I'm looking for an algorithm for the problem:

"Given an undirected graph with positive weights on its edges and some of the edges are red and some are blue. Describe an algorithm that finds the shortest (lightest) path which includes an even number of red edges, that goes from S to any vertex v."

The solution I thought about was, why not take the original Graph G(V,E) and create (I'm not quite sure if I can say "given" though I think it is) a sub graph which will include only the red edges, let's say Red(V',E'), intersect those two, so now I will have a new graph say G' which includes only the red edges.

And on that graph I will use dijkstra algorithm in order to find the shortest path.

The problem is it can ofc make some edges un-reachable so it will return there's no such path, while there might be a path if added some blue edges. I'm not quite sure how to go around it in order to get the perfect solution.


texts: Database Theory - Does the dependency preservation and lossless join properties hold for every decomposition of a relation into 3NF?

texts:
I was reading Database Systems, 6th ed by Ramez Elmasri and Shamkant Navathe. In the textbook they make a claim (in Chapter 15, section 15.2 Properties of Relational Decompositions) which I quote below:

  Claim 1. It is always possible to find a dependency-preserving decomposition $D$ with respect to $F$ [$F$ is the set of FDs of a relation $R$] such that each relation $R_i$ in $D$ is in 3NF

I have a few questions regarding this.

Is it possible to have multiple (different) decompositions of a relation into 3NF, as the claim seems to imply?
Is it the case that every decomposition (assuming the answer to first is Yes) of a relation into 3NF is dependency preserving? If not, please provide an example where a decomposition into 3NF does not uphold the dependency preserving property. Also, what about lossless join property?

Thanks!


texts: Trying to find out how to deducing formulas in FCM algorithm

texts:
FCM algorithm or Fuzzy C-Means Algorithm is a clustering algorithm with a matrix with values between 0 to 1 to representing the membership function as membership function in K-means 0-1 approach.

When the distance function in FCM algorithm is the Euclidean distance, the objetive function to minimize is:

with constrains:

$$ \sum_{i=0}^{k-1} u_{ij} = 1 \ \forall j=1, \cdots, n$$

The authors of algorithm deduce:

With:

$n$ : # elements to clustering (data)
$\alpha$ : a constant
$k$ : # of centroids at beginning
$D_{\text{euc}}(x_i, \mu_j)$: euclidean distance of j-centroid to i-element of data
$u_{ij}$ element i-j of membership matrix $u\in M_{n\times k}$
$x_i$: vectors m-dimensional

If I would like to modify the function distance, how this change affects the outcomes of minimize ? (red dashed boxes).

To find out the how. I was trying to apply multiplier's Lagrange method to $J_\alpha$ with original conditions to deduce original formulas (red dashed boxes), without successful.


texts: Complexity of K-Colorful Coloring Problem for a Hypergraph

texts:
I searched a lot trying to find a reference for the complexity of K-colorful coloring problem for a hypergraph but I cannot find it. Please if anyone has a reference for the complexity of the problem let me know. I think it will be NP-Complete

Let H = (V, E) be a hypergraph, and let ϕ be a coloring of H. A hyperedge e ∈ E
is said to be k-colorful with respect to ϕ if there exist k vertices in e that are colored distinctively under ϕ. The coloring ϕ is called k-colorful if every hyperedge e ∈ E is min{|e|, k}-colorful. Let $c_H (k)$ denote the least integer $L$ such that H admits a k-colorful coloring with $L$ colors.

The reference for the problem is E.Horev,  R.Krakovski,  and  S.Smorodinsky,  “Conflict-free  color-ing  made  stronger,”  in Scandinavian  Workshop  on  Algorithm  Theory,pp. 105–117, Springer, 2010.


texts: Trees with duplicate nodes and path cancellations

texts:
I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see the whole data structure is as a tree. A picture is worth a thousand words

Each tree node contains an object that I simply represented as an integer. As you can guess, at each layer there are many nodes that are equal. For example, the last layer has 48 leaves; however, there are only two different kind of data in the leaves, namely 11 and 12.

In addition, between each two connected node there may be a bunch of other objects. At each layer, the list are all equal. I've just shown an example using the L_0 array on the two edges of the first layer.

Each layer of the list can be thought as having a label, as shown on the left of the tree. Now, based on some other checks, not relevant for our purposes, some of the paths may be cancelled. The cancellation condition can be thought as

def cancellEdges(node1, node2):
    if node1.label == node2.label AND notInPattern(node1.data, node2.data):
        deleteEdgesBetweenNodes(node1, node2)

In our example the pattern is shown in the top-right corner. We observe that all the edges between 0 and 8 are useless, which in turn means that the leaves labeled as 8 descendant from 0 should not be reachable. In the same fashion, the edges 1 -> -> 9 and 1->10 are useless. In the picture, this fact is represented by a red background for the nodes whose incoming edge is useless.

At the last layer, the same thing happens. In this case we have also blue nodes, that simply signals that the incoming edge to that node is useless not (only) because of the pattern, but because the parent is red.

In an effort to improve memory occupancy, I simplified the data structure using a linked list, like shown in the image below.

Basically, each element of the L_x lists can be thought of SimpleNode (the array-like objects in the picture); all the nodes belonging to a layer are instead AggregateNode (the elliptic shapes in the picture). The red arrows shows the links between the nodes of the linked list.

class SimpleNode:
    data: int
    nxt: SimpleNode
    prv: SimpleNode

class TreeNode:
    data: int
    parents: List[TreeNode]
    childs: List[TreeNode]

class AggregateNode extends SimpleNode:
    tnodes: List[TreeNode]
    label: string

Since the edge cancellations may happen only between nodes with the same label, I've decided to use additional pointers to connect the internal tnodes to their parents/childs with the same label. Take care that this parents/childs are not the same ones of the original tree. For example node 9, in the full tree, has 3 parents: 4, 5 and 6; in the linked list it only has 0 as parent.

Questions

How can we keep track of the total number of active paths? It would also be useful to do this incrementally, without having to check the whole tree at the end. In other words, it may be a property of a TreeNode or an AggregateNode or even a global property. In our case, f.e. we should have for the last aggregate node numberOfPaths = 15 or, equivalently, tnode11.numberOfPaths = 10 and tnode12.numberOfpaths=5.
How can we expand the whole tree starting from the new linked list? Or also, how can we traverse (depth-first or bread-first, it doesn't really matter) the paths from the list?
Is this structure the best we can do? Is there a better data structure that can be used in this case?


texts: Minimum expected cost through an unconventional graph with probabilities at which edges are selected

texts:
I'm having trouble identifying the approach to minimize the cost of reaching a certain state in an optimization problem. I've modeled it here as a game.

Problem Structure
You buy heroes and send them into a dungeon consisting of rooms containing each two challenges (random number check with a given threshold per room) that each hero can choose between (one hero completing a challenge does not allow another to skip it). The goal is to have any hero survive to the final room, and the secondary goal is to minimize the cost for doing so.

The first challenge costs a small fixed amount and success leads that hero to the next room (other heroes must complete their own challenges). The second challenge costs a medium fixed amount and if the challenge is successful, he rolls a fair 5-sided die. Anything below a 5 will move the hero to the next room. A 5 will move the hero 2 rooms ahead.

Failure on any challenge leads to the hero's death unless "divine protection" has been bought for this attempt at the chosen challenge (can only be used in the first two rooms). You can also buy a "charms" for your hero that will improve chances of success for a single attempt by various factors (1.5x, 2x, etc).

Example:

All heroes cost 300g.
The 1.5x charm costs 650g.
The 2x charm costs 1100g.
The 2.5x charm costs 2100g (but this can't be used at the same time as protection).
Divine protection for room 1 costs 2000g per challenge.
Divine protection for room 2 costs 4500g per challenge.
In the first room, challenge 1 costs 120g and has 40.5% success before charms.
In the first room, challenge 2 costs 210g (has same success rates but also 20% of successes move 2 rooms).
In the second room, challenge 1 costs 140g and has 13.5% success.
In the second room, challenge 2 costs 230g.
In the third room, challenge 1 costs 160g and has 10.% success.
In the third room, challenge 2 costs 250g.
In the forth room, challenge 1 costs 180g and has 4.1% success.
In the forth room, challenge 2 costs 270g.
In the fifth room, challenge 1 costs 300g and has 2.7% success.
In the fifth room, challenge 2 costs 390g.
The sixth room is the final room ("you win the game").

All g values can change due to market fluctuations, but I'm looking to solve the optimization problem for any snapshot in time (where we can say the costs are 'fixed' while we're calculating, but we'll have to plug the numbers in again the next time we calculate).

Question

Without the 20% chance on successes to skip a room, it can be modeled as a dynamic programming problem, but I haven't been able to figure out an approach to make that work.
What kind of approach would be appropriate for minimizing the expected cost of putting a hero in a given room?


texts:
From Database   System Concepts, by  Silberschatz, Korth and Sudarshan :

  A domain is atomic if elements of the domain are considered to be
  indivisible units. We say that a relation schema R is in ﬁrst normal form (1NF) if
  the domains of all attributes of R are atomic.

  A functional dependency A →B is called a partial dependency if
  there is a proper subset C of A such that C → B. We say that B
  is partially dependent on A. A relation schema R is in second
  normal form (2NF) if each attribute X in R meets one of the
  following criteria:

  • It appears in a candidate key.

  • It is not partially dependent on a
  candidate key.

If I am correct, the definition of 1NF in the book is the same as in Wikipedia which says

  A relation is in first normal form if and only if the domain of
  each attribute contains only atomic (indivisible) values, and the
  value of each attribute contains only a single value from that domain.

Is the definition of 2NF in the book the same as in Wikipedia
    which says

  a relation is in 2NF if it is in 1NF and no non-prime attribute is dependent on any proper subset of any candidate key of  the relation.

?

Specifically:

I don't think the definition of 2NF in the book requires a relation
schema being in 1NF, and I wonder if I am wrong and why?
While 2NF is related to functional dependency, is 1NF related to
functional dependency between attributes in a relation schema? (I
don't see the definition of 1NF involves functional dependency.)
Does the definition of 2NF in Wikipedia require that there can't be duplicate rows?

Does the definition of 2NF in Wikipedia rely on a different
definition of 1NF? For example, see
Does 1NF require that there can be no duplicate rows?

Thanks.


texts: The idea behind the state of Imperative languages

texts:
I was reading about programming paradigms and I have a question about the state when speaking about Imperative languages. What does it mean to change the program's state? Is it just an abstract idea? I know that C is in the Imperative paradigm (In fact in the Procedural paradigm), so it has a state, but I don't understand how it is expressed in language. Is there a special space in memory that contain 1 or 0? But then, what 0 and 1 represent?

If for example we have:

int x = 5;
printf("%d,5);

How the state will be affected by each line? Also, why Functional languages does not have one and what is the impact of having one.

As you can see, I'm a bit confused about the idea behind the state. I think that a small example make a bit clear.

I also read the previous thread from the second site, but it didn't help me to understand.


texts: Describe in English the pattern in the following regular expressions

texts:
Describe (in English phrases) the languages associated with the following regular expression.
it says to be as simple as possible

#1 (x (yyy + x)*)*
#2 (c (cc)*d(dd)*)*

for number 1 I got all words in which when y is in the word it can only appear in blocks that are divisible by 3(0,3,6,9, etc.)

the second question I can not see any type of pattern.

I would like to know if the first one is correct, and if what pattern is on the second one?

Thanks


texts: Maximum number of words in deterministic finished automata with k-states

texts:
I have exercise:

We have a given finished deterministic automata. It has 5 states and is
based on the alphabet {a, b, c}. It can create n different words (we assume that n <
inf). What maximum value can n be?

W have 5 states so it should be something like this:

$\varepsilon \ | \ (a|b|c) \ | \ (a|b|c)(a|b|c) \ | \ (a|b|c)(a|b|c)(a|b|c) | \ (a|b|c)(a|b|c)(a|b|c)(a|b|c)$

1 + 3 + 9 + 27 + 81 = 121, so n = 121 - maximum number of words in DFA with {a,b,c} alphabet and 5 states.

Its okay?


texts: Decision Tree for searching an element in an n*n matrix

texts:
I just learnt decision tree concept in class. I have a question for homework. It says to prove that for searching an element in n*n matrix the lower bound is logn and prove it using decision tree.

My question here is using comparison based model, how can we have the lower bound as log n. what if the matrix is unsorted?


texts: Why do you have to worry about cache coherence if you are using shared memory?

texts: Wikipedia says that shared memory comes with lots of costs associated with cache coherence costs. But I thought the whole idea of shared memory is that all the CPUs access the same memory? So if one CPU changes that memory then other CPUs would access the same value? It would seem like this would require FEWER cache coherence costs? Is the idea that if one CPU changes its local cache before it writes to shared memory then other CPUs have to be notified?


texts: Proving that an $n$-element heap has at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes

texts:
I am having trouble proving that an n-element heap can have at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes.

Please note that I am proving a loose bound.

First I proved that a complete binary tree can have at most $2^{h+1} - 1$ nodes. However, I don't know how to use this fact to inductively prove the formula above?

The only thing thus far in my inductive proof is showing the base case ($h=0$), which is trivial.


texts:
Deciding if the infinite union of a set of regular languages is regular is undecidable.

By closure property of regular languages, regular language is not closed under infinite union so is the above problem undecidable?


texts: Finding number of memory locations in chip

texts:
I was solving some old MCQs and found this question:

A RAM chip has 7 address lines, 8 data lines and 2 chip select lines. Then the number of memory locations is _____.
(A) $2^{12}$ (B) $2^{10}$ (C) $2^{19}$ (D) $2^{13}$

Assuming a word consisting of a byte, this should have
2 chip select lines, meaning total $2^2$ chips.
With 7 address lines, we can address $2^7$ memory locations in a chip.
8 data lines should be used to access only the data in the memory location, and not to specify any location.
That'll make for a total of $2^2\times2^7=2^9$ memory locations. But none of the option matches my answer. What should be the correct answer?


texts: are for every $\alpha \in N $   ,      $   \frac{1}{\alpha-2} \geq \frac{1}{\alpha}+\frac{1}{\alpha-1}$?


texts: In which order to solve subproblems when using memoization?

texts:
I am currently trying to solve a task with memoization.  I have following recursion:

A (i, j) = f( A (i, j-1), A (i-1, j-1), A (i-1, j + 1) )

I am not sure in which order the sub-problems should be solved best, so that  multiple calculations are avoided.

Does someone have an idea which order is best?


texts:
From here: https://www.geeksforgeeks.org/algorithms-np-complete-question-2/

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? (GATE CS 2006)

(A) R is NP-complete

(B) R is NP-hard

(C) Q is NP-complete

(D) Q is NP-hard

The answer they give is B and I can see that. But I'm curious as to what is Q then? If it's not in NP and if it's not in NP hard, is there some other set that I don't know about it belongs to?


texts: Are there decision problems outside of NP?

texts:
Consider any problem in NP-hard, then it has a polynomial reduction from a problem in NP in polynomial time. Though, it isn't clear by this definition whether there are decision problems in NP-hard that are not in NP.

Are there any known ones?


texts: Memory Addressing - Alignment Clarification

texts:
I'm reading "Computer Architecture A Quantitative Approach" (5th edition) and I'm having a hard time understing this table:

I understand how Misalignment happens, i.e., some byte, half-word, word, or double word it's not a multiple of the address where the element is being stored or accessed. The part that I don't understand is that it says in the caption: "that the byte offsets that label the columns specify the low-order 3 bits of the address"

My question is why are the low-order 3 bits of the address important or relevant in this situation? I'm assuming that the low order bits are the lowest binary values in the address. My intuition is that the 3 low order bits can tell us if the address is a multiple(2,4, or 8) of whichever data is being accessed, but I'm not sure.


texts:
Why is the initial value of hash 17 and not 0?

/**
 * Returns an integer hash code for this date.
 *
 * @return an integer hash code for this date
 */
@Override
public int hashCode() {
    int hash = 17;
    hash = 31*hash + month;
    hash = 31*hash + day;
    hash = 31*hash + year;
    return hash;
}

https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Date.java.html


texts: Real-time systems and real-time operating systems

texts:
Just to understand the topic a little bit better, I would like to know if there is a difference between real-time systems and real-time operating systems.

I know that a real-time system is a system for processes that have to meet deadlines and fulfill real-time requirements. If a deadline isn't met, it can lead to drastic consequences.
And a real-time operating system is an operating system that also has to fulfill real-time requirements.
The examples I found on the internet are mostly the same and also other details are quite the same.

But are there any major differences, if yes which ones?


texts: Examples for lower bounds proof except sorting

texts:
After i read this question here.

All non-trivial examples of lower bounds always mention sorting, but i do not find other non-trivial examples, which do not rely (partly) on the sorting proof.

What are other non-trivial examples?


texts: Which matrix of Q values is being used here?

texts:
This question refers to this paper: Using Free Energies to Represent Q-values in a Multiagent Reinforcement Learning Task

In section 2.1, equations (5) and (6), I am wondering which Q values are being used to adjust the weights of the restricted boltzmann machine:

Option 1: the Q values generated by the original MDP

Option 2: the approximate Q values obtained by calculating the (negative of the) free energy of the RBM

Follow up question: When considering states $(s^t, a^t)$ and $(s^{t+1}, a^{t+1})$, how do we determine which values of $a^t$ and $a^{t+1}$ to use? Are these the optimal actions from the original MDP, or are these to be obtained through the alternating Gibbs sampling mentioned later on...(which doesn't make sense, since we would not have weights required for this CD)

Thanks for your help


texts: Computer Science and Programming for a complete novice

texts:
everyone!
I am going to learn mathematics in a university, but it will be rather ''pure'' math, so, I want to get some exposure to computer science on my own. The problem is, I've never tried any programming or computer science activities. I'm not sure where should I start. Now, I realise that internet is full of online or video courses about cs or codes, but they are specific, for example, ''how to learn C++/Python'' or ''algorithms''.
As far as I'm concerned, what I need is some kind of introductory book for computer science( basics, how this and that works and why, what is this and what is that ). Though, some people say that it's better to learn some programming language first even before getting exposed to theoretical material.
Thanks in advance, I will appreciate any answers.


texts: Getting string from phrase structure grammar

texts:
For the following  phrase structure grammar I want to construct the type of string that satisfy it, but I am not sure the way to go.

$$\begin{align*}
S &\to xTy \\
T &\to xTT \\
xTx &\to xx \end{align*}$$

The thing I am struggling with is that I can't seem to be able to reduce it fully to the alphabet ($x$ or $y$) and the recursive nature seems to keep repeating the same irreducible pattern. For instance, here is what I tried

$xTy$
$x(xTT)y$
$xx(xTT)Ty$ (expanding left first)
$xxxTT(xTT)y$ (then expand right)
$xxxT(xTT)xTTy$ (expand middle)
$xxxxTTxTTy$ (simplify)

And then when I try to simply things again it tends to start it self again kind of repeating the process at step 2 again for the T's.


texts: Segmentation technique for handwritten text (cursive and unconstrained)

texts: Although I am new to the computer vision domain, I am tasked with automating handwritten text recognition from bank cheques. I first did some preprocessing(blurring and binarization) and then dilated it so that I could segment the words. But since the words are handwritten (cursive and unconstrained), the segmentation is failing most of the time. I read up on some research papers and it seems you can use neural networks for segmentation.Is that the correct approach? Are there other alternatives? Can someone shed some more light?


texts: Understanding Incentive Compatibility of pooled Bitcoin Mining paper

texts:
I'm trying to understand the paper Incentive Compatibility of
Bitcoin Mining Pool Reward Functions (Schrijvers, Bonneau, Doneh and Roughgarden, in Financial Cryptography and Data
Security – FC 2016 Workshops, BITCOIN, 2016; PDF).

In page 3 Section 2.1, they say pool operator does not know actual $\alpha_i$ mining power of player $i$. To estimate $\alpha_i$ depends on the reported shares and solutions.

A reward function $ R\colon H \mapsto [0,1]^n$ is a function from a history transcript to an allocation $ \{a_i\}_{i=0} ^ {n} $ with $ \sum_i a_i =1 $.
I don't understand this? What allocation does the authors mean?

What I somewhat understand from next para is $ H(k) = b = (y_1(k), \cdots, y_i(k) ) $ where $y_i(k)$ is no of shares reported by player $i$ in round $k$.
This I am basing on $H$ contains for each miner $i$ the total no of shares $b
_i$ reported in that round. History transcript is given by a vector $b \in N^n $.

Also what do they mean when they say " We use vector notation for $b$, so $b_1 + b_2 $ means component wise addition of these, and  $\|b\|_1 = \sum_{i=1}^n b_i $ is the sum of components of $b$"

Could someone explain with examples or in a more concrete way ?
Also any suggestions for understanding this paper would be much appreciated. Thanks.


texts: Given start strings, find simplest DAG that constructs target strings by concatenation

texts:
Say we have a number of start strings (green) and a number of target strings (red). Two strings can always be concatenated to a new string which can then be arbitrarily often reused (two arrows in, (1,∞) arrows out). A string can also be concatenated with itself.

Is there an algorithm that can tell if this is the DAG that has the least number of nodes?
Is there an algorithm that gives a DAG that constructs the strings?
Is there an algorithm that gives the least complex (by number of nodes) DAG?
Does this problem have a name?
It seems that this is related to the https://en.wikipedia.org/wiki/Steiner_tree_problem (but it is not a minimal spanning tree, because the paths could be disjoint).
Someone pointed me to the addition sequence problem, which seems equivalent and is NP-complete: https://epubs.siam.org/doi/abs/10.1137/0210047


texts: Minimal cubical type theory to do coercion

texts:
There are a lot of different versions of cubical type theory and a lot of constructs are introduced: intervals, paths, faces, lines, coe, hcom, v-types, glue-types, com, fcom, ghcom, gcom, box and cap.
What is a minimal cubical type theory (counted in the amount of constructs/syntax) in order to do the same things as you can do with an intensional equality type: define/prove equalities and coercion?


texts: $k$th Largest Algorithm in a range $[k, k+c]$

texts:
The well-known algorithm for computing the $k$-th largest element in an unsorted array of size $n$ runs in $O(n)$ time.

How about for a range $[k, k+c]$, where $c$ is not necessarily independent of $n, k$? The obvious "brute-force" algorithm is to find the $k$th largest using the original $O(n)$-time algorithm, then the $k+1$-th largest the same way, ..., find the $k+c$-th largest (and also, the algorithm outputs these in sorted order). However, this takes $O(nc)$ time, and $c$ can possibly be $\Theta(n)$, which can lead to an $O(n^2)$ algorithm. In this case, we could have just sorted the array and extracted the elements, which takes $O(n \log n)$ time.

Is there a better (known) way of doing this? I can't find any references online.


texts: Are there established complexity classes with real numbers?

texts:
A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of:

  I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ (with a poly-time many-one reduction), so $P$ is NP-hard.

My answer was basically:

  Since $P$ has instances with values from $\mathbb{R}$, it's trivially not Turing-computable so you can skip the reduction.

While formally true, I don't think this approach is insightful: we'd certainly like to be able to capture the "inherent complexity" of a real-valued decision (or optimisation) problem, ignoring the limitations we face in dealing with real numbers; investigating these issues is for another day.

It is, of course, not always as easy as saying, "the discrete version of Subset Sum is NP-complete, so the continuous version is 'NP-hard' as well". In this case, the reduction is easy but there are famous cases of the continuous version being easier, e.g. linear vs. integer programming.

It occurred to me that the RAM model naturally extends to real numbers; let every register store a real number and extend the basic operations accordingly. The uniform cost model still makes sense -- as much as in the discrete case, anyway -- while the logarithmic one does not.

So, my question boils down to: are there established notions of complexity of real-valued problems? How do they relate to the "standard" discrete classes?

Google searches yield some results, e.g. this, but I have no way of telling what is established and/or useful and what is not.


texts: Remove x last elements of an array and reinsert them before position y

texts:
I am looking for an algorithm to move a subarray in before an element (which is not part of that subarray) in the same array where the last element of the subarray is the last element of the array with O(1) extra space and O(n) runtime.

e.g. where *p1 = 5 and *p2 = 3:

1 2 5 6 7 3 4

becomes

1 2 3 4 5 6 7

This is what I have so far (written in C programming language). Trouble arises when p1 reaches p2.

void swap(long* p1, long* p2, long* array_end) {
  long* p2_i = p2;
  while (p1 < array_end) {
    if (p2_i > array_end) {
      p2_i = p2;
    }

    // swap *p1 and *p2_i
    long* temp = p1;
    *p1 = *p2_i;
    *p2_i = temp;

    ++p1;
    ++p2_i;
  }
}


texts: How to solve an optimization problem that deals with the optimal combination of given ratios?

texts:
I'm volunteering for a non-profit, and was asked to write a program for this problem, but I'm having a little trouble tackling it. Here's the problem:

So they're a daycare, and they get paid by the government depending on specific ratio's of staff to children. Here are the possible ratios and their pay:

one staff to 3 children (3:1). Pays 14.71 dollars per hour
one staff to 2 children (2:1). Pays 9.10 dollars per hour
one staff to 1 child (1:1). Pays 7.28 dollars per hour

With every possible number of staff and number of children in the daycare, there is a combination of ratios that will give the maximum profit. How do I find those ratios? Are there any clever ways to approach this problem?

The inputs of this ideal program would be number of staff and number of children, and the output would be the combination of ratios that produces the maximum profit.


texts: Context-free grammar for"not-at-all" palindromes

texts:
I need to bulid a context-free grammar for

$\qquad \mathscr{L_4}=\{w\in\{a,b,c\}^* \mid w\text{ is not palindrome at all}\}$

Not palindrom at all:
We will say that a word $w$ is not palindrome at all if for all $i$ such that $1\leq i\leq |w|$ the $i$ letter from the beginning of $w$ is not the same like the $i$ letter of $w$ from the end, for example $abbacb\in \mathscr{L_4}$ but $ca\color{gray}bba\color{gray}bcb\notin\mathscr{L_4}$, the word must contain a even number of digits, because if there were an odd number of digits, so the middle digit "equals to itself".

My attempt:
 Let's denote $S_{\text{pal}}$ from palindrome grammar and  $S_{\neg\text{pal}}$ for the not palindrome at all grammar

$$\\S_{\neg\text{pal}}\to a S_{\neg\text{pal}}b\big|bS_{\neg\text{pal}}a\big|aS_{\neg\text{pal}}c\big|cS_{\neg\text{pal}}a\big|cS_{\neg\text{pal}}b\big|cS_{\neg\text{pal}}b\big|\epsilon$$

Similar question here.
I'm not sure if my attempt is correct or not


texts: Maximal value of directed graph with constraints

texts:
What is an algorithm to calculate the maximum "score" possible in a directed graph, with the constraint that edges with the same value can only be traversed once? For example, in the graph below, given that you can use each of a, b, and c once, the best path is to use a and b to get to 7, and c to get to 2, for a score of 9.

Edit: This is another way to formulate the problem:
Given: A set $S$ of $(key:value)$ pairs, where the key itself is a non-empty set of variables, eg - $S = \{(\{a\}:2), (\{c\}:2), (\{a, b\}:7), (\{b\}:3), (\{c\}:1)\}$. Keys may not be unique, so the word 'key' may be misleading.
Required: A subset $S' \subseteq S$ such that the total sum of values of each member of $S'$ is maximized.
Constraint: Each variable present in any of the keys of $S$ (eg. $a, b$ etc.) belongs to the list (key) of exactly one member of $S'$
For example, $S' = \{(\{c\}:2), (\{a, b\}:7)\}$ has a total value of 9, and each of $a, b, c$ occur in exactly one list.


texts: minimum number of states in cross product of two minimum DFAs

texts: If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of states in cross product DFA = num of states in FA1 x Num of states in FA2). How to think on this?


texts: Practical algorithm for testing whether an edge is Delaunay

texts:
I have a set of vertices $V$ and a set of segments $S$. I want to know whether a segment in the set $S$ is Delaunay against the vertices in $V$.

I would like to state my assumed definition of a Delaunay edge: An edge is Delaunay, iff there exists a circumsphere of its endpoints not containing any other vertex inside it.

I would like to know practical approaches/algorithms for such Delaunay-edge test.


texts: Word Wrap Algorithm and Datastructure that supports modifications of text and window size

texts:
I'm trying to find or create an algorithm for efficiently displaying text that is word wrapped.  All the algorithms (if they an even be called that) for word wrapping presume a given lot of text and window size, and compute word wrapping in $O(n)$ time.  That isn't realistic because text can be huge, users can modify text anywhere, and window sizes can change.  It is quite a problem to expect $O(n)$ modification time whenever something changes. When a user modifies the text or resizes a window, I'd like to be able to update the display in something like logarithmic time.
Here is how I formalize the a slightly simplified version of the problem:
$A$ is an array of positive integers that of length $n$.  It represents the lengths of words (and their trailing space).  $W$ is a positive integer representing window size.  For simplicity assume $W \ge \max(A)$.  Each query of $I_W$ represents fetching the word at the start of a line.  A modification of $A$ is like user modifying the text, and a modification of $W$ is like the window being resized.
I want to be able to repeatedly do queries and modifications of $A$.  A modification is the insertion, deletion, or modification of an integer in $A$.  A query is a request of $I_W[k] \in \mathbb N$, defined as

$I_W[0] = 0$
$I_W[k+1] = \text{ the biggest } z \text{ s.t. } \sum_{I_{k} \le j < z} A[j] \le W$

To describe $I_W$ another way, suppose $A$ is $[5, 3, 4, 6, 5, 1, 1, 4, 4, \cdots]$ and $W = 9$.  Then split $A$ into initial segments whose sums are $\le W$, so $[[5, 3], [4], [6], [5, 1, 1], [4, 4], \cdots]$, then $I_W(k)$ is the sum of the lengths of the first $k+1$ splits; that is, $I_W = [0, 2, 3, 4, 7, 9, \dots]$.
I'm looking for an algorithm and datastructure that would allow for linearithmic preprocessing on $A$ and something like logarithmic time modifications and queries.  I'd also like to be able to handle changes in $W$ quickly but that can somewhat be handled with threads and software design so it isn't as important.
The fact that even tiny modifications of $A$ can have a tiny or drastic impact on $I_W$ is making this fairly challenging for me.


texts:
I have this code for a recursive bubble sort:

def bubble_sort_recursive(list_):
    global counter
    for i in range(len(list_)):
        counter += 1
        try:
            if list_[i + 1] < list_[i]:
                list_[i], list_[i + 1] = list_[i + 1], list_[i]
                bubble_sort_recursive(list_)
        except IndexError:
            continue
    return list_

The counter is initialized with zero outside the function, so I can count the number of times the elements were iterated.

I was told that the complexity of bubble sort is O(N^2). But when I run with a reversed list (worst case) with size 3, the counter finishes with the value 12, shouldn't it be 9?

The same happens for other sizes:
4 -> 28
5 -> 55

What is happening?


texts: What is the complexity of calling a trivial hash function $n$ times?

texts:
The cost of computing a trivial hash function is effectively zero, so the time complexity is $\mathcal{O}(1)$; however, if I assign $n$ variables using the hash function, is the complexity $\mathcal{O}(n)$.

For example, the pseudo code would look like this:

for i=1 to n
   var[i] = hash[data[i]];
end

The only operation that is being performed is the assignment operation, but in complexity theory, it seems that the assignment operation is not usually included in defining the complexity.


texts: A recursive solution to the all-pairs shortest-paths problem

texts:
I am learning All pair Shortest Path from CLRS book,but got stuck in the begining itself.I am writing my query.

According to one of the Lemma of shortest path -:

  All Subpaths of shortest path are shortest.

Using this lemma, we can write the Structure of shortest path given as-:

  Consider a shortest path $p$ from vertex $i$ to $j$ and suppose that $p$ contains atmost $m$ edges.We can decompose path $p$ into subpath  $p^{'}$ i.e
    $ik\,\,(\,\,i\rightarrow\,\rightarrow k )$ and one edge $(k\rightarrow j)$
  From the lemma it is clear that subpath $p^{'}$is also shortest and $p^{'}$
  contains atmost $m-1$ edges.
  so we can write as

    $\delta\,(i,j)=\delta\,(i,k)+w(k,j)\label{eqn:1}  $

where $\delta\,(i,j)$=shortest path weight from $i$ to $j$

Allright!!!! I am Ok till here.

Now the Author has wriiten the recursive solution to all pair shortest path which too makes sense to me .It is given by-:

  $L_{i,j}^{m}$=Minimum weight of any path from vertex $i$ to vertex$j$ that contains atmost $m$ edges.

    $L_{i,j}^{m}$=$min_{(1\,\leq k \leq n)}$$\,\,(L_{i,k}^{m-1}\,\,+w(k,j)\,\,)$ $\,\,\,(1)$

Here $k$ is used to find out all the predecessors of $j$.

I am still ok here,but i am stuck in the following point.

  If  the  graph  contains no  negative-weight  cycles,  then  for  every  pair  of  vertices  $i$  and  $j$  for  which $\delta(i,j)\leq \infty$(i.e connected)there is a shortest path from $i$ to $j$ that is simple and thus contains at most $n-1$ edges.A path from vertex $i$ to vertex $j$ with more than $n-1$ edge cannot have lower weight than a shortest path from $i$ to $j$ . The
  actual shortest path is given by

$\delta(i,j)=L_{i,j}^{n-1}=L_{i,j}^{n}=L_{i,j}^{n+1}....   (2)$

I am not getting relation between this statment$((1)\,\,and\,\,(2)\,)$   .Please help me out to derive this.


texts: How to design a formal grammar to convert EBNF description to a list of CFG production rules

texts:
I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm.
Can CFG production rules is generated from an EBNF description by a rewrite system rewrite EBNF description to halt state that final string is composed by CFG production rules and separate character for that list (for example character '/')?
For example: From intuition view, I could convert as below:
EBNF Description:
letter = "A" | "B" | "C" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
identifier = letter , { letter | digit | "_" } ;
Generated production rules:
letter ⟶ "A"
letter ⟶ "B"
letter ⟶ "C"
digit ⟶ "0"
digit ⟶ "1"
digit ⟶ "2"
digit ⟶ "3"
digit ⟶ "4"
digit ⟶ "5"
digit ⟶ "6"
digit ⟶ "7"
digit ⟶ "8"
digit ⟶ "9"
identifier ⟶ letter
identifier ⟶ letter noname_nonterminal
noname_nonterminal ⟶ letter noname_nonterminal
noname_nonterminal ⟶ digit noname_nonterminal
noname_nonterminal ⟶ "_" noname_nonterminal
noname_nonterminal ⟶ letter
noname_nonterminal ⟶ digit
noname_nonterminal ⟶ "_"
Thank you for your reading,


texts: What does route aggregation is an automatic process means?

texts:
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 5 (The Network layer), page 448:

When aggregation is turned on, it is an automatic process. It depends on
which prefixes are located where in the Internet not on the actions of an administrator assigning addresses to networks. Aggregation is heavily used throughout the Internet and can reduce the size of router tables to around 200,000 prefixes.

My question is: in this context, what does "when aggregation is turned on, it is an automatic process" mean? Is aggregation (route aggregation) like a function available in the router which an administrator can simply turn on or off? And what does "automatic process" here means? I mean, aren't processes, especially on the network, always automatic?


texts: Is programming an emulation of the real world?

texts:
Assume that we have a car in the real world, this car would be composed of atoms, and we can do operations on this car (for example: we can move the car or change its color, etc.).
And assume that we have a car object in the computer world (in RAM), this car object obviously is not a real car but rather a representation of a real car, but we can imagine that this car object is a real car, and we can also do operations on this car object (for example: we can move the car object or change its color, etc.).
Now if we want to for example change the color of the car in the real world, we have to manipulate some of the atoms that compose the car to accomplish that.
And to change the color of the car object in the computer world (in RAM), we have to manipulate some of the bits that compose the car object to accomplish that.
However, one difference that I can think of between the real world and the computer world is that in the real world the car is visible to people, however in the computer world the car object is not visible to people (you have to paint the car object on the screen to make it visible to people).
So can we think of programming as an emulation of the real world? more specifically, can we think of the real world as "real world RAM" that can contain any object (these objects would be composed of atoms) in the same way that RAM can contain any object (these objects would be composed of bits)?


texts: Find sets of weighted objects to maximize number of sets with weight >= X

texts:
I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number of objects.
1). What is a fast and correct algorithm to solve this?
2). Is this NP-complete, hard, or neither?
Ideally, I'd want the left over set of objects that does not add up to x to be maximal as well, but would settle for an understanding of how to solve the problem without this.


texts:
I have some jobs, which calculate values. Some of these jobs require the calculated values of other jobs for their own calculation. An execution plan for these jobs can be found with a topological sort on the dependency graph.

However, these calculated values are huge and occupy a large chunk of memory. I want to find a topological order that minimizes memory usage.

To give a simple example, consider the following dependency graph:

There are three possible topological orders: $1\, 2\, 3\, 4$, $1\, 3\, 2\, 4$, and $3\, 1\, 2\, 4$. Let's look at each of them.

In the first case, the values of $1$ and $3$ can be discarded immediately after $2$ and $4$ have finished, respectively, so each of them must be kept in memory for one additional step. The value of $2$ has to be kept for two additional steps until $4$ has finished. So in total we have to keep $4$ results in memory over the whole execution.

In the second case the values of $1$ and $3$ have to be kept for two steps and the value of $2$ for one step. This makes $5$ in total, so this ordering is worse in terms of memory usage.

In the third case the value of $3$ has to be kept for three steps and the values of $1$ and $2$ for one step each. Again we have a total of $5$, so this ordering is also worse than the first one. Thus the first ordering should be chosen.

Is there an efficient algorithm to find an optimal ordering without needing to inspect all possible orderings?

Bonus: is it also possible to give an optimal solution, if the values would need different amounts of memory per job?


texts: Can every context free grammar be transformed into equivalent grammar of this form?

texts:
Show, that every context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda $ ) where  $a \in V_t$ and  $A,B,C \in V_n $ with rewriting rules of following type:

$ A \rightarrow a $

$ A \rightarrow aB $

$ A \rightarrow aBC $

My thoughts are that I need to show that every context free rule i can be written into set of context free rules that when applied generate same string as rule i.

Is that correct? If not, could you give me any hints on how to do it properly?

EDIT:

How I`m trying to do it:

Greibach normal form has rules of type:

$A \rightarrow aA_1A_2...A_n$

So I need to break long rules into shorter rules Chomsky normal form style.


texts:
Question
I want to analyze the potential of a cloud computing application that performs payroll and invoicing over the Internet from a large Internet company.I want also to describe the systems development
steps and procedures you would use to analyze the feasibility of this approach.

I would like to find material and sources regarding the above task (lecture notes,similar exercises)

I have generall knowledge of cloud computing but i want to know more about this application(cloud computing for the use of payroll)
Thanks in advance


texts:
A stone is located at the point (0,0) of an infinite grid. The stone has exactly $n$ possible moves, not necessarily unique, each described by a $vector$ of integer coordinates. The stone can make  each move at most once , and the moves it makes may be arranged in any order.The goal is to reach a point as far (in the Euclidean distance) from the initial position as possible. How far can the stone be reached ? $($ Given that output is square of max distance $)$

Example :
 consider $ n$ $=$ $4$ and vectrs are

$[$2,-2 $]$ ,[-2,-2],[0,2],[3,1],[-3,1]

Ans is $26$
Optimal way is to use  vectors [0,2], [3,1], and [2,−2].or also [0,2], [−3,1], and [−2,−2].

link for vector clarity is https://ibb.co/mJByc99


texts: Concrete understanding of difference between PP and BPP definitions

texts:
I am confused about how  PP and BPP are defined. Let us assume $\chi$ is the characteristic function for a language $\mathcal{L}$. M be the probabilistic Turing Machine. Are the following definitions correct:
$BPP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] \geq \frac{1}{2} + \epsilon \quad \forall x \in \mathcal{L},\ \epsilon > 0 \}$
$PP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] > \frac{1}{2} \}$

If the definition are wrong, please try to make minimal change to make them correct (i.e. do not give other equivalent definition which use counting machine or some modified model). I can not properly distinguish the conditions on probability on both the definitions.

Some concrete examples with clear insight into the subtle points would be very helpful.


texts: How to choose the maximum vertices you can delete from set while atleast 1 of its neighbors is in set?

texts:
We have a graph with connections to vertices given to us. For example, consider that following pairs of vertices are connected:

1 & 2
2 & 3
3 & 4
4 & 5
5 & 6

Now the graph becomes 1-2-3-4-5-6. Maximum vertices I can drop such that atleast one of their neighbors is still in the set, is: 4. This is because I can drop all but 2 and 5 since everything else has a connection to either 2 or 5.

I am trying to come up with an algorithm that can do this. So far, I have this algorithm:

Get all inputs
Find vertices with maximum connections
Drop all other vertices
Check if all vertices have atleast one neighbor in set
If not, undo last drop

This algorithm is brute force and inefficient. Is there a better way to do it?


texts: Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless?

texts:
Hello and apologies if my question will be too elementary. My background is from arithmetic geometry, but I have been recently faced with certain computational problems of combinatorial nature, where I feel way out of my league, so I will definitely appreciate some clarity on the matter :)

Long story short, I am faced with the following type of a problem, which I would like to illustrate here with an example for the sake of better clarity:

Let $S:=\{1,2,...,42\}$ be a set of integers and let $N\subset\{T\in 2^S:|T|=3\}$ be fixed (pre-generated in a specific way). Typically, $|N|$ is in the order of 1500-2000. I would like to construct all 7-el. partitions $\Sigma=\{S_1,S_2,S_3,S_4,S_5,S_6,S_7\}$ of $S$ (i.e.$S_i\neq\emptyset$ for $i=1,...,7$ and $\cup_i S_i=S$) s.t. $|S_i|=6$ and $S_i$ contains exactly one element of $N$ as a subset, $i=1,...,7$. (*)

My question is, is this computationally feasible (e.g. a few days of number crunching on a modern workstation) by using an optimized routine/algorithm? And if yes, how?

In the particular example from above, a straightforward approach to obtain all 6-el. subsets of $S$ that contain exactly one element of $N$ as a subset yielded ~ 470 000 different subsets (also see this SO thread), which does not seem aproachable by a straightforward solution of the exact cover problem. Furthermore, in another example with $|S|=48$ and $|\Sigma|=8$, it yielded ~1.5 Mil different subsets.

Note that constructing all partitions, even with fixed block size, for sets with as many elements is kinda out of reach (cfg. Bell number or Stirling number of the 2nd kind). However, conjecturally, because of the specific nature of $N$ and the additional restriction on the blocks of the partition, it is expected that there are only very few such valid partitions (probably no more than 1 or 2). In other words, I am hoping that imposing the additional restriction (*) could be still used to obtain a suitable algorithm.

Since the underlying math for a potential proof or disproof may well be out of reach for now, I am hoping to at least get some computational verification for "larger" numbers before even attempting an attack on the mathematical part.

Thanks!


texts: Whats the point of caching if the minimum single clock cycle time is the prorogation delay of the slowest component (fetching from DRAM)?

texts:
I know that the clock speed is determined by the slowest stage within the processor (usually fetch) because one clock cycle will take as much time as the slowest pipeline stage to ensure everything is synchronized.

So as fetching from DRAM is usually the slowest stage (for example during LDR instruction to memory which isn't in the cache) the time it takes for this should be the time for one clock cycle. So whats the point of caching?

I mean the processor has to wait anyway for the next clock cycle so even though the processor has fetched memory from cache very quickly wouldn't it have to wait anyway for the end of the clock cycle?


texts: Finding the expected total number of comparison for a Randomized Quick Sort

texts:
Let A = {2, 8, 11, 3, 12, 7, 10, 4, 15}

Want to find $E_4$.

Little unsure how to do this question. Would this be similar to finding the probability of the number of comparison 2/(j -i +1)?


texts: Boolean expression for sum bit of full adder

texts:
The Boolean expression I find on the internet for the sum bit of a full adder is A xor B xor Cin. Does't this expression exclude the A=1,B=1,Cin=1 situation? When that happens, the sum bit is also 1, isn't it?

Thank you very much.


texts: How can a set offer better search performance than an array

texts:
While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer faster performance than arrays do when it comes to testing for membership."

The author doesn't mention the underlying data structure and as it stands, I don't see how the second part of this statement can be inferred from the first.

If the NSSet class is implemented using a hash table, I agree that it will have faster lookup performance than an NSArray class but in principle both classes could be implemented using arrays, in which case both would have a lookup performance of O(n).

Am I missing something or is this just an incomplete statement?


texts:
I tried to do the problem Find first set bit in Geeks for Geeks, and this is the code I used.
public static int getFirstSetBitPos(int n){
    int counter = 0;
    while (n > 0){
        if ((n&1) == 1){
            return counter + 1;
        }
        n >>= 1;
        counter ++;
    }
    return 0;
}

The problem asks to solve it in a time complexity of O(logN), and my code is O(N). When I looked at the editorial, it had this solution.
// Java Code for Position of rightmost set bit
class GFG {

    public static int getFirstSetBitPos(int n)
    {
        return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;
    }

    // Drive code
    public static void main(String[] args)
    {
        int n = 12;
        System.out.println(getFirstSetBitPos(n));
    }
}
// This code is contributed by Arnav Kr. Mandal

I don't understand this return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1; I would appreciate if someone could explain.
I am new to programming and an aspiring competitive programmer.


texts: Dynamic selection of cache replacement policy

texts: There are some different cache replacement policies could be implemented in CPU. As far as I know, ones have better hit ratio on specific type of code than others, but if that type changes (for example, loops and scan of long file), other replacement policy may become more effective. Did somebody try to investigate how to choose a specific replacement policy at runtime using some statistic information from previous CPU usage? What is this information? Do you know some articles or books about that?


texts: How to use Neural Network classification if data not same size?

texts:
I have data like this.

[0 1 0 1 0]
[0 1 0 1 0 1 1]
[0 1 0 1 ]
[0 1 0 1 0 1 1 1 1 0]
...

I want to classify with Neural Network but my data different size . I can not delete or add more arbitaly data. It may make the result not correct. So, How to classification data different size ?


texts: Sorting strings with "before" and "after" constraints

texts:
I'm trying to solve a constraint-satisfaction problem for a project of mine that seems like it should have a well-known solution, but I can't for the life of me seem to find it described anywhere.

I've been poring over what literature I can find about CSP's and none of the general stuff seems to be clicking. I feel like maybe my CS chops just aren't quite up to the task, so feel free to point me to some tutorial that will make me feel stupid for even asking this, if such a thing exists.

What I'm looking to do is this:

Given a list of unique strings, where each string may have either, both, or neither of the following constraints associated with it:

before, which references another string in the list, and ensures that this string occurs before that one in the final sorting.
after, which also references another string in the list, and ensures that this string occurs after that one in the final sorting.

Sort the strings in a way that can guarantee satisfaction of all constraints.

Something like this:

'bar', no constraints
'foo', before 'bar'
'baz', no constraints
'qux', after 'baz'
'quux' before 'baz', after 'foo'

Will result in a final sort like this:

'foo'
'bar'
'quux'
'baz'
'qux'

Though it isn't a hard requirement, I would prefer the result be deterministic. There are several alternate answers to the problem above, as 'bar' has no constraints besides being after 'foo'. Of course, I don't really care which one I get back as long as the algorithm reliably produces the same result each time.

I wouldn't be surprised to learn that such determinism is impossible since it seems to be one of the biggest reasons I keep running into blocks, but I've thus far been unable to prove to myself that it can't be done.

Of course, I'll also need to be able to detect sets of constraints that are impossible to satisfy-- such as this one:

'foo', no constraints
'bar', after 'foo'
'baz', after 'bar', before 'foo'

In cases like this I don't need any kind of answer. I just need to detect it so I can throw an exception.

So far may natural inclination has been to bust out a genetic algorithm, but that of course kills the determinism and would be wasteful if there is a better solution that just requires me to know what the heck I'm doing, lol. So I want to see if I can rule out that possibility before proceeding.

Thanks ahead of time!


texts: A condition ensuring that a bipartite graph have a perfect matching

texts: There is a bipartite graph $G=(A,B,E)$ such that for every edge $(a,b)$ (where $a$ comes from $A$ and $b$ from $B$), $\deg(a) \geq \deg(b)$, and additionally $\deg(a) \geq 1$ for all $a \in A$. From this, how can I prove there is matching which covers all of $A$?


texts:
I am curious about following question. I've read other threads but the problem is slightly different:
Is the set of real numbers a language?

So my question is:

If I have a grammar, as defined in https://en.wikipedia.org/wiki/Formal_grammar#The_syntax_of_grammars

G = (P,N,S,$\sum$)

P-production rules
N-non terminals
S- StartSymbol-
$\sum$ -terminal symbols

is it possible to have the set of real numbers in the set of terminal symbols?
The definition of a grammar on wikipedia says no.

Is it possible to define it otherwise?


texts: Definition of "data-directed programming"

texts:
Section 2.4.3 of SICP provides an example of  data-directed programing in the context of dispatching on type, but I didn't find a general definition of what it is.  Wikipedia article says that it is a programming technique mentioned in SICP and seems to claim that it is the same as polymorphism.  I am not convinced however that "data-directed programing" could be a reasonable way to call polymorphism.

The following looks to me intuitively like a reasonable definition of data-directed programming:

  extensive use of data structures to direct the control flow of the program.

For example, in Python there is no case or switch statement, and one suggested work-around is to use dictionaries.  This looks to me like an example of data-directed programming.

Is my understanding correct?  If not, what would be the correct general definition?  I would like to see any references.


texts:
I'm studying KMP algorithm and I'm stuck on an example.

Suppose my text is "I am queen." and my pattern is "q".

The sp table will have only one value, q and it's sp index will be 0. Mismatch will occur at the very first index.

According to the formula: i - ( spi-1 + 1) ; the right shift will be 0.

And so the algorithm will get stuck and move nowhere.

What am I doing wrong?


texts:
I'm reading the overview book of the Intel QuickPath Interconnect and it says there:

The physical connectivity of each interconnect link is made up of twenty differential signal pairs plus a differential forwarded clock.

I can't find what is a forwarded clock, does anyone know what it is and if there is some material for reading about it?


texts: Algorithm for finding "mean center" of unweighted graph

texts: I have a large sparse unweighted undirected graph (20M vertices, 60M edges) and would like to find what I'm calling the "mean center" (the vertex w/ shortest mean distance to all other vertices. Does this already have a name?). I know of an $O(N^2)$ solution: Starting at every vertex: BFS to calculate the mean distance to all other vertices, choose the minimum. But $N^2$ is too slow for a graph this size, is there any way to calculate the "mean center" in faster than $N^2$ time? Are there any good approximation algorithms? Or more efficient algorithms which find some similar "center" of a graph?


texts: Confusion about Definition of DPDA and $\epsilon$-move

texts:
The DPDA definition is from sipser's book, and it mentions that the following PDA can convert to DPDA.

I tried it, then I confused the definition!

By definition, I could construct these

$\delta(q_1,\epsilon,\epsilon)=(q_2,\$) $

and because of "exactly one of the values"

$\delta(q_1,0 ,0 \text{ or } \$ \text{ or } \epsilon) = \varnothing$

$\delta(q_1,1 ,0 \text{ or } \$ \text{ or } \epsilon) = \varnothing$

$\delta(q_1,\epsilon ,0 \text{ or } \$ ) = \varnothing$

However, how about $\delta(q_1,\epsilon,\epsilon)$ , when I handle the $\{ 0^n1^n|n=0 \}$ ?

Does it means we can stop at two states $q_1,q_2$ with same string?

to stop at the $q_1$ is from no input string
to stop at the $q_2$ is from no input string, but $\epsilon$-move

And is it "deterministic" ?

Or why can definition allow $\delta(q,\epsilon,\epsilon)$?

Doesn't it break "deterministic" ?

Could I think that it finally stops at $\{q1, q2 \}$, and it at least contains one accept states $q1$ , so we accept it ?

Hence, by omitting the intermediate steps, I also can construct

$\delta(q_4,\epsilon ,\epsilon ) = q_r$, where $q_r$ is non-accept state with $\delta(q_r,\epsilon ,\epsilon ) = q_r$,

then all done.


texts: Formally describing a sensor network language

texts:
I have a language for sensor networks (generates C code) and I want to define the formal semantics of it.

The language has this form:

{STATE name_state:
EVERY time
SELECT {variable [, variable] ...}
[SENDIF send_condition]
[CHANGEIF change_condition GOTO new_state];
} ...

START IN initial_state;

The initial state of the program is specified by the START IN instruction.
Each state is defined by the STATE instruction.
In the specification of each state the clauses EVERY and SELECT are compulsory and the clauses SENDIF and CHANGEIF are optional.
The CHANGEIF clause is only not specified when there is a single state.

What type of formal semantics is more convenient to use?


texts:
* Initial Question *

I'm trying to write a logical formula consists of three Boolean variable C1, C2, C3.

My program takes graph as input and checks properties about them. C1 represents presence of some structural properties of the input graph (graph being strongly connected). If graph have this property, variable C1 is True else its False.

Variable C2 and C3 represent another set of properties involving other program variables.

The property i'm interested is

  If graph have this desired structural property then there is an assignment to program variables that makes C2 & C3 True.

For checking one specific graph i can just say:

SAT (C1 && C2 && C3)

And if there is a satisfying assignment i'm done.

But rather than checking properties of specific graph i'm interested in checking for every graph which have this structural property (represented by C1) also have other properties too (represented by C2,C3).

So I represent graph as arbitrary two dimensional array of size N. So that i can allow my program to iterate over any graph of size N.

Bool Graph[N][N]

I'm using CBMC (C Bounded Model checker) to write and check program.

I want to write this.

  For_all Graph[N][N] s.t C1 $\implies$ There_exists(an assignment) s.t C2 && C3

I'm not sure how to can i write this property? Any help in this regard?

Updated Question : To make question clear as after an answer i thought i was unable to put my point clear.

In my program i'm taking graph as input. based on this graph i'm trying to
make connection that if the graph have some structural property then it
has other properties also.

The structural property is: graph being strongly connected. Other
properties are based on the label of edges and nodes. So to generalize,
other properties depend on program variable x,y,z,.. and Boolean function
f.

I can build this program by using a Boolean variable B1 to inspect whether
graph is strongly connected or not, if its is B1 is True, otherwise False.
and use other Boolean variable B2 and B3 to represent other properties.
Hence both B1 and B2, B3 depend on graph and B2, B3 also depend on other
variables x,y,z,... and Boolean function f.

To check for a single graph i can ask:

SAT (B1 and B2 and B3). if there is an assignment i'm :)

Problem arise when i'm interested not in a particular graph but in every
graph (certain fixed size N). Worst possible try is to generate all graphs
of certain size and check each one by one and make sure that its the case.

The thing i'm trying to achieve is something like this :

For_all graphs G s.t B1 -> There_exist an assignment to (x,y.., f) s.t B2 and B3.

Edited

I want to iterate over all graphs (which i can do making graph arbitrary)

unsigned int Graph[N][N];  // For some specified N

but with that i'm looking to check whether there exists an assignment that makes other property works. If other property were VALID(tautologous) or Contradiction i could have checked easily. But other properties(represented by C2 , C3) are not either a Valid or a contradiction. For example with  SAT (C1 && C2 && C3) and SAT (C1 && !(C2 && C3)) both have a witness.

  I'm interested in iterating and checking that there exists at least one possible assignment for each graph that makes C1 && C2 && C3 true.


texts: Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions

texts:
Let $k\in \mathbb N$

I'm looking for a small NFA build for the language of concatenation of two words of the length $k$ which are index-wise different, i.e. $$L_k=\{u\cdot v \in \Sigma^* : |u|=|v|=k\wedge \forall i, u_i\neq v_i\}$$

Notice that since $k$ is fixed, $|L_k|=(|\Sigma|\cdot(|\Sigma|-1))^k$, and is regular as a finite language.

$%$

The trivial DFA for the language contains $k$$|\Sigma| \choose k$$+1$ states and just "remembers" which letters it have seen during the first $k$ letters, however if $k=o(|\Sigma|)$, we can create a significantly smaller NFA.

$%$

A "simple" NFA for it would be of size $O^*(2^{2k})$ (more precisely, $O(k^2 \log |\Sigma| 2^{2k+O(\log^2 k)})$ ):

$%$

Take a $(|\Sigma|,2k)$-universal set (i.e. a set of vectors $\mathcal V\subseteq \{0,1\}^{|\Sigma|}$ such that for every vector $u\in \{0,1\}^2k$ and a $2k$ indices, there exists a vector $v\in \mathcal V$ such that $v_{|I}=u$, i.e. if we look only at these $k$ indices in $v$ we find $u$). Such families of size $O^*(2^{2k})$ are known.

We think of each vector $v$ as a function $\Sigma\to \{0,1\}$, where $v(\sigma_i)=1⟺v_i=1$.

$%$

Create an NFA as follows:

From the starting state $q_0$ create an $\epsilon$-transition to a new state for any $v\in \mathcal V$. Denote this state by $q_v$.
From each $q_v$ build a path of states which accepts all words whose first $k$ letters are mapped by $v$ to 0, and the later $k$ letters are mapped by $v$ to 1.

$%$

Basically, the idea is that the universal set allowes us to partition the letters which are allowed to appear in the first $k$ symbols from the rest, and we get every word in the language since there has to be a corresponding vector $v\in \mathcal V$ which partitions it right.

So the questions are:

  What is the size of the smallest NFA for $L$?

  Is this construction optimal?

  What lower bound we can prove for such automaton size?


texts: Measuring Fitness in Genetic Programming Functionology

texts:
I recently begun working on a genetic algorithm to solve for patterns in data. More specifically, it solves for functions given a sample of ins and outs. So a possible solution would be X+2 = Y. The problem is scoring.

I began by trying to use the distance between the result and the expected result as a way of measuring fitness. The problem is the difference is not a reflection of the distance from a correct solution.

So the question: Given a random set of values, is it possible to measure how many operations(+,-,/,*) it would take to get to an certain number without using brute force. And of course, if so how?

EDIT The random set will always contain {0,1,2}.


texts:
I want to know if for any base the most significant digit is 1 or not.
Here is the code:

for(int i=3;i<=a;i++)
  {
    int x = i;
    int r = a;
    while(r/x)
    {
      r = r/x;
    }
    int rem = r%x;
    if(r==1)
    {
      count++;
    }
  }

is there any optimal way to replace the while loop nested in the for loop.


texts: How do I minimize the cost of some algorithm that performs some operation on a list?

texts:
I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $S_i$'s are lists (I couldn't think of a better way to write the problem precisely). The "hint" is more of a conjecture which I can't prove than a hint.

Let $S_0 = \{s^0_1, ..., s^0_n\}$ be a list containing $n$ positive integers. Let $k$ be the length of $S_{i - 1}$, and define $S_1, ..., S_{n - 1}$ recursively as follows: choose $1 \leq r, s \leq k, \quad r \neq s$, and define
       \begin{equation*}
       S_i := (S_{i - 1} \setminus (\{s^{i - 1}_r\} \cup \{s^{i - 1}_s\})) \cup \{s^{i - 1}_r + s^{i - 1}_s\}
   \end{equation*}
       E. g.
       \begin{align*}
       S_0 &= \{2, 3, 5\} \\
       S_1 &= \{5, 5\} \\
       S_2 &= \{10\}
   \end{align*}
       Clearly, $S_{n - 1}$ has a single element. Also, define $W_i := s^{i - 1}_r + s^{i - 1}_s$. Consider the quantity $\sum_{i = 1}^{n - 1} W_i$. In the previous example, this quantity can be $15$ or $18$. How do you have to choose $r$ and $s$ in each step so that $\sum_{i = 1}^{n - 1} W_i$ is minimal?

(Hint: Pick $r, s$ such that $s^{i - 1}_r = \min_{x \in S} x$, and $s^{i - 1}_s = \min_{y \in S \setminus \{x\}} y$.)


texts: Determining the minimum number of edges to add in order to be 3-connected

texts: A graph $G$ is said to be $3$-connected if it has no $2$-vertex cutsets (i.e., at least three vertices must be deleted to disconnect the graph). As far as I know, it is possible to determine if a simple graph is $3$-connected in $O(n)$ time (example: http://www2.tu-ilmenau.de/combinatorial-optimization/Schmidt2012b.pdf), but I would find it useful to efficiently determine which edges to add in order to make our graph $3$-connected if it isn't already (ideally, the minimum number of edges if this can be done efficiently). Is anyone aware of such an algorithm? If so, I would appreciate a reference or two.


texts: Are asymptotic lower bounds relevant to cryptography?

texts:
An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be secure.

However, an asymptotic lower bound does not rule out the possibility that a huge but finite class of problem instances are easy (eg. all instances with size less than $10^{1000}$).

Is there any reason to think that cryptography being based on asymptotic lower bounds would confer any particular level of security? Do security experts consider such possibilities, or are they simply ignored?

An example is the use of trap-door functions based on the decomposition of large numbers into their prime factors. This was at one point thought to be inherently difficult (I think that exponential was the conjecture) but now many believe that there may be a polynomial algorithm (as there is for primality testing). No one seems to care very much about the lack of an exponential lower bound.

I believe that other trap door functions have been proposed that are thought to be NP-hard (see related question), and some may  even have a proven lower bound. My question is more fundamental: does it matter what the asymptotic lower bound is? If not, is the practical security of any cryptographic code at all related to any asymptotic complexity result?


texts: Implementing cordic in integer arithmetic

texts:
Referring to this reference...
I'm trying to work out the details of an integer arithmetic implementation of the CORDIC iteration. The CORDIC pseudo-rotations can be summarized as

$$
\left(
\begin{array}{l}
x_{n+1} \\
y_{n+1} \\
z_{n+1}
\end{array}
\right) = \left(
\begin{array}{l}
x_n - d_n2^{-n} y_n \\
x_n + d_n2^{-n} y_n \\
z_n - d_n \omega_n
\end{array}
\right)
$$

Where

$$
\omega_n = \arctan \;2^{-n}
$$

and

$$
d_n = \left\{
\begin{array}{rl}
1 & z_n \geq 0 \\
-1 & \text{otherwise}
\end{array}
\right.
$$

After $k$ iterations the result should be multiplied by the scale factor, name it $K$. However if we find a sequence $\left\{ \alpha_n \right\}_{n \in \mathbb{N}}$ such that
$$
\prod_{j=0}^{+\infty} (1 + \alpha_n2^{-n}) = K
$$

We can achieve the same result of the iteration above by performing

$$
\left(
\begin{array}{l}
x_{n+1} \\
y_{n+1} \\
z_{n+1}
\end{array}
\right) = \left(
\begin{array}{l}
(x_n - d_n2^{-n} y_n)(1+\alpha_n2^{-n}) \\
(x_n + d_n2^{-n} y_n)(1+\alpha_n2^{-n}) \\
z_n - d_n \omega_n
\end{array}
\right).
$$

However I was trying to work out the bitwidth per variable necessary, in order to do that I've tried to convert each computation into a fixed point one.

$$
\left(
\begin{array}{l}
x_{n+1} \\
y_{n+1} \\
z_{n+1}
\end{array}
\right) = \left(
\begin{array}{l}
(x_n - d_n2^{-n} y_n)(1+\alpha_n2^{-n}) \\
(x_n + d_n2^{-n} y_n)(1+\alpha_n2^{-n}) \\
z_n - d_n \omega_n
\end{array}
\right) \Rightarrow \left(
\begin{array}{l}
2^{2n}x_{n+1} \\
2^{2n}y_{n+1} \\
2^{2n}z_{n+1}
\end{array}
\right) = \left(
\begin{array}{l}
(2^n x_n - d_n y_n)(2^{n}+\alpha_n) \\
(2^n x_n + d_n y_n)(2^{n}+\alpha_n) \\
(2^{2n}z_n) - d_n (2^{2n} \omega_n)
\end{array}
\right)
$$

Given that a shift of $n$ positions should be repeated for $n = 0 \ldots k$ I would have a total size of

$$
\sum_{n=0}^{k}2n = k(k+1)
$$

So If I wanted to implement CORDIC to compute $k$ bits I would need variables with size of $\Theta(k^2)$ is this correct?


texts: If possible, use binary search to find an element in sorted array

texts:
Given sorted array $A[1..n]$, we want to find an element such that,
$A[i]=i^2$,Can we use binary search to find such a element?

My Attempt:
initially, I read this link, but I can't understand the comments for why we can't find that element in $O(\log n)$. Any hint be appreciated.


texts: on-the-fly decompress a flat-file database

texts:
I'm facing the following problem. I have a flat-file database (e.g. CSV).
Since it's relatively large to store in memory, I'd like to compress it.

Given a key, I need to return the uncompressed text (record of values).

So one naive idea is to tokenize the text into words and to have the mapping $\text{word} \mapsto \text{codeword}$

Of course, this naive idea lacks of understanding of statistical properties in the data, that other compression algorithms exploits.

So the next thing I thought about is Huffman code. The problem I'm facing is that I'd like to find the optimal tokenization for the text. Let's say that one column in the CSV file contains only the text "the fox jumped over the lazy dog", it reasonable to want that the algorithm would tokenize this string as one token.

but then again, going over all possibilities isn't a feasible task.
Are there any algorithms that deals with this problem?

So to summarize, I need to:

Compress my data once and to decompress on demand
Return the requested value (a record) for a given key
Decompression should be "fast enough"

Which algorithms fit my problem?

In particular, I'd like to know if Huffman code is a good option, and if so, how to tokenize the text.

Thanks!


texts: Metrics and algorithms for complexity of a graph

texts:
I am interested in what sort of metrics are there that try to give a measure of how complex a given graph is, what are the corresponding algorithms, and what is their time complexity. A short description or list of relevant paper would be great.

It might help to say that I have two graphs and I want to somehow tell which one is ``more complex." I will use this metric as a heuristic, so I would like to try various metrics on empirical data. (It might help even more if I say that those graphs represent two FSMs.)