texts: Enumerating all paths through directed graph with loops and splits

texts:
I am looking for a way to enumerate all the possible paths between a source and one or more sinks in a directed graph, with loops.  Also, some edges must enforce a maximum number of traversals (n), so that if an entity passing through the graph has already traversed the edge n times it cannot traverse it again.

Also, entities are able to split into multiple sub-entities, and merge again later, though each sub-entity is also able to traverse loops.

My current approach is to just simulate the flow of an entity through the graph, since each edge at a split does have an assigned probability.  With a large enough sample I know I can trace the most likely paths for traversing the graph by finding all unique paths taken by simulated entities.

I do not know if there is already a theoretical solution to this problem, or where I might start looking for such an answer.

Is this a well-known, solved problem?  What technical terms would I use to research this problem?


texts:
On Alpha-Beta pruning, NegaScout claims that it can accelerate the process by setting [Alpha,Beta] to [Alpha,Alpha-1].

I do not understand the whole process of NegaScout.

How does it work? What is its recovery mechanism when its guessing failed?


texts:
I am asking a simple question. Why we say that we would always get a new hash in a blockchain? Why we can't have collisions?

One way of collision is that the hard disk becomes full and there is no more space to store a transaction.

Some body please guide me.

Zulfi.


texts: A good introductory book on cryptography

texts: Can anyone suggest me some good books on cryptography? I have just starting studying cryptography but I know elementary number theory, abstract algebra and algorithms. Also please mention the difficulty level of the book.


texts: Is it possible to prove $\mathsf{BPP = NP}$ statistically?

texts: Assuming that someone will find poly-time algorithm that statistically is wrong on ~1% of total (already runned) instances (which are very different), will it be a proof for $\mathsf{BPP = NP}$?


texts: How far meta-logical frameworks are from universal logic?

texts: I am investigating metalogical-frameworks like Isabelle/Pure (very few information), http://twelf.org/wiki/Main_Page, http://abella-prover.org/ for encoding of new logics. And natural question arises - how far those frameworks are from universal logic? I am especially interested their capabilities to encode defeasible deontic logic and monoidal categorical logics.


texts: Richard Karp's 21 NP-Hard problems, the meaning of his research?

texts:
In Richard Karp's paper "Reducability among combinatorial problems" he lists 21 NP-Hard problems. Though I can somewhat understand the ideas and motivation behind the paper I am searching for some clarity.

From what I know and understand this paper showed the parallels between the various problems. Specifically that they are all abstractly the same problem. That given a solution (specifically a P-time solution?) to one of these problems you could solve all of them because they are all statements of a more abstract problem.

Is this a proper summary of the work he presents? Is there a more eloquent and proper yet short way to say it?

Karp's paper: http://www.cs.berkeley.edu/~luca/cs172/karp.pdf


texts:
I have a non-deterministic CFG that says

  S-> aS | aB | bB | λ;
  B-> bB | λ

And I'm asked to create a deterministic CFG from that. I understand why the given CFG is non-deterministic because it contains

  S-> aS | aB | [...]

But I think what I'm confused is why in my book does it say that A->λ productions are not allowed? I can't think of any other way to keep the solution a deterministic CFG if λ is not allowed.

[EDIT]
The book defines deterministic CFG

  "To recognize the full set of context-free languages, we require a non-deterministic stack automaton. We saw that any NFA could be replaced by an equivalent DFA but we cannot do this in the case of non-deterministic stack automaton. It is our good fortune that practical programming languages can be adequately described by deterministic CFG"

  "We said that in Type 1 grammars, the nonterminal on the left-hand side could be replaced by ε. Since these restrictions are cumulative as we go from one level of the hierarchy to the next, this implies that Type 2 grammars may not have productions of the form A-> ε. In fact, we will see many CFGs have such productions, we must allow such productions as exceptions to the Type-1 restriction."
  - Introduction to Compiler Construction by Thomas W. Parsons


texts: Cutting yarn into integer-length pieces to maximize profit based on known prices for each length

texts:
My classmates and I were working on a problem on our introduction to algorithms homework, but we are having a lot of trouble wrapping our heads around it. Below is the problem:

  We are given a string of yarn of length $n$ meters, and our goal is to cut this yarn into integer-length pieces. For every integer $1..n$ we know the selling price of a piece of yarn of that length. We call the selling price of a string of yarn of length $i$ by $p_i ≥ 0$. We must give an algorithm to compute the maximum amount of money that we could make by cutting the string into integer-length pieces. Our algorithm must run in $O(n^2)$.

So we know that this type of problem can be solved using a dynamic programming approach, but we're having trouble coming up with a recurrence relation. We think that we should start with an array $L$ such that $L[i]$ denotes the maximum amount of money given with a certain amount of cuts, but we're uncertain about how exactly we should represent this and where to go on from here.

Thanks a lot in advance!


texts: Find typing derivation of STLC term with reference types

texts:
The problem is to find the typing derivation of a term of the call-by-value STLC extended with reference types. The evaluation and typing rules for this language is given in Types and Programming Languages by Pierce on page 166. The term is
$$
t = (\lambda a:\mathrm{Ref}\mathrm{Bool}. \mathrm{if}\, \mathrm{true}\,\mathrm{then}\, !l_1\, !a\, \mathrm{else}\,0)\,\mathrm{ref}\,\mathrm{true}
$$
where
$$
\mu(l_1)=\lambda x:\mathrm{Int}.x
$$
So I need to find $\Gamma, \Sigma,$ and $T$ so that
$$
\Gamma\,|\,\Sigma\vdash t:T
$$
I know you are supposed to show your work, but my problem is that $t$ doesn't seem well-typed... What am I missing?


texts:
What conditions must be fulfilled for two edges of a graph to be called adjacent?

I found a lot about adjacent nodes, but our CS course script refers to adjacent edges, with no explanation.


texts: What is the difference between regular trees and phylogenetic trees in terms of graph theory?

texts:
If I am not mistaken, a tree is any graph that does not contain cycles.
However, I am currently taking a bioinformatics course where we deal a lot with algorithms on phylogenetic trees. Usually you are given a phylogenetic tree with $n$ leafs, and then you run some algorithm that can do something trivial like simple traversing of the tree, and then you get a $O(n)$ time bound, without saying anything about the number of internal nodes.
However given a regular tree with $n$ leafs, the total number of internal nodes can be infinite.
For example the following is a tree with one leaf (two if you consider it to be rooted) and infinite number of internal nodes:

So what are phylogenetic trees that you can express the running time of various algorithms in terms of the number of leafs, even though your algorithm actually traverses the entire phylogenetic tree?


texts:
This is the definition of a handle:

1.A “handle” of a string is a substring that matches the RHS of a production.

And

2.Whose reduction to the non-terminal (on the LHS of the production) represents one step along the reverse of a rightmost derivation toward reducing to the start symbol.

I don't understand the second condition, it's confusing. Can someone clarify it please. Thank you/


texts: I want to generate a bunch of graphs of about 100 nodes, where each node is a categorial variable.  I want the graphs to satisfy complex properties, like, "if a node of type A is connected to a node of type B, that node of type B should also be either connected to both a node of type C and a node of type D, or should be connected to a node of type E" and "no nodes of type F and G can be connected to the same node."  How do I go about generating such structures?  I was thinking of using an SMT solver, but even then I'm not exactly sure how to proceed.  For instance, is there a way to do it using only BitVectors?


texts: Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace

texts:
Exercise 4.29 from Quantum Computation and Quantum Information by Nielsen and Chuang has me stumped.

  Find a circuit containing $O(n^2)$ Toffoli, CNOT and single qubit gates which implements a $C^n(X)$ gate (for $n > 3$), using no work qubits.

I've figured out that this can't be done classically.

I've figured out how to do it with $O(2^n)$ exponentially precise gates (nest the double-control-from-single-controls-and-square-root-of-operation construction inside itself $n-2$ times).

I've tried generalizing the above construction into accumulating a linear combination of controlled operations. For example, if I have 3 controls called A and B and C and make a vector of the various cases [0, A, B, C, AB, BC, AC, ABC] then:

Applying an operation unconditionally adds [1, 1, 1, 1, 1, 1, 1, 1]
Controlling an operation on A adds [0, 1, 0, 0, 1, 1, 0, 1]
Xoring A into C then controlling an operation on C (then undoing the xor) would add [0, 1, 0, 1, 1, 1, 0, 0]
Xoring (A and B) into C via a toffoli gate then controlling an operation on C would add [0, 0, 0, 1, 1, 1, 1, 0]

Then I would try to add (apply a root of X) and subtract (apply inverse square root) the various vectors I can make until the result comes out as [0, 0, 0, 0, 0, 0, 0, N].

But I keep hitting various walls, such as solutions ending up with large multiples (i.e. the gates I'm using become exponentially precise, which I think is a no-no) or just not being able to solve the system due to the interplay between generating elements with AND/XOR then solving with +/* being non-standard or creating exponential numbers of gates.

What are some other approaches to try?


texts: Genetic Algorithm Neural Network- Inputs for evolving creatures

texts:
I made a GANN program for evolving creatures. The genes that get put into the GA for each ind are the weights that go into the neural net for each creature. The NN is a basic 1 hidden layer NN with bias neurons and it uses TANH so the weights are from -1 to 1. The GA uses .8 crossover rate (.3 elitism) and .003 mutation chance per gene/weight. Ranked selection is used and 1 point crossover.

The creatures go after food that spawns in a random location after pickup and there are also traps to avoid that done move. A food raises the fitness by 1 and the trap makes it lose 1 fitness point. They start at 1 fitness (health) and if they hit to many traps and get to 0 they die and their genes aren't used in the next evolution. But not many die anyway only like 5 to 10/50 per gen. There are 20 of both traps and food and 50 creatures. There are two sensors on the creatures. One on the left side about 30 degrees from the center face and one on the right. The inputs are each sensors dis from the closest food and from the closest trap.The outputs are 2 numbers. I pick which is highest get the abs value and multiply it by a max angle of 15 degrees and the creature rotates by that amount either right or left depending on which output neuron was the highest.

Before I added in the traps the creatures were very good at getting to food quickly and accurately. And they learned how to do it relatively quickly per test (after like 15 gens they were very good). Then I added in traps and just added the inputs that were the distances from the sensors to these traps just like with the food. With both inputs to food and traps they no longer learn. They just kind of make circles or do random stuff. They aren't dying that often (their fitness starts at 1 but if they hit food before they hit a trap they wont die just lose a fitness) but they aren't learning anymore. I tried normalizing (dividing by the env square side length) but didnt change anything. So is the issue with the inputs or something else?


texts:
I am preparing for my exam in Formal languages and Automata theory and I'm looking at some old exam questions right now. I need help with the following question:

  For each of the following languages answer whether it is regular, context-free but not regular, or not context-free. A brief, informal explanation is sufficient.

  $$
  L_3 = \left\{ w \in \{a,b,c,d\}^* \Bigg| \begin{array}{l}
      \text{\(w\) does not have a substring \(aba\),} \\
      \text{each \(a\) in \(w\) is immediately followed by \(b\),} \\
      \text{and \(\#c(w)\) is odd}
    \end{array} \right\}
$$
  $$ \begin{align}
  L_4 &= \{ a^ib^jc^ka^ib^l \mid j \gt l \text{ and } i,l,k \gt 0 \} \\
  L_5 & \text{ is the image of \(L_4\) under the homomorphism }
  h:\{a,b,c,d\}^* \to \{0,1,2\}^* \\ & \text{ such that }
  h(a) = h(b) = 10 \text{ and } h(c) = 210 \text{ and } h(d) = \epsilon \\
  L_6 & \text{ is the image of \(L_4\) under the homomorphism }
  h:\{a,b,c,d\}^* \to \{0,1,2\}^* \\ & \text{ such that }
  h(a) = h(b) = 210 \text{ and } h(c) = h(d) = \epsilon \\
\end{align} $$

Here is my attempt:

$L_3$ is regular. It's the intersection between 3 regular languages. Regular languages are closed under intersection, so the resulting language is regular. The language where $w$ does not have a substring $aba$ is just the complement of the language $aba$, regular languages are closed under complement, so the resulting language is regular. The language with an odd number of $c$ is regular. Hence the resulting language when taking the intersection between these languages is regular.

$L_4$ is not context-free. When reading the first $a$'s we will push the $a$'s onto the stack. Then we will read the first $b$'s and push them onto the stack. Then we will read the $c$'s. When we now read a second group of $a$'s, we will not be able to compare the number with the first $a$'s, because $b$'s are on the top of the stack and if we pop them then we will not be able to compare the number $b$'s in the beginning and the end. Hence, $L_4$ is not context-free.

$L_5$ is context-free but not regular. The language in question looks like this:
$$ 10^{i+j} 210^k10^{i+l} \text{ where } j \gt l \text{ and } i,l, k \gt 0 $$
A grammar can be constructed which generates at least one more $10$ in the beginning of the string than $10$ after $210$.

$L_6$ is regular because it's given by the regular expression:
$$ 210^{2i + j + l} \text{ where } 2i+j+l \text{ is any number } \gt 0$$

Is this correct? Note that informal explanations is sufficient in the answer and that no grammars has to be given.


texts: How to index a tree to allow efficient search for paths?

texts:
By "indexing" I mean assigning addresses or labels or whatever to nodes to make them easier to locate, similar (in its effect, not necessarily in the implementation) to how a database can be indexed.
I feel this question must be pretty elementary, but as a CS noob I don't know how to search for the answer. I may not even be phrasing the question correctly.
So let me describe a hypothetical use case. Say my program stores a chess game (including variations) as a tree, with each node representing the state of the game after a move. Given any two nodes which are guaranteed to be in the tree, what is the most efficient way to find the path (a sequence of intervening nodes) from one to the other? I'm mostly concerned with time complexity, although I'd like to save space as well (not sure how to express myself more precisely).
Edit: to clarify what I want, say I have a Python program like this:
tree = Tree(game_record)  # there's a tree constructed from a game record

# this tree can be traversed by calling `advance` and `backtrack`
tree.advance(child=0)  # advance the game into the first child of the current node
tree.backtrack()  # backtrack to the parent of the current node

# and it can tell you which node it's currently at
current_node = tree.current_node()

# now this is my question: at first we're at one node
node1 = tree.current_node()
# after some advancing and backtracking, we arrive at another
node2 = tree.current_node()
# I want a method that returns the path from node1 to node2
tree.find_path(node1, node2)  # should return something like [node3, node4, ...]

# what would be a good way to implement this method?

Walking the whole tree is probably not it. I'm thinking that maybe each node can be assigned an informative address, perhaps an array. One scheme would be to let a child's address be one element longer than its parent's, where the extra element uniquely identifies the child. So if the first node has address [0], its children would have [0, 0], [0, 1], ... and the children of [0, 1] would have addresses like [0, 1, 0], [0, 1, 1], and so on. With this scheme the nodes on the path between any two nodes can be directly read off from their addresses.
With a tall tree though, the addresses can get quite long. Not a real concern for a chess program, but this way of indexing a tree just feels inefficient and inelegant to me. Is there a better way to assign addresses? Or is there a completely different approach to this problem?


texts:
In Splay trees, by definition - the required element x - rises to the root of the tree, using the operations: zig, zig-zig, zig-zag. And the formula zig of the step is this: 1 + 3 (r '(v) -r (v)), where - r' (v) -r (v) is the length of the path before the path x is raised to the vertex, and the coefficient 1 is " actual payment for actions "

But here is the question: where does the coefficient 3 come from?

The zig-zig and zig-zag estimates for the step are: 3 (r '(v) -r (v))

again the question: what does the coefficient 3 mean?

and where did it go 1 - like "actual payback for actions"? ("actual payment for actions" - in terms of accounting value)


texts:
Suppose we have a rules derived from a treebank.
And in order to get a syntax tree of a given sentence we use the cyk algorithm.
In order to use the cyk we should convert the rules into chomsky normal form,
Such that all of my rules are A -> B C or A -> a (A,B,C are non-terminals and a is a terminal).
From the cyk we get the most probable tree, constituted from the cnf rules.
But what if we want to de-transform the tree to be constituted from the original rules?
We can expand very easily the Binary rules into the original.
But what about unit productions? for example; A->B->a transformed into A->a in cnf, how do we get the original unary rules path A->B->a?
Any ideas will be helpful.


texts: Is any of the assumptions hold true for the mentioned?

texts:
Suppose the use of linear regression. The result of the MSE is 120.5(mean squared error) for the train-set. Wev'e reached the minimum of training the data.
Is it possible that by applying Lasso(L1 form) we would get a lower MSE for the train? and for the test? is the same also holds for Ridge(L2 form)?

Lasso Train
Lasso Test
Ridge Train
Ridge Test


texts: How come the branching factor of chess is 35?

texts:
I was studying about minmax algorithms and it said the branching factor of a chess game is around average 35. Meaning a player can move about 35 legal moves per position.

I am not able to comprehend this.Like if I do the opening in chess I was able to count 20 possible legal moves.(1 or 2 possible moves for 8 pawns that gives us 16.
2 possible for 2 knights respectively giving a total of 20)

So how it was calculated?


texts: I want to flatten a binary tree into a linear array, and I wonder if there are specific algorithms to improve locality in the linearized representation (for instance, ensuring that all data from the left child of the root node appears before the data from the right child is an easy optimization.) What is the recommended approach to maintain high locality?


texts: Compute equality comparison without comparison operators

texts:
Is there a possibility to compute the result of an integer equality comparison by only using arithmetic or bitwise operations? Negative values use the two-complement representation.

I am looking for a generic algorithm, which results in two possible values for equality and inequality but not using comparison operations.


texts: Relational Algebra - Mistake in the quiz?

texts:
I've just done a mini test and scored 9/10, however, from my understanding, I think this question is incorrect.

Here is the only question which I don't understand how it can be correct:

So I joined up the relations and get this:

A | R.B | S.B | C | D
1 |  2  |  2  | 4 | 6   //this meets theta-condition R.A<S.C AND R.B<S.D
3 |  4  |  4  | 6 | 8   //this meets theta-condition R.A<S.C AND R.B<S.D
3 |  4  |  4  | 7 | 9   //this meets theta-condition R.A<S.C AND R.B<S.D
5 |  6

So the potential answers are:

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

But, as seen in the question I do not have matching-solution for any of these and I made an educated guess and concluded that there was a mistake in the paper... or did I make the mistake?


texts: What is a protocol for determining which of two numbers is larger, without sharing those numbers?

texts:
Situation: Alice has selected a positive integer $a$, and Bob has selected a positive integer $b$. Alice and Bob want to know whether $a > b$, $a = b$, or $a < b$, but neither wishes to reveal their chosen number to the other party.

How can Alice and Bob make this determination?


texts: can someone provide a good resource for understanding 2 opt heuristic?

texts: I have looked into wikipedia and this MIT slide. A step by step iteration of the algorithm with a clear example would be appreciated.


texts: Graph traversal problem touching every node exactly once

texts:
Is there a name for the problem:

  Suppose you have a connected, undirected graph; find a path that touches every node exactly once.

This is basically the complement of the Hamiltonian Path problem, and the Traveling Salesman Problem without the minimum distance constraint.

I've googled and StackExchange'd and come up dry, though it's possible I just lack the proper vocabulary.

Bonus points if you can point me to an algorithm or a set of requirements for such a path to exist.

Edit:  It turns out I had Hamiltonian Path mixed up with the Eulerian Path problem.  I had looked up both problems about 10 years ago, and evidently got them mixed up in my head in that amount of time.  Then, being sure I knew what a Hamiltonian Path was, I didn't actually read my attached link.  /facepalm


texts:
Just came across this transcript that states:

The principle is that prediction is the same thing as compression. And
what that means is that whenever you have a prediction algorithm, you
can also get a correspondingly good compression algorithm for data you
already have, and vice versa.

Even though the article gives some examples, I would like to know some answers from this community on the question: Is Prediction the same as Compression?


texts: Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?

texts:
So we know a nondeterministic Turing machine (NTM) is just a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. Commonly used to dicuss P vs NP, and how NP problems cannot be solved in polynomial time UNLESS the computation was done on the hypothetical NTM.
We also know an NTM would use a set of rules to prescribe more than one action to be performed for any given situation. In other words, attempt many different options simultaneously.

Isn't this what distributed computing does across commodity hardware? Run many different possible calculations in parallel? And the GPU, does this within a single machine. Why isn't this considered an NTM?


texts: Allowing an empty (epsilon) transition in a PDA

texts:
I'm trying to allow an empty transition in a PDA for the following language:

Alphabet: $Σ = \{a, b, c\}$
Language: $L = \{ a^ib^j \mid i \neq j \} \cdot \{ c \}^\ast$

Examples of words in $L$:

$\varepsilon$
$aabccc$
$abbccc$

Not in $L$:

$abcc$
$aabbc$

Here is what I came up with:

The diagram above uses JFLAP - where the symbol $Z$ reflects the empty stack. The symbol $λ$ is the empty symbol $ϵ$.

It accepts everything as it should, but I don't know how to let epsilon get through. q7 to q8 is when there is more b than a. So there should be a way to allow q7 to q9 where a is more than b but also epsilon can get through. Thoughts? I would like to simply set epsilon through but than aabbc can get through easily enough.


texts: Is a universal assembly language for all computers possible?

texts:
I would like to ask a few questions about Assembly language. My understanding is that it's very close to machine language, making it faster and more efficient.

Since we have different computer architectures that exist, does that mean I have to write different code in Assembly for different architectures? If so, why isn't Assembly, write once - run everywhere type of language? Wouldn't be easier to simply make it universal, so that you write it only once and can run it on virtually any machine with different configurations? (I think that it would be impossible, but I would like to have some concrete, in-depth answers)

Some people might say C is the language I'm looking for. I haven't used C before but I think it's still a high-level language, although probably faster than Java, for example. I might be wrong here.


texts: Find the median in two AVL BSTs in O(log(n))

texts:
So theres the classic problem of finding the median in an AVL BST in O(log(n))*
However given two AVLs, each having N different values (all values in both trees combined would be 2N different values) how would one find the median** in O(log(n))?

edit: Nodes can have the size of the subtree in each node like in *

I've been given a hint: Let one of the trees be A and the other B, and let AL denote the left subtree of A, and so on for AR BL BR.
In O(1), rule out the existance of the median in one of the subtrees.

edit: so far I have this:

let X=min{tree roots}, Y=max{tree roots}
|YR|+|XR|>=n   => XL is out
|XL|+|YL|>=n-1 => YR is out

as far as I can tell, this holds well and is O(1). I'm not too sure how to proceed from here.

Thoughts and hints would be appreciated!

for further clarification, the trees are like in the last page of:
https://courses.csail.mit.edu/6.006/spring11/rec/rec04.pdf

*by storing the size of the subtree in each node, this is simple enough

**the median here is defined as the Nth key if they were to be layed out sorted from low to high.


texts: Am I right about the differences between Floyd-Warshall, Dijkstra and Bellman-Ford algorithms?

texts:
I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you.

Dijkstra algorithm is used only when you have a single source and you want to know the smallest path from one node to another, but fails in cases like this.
Floyd-Warshall algorithm is used when any of all the nodes can be a source, so you want the shortest distance to reach any destination node from any source node. This only fails when there are negative cycles.
Bellman-Ford is used like Dijkstra, when there is only one source. This can handle negative weights and its working is the same as Floyd-Warshall except for one source, right? (This is the one I am least sure about.)


texts: Popcount Orders and Lexicographic Orders

texts:
A popcount order of a two bit vector {1,1}=3 can be given by:

{{1, 1}, {1, 0, 1}, {1, 1, 0}, {1, 0, 0, 1}, {1, 0, 1, 0}, {1, 1, 0, 0}, {1,
  0, 0, 0, 1}, {1, 0, 0, 1, 0}, {1, 0, 1, 0, 0}}

and as a sequence of integers:

{1, 2, 4, 8, 16, 32, 64, 128, 256}

We are basically just shifting bits...

A Mathematica code for it is:

HammingCycle[x0_] := Module[
  {x = x0, t = BitOr[x0, (x0 - 1)] + 1},
  out = BitOr[t, BitShiftRight[BitAnd[t, -t]/BitAnd[x, -x], 1] - 1]
  ]

where the input is an integer, for example 3 in the above...
The sequence is a lexicographic order as well.
Is it possible to get a function f(n) where I could get non-recursively a given value in the order? For example, f(5)=16...


texts: When an algorithm says Summation this, and Integral that, what does it mean in coding terms?

texts:
I'm a student at a college with only two units of mathematics and I don't know if I'm asking in the right place so please bear with me.

I'm currently reading GPU Gems by nvidia and I have a question. It uses Sigma, as in summation, and integral a lot, but when look at the implementation of some of these algorithms, for example, Perlin noise, I can't find any sort of "summation" i.e.:

sum = 0
for i in range(x):
    sum += f(i)

They just convert the Sigma's formula to code. As for integral, I was never very good at them so I have a very weak foundation in them --- Therefore I can't even close to imagine how to convert an integral from an algorithm to code. I know integrals are two things: the area beneath the curve, and the reverse of the derivative --- But how can you derive an algorithm?

For example, this is from the Worely noise algorithm. How do you translate it to code, like Python, or anything?

I'm not asking for code, just explanation. And I hope this is the right place. Thank you.


texts: How to prove that language is decidable?

texts:
Prove or disprove:
The following language $L$ is decidable:

$\{ \langle M, x\rangle: M \text{ is a Turing machine and } M(x) \text{ halts in less than } |x|^2 \text{ steps} \}$

So for proving I need to construct a TM $U$ if it accepts $L$, so $L$ is decidable, otherwise not.

My steps are:

$U$ = "On input $ \langle M, x\rangle$:

$i:=1$;

$n := |x|^2$
Simulate one step of $M$ on $w$.
If $M$ accepted $w$ then $U$ accepts.

If $M$ rejected $w$ then $U$ rejects.

If $i ≥ n$ then $U$ rejects.
Else $i:=i+1$; goto step 2."

Because $U$ is a decider machine, $L$ is a decidable language.

Is this solution correct? Or I should do it in another way?


texts:
Regarding the difference between Two Vs Dual Port RAM Here is what I understand:
The first can read and write at the same time but can't read twice or read twice at the same time while the second can read and write, read twice or write twice.
Is this correct?
Plus, Is this connected to software or hardware, let's suppose I have 2*8=16GB Ram how can I convert them from Two port to Dual port?


texts: How strong is equivalence of lambda expressions?

texts:
Consider two lambda expressions $\mu$, $\nu$ representing computable functions $f_{\mu,\nu}:\mathbb{N} \rightarrow \mathbb{N}$. If $\mu$ and $\nu$ are equivalent under the combination of $\beta$-reductions, $\alpha$-conversions and $\eta$-conversions then $f_\mu=f_\nu$.

  Under what conditions does the converse hold? In particular, if it is possible to prove in Peano arithmetic that $f_\mu=f_\nu$, does it follow $\mu$, $\nu$ are equivalent in the above sense?


texts: Undecidability of whether a given TM halts or only has loops which can be detected by some TM

texts:
This might be a bit of an abstruse question, but it's something I've been trying to prove.

I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all Turing Machines that either always halt, or have non-halting loops where all of which can be detected (a positive decision made on it's existence) by some Turing Mahcine.

I'm trying to do a reduction from the Entscheidungsproblem, and my proof looks something like this:

Create a Turing machine $D$ on input $<M,w>$ that does the following:

Mechanically create TM $M_2$ which does the following on $x$:

if $M$ accepts $w$ (via simulation from UTM): accept $x$.
if $M$ rejects $w$: loop in a manner such that $M_2$ would not be a member of the aforementioned set.

Run decider for above problem on $M_2$:

if decider accepts, it should accept because if $M$ accepts $w$, $M_2$ must always halt and must be a member of the set in question.
if decider rejects, it should reject because if $M$ does not accept $w$, $M_2$ must have a non mechanically detectable loop and is not in the set.

The above Turing Machine $D$ should therefore decide Entscheidungsproblem and shows the reduction. However, I'm not sure how to show that it possible to mechanically create a loop which cannot be mechanically detected, or whether an alternate method of proof would be adequate.

Any insight in this proof would be appreciated.


texts: Thorup : What is the meaning of super distance?

texts:
While reading Thorup's Algorithm to solve SSSP problem, I have one point that I can't understand: super distance.

It says: "For each vertex we have a super distance $D(v)\geq d(v)$"

$d(v)$ must refer the shortest distance from origin to $v$, but what is $D$ ?

Is it just a distance value from origin while calculation until $D(v)=d(v)$ ?


texts: Determine interference factors in parallel computing

texts:
Parallel processes interfere with each other in many ways, by competing for shared resources such as shared caches, memory, disks, etc.

Would it be possible to determine latent factors just with a runtime analysis, by means of comparing the runtime of the respective applications while running them many times in different combinations? Or would the required sample size be too big for the method to be feasible?

If comparing only the runtimes would not result in significant results, which variable would be best suited to observe? L1-cache-misses, L2-cache-misses, page faults, total memory usage, tlb-misses, etc.


texts: Definition of space complexity when algorithm cycles.

texts:
I'm reading side by side my class notes and Papadimitrious' Computational Complexity book. At this point they are talking about space complexity. They give rules for computing space employed in an algorithm that runs on a multi-tape Turing machine:

We count the cells used.
If we don't write in the input, this cells don't count.
If the output cells are written from left to right, they don't count.

The final requirement is expressed differently in Papadimitrious' and my notes. In the books it is written:

  The cursor of the input string does not wander off into the blank
  symbols after the end of the input. It is a useful technical requirement, but not necessary.

In my notes:

  In an algorithm where space is counted, there can exist computations
  that never end, but one can always transform the algorithm into
  another that doesn't cycle.

So how does one measure the space complexity of an algorithm that may cycle forever? Are this statement equivalent to each other?


texts: Operator precedence in propositional logic

texts:
there is some kind of priorities for the elements in propositional logic ?

for example : p ∧¬q → r , given this ,we there may be two options

(p ∧¬q) → r  OR p ∧ (¬q → r) , which one is the correct ?


texts: Semi-automatic layout algorithms for a mind map

texts:
There're some existing tree layout algorithms such as Tidier Drawings of Trees and Drawing Non-layered Tidy Trees in Linear Time. I call them as automatic layout algorithms since positions of nodes are determined entirely by the algorithm instead of the user.

Now I need an algorithm that allows positions of some nodes to be affected by the user (e.g. after node being dragged to another position) while calculate positions of other nodes.


texts: Complexity of algorithm to find number of elements > element index i in an array

texts:
The question is:

Given an array of size N, arr, create another array whose index i = number of elements in sub-array(arr, i+1, N-1) that are greater than arr[i].

Eg. if input array is,
5 3 9 8 2 6
output array is
3 3 0 0 1 0

O(N^2) is simple just two for loops.

I think a O(N*logN) is possible by starting from last element and adding each element to a height-balanced BST with a size element.

Any thoughts on if we can do O(N)?


texts: Universal Turing machine simulating the null Turing machine?

texts:
The definition of the universal Turing machine is

$$
U(\langle M \rangle,p)=M(p)
$$

where U is a universal Turing taking two inputs $\langle M \rangle$, the binary encoding of a Turing machine, and $p$ a binary program.

What happens in the case where we feed the null Turing machine to the UTM.

$$
U(0,p)=?U(p)?
$$

Will this give out the outputs that are specific to the given formulation of the UTM being run?

Also, is there any kind of general properties of $U(p)$ between the universal Turing machines? My intuition tells me $U(p)$ must be the same answer for all UTMs and all $p$, but I would like confirmation.


texts:
I have a range query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in the order that they appear in the input. The operations can be one of the following: update a position of the array with a new value, insert a new element at some index of the array, remove an element at some index of the array and query information about a range of the array.

I tried an implementation of Segment Tree where the nodes are stored in an array. Left child of node at index p is at index 2p, right child is at index 2p + 1. This implementation is not enough, because the tree is static. All I can do are range queries and update positions of the original array. Inserting or deleting elements in the original array requires the tree to be rebuilt, so the running time is O(n) (too slow for the test cases). My program is correct, but too slow.

I Googled about Segment Trees with insertion/deletion and I read that is possible to do that with self-balancing binary search trees, like AVL or Red-Black trees. But I'm having trouble to understand how insertion or deletion would work in this dynamic Segment Tree that I need.

Does anybody knows something about that?


texts: What is the need of re-sampling the image for HOG features?

texts:
I read Dalal and Triggs paper for HOG description and a blog Chris McCormick HOG regarding the same. The blog says that the image needs to be re-sampled at different scales to recognize different person.

My question is: Already we have a window which we place on the image having a size of 64*128 and which slides over the image. Then why re-sampling instead of sliding the whole window over the image which can detect the persons instead. ?

Please rectify if I am wrong, thanks in advance !!


texts: If $L$ is a regular language, how to prove $L_1 = \{ uv \mid u \in L, |v| =2 \}$ is also regular?

texts:
If $L$ is a regular language, prove that the language
  $L_1 = \{ uv \mid u \in L, |v| =2 \}$
  is also regular.

My idea: $L$ can be represented as a DFA and then you could add 2 consecutive transitions from every final state for the letters of $v$, creating a new NFA diagram. Is that correct? I'm not sure how to make this a formal proof.


texts:
I need to implement LU-decomposition in Kaira. In Kaira the programmer writes the "parallel part" as the diagram similar to Petri Nets.

So, could you, please, recommend me some parallel algorithms for LU-decomposition which are really easy to understand and implement? The low difficulty of the implementation has the highest priority for me, because I'm not very familiar with Kaira and I'm in hurry a little.

I looked at a Fined-grained LU-factorization, but I'm curious if some other algorithms are used.


texts: Given a list of strings, find every pair $(x,y)$ where $x$ is a substring of $y$. Possible to do better than $O(n^2)$?

texts:
Consider the following algorithmic problem: Given a list of strings $L = [s_1, s_2, \dots, s_n]$, we want to know  all pairs $(x,y)$ where $x$ is a substring of $y$. We can assume all strings are of length at maximum $m$, where $m << n$ and are all over a finite alphabet $\Sigma$ with $|\Sigma| << n$. We may also assume that the number of pairs $(x,y)$ where $x$ is a sub-string of $y$ is much smaller than $n$.

A trivial algorithm would be this:

1. foreach x in L:
2.   foreach y in L:
3.      if x is substring of y:
4.         OUTPUT x,y

However, this has complexity $O(n^2 \cdot m)$ - I am curious to know whether there is a faster algorithm?

Edit:
As pointed out in the comments, there can be at most $n^2$ such pairs, so I don't see how there can be an algorithm faster than $O(n^2)$. However, I was wondering if there is something like a $P-FPT$ algorithm where the squared complexity is dependent on the number of output pairs, rather than $n$? Or at least an algorithm that reduces the complexity to something better than $O(n^2 \cdot m)$.


texts: Difficulty in understanding the "expontential average" plot of the estimate of the next CPU burst with the actual CPU burst

texts:
I was going through the portion of exponential averaging (to find the CPU bursts) under Shortest Job First (SJF) Scheduling from the dinosaur by Galvin et. al.

Let $t_n$ be the length of the $n$th CPU burst, and let $\tau_{n+1}$ be our predicted value for the next CPU burst. Then, for $α, 0 ≤ α ≤ 1$, define
$$\tau_{n+1}= \alpha.t_n+(1-\alpha).\tau_{n}$$

Using $\alpha=\frac{1}{2}$ they give a plot as follows:

I am facing few issues with the plot shown above:

I feel that the footer of the plot,i.e. the CPU burst and the guess, do not align. What I feel is that the $0$ th CPU burst time of $6$ units should be above the $0$ th "guess" of $10$ units in the footer...
Though the domain is discrete as a whole, but why is the blue curve continuous? Moreover, strikingly between the time intervals $2-3$ and $3-4$ why is there a sudden dip in the blue (estimate) curve?


texts: A Guess Turing Machine that accepts a random Binary number

texts:
I'm trying to construct a turing machine that accepts any random binary numbers. From the theory (and partial example) in this video, I understand (correctly?) that this is something that is more easily doable with a Non deterministic turing machine.

So I have come up with a concept as such that I start with state Q1 (from the left side of the band) and upon reading a zero I move right, and upon reading a One 1 move right and the machine enters the same state, again and again until the complete word is read.

I understand that this is a way I can accept an input. What I dont understand is how to include accept and reject states on the machine? I would appreciate all help on the matter.


texts: How to show that there are $\binom{M+K}{M}$ different number of type bins?

texts:
In textbook by Vazirani's textbook, chapter 9 about Bin Packing. He give the following lemma.

  Lemma 9.4 Let $\epsilon >1$ be fixed, and let K be a fixed nonnegative integer. Consider the restriction of the bin packing problem to instances in which each item is of size at least $\epsilon$ and the number of distinct item sizes is K. There is a polynomial time algorithm that optimally solves this restricted problem.

Proof. The number of items in a bin is bounded by $1/\epsilon$. Denote this by M. Therefore, the number of different bin types is bounded by $R = \binom{M+K}{M}$. Which is a large constant. Clearly, the total number of bins used is at most n. Therefore, the number of possible feasible packings is bouned by $P=\binom{n+R}{R}$, which is polynomial in n. Enumerating them and picking the best packing gives the optimal answer.

Question: We know a fact which is: $\binom{n+k-1}{n}$, now in order to find the number of different bin types we it should be something like $\binom{M+K-1}{M}$ why in the proof it is different?!!


texts: What level of maths do I need for artificial intelligence?

texts: I want to learn maths for artificial intelligence. I heard that main areas of mathematics for AI are Multivariable Calculus, Linear Algebra, Probability and Statistics and Discrete Mathematics. But what level of these subjects do I need? For example the easy level is like Calculus of Gilbert Strang and 18.01 Calculus from MIT Open Course Ware. The hard level is Apostol's or Spivak's Calculus. Do I need easy level of maths or hard level to be good at artificial intelligence and its areas (machine learning, pattern recognition).


texts: Can I use Θ if tightest lower and upper bound are not the same?

texts: When analyzing the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same, is it bad to denote the running time in theta notation? If an algorithm has a running time of $\Theta(n)$, is it safe to assume that the upper and lower bound are the same?


texts:
Suppose we have a DAG $G$ with one source node $s$, ie. it has a path to every node, and target node $t$ which every node has a path to it. For a pair of paths from $s$ to $t$ we can define a distance function $d(\cdot,\cdot)$ as:
$$d(P_1,P_2) = |(P_1 - P_2) \cup (P_2 - P_1)|$$
We want to find  the maximum value of this function computed all possible paths between $s$ and $t$:
$$D = \max_{P_1,P_2} \big\{ d(P_1,P_2)\big\}$$

You can think of this measure as a distance between two paths and therefore the problem can be thought of finding the "diameter" of a graph that its vertices are paths on $G$ and its edges' weights are determined by this formula.

Because $G$ is a DAG the number of paths between $s$ and $t$ is finite and therefore the quantity is well defined.

I have tried to find an upper bound for $D$ in a linear time with respect to nodes and edges of the graph.
Suppose we take a random path $P_r$. We try to find the path that is maximally different from $P_r$. If we find the most distant path from this path, namely $P_s$ diameter cannot be bigger than $2 d(P_r,P_s)$, that is:
$$D \le 2 d(P_r, P_s)$$
This can be done by setting the weight of the edges on $P_r$ to zero and then finding the maximum distance between $s$ and $t$ on the new graph. This can be done in linear time. But I haven't figured a way on how to choose the $P_r$ or how to directly compute $D$


texts: Relationship between inductive families and type-returning functions

texts:
Dependently typed languages such as Agda support inductive families, also called indexed datatypes, which allow type parameters to vary between constructors. This can be used to define a set of relations between types, which can be used to constrain existentials. For example, we can capture the relation
$$\begin{align*}
\mathsf{Unit} &\longmapsto \mathsf{Bool}\\
\mathsf{Nat} &\longmapsto \mathsf{Int}
\end{align*}$$
in the following Agda type:
data Link : Set → Set → Set where
  link-a : Link ⊤ Bool
  link-b : Link ℕ ℤ

We can then define a type Tie that pairs a value of type Link A B with a function A → B:
data Tie (L : Set → Set → Set) : Set₁ where
  tie : ∀ {A B} → L A B → (A → B) → Tie L

Just for further illustration, here are a few examples of working with these types:
tie₁ : Tie Link
tie₁ = tie link-a λ tt → true

tie₂ : Tie Link
tie₂ = tie link-b λ n → + n

app-tie : Tie Link → ℕ → Bool ⊎ ℤ
app-tie (tie link-a f) _ = inj₁ (f tt)
app-tie (tie link-b f) n = inj₂ (f n)

This is a useful technique, and this pattern is common in languages like Haskell (where inductive families correspond to GADTs). However, in Agda, the construction is somewhat awkward, as Tie belongs to Set₁ rather than Set due to the need to existentially embed A B : Set in the tie constructor.
I find this unsatisfying, as a simple rearranging of our types allows a definition of Tie that belongs to Set. Instead of defining Link as an inductive family, we define it as a combination of an index and a type-returning function:
data LinkI : Set where
  link-a′ : LinkI
  link-b′ : LinkI

Link′ : LinkI → Set × Set
Link′ link-a′ = ⊤ ,′ Bool
Link′ link-b′ = ℕ ,′ ℤ

Now we can define a version of Tie that contains no types and therefore belongs to Set:
data Tie′ {I : Set} (L : I → Set × Set) : Set where
  tie′ : (i : I) → uncurry′ Morphism (L i) → Tie′ L

At first blush, we seem to be able to do all the same things with this formulation:
tie′₁ : Tie′ Link′
tie′₁ = tie′ link-a′ λ tt → true

tie′₂ : Tie′ Link′
tie′₂ = tie′ link-b′ λ n → + n

app-tie′ : Tie′ Link′ → ℕ → Bool ⊎ ℤ
app-tie′ (tie′ link-a′ f) _ = inj₁ (f tt)
app-tie′ (tie′ link-b′ f) n = inj₂ (f n)

However, this indirect encoding is annoying to work with. Seeing as the transformation is entirely mechanical, intuitively it seems we ought to be able to somehow achieve Tie Link : Set while retaining Link as an indexed type, but it isn’t clear to me that this is actually possible.
Given the above context, my question is threefold:

Are Tie and Tie′ meaningfully distinct, in the sense that Tie allows doing things that Tie′ does not? If so, what?

One can argue that tie does in fact contain A B : Set while tie does not, so Tie must surely belong to Set₁. But the types A and B can always be easily reconstructed from Link A B, so surely they don’t need to be stored, in a similar sense to that described in Inductive families need not store their indices. Is this reasoning flawed, or is this simply an implementation infelicity?

Has the relationship between these two constructions been treated explicitly in any existing literature?


texts: Why Halting problem is Recursively Enumerable?

texts:
If we take this definition as R.E. set definition (Computability, Complexity and Languages book written by Davis in page 79)

$Definition.$The set $B\subseteq N$ is called r.e. if there is partially computable function $g(x)$ such that
$B = \{x \in N | g(x) \downarrow\}$

Halting problem is set of $(x,y)$ which program with number $y$ halts on $x$, I really can't understand when there is no program for Halting problem then what $g(x)$ is going to be applied for it?


texts:
I have read that  the NFA size (i.e., the number of states) is linear in the number of characters in the regular expression. This holds even in the presence of character repetitions.

I would like to know why is it so?

If I have a pattern like this , [b-d]at then the number of states will be just 4 incase of NFA ? Size of DFA for this regular expression will also be 4?


texts: How can I argue that $3\mathsf{SAT}\leq_p \mathsf{IndSet}$ is polynomial in time?

texts:
Given the reduction $3\mathsf{SAT}\leq_p \mathsf{IndSet}$ as follows:

How can I argue that it's in polynomial time? I understand how the reduction works, but even though it appears rather trivial, I can't explain why it's efficient.

  To place $\mathsf{IndSet}$ in $\mathsf{NP}$-Hard, we will show $3\mathsf{SAT}\leq_p \mathsf{IndSet}$:

  Given
  $$\phi=\bigwedge_{m=1}^{n}(x_m\vee y_m\vee z_m)$$
  with $m$ clauses, produce the graph $G_\phi$ that contains a triangle for each clause, with vertices of the triangle labeled by the literals of the clause. Add an edge between any two complementary literals from different triangles. Finally, set $k=m$. In our example, we have triangles on $x,y,\overline{z}$ and on $\overline{x},w,z$ plus the edges $(x,\overline{x})$ and $(\overline{z},z)$.

  We need to prove two directions. First, if $\phi$ is satisfiable, then $G_\phi$ has an independent set of size at least $k$. Secondly, if $G_\phi$ has an independent set of size at least $k$, then $\phi$ is satisfiable. (Note that the latter is the contrapositive of the implication "if $\phi$ is not satisfiable, then $G_\phi$ does not have an independent set of size at least k".)

  For the first direction, consider a satisfying assignment for $\phi$. Take one true literal from every clause, and put the corresponding graph vertex into a set $S$. Observe that $S$ is an independent set of size $k$ (where $k$ is the number of clauses in $\phi$).

  For the other direction, take an independent set $S$ of size $k$ in $G_\phi$. Observe that $S$ contains exactly one vertex from each triangle (clause) , and that $S$ does not contain any conflicting pair of literals (such as $x$ and $\overline{x}$, since any such pair of conflicting literals are connected by an edge in $G_\phi$). Hence, we can assign the value True to all the literals corresponding with the vertices in the set $S$, and thereby satisfy the formula $\phi$.

  This reduction is polynomial in time because $\Huge\dots?$

I've looked at many different examples of how this is done, and everything I find online includes everything in the proof except the argument of why this is polynomial. I presume it's being left out because it's trivial, but that doesn't help me when I'm trying to learn how to explain such things.


texts: How to show that a non-empty $L$ is recognizable iff there exists a total computable function whose range equals $L$

texts:
This almost makes sense to me, but I feel like I'm missing something.

I know that for a decidable language, there must exist some total computable function $f$ that can take in any $x \in \sum^{*}$ and tell us whether or not $x$ is accepted (while my textbook is unclear, I would infer from this that decidable languages and computable functions are equivalent?)

So I can see that $L$ is decidable if and only if some computable function can determine if $x \in L$ or not, which implies the existence of a function $f(x)$ that outputs $x$ if $x \in L$, and nothing otherwise (this makes sense in my head at least...correct me if I'm wrong). How would I use what's given to show that this is true for any recognizable $L$ though? Computable functions have finite steps have to halt, from my understanding, so how that they be used to check if $x$ belongs to a recognizable but undecidable language?


texts: almost realtime push down relation vs realtime pushdown relation?

texts:
Almost realtime pushdown relation pop a symbol for each empty step.
Realtime pushdown relation does not perform any empty step.

What do they mean by empty step?


texts: confusion due to the apparent difference in semantics of two beta reductions

texts:
Let us consider the following lambda expression  :

$ (\lambda func.\lambda arg$ $( func$ $ arg)$ $\lambda x.x)$

so  $ (\lambda func.\lambda arg$ $( func$ $ arg)$ $\lambda x.x)$
can be seen as $ (\lambda func.(\lambda arg$ $( func$ $ arg))$ $\lambda x.x)$
and will be in a form $ (\lambda x$$.M) N$ form.

As such this can be perceived to be a function which is taking $ N $ as an argument .  Hence here $ func $ takes the value of the argument .

Now $ (\lambda func.\lambda arg$ $( func$ $ arg)$ $\lambda x.x)$ , if I am not wrong can also be seen as

$ (\lambda func.((\lambda arg$ $( func$ $ arg))$ $\lambda x.x))$ and can be seen in a form $ \lambda func.($ $( \lambda x .M)N$) thereby $x$ taking the value of the argument .

Now by church rosser theorem both the beta reductions should lead to equivalent expressions , however here the argument being taken up by two different bound variable makes me doubt the semantic consistency .

How is the semantic inconsistency , resolved ?
(I think this might be stemming from some big gap in my understanding )


texts:
I have

two red-black trees $T_1$ of black height $H_1$ and $T_2$ of black height $H_2$
such that all the nodes $N$ belonging to $T_1$ are less than (in value) all the nodes $N$ of $T_2$
and a key $K$ such that $K$ is greater than all the nodes of $T_1$ and less than all the nodes of $T_2$.

I wanted to devise an algorithm to combine $T_1$, $K$ and $T_2$ into a single red-black tree $T$.

I could delete each element from either $T_1$ or $T_2$ and put it in other tree. But that will give me an algorithm of time-complexity $2^{H_1}$ or $2^{H_2}$ (depending on the tree from which I have deleted the elements from). I would like to have an algorithm which is $O(\max(H_1,H_2))$.

  Definitions :  Black-height is the number of black-colored nodes in
  its path to the root.

  Red-Black tree : A binary search tree, where each node is coloured
  either red or black and

  The root is black All NULL nodes are black
  If a node is red, then both its children are black
  For each node, all paths from that node to descendant NULL nodes have the same number of black nodes.


texts: An algorithm to find the closest match between 2 arrays of RGB pixel tuples

texts:
So I'm looking for a bit of an abstract algorithm and I'd appreciate any references to read up on. This is a bit tough to explain but I'll try my best.

Suppose we have 2 arrays of RGB pixel tuples-

A -> {(56, 39, 75), (125, 222, 32), (156, 201, 102)}

B -> {(125, 195, 93), (53, 31, 67), (118, 219, 48)}

I'd like the sort the second array in such a way that for each index of the 2 arrays, the corresponding RGB tuple pairs have the least deviation in value such that the optical difference between the 2 tuples is imperceptible to the human eye. For example, the difference between (122, 36, 18) and (126, 31, 25) is imperceptible, this is what we want.

For the example arrays A and B, I think sorting B like so will keep the arrays as optically identical as possible-
{(53, 31, 67), (118, 219, 48), (125, 195, 93)}

Constraints

Both arrays are of same length
The RGB pixel tuples themselves must remain unchanged, only their order in the array should be changed.
The first array must remain unchanged, only the second should be sorted accordingly
There may not be enough optimal elements in the second array to provide a perfect/good match, in this case the least amount of sacrifices will be preferred. The end goal is for the new pixel array to be as identical to the original array as possible. The least amount of sacrifices will ensure that the arrays of pixels, when turned into a picture, will look as identical as possible.
Note: By the word "sacrifice", I mean when the deviation in 2 pixel tuples is enough for the human eye to notice a difference.


texts: Delete a range of keys in a binary search tree in better than $O(n\lg n)$?

texts:
Obviously, the brute force method of:

DeleteRange(root, low, high)
    for n = low to high
        if n == root.key // key found
            return DeleteNode(root) // O(lg n) to delete
        elseif n < root.key // in left sub-tree
            root.left = DeleteRange(root.left, n, high) // recur into left sub-tree
        elseif n > root.key // in right sub-tree
            root.right = DeleteRange(root.right, n, high) // recur into right sub-tree
        else // root.key == null, key not found
            return null
   return root

would take $O(n\lg n)$ time. So is there any "smarter" way of deletion that would do the same thing with less complexity, perhaps pruning entire sub-trees at once? Assume that the deleted nodes are not needed and the only concern is with returning the root of a binary search tree where the nodes between the range of two keys are deleted.


texts: Are all databases reducible to this ultimate abstract database design?

texts:
I've designed a few databases in my time, and on more than one occasion the drive to abstract common elements from specific tables has led me to create generic top-level tables which contain those common elements.  For example:

Table      Column         Column

Hamburgers Item           Topping
           Cheeseburger   Tomatoes
           Mushroomburger Swiss

Could be "simplified" ("normalized") as:

Table      Column         Column

FoodTypes  ID             Name
           1              Hamburger
           2              Topping

Food       Item           TypeID
           Cheeseburger   1
           Mushroomburger 1
           Tomatoes       2
           Swiss          2

Recently I've gone over the deep end with this approach, abstracting and re-abstracting a fairly complex database design until I was left with something both very simple and yet completely un-resembling of the actual data being stored.

This has led me to the conclusion that all databases could be "summarized" in a single monstrous table called "Entries" with columns:

ID       Type     Value1     Value2

For example:

ID       Type     Value1     Value2
4321     Item
8746     Descrip  4321       Food
5673     Item
9876     Descrip  5673       Hamburger
0341     Item
1234     Descrip  0341       Lettuce
5478     Relation 5673       0341
2381     Descrip  5478       Topping
2244     Relation 5673       4321
2160     Descrip  2244       Class
4436     Relation 0341       4321
7547     Descrip  4436       Class

Here, using these 4 columns in 1 table, I have created two objects sharing a common superclass, given them an attribute, and defined not only a relationship between them but the class of that relationship as well.  We could now say "Lettuce is a Topping of Hamburger, both of which are Foods".

There would of course be a set of rules for this system, but that is beyond the scope of this question.

My question is, is this not logically the case?  If so (or if there is a different, "correct" answer), what is this in relation to real databases?  Does such a system exist, or should it not?

I'm not sure if I've gone far enough in my analysis, and I feel like I'm on the verge of some insight which is profoundly obvious to mathematicians and computer scientists (like "yes, all relational data can be described in terms of binary operands like F[a, b]).


texts: What data is stored in the symbol table for a number token?

texts:
I'm reading the Dragon Book. The following is from the start of Section 3.1.3.

  When more than one lexeme can match a pattern, the lexical analyzer must provide the subsequent compiler phases additional information about the particular lexeme that matched. For example, the pattern for token number matches both 0 and 1, but it is extremely important for the code generator to know which lexeme was found in the source program. Thus, in many cases, the lexical analyzer returns to the parser not only a token name, but an attribute value that describes the lexeme represented by the token; the token name influences parsing decisions, while the attribute value influences translation of tokens after the parse.

From what I understand the symbol table stores the variable name and the some details like the type, scope etc. So if a character 0 is found by the lexical analyzer, it matches the pattern for a number so it uses the token name number so the token becomes <number, attrb>.

As per the snippet I have cited above, I don't understand what data is stored in the symbol table for numbers. Is the value of the number stored in the symbol table?


texts: What is the time complexity of this nested loop code?

texts: In this loop $j$ is dependent on $i$, and $j$ is executing like $n/2$, $n/2-1$, $n/2-2$, ... So does this sum up to $O(n\log n)$?


texts: Prove that REG is closed against removing all but lexicographicaly largest words (per length)

texts:
Let $\Sigma_n = \{0, 1, ... , n-1\}$.  Suppose $L \subseteq$ $\Sigma^*_n$, and let
$\qquad\displaystyle\mathcal{B}(L) = \{ x \in L : x = \textrm{lex}\max L_m, m \in \mathbb{N}_0 \}$,
where $L_m = L \cap \Sigma_n^m$ and $\mathrm{lex}\max$ denoting the lexicographic maximum.
For example, $\mathcal{B}(\{0,1\}^*) = 1^*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^*) = (10)^*(\epsilon \cup 1)$.  Prove that if $L$ is regular, then so is $\mathcal{B}(L)$.

Any hints?  I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.


texts: Calssifying the Partitions of the problem Cycle Decomposition of Markov Chains

texts:
The book Cycle Representations of Markov Processes
 solves the problem of Mapping Stochastic Matrices induced from a Markov Chain into Partitions using a $\lambda$-preserving ($\lambda$ is a Lebesgue Measure) transformation of the interval $f_{t} = (x+t) \bmod t$ ( $t$ is the rotational length to be considered is $\frac{1}{n!}$) but don't explain if the partition is a Markov Partition or a Generating Partition.  I searched several references looking for this proof but there is nothing written about these partitions. If these particular partitions are Markov, how to prove this fact?


texts:
The rule is that an isolated lit square in a grid of squares must be paired in the x-direction (either immed. left or right of it) AND y-direction.  That is, from surrounding cells, the closest lit or on square moves to the isolated square to join it in the x or y-direction, and the isolated square moves to the one moving towards it, in the most efficient manner, and also another surrounding one must pair in the y-direction if paired first in the x-direction, so that an isolated square must be paired in the x and y-direction.

Also, say you have a large square of many completely lit squares, and an isolated square to the left at some distance.  Then a small square of 4 squares pops out and moves (all at once, because in the rule there is an additional rule that when choosing to pair in the x or y-direction of an isolated lit cell, the ones to pair do so to maximize both x and y pairing, so here, one small square would pop out, then the one immediately behind it joins the first behind it (because if only the one above moved to join in the y-direction, it would not be paired in the x).  And you can see that as squares move to the one isolated, they too must be paired from surrounding as they move in the most efficient way.  When the small square of 4 leave the large square, there will be a small indention in the large square.

This is a programming where the closest lit squares move together to pair isolated squares, and wonder if it would be any more computationally intensive than a regular automata where there is no "movement" like this, but rules on turning on or off cells.  No cells are born or die here.


texts: Find minimum number of time points that cross out all intervals

texts:
Say we have a set of time intervals, that may intersect. A time point "marks" all of the intervals that are still unfinished at that time point. I wish to find an algorithm so that I can mark all of the intervals using the least amount of time points. E.g. if all of the intervals have not finished at time 6, one point is enough, as point 6 it marks all of the intervals of the problem. Starting and ending time points ( [s(i),e(i)) ) for each interval i are given. Time points are integer values.

The point i marks intervals that have started before i and finish after i, or intervals that started exactly at i.

Obviously, I would like something better than plain out trying all possibilities.

I have tried a greedy algorithm, more specifically choosing the point that marks the most intervals at a time (it is easy to see that it is only worth considering points at which an interval starts), removing the intervals it marks and repeating with the remaining intervals. I have found counter-examples showing it does not always give correct results.

The next try would be dynamic programming, which I am breaking my head with right now. However it gets too complex. In the recursive calls I have to make a call for the possibility that the time point checked will be included, and one for the possibility that it will not. However, I must find a way to select a time point anyway, in the case not selecting it will lead to intervals not being marked at all - in that case, I must recognize that before proceeding to the next recursive calls, as I will get false results. It also is a problem how I will keep a record of which intervals proceeded to the recursive call unmarked, without taking too many actions that will increase complexity.

Interval graphs might give me some ideas. If we are talking about interval graphs the problem can be expressed like this: Suppose we have a graph. The nodes are NOT the intervals, but the starting points of each interval. If a starting point of an interval 1 intersects with an interval (at any of its points) interval 2, then its node is connected to the starting point node of that interval 2 with a directed edge. Choosing to mark a node removes the said node and all the nodes it is connected to. What is the least number of markings I must execute in order to erase the whole graph?


texts: Sorting array with at most two inversions

texts:
I have created an algorithm to sort an array of size $n$ with at most 2 inversions with exactly $n$ comparisons in the worst case.

I have no idea how to prove that it is optimal in terms of the number of comparisons. The only argument which came up to my mind is that we of course have to read the whole array, but I don't think it is a proper argument. I tried to use argument similar to minimal number of comparisons to find minimum (with graph), but it doesn't seem to be good in that case.

How can I prove that $n$ comparisons is optimal in the worst case?


texts: Supporting material for theory of computation

texts:
Possible Duplicate:
  List of intro TCS books for those who don’t know much about TCS

Im taking a course on Theoretical  computer Science. and I use Sipser's Introduction to Theory of Computation as my reference manual. However, many times I find myself lost in the proofs. Ive tried following Shai Simpson's online lectures ,but would prefer something more watered down and easier to understand. Im open to any pointers/strategies or resources.


texts: What makes a common programming language non-context-sensitive but RE?

texts:
I have a vague understanding that a (sane) programming language is RE as they are Turing-complete, being able to describe any Turing machine.

But I cannot pinpoint what aspect makes a programming language RE, not context-sensitive. For example, I'm guessing the variables in any scope structures like for can be described in a context-sensitive grammar with a fairly bulky (but finite) number of production rules.

One wild guess is that it's because of pointers or references, making it impossible to describe with a finite number of production rules. Can anyone teach me about why it is?


texts: What is the average degree of a complete graph and why?

texts:
Is it correct that the average degree of a complete graph $K_n$, is $(n-1)/n$? or is it only $(n-1)$?

I have the answer of my professor which is $(n-1)$, but I didn't understand why.


texts:
Given a procedure/function

$Select(S,r)$ - which selects element of rank r from set S
which uses at most $|S|. constant$ comparisons

We design another function $Multiselect(S,R)$
with $R =\{r_1<r_2<...<r_k\}$
returns $X =\{x_1<x_2<...<x_k\}$  such that rank of $x_i$ is $r_i$

What is the minimum no of comparisons for this function?

From Wikipedia I found the upper bound for it -

But while utilising this for deriving the answer I got it totally messed up!
I tried using algorithm to utilise Select(S,r) repeatedly each time
each time decreasing the search space by logn  ... but I guess the answer could be found
in a more concise mathematical way.

By the way, answer given was - $constant.|S|(1+logR)$


texts: Right equivalent elements arising in the proof of the Schützenberger Theorem

texts:
As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{[1]}$). My question arises on page 193 in line 11, namely in the equation: $$" \gamma ( f x ) M ( = mM = mM \cdot M)"$$
But I will break this down in my own words to make this understandable (hopefully).

Let $M$ be an aperiodic monoid, $\Sigma$ a finite alphabet and $\gamma : \Sigma^* \to M$ a surjective monoid-homomorphism. Fix an element of $m \in M$, whose generated right ideal satisfies $m M \neq MmM$ and $mM \neq M$.
With these define the language $L = \gamma^{-1}(mM)$ and $\hat{L} = L \setminus (L\Sigma^+)$ (one can prove that $\hat{L}$ is the smallest set satisfying $L = \hat{L}\Sigma^*$) and $M'' = \{m'\in M \mid \gamma^{-1}(m')\Sigma \cap \hat{L} \neq \varnothing\}$.
For a fixed $m' \in M''$ one can find a $w \in \gamma^{-1}(\{m'\})$ and a $\sigma \in \Sigma$, such that $w \sigma \in \hat{L}$.
Now one has to show, that $mM = \gamma(w \sigma) M$.

Well in my opinion $\gamma(w \sigma)M \subseteq mM$ is rather easy, because $w\sigma \in \hat{L} \subseteq L$, therefore $\gamma(w\sigma) \in mM$, which implies ($M \cdot M = M$) this direction.

But I have trouble proving the opposite direction. I gladly appreciate every hint you give me, because I seem to have some kind of blockade in thinking about this. My guess is that the special property of $\hat{L}$ (above in parentheses) is somehow involved.

Reference:
$^{[1]}$ M.P. Schützenberger. On finite Monoids having only trivial subgroups. Inform. and Computation, 8:190-194, 1965.
A copy can be obtained here: Schützenberger Theorem


texts: How to determine index being access in memory

texts:
Having 4GB byte addressable main memory in 32-bit system divided into block of size 1024 bytes.
If processor wants to access a memory location 0xFC347004. Corresponding block is found in cache.

Which index, within this block, will be accessed?


texts: Boosting algorithms: Confusion between "weak classifiers" versus "number of boosting rounds"

texts:
I've been reading up on boosting algorithms.

I understand that the main crux of the algorithm is to build weak classifiers that are slightly better than random guessing, and then to add them up so that we end up with a strong classifier. This is done via "boosting rounds".

With different papers using different variables, like k, n, m, etc, it's gotten a bit confusing.

I just want to confirm, if I run a boosting algorithm for, say 150 rounds, is that equivalent to saying that I'm training 150 weak classifiers? I mean, is a weak classifier the output of one boosting round?


texts: Amortizing or batching circuit evaluation for many different inputs?

texts:
Suppose that I have a boolean function of size $k$ with $n$ inputs. I would expect to be able to evaluate it on all possible inputs in time $O(k*2^n)$ simply by calculating all the intermediate values for every possible input. Is it possible to do this faster in general, for example in time $(k+2^n)$?

In the special case of linear functions I would expect to be able to do this by going from point to point in gray code order, so that only one bit changes each time, or by calculating tables of size $1,2,4,8,\dots,2^n$ for the functions produced by holding the last $n-i$ bits at zero, using each table to calculate the next one. Are there generalizations of this for general boolean circuits, or are there proofs that no such generalizations are possible?

I have a slightly off-the-wall motivation for this. I am interested in the simulation hypothesis. One reason for running a large number of simulations would be to investigate the result of running the same scenario for all possible inputs.
I would be interested to learn that there was, or was not, a significantly more efficient approach which would achieve the same ends, especially as such a more efficient approach would not have a direct link between any particular set of simulated histories and any particular act of the program, as the increased efficiency of the program would be mean that it could not be the case that every possible history could be mapped to its own set of program activity.

Edit - batch calculation as described above is more powerful when the batch step is used inside a recursive call, as then you don't need to go through all 2^n answers at once. For #P-complete problems, each recursive call returns the number of solutions found within some range of values. For NP-complete problems, each recursive call returns whether a solution is found in some range of values.

Each recursive call uses the batch mechanism to compute the answers for 2^k different problems. This corresponds to k bits of the n bits available. So the lowest level of the recursion just looks at 2^k different results to see whether they are solutions or not, but the highest level looks at 2^k results which are each e.g. the number of solutions found within 2^(n-k) evaluations, each with the k top bits of n set to a different value. Here I assume that the language used to express our function f() is sufficiently flexible that level i+1 can treat level i as just a function f() to consider at 2^k points, even though this f() amounts to a transformation of the original f() producing a function which counts the number of solutions in a particular range or says whether this number is non-zero.

If the cost of level i+1 of the recursion is X_i+1 = b + a*X_i then for a!=1 we get
X_i = a^i + b/(1 - a) and for a=1 we get X_i = ib (with variations depending on what X_0 is). Remember that the number of possible solutions examined at each level is 2^(ik) so for small a compared to 2^k this is a large speedup, and for the case of a=1 we would find that P=NP and even P=#P.

(I remain interested in answers that would firm this up or extend this)


texts: Algorithm for finding two vectors that span a plane

texts:
My problem is as follows. I am working on an experiment where I need to align a 3D vector with spherical coordinates $\vec{v} = (r, \phi, \theta)$ (red) to an infinite 1D line (blue). That line lies, at some unknown angle $\xi$, in an infinite 2D plane, with unknown vector span (green).

To do this alignment, I can independently vary $\phi$ and $\theta$ and measure some signal $S$. However, my 'vision' is limited; I have two 'signals' that I can measure, $S_P$ and $S_L$, where $S_P$ is maximal when the vector is in the plane and quickly reduces in visibility when it is not, and $S_L$ is maximal when the vector is parallel to the line, and quickly reduces in visibility when it is not. $S_L$ is thus very hard to use from a random starting vector; it pretty much only works when I am already in the plane. $S_L$ is less stringent; it is visible when you are close to being in plane, from which I generally start.

My idea is therefore as follows: in spherical coordinates I algorithmically control $\phi$ and $\theta$ while monitoring $S_P$, to find two vectors that span the plane. I use these two vectors to set up a new polar coordinate system of that plane, in which I can then sweep the polar angle to find $\xi$ and maximize $S_L$.

The second part should be trivial, but the first part is what my question is about. How do I algorithmically find two vectors that span the plane, controlling $\phi$ and $\theta$ and monitoring $S_P$?

As it currently stands I can find a single vector that works by simply varying $\phi$ and $\theta$ until $S_P$ reaches a maximum in both parameters simultaneously, but how do I go from there to find a linearly independent vector that is also in the plane? How should I algorithmically 'walk' through $\phi,\theta$ space to find that other vector? I say walk because what I envision the method to be like is that I start from the local maximum, 'overrotate' in $\theta$, bring $S_P$ back up with $\phi$ and overrotate, that one a bit, and then go back to theta and repeat. That will walk me through the angle space, but how I use this to find the second vector I don't see.


texts: Prove that the set of recursive languages is infinite

texts:
I know that set of all deciders is countable. I am wondering whether it is infinite.In other words can we prove that the set of recursive languages is infinite ?

Edit : The above question has small mistake as pointed out in one of the comments .. Since every recursive language has infinitely many deciders .. the two questions are indeed not equivalent . For people who are wondering why there are infintely many deciders , take a decider D and keep on adding some useless states, transitions, tape symbols so that you get new decider with a larger description than D and since you can continue this process indefinitely , there exists infinitely many deciders for a recursive language.


texts: Show that the set of TMs that can write z is undecidable

texts:
I want to show that

$\qquad L =  \{\langle M \rangle \mid \text{TM $M$ will write a $z$ to the tape at some point for some input}\}$

is undecidable.

I'm really not sure how to show this is undecidable. I know that a language is undecidable if M would not be able to determine if 'z' is or is not in the language.


texts: Is relational algebra a procedural, imperative, and/or declarative language?

texts:
In Database System Concepts 6ed,

6.2 The Tuple Relational Calculus
When we write a relational-algebra expression, we provide a sequence of procedures that generates the answer to our query.
The tuple relational calculus, by
contrast, is a nonprocedural query language. It describes the desired information
without giving a speciﬁc procedure for obtaining that information.
A query in the tuple relational calculus is expressed as:
{t | P(t)}. That is, it is the set of all tuples t such that predicate P is true for t.

Does the above mean that relational algebra is a procedural language?
Is relational algebra a declarative language?
Is the tuple relational calculus  a declarative language?
Is the tuple relational calculus more declarative than relational algebra is?
Is a procedural language  an imperative language? (This is always what I heard, but I also  heard that SQL is a declarative language (so is relational algebra) so is not imperative.)
What is the correct or most reasonable or most accepted definition of procedural languages, imperative languages, and declarative languages?
Thanks.


texts: How does continuous computer vision works?

texts:
First: I have programmed a few programs dealing with computer vision (not with libraries but from scratch):

Simple Character and Figure Recognition
Character and Figure Recognition with Neural networks
Facial recognition

so I am not asking for details on these.

The characteristic of all my programs is that once you focus your camera on something you want to analyze, you hit a command (it can be through several means- serial, voice orders, etc- it is not relevant how) and the system takes a photo and analyze it, then produce a result in some cases the camera is deactivated since it is resource intensive.

Following all that introduction,
my question is:

How do the programs that do continuous recognition work?

You have seem them, the camera is all the time on and it continually recognize or process things. Does it just do all the processing every frame? Or perhaps do the processing in a multithreaded way (for resource intensive processing)?

My apologies if the question is too beginner-like. I would really like to modify my work and increase my knowledge


texts: Strict polynomial hierarchy and reduction

texts:
The following exercise gives me headaches:

  Show: If the polynomial hierarchy is strict (i.e. $\forall k \in \mathbb{N}. \Sigma_k \neq \Sigma_{k+1}$), then there is no $\text{PH}$-complete problem for polynomial-time reductions (i.e. there is no problem $\text{P} \in \text{PH}$ such that each problem in $\text{PH}$ can be reduced to $\text{P}$ through a function $f \in \text{FP}$).

The exercise describes in detail what has to be shown, but my issue is that I don't know how to show this. Can somebody please help me?


texts: Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm

texts:
Roughly, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain.

The algorithm specifies splitting the edges at their midpoint (except in the case of small input angles where concentric circular shells as suggested. This question is unrelated to these cases.)

In certain domains, given a segment, there are points on the segment that I would prefer to split on that are not necessarily the midpoints (unrelated to the concentric shell trick). These points are chosen based on some domain specific underlying data (considerations beyond the graph structure the algorithm is aware of).

What are the implications of splitting on non-midpoints?
What needs to be taken into consideration when selecting among several non-midpoint candidates?
Does splitting on non-midpoints affect any of the convergence properties
of the algorithm?

Another way to ask this is: Are there split points that are better than the a-priori selected midpoints?


texts: In a programming contest I've encountered a problem which is for sure a linear programming problem. I know quite a lot about LP (the simplex method, its exponential complexity, interior point methods, their polynomial complexity, etc.), yet I stumbled upon it. What is the simpliest algorithm for linear programming by means of implementation? Is there an algorithm I can implement in Python or C++ under tough time limitations?


texts: Hypergraph sorting computational complexity

texts:
For a hypergraph, I want to know the computational complexity of this step in my algorithm what is the computational complexity of this kind of sorting

Sort the hyperedges in descending order based on the number of common vertices with other hyperedges

I implement this step by calculating the degree of each vertex (the number of hyperedges it belongs). Then, for each hyperedge, I count the number of vertices that have degree greater than one and order the hyperedges

So the time complexity is $O(M+|\mathcal{E}|K_c+ |\mathcal{E}|)$ is it correct assuming that we have M vertices


texts: Is regex with backreference still able to be implemented by finite automata?

texts: I recently learned that regex support backreference which enables referring to a matched group in the pattern itself. E.g. a regex (.)\1{2,} matches two or more consecutive appearances of the same character like 'aa', '...', '------', etc. However, such feature seems exceeds the capability of finite state machine which is the underlying implementation of regex. It seem like it needs to remember the matched part and match with it again, but the matched part its self have infinite possible values. I'm just speculating but have no idea to prove or disprove it. My doubt is, does the regex with backreference still have finite number of states?


texts:
I was given the follow proof:

$$T(n)=n+2T(\frac{n}{2})$$ Will prove that $$T(n)=O(n*logn)$$

For $2:$

$$T(2)=2+2T(1)=2\leq 2*log(2)$$

Assume it is correct for $n-1$ in particular for $\frac{n}{2}$ and prove for $n$:

$$T(n)=n+2T(\frac{n}{2})\leq n+2(c\cdot \frac{n}{2}\cdot log(\frac{n}{2}))=n+cn(log(\frac{n}{2}))=n(1+c(log(\frac{n}{2}))$$

$$=n(1+clog(n))=n+c\cdot nlogn$$

Why is it $O(n*logn)$ and not $O(n)$?


texts: Relationship between depth and the vertical displacement of the object between two frames

texts:
I am trying to find the relation between the vertical displacement of an object to the depth of the object.

Say, there is an object in an image and as the center of gravity of this object moves vertically upwards, we know that it is moving away from the camera.

We know at the same time, that the dimension of the image would reduce because the object is moving away from the camera.

So, two things are happenning - 1 . the objects center of gravity is moving up vertically and 2. the object dimension is decreasing because the object is moving away from the camera.

Is it possible to find a relationship between "the vertical displacement of the object from one frame to another frame" and "the distance  of the object from the camera from one frame to another frame" ?


texts: Where do you exactly use data structures?

texts:
I know what data structures is, How it works & importance of it. I just have some doubts on where do we actually use it.

When database can do filtering, fetching, sorting efficiently, Why we need to use data structures in db data?

I was working on a project which uses Cassandra database. In that I'd to filter data based on two fields. The two fields are indexed. But I can't filter it as it will force me to use Allow filtering but It's not a recommended one.

In this case I thought to fetch rows filtered by one indexed column & rest by our program (Java/Python etc) so we need to use better data structure here. Is this a correct approach? If not what's the solution for these kind of problems?

Let's assume I've billions of list of string data in a db table, I want to use it for autocomplete for that it's better to use tries data structure, How can I do this? fetch all data into memory and process?

If my approach is wrong, Are data structures mainly used for in memory data?


texts: prove sufficient number of comparisons for the merge problem

texts:
It is given two subsequences. Their length are following: $2$ and $5$.
I can show that lower bound of comparisons is $5$. My problem is that I can't show that $5$ is sufficient number of comparisons to merge these subsequences.
In order to show lower bound I use tree of comparisons (number of leaves is $21$, so height is at least $5$).
However, when it comes to proof of sufficient number of comparison I have no idea.  The only idea that comes to my mind is following:
Let our subsequences will be: $(a, b)$ and $(c, d, e, f, g)$. Let say, that we must use $k$ comparisons to find place for $a$, where $k\le 5$. Now, because of fact that $b\ge a$ we must do at most $5-k$ additional comparisons. Thus, $5-k+k=5$.
What about this proof ? Maybe you have other approach?


texts:
In my world there are nodes and lines, I want to see if there is any path between node A, and node B, that do not cross any line(including the lines of the path itself) and do not go thru the same node twice. What would be the efficiency of such algorithm and where can I find more information about it.

So far I been reading about A* algorithm, but I do not need the shortest path, just to see if there is any path like this exist at all.


texts:
T (n) = T(√n) + 1
The easy way to do this is with a change of variables. Let m = lg n and
S(m) = T (2^m).

T(2^m) = T (2^(m/2)) + 1

S(m) = S(m/2) + 1

Can any one explain why 1 and 2 are same and this works ??


texts: How to explain that a program that runs in NTIME(O(lg n)) is in the class P?

texts:
if a non-deterministic program executes only lg(n) decisions on each branch of the computation tree, then the problem this program solves is in P? That means, there is a deterministic algorithm that computes the solution in a polynomial time.
The answer yes looks intuitive to me when I'm looking the tree, but I don't know how to actually "proof" that


texts: Mixed integer non convex optimization problem

texts: If an optimization problem is mixed integer non-convex problem. The optimal solution by applying brute exhaustive search is infeasible to be applied in practice due to high complexity i.e. $O(N^K)$. Can we say that it's NP hard problem? If yes, can someone explain with more details.


texts:
Consider the code $C=\{c=(c_1...c_n): c \in \Bbb F_q^n, c_1=c_n\} \subset \Bbb F_q^n$.

I was able to prove that the code is a linear code because it is closed under addition and scalar multiplication.
Also, it is clear that the length is n.

However I am having a hard time with minimum distance, dimension, and size.

For minimum distance: I know that for a linear code the minimum distance is equal to the minimum weight, or number of places with nonzero entries, of all nonzero codewords in C. However, I think the minimum weight can range between 1 to n entries, so does this mean that the minimum distance is 1?

For dimension and size: I know that the dimension is the order of the basis for C. I think that the basis is $B=\{10...01, 010...0, 001...0, ... , 0...010\}$, and so the dimension would be $n-1$, but I am unsure on this.
If the dimension is $n-1$, then the size would be $q^{n-1}$.

Any help is appreciated, thank you in advanced. Please also let me know if this post does not belong to this stack exchange.


texts: Proving that the shortest simple path problem between two vertices $s$ and $t$ in a graph is NP-complete

texts:
How to show that the shortest simple path problem between two vertices $s$ and $t$ (finding a minimum weight path between $s$ and $t$) in a graph is NP-complete? I saw the following proof in a combinatorial optimization lecture, which I didn't understood (I stressed the moment that I didn't understand).
Let $P_1$ be the Hamiltonian path problem:

The Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete. From Wikipedia.

Does it exists an Hamiltonian path in $G$?
Let $P_2$ be the shortest path problem in a directed graph.
If $G$ is the graph within which we search such a Hamiltonian path, we transform $G$ into $\hat G$, replacing each edge $(i,j)$ with two edges $(i,j)$ and $(j,i)$.
For each edge $\{i,j\}$ in $G$, we erase $(i,j)$ and $(j,i)$ from $\hat{G}$, give a weight of $-1$ to all remaining edges, and calculate the shortest (simple) path from $i$ to $j$. If the path length is $-(n-1)$, then this is a Hamiltonian path in $G$. If we found no such path going over all edges, then $G$ has no Hamiltonian path.

Why is is the case that if the path has length $-(n-1)$ then it constitutes a Hamiltonian path in $G$?
Why if not such path has length $-(n-1)$ then $G$ has no Hamiltonian path?

Maybe if you were kind to help me understand with a visual example I would better understand?
Last but not least, how did we proves that Hamiltonian path is NP-complete?


texts: Need help analyzing the runtime analysis of this algorithm/algorithms in general

texts:
This is the algorithm I was trying to find the runtime of (doSomething) -
Procedure findMinMax(int A[], int start, int end)
int min = max = A[start]
int i = j = start
for(int k = start; k <= end; k++)
if(A[k] < min)
i = k
min = A[k]
if(A[k] > max)
j = k
max = A[k]

end for
return {i, j}
end findMinMax

Procedure swap(int A[], int i, int j)
int temp = A[i]
A[i] = A[j]
A[j] = temp
end swap

Algorithm doSomething(A[])
Input: array A of N integers
Output: ?
int i = 0
int j = N-1
while(j - i > 0)
int[] minMax = findMinMax(A, i, j)
int min = minMax[0]
int max = minMax[1]
if(min == j && max == i)
swap(A, min, max)
else if(min == j)
swap(A, i, min)
swap(A, j, max)
else if(max == i)
swap(A, j, max)
swap(A, i, min)
else
swap(A, i, min)
swap(A, j, max)
i++
j--
end while
return A
end doSomething

The indenting of the code is bad in the code block, so here is an image of the code with proper indenting if that helps -
The while loop runs n/2 times. This is because i is always incremented by 1 at the end of the while loop and j is always decremented by 1. None of the helper methods called inside of the while loop and none of the other constant time statements called changes i and j, so the while loop ALWAYS runs n/2 times.
Inside of the while loop, the swap functions are called. These are of O(1) constant time and don't affect the runtime. But, findMinMax is also called, which has an O(N) runtime.
In my eyes, I thought that the overall runtime of doSomething would be O(NlogN). The while loop running n/2 times would be equivalent to something like: "for(int i = 0; i < N; i += 2)". That for loop by itself (not considering what is inside of it) has a runtime of O(logN). I figured the same logic applies here and that the while loop has a runtime of O(logN). Multiply that by the runtime of findMinMax which is inside of the while loop body and you get O(NlogN).
However, the answer key disagrees. The answer key states that the runtime of the algorithm is O(N^2).
The reasoning is -

That doesn't really make sense to me. Why was a summation used? I thought they were only used to find runtimes when there was an inner loop dependent on the outer loop. Furthermore, why does 2k or 2k + 1 go inside of the summation?
I also tried using a summation for something like -
for(int i = 0; i < N; i+=2) {
   //O(1) operation
}

I got the summation -

which simplifies to N/2, and thus O(N), since the 1/2 constant gets factored out.
I obviously do not see why a summation was used for the doSomething algorithm runtime calculation, especially since there was no inner loop which depended on the outer loop (i.e. "for(j = i + 1)"). The summation logic didn't even work for that other code block I posted just above.
Any help/clarifications would be appreciated!


texts: Extracting the set of chains from a partial order

texts:
Given a partial ordered set (poset) $S$, is there a known procedure or algorithm to find the set of chains (i.e. subsets of $S$ where every two elements are comparable)?

Note: I am asking here instead of math.SE because i'm looking for an algorithm for the problem.


texts: Finding all edges on any shortest path between two nodes

texts:
Given a directed weighted graph with non-negative weights, how can I find all edges that are a part of any of the shortest paths from vertex X to Y?

In the example below the yellow edges are the solution for finding the shortest path between A and D (note that other examples may have more than one path).

I know how to find all nodes that are a part of a shortest path so I thought that all edges that sit between two nodes which are both on a shortest path means that the edge between them is also a part of the shortest path, but that is not true.

Any ideas would be appreciated.


texts: algorithm to sample function so that integral is unaffected

texts:
I have an array with a hundred thousand entries representing the x and y values of a function. Since I frequently need to integrate this function (in a product with other functions) I am looking for an algorithm that allows me to reduce the number of function points without changing the value of the integral. I am looking for a way to reduce the number from hundred thousand down to one thousand so that

$\int_{\text{ thousand}} f = \int_{\text{ hundred thousand}} f$

Right now I am taking every 100th point, but in the end I end up with an error of 10^-7 which is rather large for my application.

Is there a smart way to choose these points so that the integral remains the same?

Thanks a lot

EDIT: Since I need the actual integration to be very fast I am sort of restricted to simple algorithms like simpson or trapezoidal. So I am looking for a method to choose the integration points so that the value of the integral doesn't change for one of these two integration routines.


texts: How to construct the objective function for genetic algorithm optimization?

texts:
I am trying to optimize a coefficients of  filter by minimizing sum-squared error.  I want to use a genetic algorithm (GA) optimization wherein the coefficients of filter form the GA's chromosome (a vector).

How can I construct the objective function, given that I want it to use least-squares minimization?


texts: How to convert a centralized algorithm to a distributed algorithm?

texts: Is there any algorithm or procedure to convert a centralized algorithm to a distributed algorithm? Is there any theoretical result or relevant complexity analysis?