texts: Explaining the difference between computer science and computer literacy

texts:
What is a good metaphor or example to explain to an English major the difference between classical computer science and "being good with using MS-Windows"

computer science
computer programming
using computers

3 profoundly different things.   Most people have no idea what Computer Science even is.  They just see the word "computer". Hence, "he is a Computer Science major" can be interpreted as "He can hook up my printer".  Or that he's "good with computers". Even fewer people know the difference between computer programming and Computer Science.

Computer Science is computing theory.  CS can be learned without actual computers.   CPU micro architecture.  How to sort numbers, how to traverse lists, etc.  State machines.  Algorithms, big(Oh), etc.  How to design a programming language or compiler.

Programming is writing code and creating applications in a language and compiler created by a computer scientist.

Lastly, there is using a computer (using a GUI, mouse, and keyboard.  Internet, MS-Office, etc)

Yet all three of these are used interchangeably by laymen.

What is a good metaphor or example to explain to an English major the difference between classical computer science and "being good with using MS-Windows"   Or simply, a pithy example of how real computer science has nothing to do with using MS-Windows.


texts:
There's a problem called Cutting Sticks - we start with one stick and n points where it needs to be cut. Cutting a stick costs the length of that stick. Of course, we want to minimize the toal cost.

Example:
There's a stick of length 100, with cutting points at 25, 50 and 80 (so n = 3).
Consider two ways to cut it.

The first way, we make a cut at 25 (with cost 100), then at 50 (with cost 75 - the stick we're cutting has length 75), then at 80 (with cost 50). Total cost: 225.

The second (optimal) way would be to cut succesively at 50 (cost 100), 20 (cost 50) and 80 (cost 50), for total cost 200.

There exists an $O(n^3)$ DP algorithm. First, we use an array A to save the endpoints and the cuttingpoints (in this case 0 through 4, with 0 and 4 being the endpoints), so $A = (0, 25, 50, 80, 100)$.

Use the following recursion:

$\text{min_cost}(i, i + 1) = 0$ and
$\text{min_cost}(i, j) = A[j] - A[i] + \min( \text{min_cost}(i,k) + \text{min_cost}(k,j) : i < k < j)$

The final answer would be $\text{min_cost}(0, n+1)$

Every calculation of $\text{min_cost}(i, j)$ is $O(n)$, and we need to calculate $O(n^2)$ values, so this algorithm is $O(n^3)$.

To my actual question: I've read that the Knuth Yao DP speedup could make it $O(n^2)$. I've tried to look it up, but I can't find a good explanation what it is (I've found some short explanations which are too short, and don't help me understand it).

Could anyone explain it to me, preferably with a bit of pseudocode?


texts: Choosing array size for known number of keys in seperate chaining using mod method

texts:
If we know the number of keys that we are going to get ,how do we calculate the size of the array we will need to store our separate chains in the hashtable?

All that using the mod hashfunction


texts: Clarifying $\sum_{h=0}^{\lfloor lg(n)\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n)\rfloor}\frac{h}{2^h})$ in BUILD-MAX-HEAP

texts:
I was going the text Introduction to Algorithms by Cormen et. al. Where I came across a step in the analysis of the time complexity of the $BUILD-MAX-HEAP$ procedure.
The procedure is as follows:
BUILD-MAX-HEAP(A)
1   heap-size[A] <- length[A]
2   for i <- ⌊length[A]/2⌋ downto 1
3       MAX-HEAPIFY(A,i)

Now the authors claim to derive a tighter bound by observing that the time for $MAX-HEAPIFY$ to run at a node varies with the height of the node in the tree, and the heights of most nodes are small. The tighter analysis relies on the properties that an $n$-element heap has height $\lfloor lg (n)\rfloor$ and at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of any height $h$.
So,$$\sum_{h=0}^{\lfloor lg (n)\rfloor} \lceil \frac{n}{2^{h+1}} \rceil O(h)= O(n \sum_{h=0}^{\lfloor lg (n)\rfloor} \frac{h}{2^h})  \ldots \tag 1$$
Now it is in the above step that I am facing the problem. How are the authors getting the expression on the RHS using the LHS so simply(as if intuitively). However I do not seem to share the same intuition.
Now the maximum height of any node is the height of the root which is $\lfloor lg (n)\rfloor$. Now let us find a bound for the minimum possible value of the fraction $\frac{n}{2^{h+1}}$ ,which occurs when $h=\lfloor lg (n)\rfloor$
So, $$\frac{n}{2^{\lfloor lg (n)\rfloor+1}} = \frac{n}{2.2^{\lfloor lg (n)\rfloor}}\geqslant\frac{n}{2.2^{lg (n)}}=\frac{n}{2n}=\frac{1}{2} \ldots \tag 2$$
Now from the analysis step by the authors in (1) they are assuming
$$\lceil \frac{n}{2^{h+1}} \rceil \leqslant c.\frac{n}{2^h}, c>0 $$
Now as far as I know from mathematics,
$$\lceil \frac{n}{2^{h+1}} \rceil \lt \frac{n}{2^{h+1}}+1$$
And for the way the authors worked out , it must be the situation as below,
$$\lceil \frac{n}{2^{h+1}} \rceil \lt \frac{n}{2^{h+1}}+1 \leqslant c.\frac{n}{2^{h}}$$
So, $$\frac{n}{2^{h+1}}+1 \leqslant c.\frac{n}{2^{h}}$$
$$\iff 1 \leqslant c.\frac{n}{2^{h}}-\frac{n}{2^{h+1}}$$
$$\iff 1 \leqslant \frac{n}{2^{h+1}}(2c-1)$$
$$\iff \frac{n}{2^{h+1}}\geqslant \frac{1}{2c-1} \ldots \tag 3 $$
Now for (3) to comply with (2) we should have,
$$2.c-1 \geqslant 2 \iff c \geqslant \frac{3}{2}$$
Now is that single line in (1) worth this much effort or is it the situation that the step is trivial or intuitive that we can just mentally do the step. If it is the latter, please enlighten me with such intuition..
Even in this answer here that $\frac{n}{2^{h+1}}\lt\frac{n}{2^{h}}$ is intuitive but that $1\lt\frac{n}{2^{h}}$ is not quite intuitive and requires the use of (2) I feel


texts:
I am looking for articles relating to algorithms that deal with automatic selection of seating assignment.
I need an algorithm (preferably more than one) that can automatically select a seating place while enforcing certain constraints that are predefined.
Originally I was planning on having the seats selected on the fly, meaning whenever a new person comes, the system selects the optimal seat for him based on the seats which were already taken, but I guess it is not a must.
if there is a more general algorithm that can also present an approach fit for my problem that is also great.

Lets call the seated people "players" , and our seating domain lets picture as a 2d matrix. lets say we have several groups among our "players" and you can set your "players" anywhere within the matrix as long as they are not seated next to other "players" from their own group . I am not claiming there is a perfect solution, I am looking for articles that are dealing with some approach for giving a solution - if you can direct me to an article or even give me a name for that kind of problem it is also good for me.

Thanks,
Olaf


texts: All soldiers should shoot at the same time

texts: When I was a student, I saw a problem in a digital systems/logic design textbook, about N soldiers standing in a row, and want to shoot at the same time. A more difficult version of the problem was that the soldiers stand in a general network instead of a row. I am sure this is a classical problem, but I cannot remember its name. Can you remind me?


texts: Early termination of A* with weak heuristic if solution is known

texts:
I have a large graph G and a pair of nodes s,t.  I want to use the A* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent.

Suppose I already know of a path whose length is guaranteed to be at most 1.1 times as long as the shortest path.  Does this help A* find the shortest path faster?  If so, how and why?  Can knowledge of this path be used to improve the running time of A*, reduce the number of nodes, or make the heuristic more accurate?

One improvement I can see is to remove the all the nodes in the open list which exceed the current solution. But if the heuristic is weak, this wouldn't help in reducing the number of nodes to be explored in the open list. So, in what other ways one can use the knowledge of known path in hand to help A* terminate itself earlier than without the knowledge of known complete path.


texts:
I am trying to write IDA* for Sokoban puzzle problem (http://en.wikipedia.org/wiki/Sokoban) but It seems that my heuristic is not so good for making the algorithm fast.

My heuristic is to consider $h(s)$ as minimum  distance between the Player and Boxes plus minimum distance between a Box and a Target in state $s$.

Can you please provide some better heuristics for this problem?

Edit: consider the number of Boxes(and Targets) is at most 3!


texts: Is the following problem decidable in polynomial time?

texts:
We are given an initial set of tuples $S_0=\{(x_i,y_i)|i\in [n], \forall i:x_i,y_i\in \mathbb{N}\}$ and a number $B\in \mathbb{N}$.

At time $t$ we are allowed to remove ($S_t := S_{t-1} \setminus \{(x_i,y_i)\}$)

a pair $(x_i,y_i)\in S_{t-1}$:  if $$x_i + \Sigma_{j:(x_j,y_j)\in S_{t-1}, j\neq i} y_j \geq B$$.

(That is if the sum of $x_i$ and the rest of the $y_j$'s is at least $B$ we're allowed to remove tuple $i$).

The problem is finding a sequence of tuples which can be legally removed, and leave a minimal cardinality set (i.e. remove as many tuples as possible).

Is this problem in $P$ as it is?

What if we know that $\forall i:y_i\leq x_i$?

Example: Assume $S_0 = \{(5,3),(5,5),(1,1),(6,0),(2,2)\}, B=10$ then $(<1,1>,<6,0>,<2,2>,<5,3>)$ is an example of a maximal output sequence.


texts: Language of words whose run lengths are all distinct

texts:
Assume $ \Sigma=\{0,1\}$, is $L$ a regular language? If it is not, how should we prove it with pumping lemma?

  $$L = \{1^{a_1} 0^{a_2}\ldots 01^{a_k} \mid k \in \mathbb N , a_i \geq 0 , \text{ the $a_i$ are all different}\}  $$


texts:
My first question here, I think this will be an easy one.

As for definition:

NP:
NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine. (wiki)

P:
P Contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. (wiki)

(a) I thought, that you can convert every Non-deterministic Turing machine into a equivalent deterministic Turing machine ?

I am not sure about that I know it is possible with NFA's to DFA's.

But if (a) is true, wouldn't that mean that P=NP?


texts: $\tilde \Omega$ for division by logarithmic factor

texts: Is $\Omega \left(\frac{n}{\log{n}} \right)\subset \tilde\Omega(n)$?


texts: Unique Stable Solution in Stable Marriage Problem: Is it Pareto-efficient and a Nash Equilibrium?

texts:
The deferred acceptance algorithm solves the Stable Marriage Problem in a two-sided network, where each agent has complete preferences over each agent of the other side. There is always at least one stable matching but there can be several. Traditionally, the problem was solved by having men propose and women accept/reject a proposition, which leads to a stable matching that is male-optimal but at the same time female-pessimal. But it is also possible to switch roles and have women propose and men accept/reject, which leads to the female-optimal stable matching, which at the same time is the male-pessimal.

Now, imagine a network with more men than women. I observed that in this case the male-optimal matching and the female-optimal matching are (so far) always identical, as in this simple example:

    Women's preferences
        A   B   C   D
M   U   1   1   1   2
e   V   2   2   2   1
n   W   3   6   5   4
    X   6   3   4   5
    Y   5   4   3   6
    Z   4   5   6   3
Read: Woman A's 1st choice is Man U

    Men's preferences
        U   V   W   X   Y   Z
W   A   1   1   2   2   1   1
o   B   2   2   1   4   2   2
m   C   3   4   3   1   3   3
e   D   4   3   4   3   4   4
n
Read: Men W's 4th choice is Woman D

    M   F   pM  pF
    U   A   1   1
    V   B   2   2
    Y   C   3   3
    Z   D   4   3
    W   NA  0   NA
    X   NA  0   NA
    Read: Man Z is matched up with Woman D. She is his 4th choice, while he is her 3rd choice

Above example returns the stable matching consisting of four matches A<->U, B<->V, C<->Y and D<->Z (while men W and X did not find a match), regardless if I start with men proposing or women proposing.

Now, what are the consequences if there is only one stable matching? I would love to understand if my thoughts are correct:

First, I observed in my model always the same result, regardless if I used female-optimal algorithm or male-optimal. Since male-optimal solution = female-optimal solution, I claim there exists only one stable solution, which naturally is the optimal (and pessimal) solution for both genders.
Second, given this stable matching, I cannot improve anybody's position in a ranking without making another person's situation worse. The algorithm stops once there is no blocking pair. Therefore, this matching is pareto efficient.
Third, if only one stable matching exists, there is no possibility for any of the players to improve their situation by changing their strategy and creating a fake preference list (stating their actual preferences is their best strategy). I claim therefore that this is a Nash Equilibrium.

Example: In above example, U and A both have received their very first choice. They cannot be possibly happier. V and B would have liked A and A better than each other, but as U and A are already matched up with their ideal partner, V and B are the next best option. This continues until W and X, who both ended up without a match. However, no matter how they would have ranked their preferences, they always would have ended up without a match


texts:
I read about Virtual Memory in various CS references, however I'm still not sure whether CPU caches such as TLB, L1 and L2 are integrated within MMU. Also I don't know if the hit/miss operations are managed by hardware (i.e MMU) or by software (i.e OS).

Does anyone have any idea?


texts:
I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to be in $O(t \cdot \log_t{n})$ time complexity. I also need to show that the function does not make the regular functions (insert, delete, split child) any different then what they used to be before ( time complexity- wise)
for example, for this tree (Only example! max degree = 3, t=2 because $MaxDeg = 2 \cdot t - 1$):

find(50) would return: 6 (because its in the sixth element of the sorted keys: 10 10 20 20 20 50 60 70 80)
I thought about storing how many keys are before each key, and thus we can actually do it in $O(1)$ but it seems unrealistic, if the question asks for $O(t \cdot log_t{n})$
Thank you!


texts:
Been getting a lot more spam lately and this question came to mind.
We already use SSL certificates to authenticate websites, can we do something similar for email?

If so, why do I still receive spoofed emails?


texts:
I was reading “Introduction to Algorithms” by CLRS and it says

  Note that f(n) = Θ(g(n)) implies f(n) = O(g(n)) since Θ notation is a stronger notation than O notation. Written set theoretically, we have Θ(g(n)) ⊆ O (g(n)) .

This means that Θ is a subset of O . Both the statements seem contradictory.


texts: Expected length of a random walk on a line

texts:
I am given the following randomized algorithm for SAT,

Input: A satisfiable CNF-formula $\varphi$.
Output: An assignment $\rho$, such that $\rho \models \varphi$.

The algorithm works as follow:

Choose an arbitrary assignment $\rho$.
As long as $\rho \not \models \varphi$

Choose a clause in $\varphi$ not satisfied by $\rho$ uniformly at random.
Choose a variable $x\in_{u.a.r}\operatorname{VAR}(C)$.
Flip the value of $\rho(x)$ (set $\rho(x) = \overline{\rho(x)}$).

We have to prove that for a 2-CNF Formula, the algorithm has polynomial expected running time.

I have proven that for a fixed assignment $\alpha$, such taht $\alpha \models \varphi$, with probability $p \geq 1/2$, after each iteration the number of variables that are assigned different values in $\alpha$ and $\rho$ decrease by one. With probability $1-p$, the assignments $\rho$ and $\alpha$ differ at one extra variable.

Now I have to prove, that the algorithm finished in expected polynomial number of steps. I was able to add one more step of abstraction. Let $X_i$ be the random variable that indicates the number of steps needed to make $\rho = \alpha$, when $\rho$ and $\alpha$ differ by exactly $i$ variables. Then it holds that
$$E[X_i] = 1 + p E[X_{i-1}] + (1-p) E[X_{i+1}],$$
and $X_i \leq X_{i+1}$ for all $i$ and $E[X_0]$ is equal to 0. We need to find a polynomial bound for $E[X_i]$.

Since $p\geq 1/2$ and $X_i \leq X_{i+1}$, the following must hold
$$E[X_i] \leq 1 + \frac{E[X_{i-1}] + E[X_{i-1}]}{2}$$

Now this can bee seen as walking on the integer line, in each step we move either one step to the left or one step to the right and the probability of moving to the left is at least one half. We have to prove that in expected polynomial many steps (polynomial in the starting position), we reach the number $0$ on the line.

Any help on this problem is very appreciated :)


texts:
Is it possible to solve the max sub-array product problem using divide and conquer?

Given an integer array numbers, find the contiguous sub-array within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.


texts: Are there ways to automatically (no human testing) measure a $9 \times 9$ Sudoku puzzle's average hardness for a human to solve?

texts: So most resources providing Sudoku puzzles assign a difficulty category to each puzzle, even some I've seen with 15 or more difficulty categories. But what is a good way to assign these difficulty categories? If enough human puzzle solvers were used, the average time for a human to complete a puzzle and the percentage of people who successfully solved the puzzle could be computed for the human sample, and difficulty categories assigned accordingly. But it seems like there should be predictable scenarios that keep appearing as various puzzles are being solved that affect the average human difficulty, which could be automatically detected as a computer solves the puzzle and then these patterns could be assembled into a predicted average difficulty for humans. Are there / what are good techniques to do this? Maybe machine learning with enough training data of human performance on sample puzzles?


texts: Doubt in definition of closure under concatenation operation in Recursive Enumerative languages

texts:
I recently started studying theory of computation.

Recusive enumerable language – closed under concatenation. Sir, I have a doubt regarding understanding of this.

Please Note - RE shortform i am taking for Recusively enumerative language

One way --> If L1, and L2 are RE s then L1.L2 is RE then RE is closed under concatenation.

Another way if we talk interms of strings,
If for all ‘a’ belongs to L1 and for all ‘b’ belongs to L2 then w=a.b belongs to L1.L2.

What about the other side? Please see if this is correct?

  For closure under concatenation, If w belongs to L1.L2 then all or some string splits of w into 2 make 1st part acceptance under L1 and 2nd string split acceptance under L2?

I was thinking, as L1 and L2 are REs we can make L1.L2 RE by concatenating L1 and L2 turing machines and make start state as start state of L1 and endstate as final state of L2. But when i am thinking in terms of string input i am getting confused

THe proof in my textbook says that we can non-deterministically split w into 2 parts so that each part accepted by Turing machines for L1 and L2 respectively. If string length is n, then we can have (n+1) kinds of 2 splits of w-string. Will the L1.L2 turing machine accepts all these n+1 types of w-splits? But this is what we need to prove right?


texts:
I have to prepare 30 minutes of oral examen about the subject called parsing. Where I have to talk about it. And then I shall hand in like 30 pages (including code and figures etc).
I don't know how to structure it and what I can talk about. So what I really need is a disposition! What I have thought about this far:

Languages
Operation on formal languages
Regular Expressions
DFA/NFA (+ from NFA to DFA; minimizing DFA)
Regular languages
Stack automaton
Context-free grammar
LL grammar
Compiler
Bottom-up
Top-down

But I honestly don't know if that is a good structure? Does all these subject fit under the subject "parsing"? And what would you tell about a compiler? Where would you show some code and how?
I don't ask you to do the work for me, it would just help me enormously if you could help me write a disposition so I can get started.


texts: Agda: Which part does this type introduce universe inconsistency?

texts:
I was trying to prove following lemma,

  my_thm : ¬ (∀ {M : Set} (P Q : M → M → Set) →
    (∀ x → ∃ M , λ y → P x y ∨ Q x y) →
    (∀ x → ∃ M , P x) ∨ (∀ x → ∃ M , Q x))
  my_thm = ?

while Agda gives following mistake:

Set₁ != Set
when checking that the expression
{M : Set} (P Q : M → M → Set) →
(∀ x → ∃ M , λ y → P x y ∨ Q x y) →
(∀ x → ∃ M , P x) ∨ (∀ x → ∃ M , Q x)
has type Set

honestly, in my untrained eyes, this type looks entirely routine to me, and it shouldn't introduce universe inconsistency.

all extra quantifier and connectivities are defined as following,

  data _∨_ : Set → Set → Set where
    inl : {A B : Set} → A → A ∨ B
    inr : {A B : Set} → B → A ∨ B
  infixl 20 _∨_

  ¬_ : Set → Set
  ¬ P = P → False
  infix 40 ¬_

  data ∃_,_ : (A : Set) → (A → Set) → Set where
    ex : {A : Set}{P : A → Set} → (x : A) → (ev : P x) → ∃ A , P
  infix 10 ∃_,_

which part introduces Set1 in this code?

ok, it turns out it's caused by negation: ¬_ : Set → Set. However, I still not understand. why this innocent looking function does not do what I want? what's the correct way of implementing it?


texts: Repeated point in polygon: preprocessing complexity given logarithmic query time?

texts:
I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is not necessarily simple. I am interested in the case where a polygon has many edges.

Let $n$ be the number of vertices of the polygon. I have an algorithm that performs the online phase in $O(\log n)$ time but the preprocessing phase requires $O(n^3)$ time and space in general, $O(n^2)$ time and space for simple polygons, and $O(n)$ time for star-shaped polygons.

Can we do better? Specifically, does anyone know lower or upper bounds, constructive or not, for the preprocessing phase given $O(\log n)$ query time?

I'm working in two dimensions, and the points have floating point coordinates (i.e., not integer coordinates).

My algorithm is similar to a standard algorithm and has similar performance characteristics. I discovered it independently so it differs in some immaterial ways but it's not original. It works as follows:

Preprocessing:

Translate polygon into first quadrant. (This is to simplify later calculations but isn't strictly necessary.)
Create a ray passing from the origin through every endpoint and intersection point of an edge. In each resulting cone no edge crosses another.
For each cone, sort the edges crossing that cone by their distance from the origin.

Online:

Apply the same translation to the query point as was applied to the polygon.
Using binary search, find the cone containing the point, or if none, return false.
Using binary search, find the number of edges in the point's cone for which the point and origin are on the same side. Return whether this number is odd.


texts: SAT algorithm for determining if a graph is disjoint

texts:
What are some good algorithms to have a SAT (CNF) solver determine if a given graph is fully-connected or disjoint?

The best one I can think of is this:

Number the nodes 1..N, where N is the number of nodes in the graph.
define N^2 variables with the ordered pair (P, Q), where P = 1..N and
Q = 0..N-1.
Set (1,0) to true.
Set (A,P+1) to true iff there is an
edge connecting node A and node B and (B,P) is true.
If there exists
a true (X,Y) variable for all possible nodes X, then the graph is
connected.

Effectively, (X,Y) means "Node X is Y steps away from node X".

This seems inefficient at O(N^2) variables. Can this be improved?

A comment (from when I posted this on cstheory.stackexchange.com) asked why I would need a SAT-based algorithm when O(N) algorithms for connectivity are well-known. The reason is simple -- I have many other SAT-based constraints on the graph that also need to be satisfied at the same time.


texts: Solving this recurrence: T(n) = 9 T(n/2) + n^3 lg n

texts:
Would it be possible to use the master theorem to solve the following recurrence?

T(n) = 9 T(n/2) + n^3 lg n

This recurrence hasn't been mentioned before in any of the questions on StackOverflow.

Best,


texts:
Today I heard of BNF which is a language for languages. Also heard that it specifies the entire syntax of C in four pages. So I thought of checking it out. After reading through this page, I got a fair idea about how to read the syntax.

But I don't understand what the first two lines mean:

%token int_const char_const float_const id string enumeration_const
%%

Also I am reading BNF just because I am just curious. How should I proceed to understand the formal syntax by reading BNF?

Here is the BNF syntax of C.


texts: What are the drawbacks of fully-convolutional neural networks?

texts: It is possible to replace the fully-connected layers of a CNN with convolutional layers, making it fully convolutional. Fully-convolutional networks (FCNs) can be applied to inputs of various sizes, whereas a network involving fully-connected layers can't. Still, for the input size the network was designed for (e.g. 224x224 in the case of VGGNet) the mathematical operations performed are exactly the same in both. What are the drawbacks of a FCN? Can we just throw away all fully-connected layers and replace them with their convolutional counterpart?


texts: Implement queue with a linked list; why would it be bad to insert at the head and remove at the tail?

texts:
In my textbook, Data Structures and Algorithms in Java, the author says when implementing a queue using a linked list you choose the front of the queue to be at the head of the list, and the rear of the queue to be at the tail of the list. In this way, you remove from the head and insert at the tail.

The author then asks cryptically, "Why would it be bad to insert at the head and remove at the tail?" without providing an answer.

I can't see what the difference really is. In effect, "Head" and "Tail" are just arbitrary names we define. What would be so bad if to enqueue() we add a head and create a reference to the old head, and to dequeue() we take from the tail and move the tail over?

What is the answer to the author's question?


texts: Is ROM primary memory or secondary memory?

texts:
According to this picture ROM is classified under Main Memory , but isn’t ROM a secondary storage because it’s external and non volatile ?
Any clarification with reference links will be highly appreciated.
Thank you.


texts: How do you work out the segmentation table, offset and frame size in segmented memory management?

texts:
If I had a process, 1, which has the following segments:
Segment 1 - 50 bytes
Segment 2 - 200 bytes
Segment 3 - 90 bytes
and I know that the total bytes in memory is 1024, how do I work out the offset/base/limit and the frame size for each segment that needs to be placed in physical memory?
Thank you for the help in advance.


texts:
I am trying to build a tool for solving TSP problem using a conversion to SAT.
Does there exist an efficient conversion from the Travelling Salesman Problem to the Satisfiability problem? Since they both are NP-Complete it seems like the answer might be yes.   I just need a conversion that is tractable in practice.  There are very efficient tools for the satisfiability problem and I think that if I can covert TSP to SAT, I can take advantages of thoses tools.


texts: How to solve this recursive relation T(n)= 2T(n/2) + 3T(n/5) +n

texts:
I don't think I'm able to solve this using the master's theorem, and solving separately doesn't seem to make sense. How does one go about solving this recursive relation?

T(n)= 2T(n/2) + 3T(n/5) +n


texts:
Has there been any attempt at a general theory to describe how an algorithm can be "deformed" to solve the problem more efficiently?

For example suppose we have an algorithm (say sorting a list of numbers) which solves the problem in $O(n^2)$. Can we deform this algorithm (in the "space of algorithms") to an algorithm which solves the problem in $O(n \log(n))$ time?

My motivation for asking this questions comes from analysis where if we want to solve the equation $f(x) = 0$ one technique is to first guess an $x_0$ such that $f(x_0)$ is small, then look in the neighborhood of that $x_0$ to find $x$.

Of course, I'm guessing the answers is no, but I'm sure a question similar to the above must have been posed somewhere in the literature somewhere.


texts:
I am having trouble to get the intuition behind the following approach:
We take the fraction point (say: .642) and continuously multiply by 2,
taking whatever ends up right of the point as our next number (either 0 or 1) after the fixed point in the binary number. Then we take whatever is left after the decimal point and repeat.


texts: Could computer architecture be reworked to support switching from binary to ternary, for example?

texts:
I was investigating why computers use binary instead of ternary and, from what I understand, found it's for precision. We want to avoid getting the wrong answer when computing math, and if we were to look at a bit at the wrong time in, for example, a base-10 system we might accidentally catch it switching states and accept the output before it's done switching states.

Please let me know if I've misunderstood this. I know there's a lot going on under the hood in computer hardware.

Assuming I understood correctly though, would it be feasible to redesign computers to be able to switch "languages" in some components in real-time in favour of speed/size instead of accuracy? It's well-known that 8 bits in base-10 can store 390,625 times more data than in binary, so there are obviously massive implications if possible.

To clarify: my question is about the feasibility of designing a computer which could switch between the two languages in real-time based on user-defined required output.

Edit: As clarified above, I am not asking about the benefits of binary over ternary. I am asking about the benefits of using them together, in real-time, and if that could even be possible. Thanks.


texts:
Are there reductions from SETH (Strong Exponential Time Hypothesis) to lowerbounds against threshold circuits? (maybe for computing Boolean functions of the form OR-of-AND-of-OR)

In threshold circuits I am allowing for circuits which end with a summing gate and hence these circuits are computing real valued functions on the Boolean cube.


texts: Kolmogorov Complexity, struggle with equation

texts:
I am working on understanding Kolmogorov Complexity. I've been struggling with the following exercise for quite some time now and would appreciate any inputs.

Show that there exists a constant $c$, such that for each $n \in \mathbb{N} -\{0\},$${K((01)^2}^n) \leq \lceil \log_2(n+1)\rceil +c = \lceil\log_2(\log_2(\frac{|{(01)^2}^n |}{2}))\rceil +c $

Through experimentation, I've come to the conclusion that $|{(01)^2}^n| = 2\cdot2^n \implies \log_2(|{(01)^2}^n|)=n+1$. Why is it wrong to simply substitute this in the above equation like so:

${K((01)^2}^n) \leq \lceil \log_2(n+1)\rceil +c = \lceil\log_2(\log_2(|{(01)^2}^n |))\rceil +c $

Why is the length of the string divided by 2 in the problem statement?


texts: Language with $\log\log n$ space complexity?

texts:
We know that every non-regular language can be recognized with $ \Omega
 (\log\log n) $ space complexity.

I'm looking for an example of a language which is $ \Theta
 (\log\log n) $ space complexity (if such exists).


texts: Pac learnable when changing distribution

texts:
if H is Pac learnable according to

  Definition 3.1 (PAC Learnability) A hypothesis class H is PAC learnable
  if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the
  following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X$, and
  for every labeling function $f \colon X \mapsto  \{0,1\}$,  if the realizability assumption holds
  with respect to $H,D,f$, then when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$ and labeled by $f$, the algorithm returns
  a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $$L_{(D,f)}(h) \leq \varepsilon.$$

and the algorithm returns h* (for specific S of size
$m_H(\varepsilon, \delta$) and distribution D) , I can define a distribution D' that gives 0 for each x s.t. h*(x)=f(x) and that will give me $L_{D'}(h*)=1$.
I am trying to understand why this is ok (not a contradiction for H being PAC), so I have 2 questions on this:
$$$$
1. my guess is that since the algorithm does not depend on the distribution but does on S (that depends on it), we will probably get with the new distribution D' a different S that will return a different h that keeps us with $L_{(D',f)}(h) \leq \varepsilon.$ with probability $1 - \delta$. Is this the right explanation?
$$$$
2. After defining the new distribution D' is it right to say that (D',f,H) still hold the realizability assumption? I don't see why not but want to be sure.

  definition 2.1 (The Realizability Assumption) There exists $h* \in H$ s.t.
  $L_{(D,f)}(h*) = 0.$. Note that this assumption implies that with probability 1 over
  random samples, S, where the instances of S are sampled according to D and
  are labeled by f, we have $L_S(h*) = 0$.

Thank you


texts: Can quantified renamable Horn formulas be identified using the same procedure as unquantified formulas?

texts:
Definition: A renamable Horn formula is a Boolean formula that can be transformed into a Horn formula by flipping the polarity of every instance of one of more of its variables.

Example:

$\qquad (x_1 \lor x_2 \lor x_3)\land (\lnot x_1 \lor \lnot x_2 \lor  x_3)$

This formula is renamable Horn because flipping the polarity of $x_2$ and $x_3$ produces the Horn formula

$\qquad (x_1 \lor \lnot x_2 \lor \lnot x_3)\land (\lnot x_1 \lor x_2 \lor \lnot x_3)$

Can I extend the test procedure for identifying renamable Horn formulas, as described in the Harry Lewis paper "Renaming a Set of Clauses as a Horn Set", to quantified formulas?

The paper states: Let $S$ be a set of clauses, say $S = (C_1 ..... C_m)$, where each $C_i = (L_{i1} .... , L_{il})$. Then
define $S^*$ to be the set of clauses

$\qquad \bigcup_{i=1}^m \bigcup_{1\leq j <k\leq l} ((L_{ij}, L_{ik}))$.

Then $S$ is renamable-Horn if and only if $S^*$ is satisfiable.

Is this procedure applicable to quantified Boolean formulas also?


texts: Why does a polytime hitting set generator derandomize RP?

texts:
I am reading Goldreich, Vadhan, Wigderson: Simplified Derandomization of BPP Using a Hitting Set Generator and trying to understand the result that polytime hitting set generators (HSGs) would not only imply $\mathsf{RP = P}$ but $\mathsf{BPP = P}$ as well, but I can't even conceptualize why the former holds.
The paper states that

Having such a generator that runs in polynomial time enables a trivial deterministic
simulation of an RP algorithm by using each of the generator’s outputs as the random pad
of the given algorithm.

Every paper or lecture notes I've found on the topic of HSGs and $\mathsf{BPP}$ derandomization also mentions that $\mathsf{RP}$ derandomization is trivial using an HSG, simply by trying all elements of the hitting set as random pads.
I am confused as to why this is the case. At least one element of a hitting set must be accepted by circuits that accept over half of their inputs. However, RP circuits don't necessarily accept over half their inputs; rather, if $x \in L$, only then will the circuit accept over half the time. I assume that fact is related to why a hitting set must contain a valid $\mathsf{RP}$ random pad, but I do not understand exactly how.
So, my question is: how do the circuits in the definition of an HSG relate exactly to $\mathsf{RP}$ circuits? i.e. how do the elements of the hitting set - which are to be the random pads across all inputs - relate to the randomness of RP algorithms when such algorithms accept over half the time only when $x \in L$?


texts: How to calculate the size of a page in a two level paging CPU?

texts:
I am having difficulties with understanding the concept of paging.

As a result I've got no idea how I can solve the following exercise - I'm lacking one more equation to solve it.

I've read a lot about paging and watched a few tutorials, but I still cannot solve paging problems easily. I'll provide some of the resources I learnt from at the bottom of this question.

Background:

The CPU has two level paging and the logical and physical addresses are of $34$ bits size each.

The sizes of the page table directory, the table directory and the page are equal.

The logical address $(12345678)_{16}$ has been translated to the $(ba9678)_{16}$ physical address.

What's the size of a single page?

My attempt:

The logical address can be decoded to:
$$(00\ 0001\ 0010\ 0011\ 0100\ 0101\ 0110\ 0111\ 1000)_2$$
The physical address can be decoded to:
$$(00\ 0000\ 0000\ 1011\ 1010\ 1001\ 0110\ 0111\ 1000)_2$$
So, as you can see, they share the last $14$ bits.
Hence, the number of bits representing offset is $\leq 14$.
The physical address looks like this:

+-----------+-----------+--------+
+-page-size-+-page-size-+-offset-+
+-----------+-----------+--------+

because page size = page table size = table directory size.
Therefore, we get the following equation:
$$
2\times \text{page size} + \text{offset} = 34
$$
However it is not sufficient to tell what is the page size. I'm stuck.

Resources:

Segmentation and paging
Wikipedia (discouraged)
Video tutorial by Anshul Agarwal: part 1, 2, 3, 4 and 5.


texts: What is inner kernel in context of BLAS libraries

texts: I was reading about BLAS (Basic linear algebra subsystem) and I frequently encountered the term "inner kernel". What does it mean by "inner kernel"?


texts: Functional dependencies on relational schema

texts:
Given a relational schema $R(V,W,X,Y,Z)$ with functional dependencies $F = \{VW \to X, X \to YZ, W \to VX, V \to W, Z \to XY\}$. What are the keys of $R$?

Is the key just $V$? If so,  is $\{ R_2(V,W,Z), R_3(V,X,Y) \}$ the lossless-join decomposition of $R$?


texts: Computing min and max using median of 3 elements

texts: How can I write an O(n)-time algorithm to find the minimum and maximum,  given a list of n elements drawn from a totally ordered set using the subroutine median3(x,y,z) which returns the index of three elements x,y,z?  You are not allowed to read or compare the elements directly; the only operation that is allowed is invoke the median3 subroutine.


texts: Linear time algorithm for array with distinct element

texts:
Given an array, if all the elements are distinct, can we find the count of elements which are lesser than an element and present to the left of that element in linear time if we have to do it for every element.

I know this can be solved in O(nlogn) time by using self balancing trees, but I want to know whether we can solve it in O(N)?


texts: Confusion about the geometric interpretation of the simplex method for linear programming

texts:
In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of the simplex algorithm for linear programming:

Check whether the current vertex is optimal;
Determine where to move next. In particular, it says

  As we will see, both tasks are easy if the vertex happens to be at the origin. And if the vertex is elsewhere, we will transform the coordinate system to move it to the origin!

Later, it explains how to transform a vertex $\vec{u}$ into the origin, by shifting the coordinate system from the usual $(x_1, \cdots, x_n)$ to the "local view" from $\vec{u}$.

  These local coordinates consist of (appropriately scaled) distances $y_1, \cdots, y_n$ to the $n$ hyperplanes (inequalities) that define and enclose $u$.
  Specifically, if one of these closing inequalities is $\vec{a_i} \cdot \vec{x} \le b_i$, then the distance from a point $\vec{x}$ to that particular "wall" is
  $$y_i = b_i - \vec{a_i} \cdot \vec{x}.$$
  The $n$ equations of this type, one per wall, define the $y_i's$ as linear functions of the $x_i's$, and this relationship can be inverted to express the $x_i's$ as linear functions of the $y_i's$.

I am able to understand the linear algebra computation (e.g., row operations) behind this coordination system transformation. However, it does not quite fit what I learn in undergraduate linear algebra textbooks about basis change.

In particular, in my knowledge, a basis is given as a set of vectors and the coordinates of a vertex under a basis $\mathcal{B}$ are the coefficients of the linear combination representation of the vectors in $\mathcal{B}$. However, the description above considers hyperplanes and the distances from a point $\vec{x}$ to them. What is the theory behind this kind of coordinate systems and its transformation?


texts: Search problems that can also be solved by junction trees and searching cliques

texts:
Assume having a graph $G_{variables}=(V,U)$ where $V=\{v_1,v_2,…,v_n\}$ is a set of variables; each variable $v_i\in V$ is associated with a set of possible values (it's domain) $dom(v_i)$.

Let $P$ be a search problem (i.e reachability problem) over graph $G=(O,E)$ where $O$ is the cartesian product of the variables domains. Let $T$ be a junction tree resulted from $G_{variables}$. $P$ can be also solved through searching every clique in $T$. I am looking for keywords/examples of such problems. $G_{variables}$ preferably to be DAG.


texts: Algorithms for verifying and solving three-coloring

texts:
I found the following problem that I am trying to answer:

  Consider the three color problem where V, vertex set of a bipartite graph. can be partitioned into three subsets such that there is
  no edge between verticies of the same subset. Show that this problem is in NP by describing:

  A polynomial time algorithm for verifying a given graph coloring.
  [Hint:Use graph traversal].
  A nondeterministic polynomial time algorithm for graph coloring.

For 1) I attempted to solve this problem using search algorithm like depth-first search/breadth first search. At each vertex, I would check to see if any of adjacent vertices have different color from the current vertex. If not, then graph is not colored correctly. This is worst case O(|e|), linear time. Is this correct ? How can I answer this question ? And how would I do part 2)?


texts: Is it possible to give a guarantee about the accuracy of the local time?

texts:
Assuming there is no attack/bug and I use NTP: Are there any formal guarantees about the accuracy of the local time? Can there be any over the network?

Even if the communication is going directly between the time server (stratum-1) and the client, I have no idea if the devices / protocols on OSI layer 1-4 have time guarantees.

Maybe something like the following can be guaranteed: With a probability of 99% the currently set local time is off by less than 20ms.

(I've added the "cryptography" tag as certificates are also only valid for a given time - in this case it would be important to have a guarantee even with a possible attacker)

What I found

  Clock synchronization at the 10 millisecond level over long distance wide-area networks (WANs) (2000 km), and at the 1 millisecond level for local-area networks (LANs), is routinely achieved.

Source: Cisco, Network Time Protocol: Best Practices White Paper. 2008.


texts: Is possible to prove undecidability of the halting problem in Coq?

texts:
I was watching the "Five Stages of Accepting Constructive Mathematics" by Andrej Bauer and he says that there is two kinds of proof by contradiction (or two things that mathematicians call proof by contradiction):

Assume $P$ is false... blah blah blah, contradiction. Therefore $P$ is
true.
Assume $P$ is true... blah blah blah, contradiction. Therefore
    $P$ is false.

The first one is equivalent to the Law of Excluded Middle (LEM) and the second one is to how prove negation.

The proof of the undecidability of the Halting Problem (HP) is a proof by contradiction: assume there is a machine $D$ that can decide the HP... blah blah blah, contradiction. Therefore $D$ does not exist.

So, let $P$ be "$D$ exists and can decide the HP".
Assume $P$ is true... blah blah blah, contradiction. Therefore $P$ is false.

This looks like the second kind of proof by contradiction, so is possible to prove the undecidability of the halting-problem in Coq (without assuming LEM)?

EDIT: I would to see some points about proving this using contradiction. I know that this can also be proved using diagonalization.


texts: Describe an algorithm for painting cards in the following game

texts:
It's my first question out here, so please don't judge me too strictly.
I heard of the following game: there's set of cards with different set of objects (but the same number of them on every card) painted on cards, while for every pair of cards there's one and only one common object. The game is for two players. At each step each player draws a card and puts it along the card of the other player. The player who is the first to pronounce the common object wins the step and takes both cards. The one who attains all cards first is the winner.

Specifically:
1. There're 50 cards
2. Each card contains 8 different objects
3. There's set of 36 possible different objects (from which 8 objects are chosen)
4. The set of cards has the following property: for each pair of cards there's one (and only one) common object

What I'm asking is how to build an algorithm that chooses the subset of objects to paint on cards.

To make it strict:
Input:{N, O, K},
N-number of cards
O-total number of objects
K-number of objects on a card

Output:
N lines of k numbers each: n_1, n_2, ..., n_N where
n_1= {k1_1, k1_2, ..., k1_K}
n_2= {k2_1, k2_2, ..., k2_K}
....
n_N= {kN_1, kN_2, ..., kN_K}
such that for any i,j<=N exists |n_i X n_j|=1, where X is intersection of sets

It's clear to me, that not for all triples {N,O,K} there's a solution.
No limitations on time/space complexity. All supporting data structures are allowed. Thanks in advance


texts: How does coarser lock granularity cause an decrease in time required to acquire and release locks?

texts:
I understand the principles required to program locks and I have run into the following problem:

In my Operating Systems course, as well as on Wikipedia, one of the notions associated with lock overhead is the time required to acquire and release locks. And it is also implied that coarser granularity leads to less overhead (I agree it causes less memory to be allocated and less time for initializing locks), but I do not agree that it causes less time to be spent acquiring/releasing locks.

In my view, the number of times locks are being acquired/released is dependent only on the number of times threads are trying to enter a critical section and therefore, it should be the same regardless of the granularity chosen for the locks. My lecturer said in the lecture that because there are more locks, therefore the time spent to acquire/release is higher in the case of finer granularity.

It would be great if someone could explain why does coarser granularity lead to a decrease in time required to acquire/release locks compared to finer granularity.


texts: Is this line from the rational wiki p vs np bit correct? " A computational problem is considered "in P

texts:
http://rationalwiki.org/wiki/Pseudomathematics#P_vs._NP_problem

  A computational problem is considered "in P" if an algorithm exists
  that can solve the problem in "polynomial time" — that is, it's O(n),
  or O(n2), or O(n3), or any order where the n is raised to some fixed
  power. If, however, the fastest algorithm is something like O(2n),
  where the n appears as an exponent, then the problem isn't being
  solved in polynomial time and isn't "in P".

I recently took an algorithm analysis course that I didn't feel was taught well and I spent a while trying to understand "poly time" and nothing I read led me to believe that an O(2n) algorithm was not considered to be in P. Is that the case?


texts: Unrecognizability of $L(M_1) \cap L(M_2) = \emptyset$

texts:
Let's define a language $$C = \{ \{M_1, M_2\} \mid M_1, M_2 \text{ are TMs s.t. } L(M_1) \cap L(M_2) = \emptyset \}$$
We have to show that $C$ is unrecognizable.
I am having trouble going on about with this proof. I am trying to do this by reduction, showing that this language is unrecognizable, but I am unsure on how to reduce this problem into a simpler problem.


texts: Question regarding definition of recursive function

texts:
According to Wikipedia, and also a very common definition of a recursive function found in several books, "functions that call themselves from within their own code". I agree that this solves the problem for most of what I think recursive functions are, but, suppose you have the following "iterative" code written in C:

int foo(){
    return 2;
}

The unique pourpose of this function is to compute the value "2". Can we say this is also a "recursive" function? Saying it only relies in a base case. I can see the function isn't calling itself in their body, even though, I can't find a way to compute it in another way, using the self-calling part.

Besides, I'm aware of the fact that every iterative function has a recursive implementation, so, in this case this function does have the same implementation for the iterative and for the recursive view?


texts: Solving Recurrence Equations containing two Recursion Calls

texts:
I am trying to find a $\Theta$ bound for the following recurrence equation:

$$ T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42 $$

I figure Master Theorem is inappropriate due to differing amount of subproblems and divisions. Also recursion trees do not work since there is no $T(1)$ or rather $T(0)$.


texts: Turing Machine where branches are resolved via arbitrary operator

texts:
Alternating Turing Machines output Boolean values and combine the values returned by branches via the any/all operators. Is there a name or theory behind the class of Turing Machines where there is no restriction to the Boolean space and the any/all operators?

For example, I want a machine where terminal states output real values and non-terminal states use the min operator to combine the outputs of branches.

Additionally, are there subclasses of this class? I imagine operators which have certain properties (associativity, idempotence, and especially properties related to ordering or transitivity) would have interesting guarantees regarding interruptibility in the same way that a machine using only the any operator can terminate as soon as it finds one accepting state.


texts:
In looking for a programming function to validate an IP address within a subnet, I had to calculate the subnet mask from a given CIDR bitmask value ie. 192.168.0.0/24, the value 24 in this example.

The first step is to convert the bitmask value (24) into an unsigned 32bit integer.  I found this on the internet (specific to our 24 bitmask example):  mask = (( 2^24 ) - 1) * ( 2^(32-24) ).  This gives me an integer value of 4,294,967,040 which is exactly the binary number I am looking for where the first 24 bits are 1, while the remaining bits are 0 11111111.11111111.11111111.00000000.  Obviously, this works for any bitmask value 0-32.

I would like to understand why this works:  mask = (( 2^bitmask ) - 1) * (2^( 32-bitmask ))


texts: How can a Turing machine write the description of the n-th Turing machine?

texts:
I am trying to interpret the following problem:

"Describe an algorithm for a Turing machine which receives the integer n as
input and proceeds to write the description of the n-th Turing machine from
the standard enumeration on its tape."

I am confused about how a Turing machine itself can represent another Turing machine (the n-th Turing machine).


texts: How do I interpret this formal languages definition?

texts:
Given the formal language

$L_1 = \{wcw | w\in \{a,b\}^+\} $

Does this definition requires $w$ to be exactly the same before and after the terminal character $c$ or can it be different?

Example:

Are $aabca$ or $abca$ accepted words of $L_1$, or only words like $aabcaab$ or $aca$?


texts: Are there strongly-polynomial algorithms that take more than polynomial time?

texts:
In [1] strongly-polynomial is defined as either:

The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic operations which is bounded by a polynomial in the number of input numbers.
A polynomial algorithm is a polynomial space algorithm (in our standard Turing machine model) and polynomial time algorithm in the arithmetic model (see this question for a clarification).

Why do they restrict to polynomial TM space as opposed to polynomial TM time? (this came up here)

It seems strange for an algorithm that takes a number of TM steps unboundable by a polynomial to still be considered strongly-polynomial (provided it takes polynomial space and a number of arithmetic operations polynomial in the number of numbers in the input). Can it be shown that such an algorithm does not exist? Perhaps based on this argument: the number of arithmetic operations would not be polynomial, since under the arithmetic model every operation is an arithmetic operation (?).

[1] Grötschel, Martin; László Lovász, Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.


texts:
Is it possible to do an edge detection using ONLY opening and closing  operations?

Where:

opening- $X\bullet  B = (X \ominus B) \oplus B$

closing- $X\circ B = (X \oplus B) \ominus B$

(I know we can do it with erosion dilation)


texts: How to optimize Dijkstra's algorithm for a grid graph?

texts:
I'm trying to apply Dijkstra's algorithm to the Problem 83 on projecteuler.net. The problem reads:

  In the 5 by 5 matrix below, the minimal path sum from the top left to
  the bottom right, by moving left, right, up, and down, is indicated in
  bold red and is equal to 2297.

131   673   234   103    18
201    96   342   965   150
630   803   746   422   111
537   699   497   121   956
805   732   524    37   331

  Find the minimal path sum, in matrix.txt (right click and 'Save
  Link/Target As...'), a 31K text file containing a 80 by 80 matrix,
  from the top left to the bottom right by moving left, right, up, and
  down.

I wonder if the original algorithm can be simplified due to the fact that the graph is represented as a matrix?

In particular, I've noticed that every edge in the graph is only relaxed once (i.e. the node's distance is changed only once from infinity to some value). Can I rely on this fact in my code?


texts: Using dynamic programming to maximize work done

texts:
Say that there are $n$ days and there is $x_1, x_2, ...,x_n$ amount of data to process on each day. Your computer can process $s_1$ amount of work on the first day since rebooting your computer, $s_2$ work on the second day since a reboot, up to $s_n$. On each consecutive the day the amount of work your computer can perform without being rebooted decreases. In other words, $s_1 >s_2>...>s_n>0$. Any day you reboot your system you cannot do any work.

The problem is to find an algorithm using dynamic programming to figure out the maximum amount of work possible given $x_1...x_n$ and $s_1...s_n$. This means we must determine which day(s), if any, we should reboot on.

For example:

n| 1 | 2 | 3 | 4
x| 8 | 3 | 11| 5
s| 9 | 4 | 2 | 1

The most optimal solution here would be to reboot on day 2, so that we can perform 8 work on day 1, 9 work on day 3, and 4 work on day 4 for a total of 21.

This seems somewhat similar to the partition problem but I am having trouble coming up with a recurrence relation I can convert to dynamic programming.

If we say that our final reboot occurs on day $i$, then our maximum work should be the amount of work done from days $i$ to $n$ plus the maximum work we can do on days $1$ to $i-1$.

So if we say $M[x_1...x_m,s_1...s_n]$ represents the maximum amount of work we can do on days $1$ to $m$, I write the following recurrence relationship:

$$M[x_1...x_m,s_1...s_n] = \max_{i=1}^m\{M[x_1...x_{i-1},s_1...s_n]+R[i]\}$$

Where $R[i]$ is simply the max amount of work you can do from days $i$ to $n$ without rebooting, which is simple to calculate.

Does this seem like it is a valid recurrence relation? Also, I am not quite sure what my base cases would be. Perhaps that $M[x,s] = \{x$ if $s \geq x$ else $s\}$? I am not sure if this covers all possibilities though.


texts:
Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$. Integer $M$ is given and it is the same for all calculations however we need to solve for $X$ for more different numbers.  One important thing that we know is that $\gcd(M, 10) = 1$.

I rewrited the equation in this type:
$X * 10^L \equiv M - D \mod M$. If $M$ was prime number we could just multiply $M-D$ by $(10^L)^{M-2}$. However $M$ might be arbitrary integer. How can we use the fact that $\gcd(M, 10) = 1$


texts: I am trying to understand why $BPP \subseteq EXP$. This question almost gives the answer (simulate $BPP$ machine on all possible toin cosses and then "act accordingly"). However, it is not clear to me what act accordingly means: I am thinking we need to count how many times the probabilistic Turing machine accepts and how many times it rejects and then act upon this information - but how exactly?


texts: Role of Term Constants in Simply Typed Lambda Calculus

texts:
In the Wikipedia article on Simply Typed Lambda Calculus (among other places), there is a notion of a "term constant".  This is particularly notable in the production grammar given:

In this production grammar, the c is the term constant.  I am new to the simply typed variant of lambda calculus -- I do not understand what role this constant plays in the overall computations of STLC.  Can anyone give some examples of how the term constant is used and explain its general purpose?


texts: Sorting n elements in worst case of $\sqrt{n}\log n$

texts:
Can $n$ elements be sorted in a worst case time of $\sqrt{n}\log n$? Why or why not?
I've seen algorithms being sorted in the worst case of $n\log n$, so why can they be or cannot be sorted in $\sqrt{n}\log n$?


texts: Training preamble in convolutional codes

texts:
as I was examining the VirtualWire library used in Arduino projects, I noticed that the header of the messages that are transmitted begin with a 36 bit "training preamble." What exactly is a training preamble? Can anyone elaborate?
The link to the libraries documentation can be found here.

My initial understanding is that it is there to allow the received to sync correctly with the transmitted bits. So essentially, the first 36 bits can all be wrong, but that's not of concern, because we are just using them to "train" or rather sync the transmitter and receiver. Am I correct in my thinking?


texts:
Can someone please explain to me how the Wikipedia example on the left for a balanced binary tree is correct?

  One common balanced tree structure is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1

For node ABCDE, isn't the height of left subtree 2 and the height of the right subtree 0, making the difference of height 2?

EDIT As David rightly pointed out:

  That page defined "balanced" immediately above the example you're asking about, and it defines balanced in a different way to you.

I thought that the example was using the definition that comes immediately after the example, which I have quoted above. Apologies for the confusion.


texts: Why top down merge sort is popular for learning, while most libraries use bottom up?

texts:
Most libraries use some variation of bottom up merge sort, but top down merge sort seems to dominate web sites and forums.

Assume reasonably optimized implementations, where a single working array is used in addition to the original array, and copy or copy back avoided in top down merge sort by tying the direction of merge (to or from the working buffer) based on level of recursion (bottom up does this based on merge pass), then the key differences are the generation and storage of indices for runs via recursion and storage on the stack for top down versus iteration and storage possibly in registers for bottom up, and cache locality affected by the order of merge operations (top down is depth first, left first, while bottom up is breadth first).

For cache locality issues, assuming at least a 4 way set associative cache, that's enough for 2 lines for input, and 1 line for merged output, and the merge operation is a sequential operation for the 2 input runs and the merged output run. It's not clear to me if there are a few levels of recursion for top down versus passes for bottom up where top down is more cache friendly.

In all the benchmarks I've run, bottom up merge sort is faster than top down, which would explain why most libraries use some variation of bottom up merge sort. As array size increases, the relative difference decreases because most of the time is spent in a merge function that can be identical for top down and bottom up.

From a historical perspective, going back to the days of disk or tape sorts, merge sort started out as bottom up merge sort (or a variation called polyphase merge sort).

My questions are when and why top down merge sort became more popular in a classroom environment, or later on the web?

Update - I'm also wondering why bottom up merge sort seems to be so rarely seen in a classroom environment, web sites, or forum sites. My guess is that 80+% of the questions about merge sort at Stack Overflow are about top down merge sort. I only recall one question about bottom up merge sort in the last month or so.


texts: Min-Max number of shifts and reductions in bottom-up parser

texts:
Given the Grammar has no unit or ɛ-productions,
What is minimum & maximum number of shifts and reduce needed by bottom-up parser?


texts:
How can I show that $\{a^ib^jc^k|i=0 \lor j=k\}$ is not regular?

I tried applying the pumping lemma but it does seem to have a pumping length of 1?

Alternatively there is the Myhill–Nerode theorem.
Are $\{a^ib^j|i=0 \lor j\in\mathbb{N}\}$ infinite many equivalence classes?


texts:
I am trying to solve the Problem CTRICK on SPOJ. I have an $O(n^2)$ solution that is giving “Time Limit Exceeded”. After browsing for some hints, I found that it can be solved using Interval Trees. But I have no idea, how to think it that way. Here is the problem:

The magician shuffles a small pack of cards, holds it face down and performs the
following procedure:

  The top card is moved to the bottom of the pack. The new top card is dealt
  face up onto the table. It is the Ace of Spades.
  Two cards are moved one at a time from the top to the bottom. The next card is
  dealt face up onto the table. It is the Two of Spades.
  Three cards are moved one at a time…
  This goes on until the $n$th and last card turns out to be the $n$ of Spades.

  This impressive trick works if the magician knows how to arrange the cards
  beforehand (and knows how to give a false shuffle). Your program has to determine
  the initial order of the cards for a given number of cards, $1 \le n \le 20000$.

  Input 1:

4

  Output 1:

2 1 4 3

  Input 2:

5

  Output 2:

3 1 4 5 2

Please suggest me some ideas.


texts:
I am looking for an efficient algorithm that lets me process the minimax search tree for chess with alpha-beta pruning on a distributed architecture. The algorithms I have found (PVS, YBWC, DTS see below) are all quite old (1990 being the latest). I assume there have been many substantial advancements since then. What is the current standard in this field?

Also please point me to an idiot's explanation of DTS as I can't understand it from the research papers that I have read.

The algorithms mentioned above:

PVS: Principle Variation Splitting
YBWC: Young Brothers Wait Concept
DTS: Dynamic Tree Splitting

are all are discussed here.


texts: Emulating boolean circuits using addition and multiplication (mod 5)

texts:
I'm trying to use gates that do addition and multiplication modulo 5 to emulate logic gates.

Assuming false and true are mapped to 0 and 1 respectively (with 2, 3, and 4 being invalid), I figured out I can map the operations like this:

a and b -> a*b (mod 5)
a or b -> 2*(a+b)*(a+b+2) (mod 5)

I was wondering if there was a simpler approach.

For the application I have in mind, a toy example of secure multi party computation using secret sharing, I haven't shown/discovered/figured-out yet if it's safe to re-use private values. If I have to recompute a, b, and a+b two times in order to do an or, costs would be exponential in the length of the circuit. (I'm only using tiny circuits so that's not a big deal, but it would be interesting to know if it was just a non-issue via a clever transformation.)


texts: Find and sort 2d array elements like radar

texts:
I don't know relevant keywords about this algorithm.
I can show you visually

Any ideas are appreciated


texts: Where does entanglement fit into quantum computing?

texts:
I've been reading up on quantum computing online from various sources, including this link http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm.

I get how quantum gates work, destructive interference, and how you can simulate a quantum computer using matrix math and complex numbers.

Does entanglement have a use in quantum computing?  I haven't yet seen anything explicitly talk about entanglement and whether it's used in QC, but I feel like it's possible it might be implicitly stated and I could be missing it - or maybe not!

Thanks!


texts:
What is the regular grammar of the language: $$L=\left\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\}\:above\:\Sigma =\left\{a,\:b,\:c,\:d\right\}$$
My attempt: $$S\rightarrow aAbcBd|aXd$$ $$A\rightarrow aAb|\epsilon$$ $$B \rightarrow cBd|\epsilon$$
But I'm not sure if I'm right until here. Is it good?
Edit: This language is not regular, for this language you can look for the answer down: $$L=\left\{a^nb^nc^md^m\left|n,m\ge 1\right|\right\} \cup \left\{a^nb^mc^md^n\left|n,m\ge 1\right|\right\}$$


texts: Do most bitstrings expand if they halt when executed by a Universal Turing machine?

texts:
According to the counting argument, most bitstrings are incompressible or only slightly compressible.  However, the counting argument does not work in the opposite direction, since there are an infinite number of bitstrings that are longer.  So, the counting argument does not tell us whether most bitstrings will or will not expand when run on a universal Turing machine and halt.

Is it known whether most halting bitstrings will expand?

By 'expand' I mean that a bitstring $b_1$ generates a bitstring $b_2$ when run on a universal Turing machine,
\begin{align*}
 \mathcal{U}(b_1)=b_2,
\end{align*}
such that the length of $b_2$ is greater than $b_1$
\begin{align*}
\ell(b_2) > \ell(b_1).
\end{align*}


texts: What is an estimation of the Kolmogorov Complexity for the first N integers?

texts: I'm aware some ints have higher or lower Kolmogorov Complexities. For example, the number 5.41126806512 has a very low complexity as it can be expressed by 17/pi. I'm also aware that, though the KC varies depending on the expression language, it is always the same up to a given constant. So, I ask: is there a way to calculate an approximation of the KC for the first N ints?


texts: How to construct a sequence of polynomial-time Turing machines

texts:
I know that similar questions have been asked before but I still wasn't able to find answers to all my questions.

In many proofs in complexity theory we use an enumeration of some $T(n)$-time Turing machines. For simplicity, let's consider polynomial-time TM's. I want to know exactly how we construct such an enumeration.

I know that the following observations are important:

TM's correspond to the natural numbers: each binary sequence (natural number) encodes some Turing machine (if we have a sequence that does not encode a valid TM, we say that it is a trivial machine that halts and rejects on all inputs immediately)
Every TM's is represented by infinitely many strings/natural numbers, because we allow the encoding to end with any number of 0's (that do not matter for the encoding).

So if we want to obtain an enumeration of TM's that halt in polynomial time for some input $x \in \{0,1\}^n$, we can let each TM of our enumeration of all TM's (the natural numbers) run on input $x$, but then with a counter and an extra tape. If the TM hasn't halted in $n^i + i$ steps, with $i$ the length of the sequence that encodes the TM, we remove it from our enumeration. Because every TM is represented by an infinite number of strings, we now have any TM that runs in time $O(n^c)$ for some $c$.

Please tell me if this is not correct.

My confusion lies here: we need TM's that run in polynomial time for all inputs. Do we need to go over all possible inputs? There are only finitely many inputs of length $n$, but how are we sure that some TM does not use more than polynomial time for a larger input? Or is this some trivial consequece from the deterministic nature of Turing machines?


texts: Longest common substring many strings to one

texts:
I'd like to find longest common substring (occurrences, start index) between one string and many others.

For example

source string - "abcdefghijklmncdop"
other strings - ["cd", "ghi",
"mn", "zw", "cdewxyz"].
Expected result -(original string, substring, index in source string) =  [(cd,cd,2),(cd,cd,14),(ghi,ghi,7 ),...(cdewxyz, cde, 3]

I could create suffix array from the source string and search all possible substring occurrences sequentially - but it doesn't seem that efficient. The other strings array might be very large, so creating joint arrays with special delimiter is not considered.

I also thought on creating suffix tree, but I there are many source strings soe space complexity might become an issue.


texts: How can I make k nearest neighbor queries fast on unit hypersphere?

texts:
I have $m$ points $D = \{x_1, \dots, x_m\}$ with $x_i \in \mathbb{R}^n$. After some preprocessing / building up data structures for those points, I get $T$ queries $y_i \in \mathbb{R}^n$ with $i=1, \dots, T$. Each query comes at a time and independently. The datastructures for the queries should not be modified by the past queries. After receiving an query $y_i$, the $k$ nearest neighbors

$$NN_k(y_i) \subset D \text{ with } |NN_k(y_i)| = k \text{ and }$$
$$\forall x_a \in NN_k(y_i) \forall x_b \in D \setminus NN_k(y_i) : \|x_a - y_j\|_2 \leq \|x_b - y_j\|_2$$

All points $x_i$ and all queries $y_j$ are on the unit hypersphere, so $\|x_i\|_2 = \|y_i\|_2 = 1$.

How do I process those queries fast?

Limits

To get a feeling for what matters, here are some orders of magnitude:

$100 \leq n \leq 1000$: Dimension of points
$m \geq 100\,000$: Candidates
$T \geq 10\,000\,000$: Number of queries
$3 \leq k \leq 20$: Expected number of returned points
Reasonable memory consumption (e.g. less than 2GB for the data structure)

The query time for a single brute force approach is in $\mathcal{O}(m \cdot n)$ as it just compares every candidate point in $D$ with the query and stores the closest $k$ of them.

Misc

I've just implemented this with Python (see code).

k=5, n=128, m=100000, T=100: 0.56s per query. (Brute force approach)

That is actually much better than I expected. However, I guess this could be an order of magnitude faster with a good data structure / smarter algorithm. I wrote the Python script in a way which should make it easy to run your own experiments on your tests, if you like.


texts: Average Intelligence Quotient of Computer Scientists?

texts: Have there been studies measuring the average IQ of successful computer scientists/programmers? The US military uses the AFQT test to determine intelligence of potential recruits (100 million Americans aren't intelligent enough to be accepted, according to the source). But I know of no similar way to gauge the average IQ makeup of computer scientists/programmers. That a considerable number of them have a facility with math and have degrees doesn't suggest that they are necessarily geniuses, but does suggest they would place much higher than the average person on IQ tests. I've known a few people who have pursued computer programming and have given up, And not for lack of effort but due to what they felt was a lack of brainpower necessary to grasp a language.


texts: Does a context-free grammar with multiple variables have a "starting" point?

texts:
So lets consider the following grammar

$$
\begin{align*}
S &\to 0 \mid 0A \\
A &\to 1
\end{align*}
$$

would the string "1" be accepted by the language or must the language start with $S$?


texts: Can one consider living (biological) cell to be Turing Complete?

texts:
Universal Turing Machine can be boiled down to two components.
Infinite tape of input and an action table, a finite state machine that moves read/write head along the tape and writes to it depending on input provided by the tape.

From this point of view cells have some properties very similar to UTMs, the DNA is in an essence a tape of instructions that can be read and written to.
Rest of the cell behaves similar to action table, defining rules that guide which part of DNA is read and when it happens, a moving "head" along DNA "tape".

Subquestion 1: DNA can be used for computation. Can entire cell be used for similar purposes?

Subquestion 2: If every living organism contains at least one UTM is it possible that all organism are in some sense Turing Complete?


texts: Relation between "syntax" and "grammar" in CS

texts:
I do sure that "grammar" and "syntax" is two different thing in CS, e.g

  Syntax of Java language is defined by a context-free grammar.

My question are

What is different in definitions of "grammar" and "syntax" in CS?

What is relation between them, can we describe it by using set theory?


texts: A bound for the minimum vertex cover of scale-free graphs

texts:
For a complete graph, the size of minimum vertex cover is $n-1$.

I was wondering whether there exist an upper bound (or an expected value or upper bound) for the size of minimum vertex cover for scale-free graphs, i.e. such whose degree distribution follows a power law.

I searched and didn't find anything, is anybody aware of any bounds?


texts: Is relation extraction considered a subtask of information extraction?

texts:
I'm currently trying to investigate the relationship between relation extraction (RE) and event extraction (EE). Doing more reading on the two tasks has caused me to question my initial belief that RE is within the task of information extraction (IE).
The reason why I believe so is because RE is typically modeled as a prediction task where a model is given two entities and tasked to predict the relationship between them, whereas EE seems to be typically modeled as a sequence labeling task to extract an event trigger and the event's arguments.
More formally, I believe the two can be modeled as:
$$
\begin{align}
\text{RE} & \rightarrow p(r\ \vert\ e_1, e_2, c) \\
\text{EE} & \rightarrow p(l_i \vert\ c)\quad \text{where}\ l \in \{\text{null}, \text{trigger}, \text{argument}\}
\end{align}
$$
where $r$ denotes the relation, $e_1$ and $e_2$ each denote the two entities, $c$ denotes the provided context, and $l_i$ refers to the label of the $i$th token given context $c$.
Anyway, this has led me to believe that RE and EE are fundamentally different tasks, and whether RE is even considered to be within the larger umbrella of IE. Any opinions or pointers to resources/papers are appreciated. Thanks.


texts:
Suppose we need to find a tight asymptotic bound on the worst case run time of the following program

t = 0;
for i = 0 to n-1 do
  for j = i+1 to n-1 do
    for k = j+1 to n-1 do
      t++;

I can't for the life of me figure out what the run-time would be. I have a feeling it would have n! in there somewhere, but I can't seem to wrap my head around it. All help is appreciated


texts: looking for a strongly NP Complete related problem

texts:
I'm looking for a problem that is NP-Complete (even) if the number of input values is at most a polylog of the input size. So some or each value in the input should be so large that the number of values is "negligable".

One way to do this is to say that there is only one input value that should be split and represents the input to another NPC problem. But I consider this a bypass and I'm looking for a more conventional problem.

According to Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded? and its answers, I cannot simply take a strongly NP-Complete problem and represent its input as unary.


texts:
Consider the following setup:

Input: An array of tasks $T=[t_1,t_2,...,t_k]$ where each task $t_i$ is an object that has the following features: start time $s,$ finish time $f$ and coordinates $x$ and $y$, which give the location where the task needs to be performed. Next, we have an array of people $P=[p_1,p_2,...,p_m]$ where each person $p_i$ is an object which initially starts at the origin, i.e. $p_i.x =p_i.y=0.$ Consider the function assign which assigns positions every $10$ minutes to each person of the array $P$ based on the new task array $T$ recieved. Note that every 10 minutes we receive a new array $T$ containing tasks that must be assigned. Furthermore, each person moves at a speed $v$ km/hr to the assigned position.

The goal is to assign as many tasks as possible. What possible algorithms should I look for in order to solve this problem?


texts: About being able to sample a permutation of a finite set uniformly at random

texts:
I was looking at this question.

So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then one can't using this uniformly at random sample a permutation of another finite set (chosen may be adversarially) and also have the algorithm be guaranteed to halt.

Is the above summary right?
Is there a reference to a proof of the above?
Is there a fundamental understanding of this impossibility?
If one is allowed say (1) exponential space or (2) the oracle was picking the numbers with some bias then can we get across this impossibility?
What are the consequences if hypothetically one could do the above?


texts: Question regarding the assumptions of the No-Free-Lunch-Theorem for Search

texts:
I am trying to understand the No-Free-Lunch-Theorem for search (can be found here: http://axon.cs.byu.edu/~martinez/classes/678/Papers/Wolpert_NFLsearch.pdf) and have a question regarding the assumptions that were made by Wolpert et al. with respect to the "general nature" of a search algorithm.
In the paper, the following definitions were made:

$\mathcal{X}$ is the (finite) population of solutions,
$\mathcal{Y}$ is the (finite) evaluation space (e.g. a subset of $\mathbb{R}$),
$f : \mathcal{X} \rightarrow \mathcal{Y}$ is a cost-function,
$d_m = \{ d_m(i) : 1 \leq i \leq m \} = \{ (d_m^x(i), d_m^y(i)) : 1 \leq i \leq m \} \in \mathcal{D_m}$ is the "history", i.e. the sequence of solution/cost-pairs $(x_1,f(x_1)),\dots,(x_m,f(x_m)) \in \mathcal{X} \times \mathcal{Y}$ that were found until time point $m$,
$a : \cup_{i \geq m} \mathcal{D}_m \rightarrow \mathcal{X}$ is a decision function that yields the next solution dependent on the recent history and
$\vec{c} \in \mathbb{N}^{\mathcal{Y}}$ is the histogram, which is the vector that stores the number of times every score was reached up until time $m$.

The work then shows that the equality $$ \sum_{f} P(\vec{c} \mid f,m,a_1) = \sum_{f} P(\vec{c}\mid f,m,a_2) $$ holds for all $m=1,2,\dots$ where $a_1$ and $a_2$ are arbitrary decision-functions and the sum spans over all possible cost-functions. The proof was done via induction on $m$, in which the equality
$$ P(x \mid d_m, f, m+1, a) = P(x \mid d_m, a) $$
was neccessary for the induction step (page 6). As I understood it, this basically means: the choice of the next solution $x \in \mathcal{X}$ is only dependent on the previous history $d_m$, since $x = a(d_m)$, and therefore independent of the cost-function $f$.
I agree that this holds if based on the above definitions, but I don't really think that this is how most search algorithms work? For example, a simple hill-climbing-algorithm would select a set of neighbours for every solution, compare them, and would then select the best neighbour, dependent on how they score on the cost-function. Therefore, the choice of the successor $x$ would depend on $f$, and one would have something like $x = a(d_m,f)$, i.e. the above part in the induction step wouldn't work.
So, my question basically is: am I missing something or is this work based on a wrong understanding of search algorithms?


texts: Average Case runtime for random choice search

texts:
Assuming we have an array with $n$ Elements and want to find an unique element by randomly (uniformly) choosing. What would be the average case runtime?

My thoughts so far:

The chance to find the element is $\frac{1}{n}$ in every step. Thus, to find the element after $k$ steps is $(\frac{1}{n})^k$. Now we can calculate the expected value and get $\frac{n}{(n-1)^2}$. But: that doesn't really make as it returns results $< 1$ for $n > 2$.


texts: Can the pseudo-random-sequence generator be described as a finite state automaton?

texts:
I am thinking some real examples of FSAs in order to help me know how to use the model of the FSA. As I know, the pseudo-random-sequence generator should be a kind of DFAs or FSTs . But I cannot describe a pseudor-andom-sequence generator (e.g. LFSRs) by using $(Q, \Sigma, \delta, q_{0}, F)$.

Specifically, the input of the pseudo-random-sequence generator is the seed which is a short string. However its output is a long (or even an infinite) string. Maybe we   need construct a FSA with a clock, but I have no idea. And what is  $F$ (the set of final states) here? I cannot image what is the language of a pseudo-random-sequence generator.


texts:
I have this problem which is described as follows:

Input:
    You are given a multi-set $M$ (a set that can contain duplicates), and two numbers $P$ and $T$.
    $M = {(x_1,y_1), (x_2,y_2), ..., (x_n,y_n)}$.
    Each $x$ and $y$ is an integer $>= 0$.
    $P$ in an integer $>= 0$.
    $T$ is an integer $> 0$.

Question:
    Is there a subset $G$ of $M$, such that the sum of every $x$ value of $G$ is $> P$ and the sum of every $y$ value of $G$ is $< T$?
    (Note: You are basically taking from $M$. For example: if $M$ has two $(1,1)$'s then $G$ can contain at most two $(1, 1)$'s)

I want to reduce it to from the subset sum problem, but I am not sure how because there's two conditions to solve for...

Can anyone help with this problem?


texts: spanning tree of a DAG (directed acyclic graph) with less forward arcs

texts: I am new to this algorithm and graphs. Just started learning. Could someone help me which algorithm is best suited to find the spanning tree of a Directed Acyclic Graph with less forward edges?


texts: Is it possible to construct 3-dimensional microchips?

texts: In our daily computer, the microchips in it are 2-dimensional, but could it be possible to produce 3-dimensional ones, in some way similar to the brain structure?


texts: This algorithm Big O is true or false and why?

texts:
I have a doubt with this affirmation, I like to know if is true or false and why
$$\log(n) ∈ O(n^{1/2})$$


texts:
I am trying to solve this algorithm exercises (http://neuralnetworksanddeeplearning.com/chap1.html#exercise_513527) in Michael Nielson's online book: Neural Networks and Deep Learning (http://neuralnetworksanddeeplearning.com/chap1.html#complete_zero).

In another word, he says that there is a way to use four neurons to decide 10 digits on top of of the last hidden layer (which consists of 10 neurons and decides 10 digits separately with a high correct rate).

However I couldn't figure out the way. Do you have any idea about this? I look forward to your idea. Any help is appreciated.


texts:
Suppose $P \neq NP$. Does it imply that there exists some superpolynomial time bound, such that any $NP$-complete problem, like SAT, can be used to simulate an arbitrary deterministc Turing Machine working in that time bound?

Rephrasing does $P \neq NP$ imply that there exists some class $D$ of languages solvable by a deterministic Turing Machine, such $P \subsetneq\ D \subseteq NP$ and SAT is $D$-hard?


texts:
Problem Statement

The problem is to calculate the coefficients $A_{j_1\cdots j_n}$, of a square matrix A with size $N$ by $N$ of complex double elements, whose weighted sum with $N^2$ irreducible matrices $[j_1]\otimes \cdots \otimes [j_n]$ is equal to $A$. $N=2^n$, where $n$ is a natural number. $[j]$ are the Pauli matrices for $j=(1,2,3)$ or identity for $j=0$. $\otimes$ is the Kronecker product.

Input

Square matrix $A$ with size (2^n,2^n), where $n$ is a natural number.

Output

Weighted coefficients $A_{j_1\cdots j_n}$, where $j=(0,1,2,3)$.

Details that might be relevant in identifying Missing Application

I wrote a program that computes the full decomposition of a $N
\times N$ matrix into the sum of weighted gamma matrices and their multi-linears in $\mathcal{O}(N^2\log{}N)$ steps.
$$
A = \sum_{k=0}^{n}\sum_{j=1}^{\begin{pmatrix}2n+1 \\ k\end{pmatrix}}
A_{k\{j\}}\sigma^{k\{j\}}
$$
$A$ is the matrix to decompose. $N=2^n$, where $n$ is a natural number. $A_{k\{j\}}$ are the weighted elements to be computed. $\sigma^{k\{j\}}=\gamma^{j_{1}}\gamma^{j_{2}}\gamma^{j_{3}}\cdots$ are the multi-linears equal to the product of $k$ unique gamma matrices. $k\{j\}$ is the $j$th set of uniquely chosen $k$ indices. For example in $N=4$ and $k = 2$: $k\{j\}$ is pick the $j$th element from the list $(01,02,03,04,12,13,14,23,24,34)$, where none of elements share the same indices. Another representation of
$$
A = \sum_{j_1=0}^{3}\cdots \sum_{j_n=0}^{3} \
[j_1]\otimes \cdots \otimes[j_n] \
A_{j_1 \cdots j_n}
$$
where $\otimes$ is the Kronecker product, $[1]$, $[2]$, $[3]$, are the Pauli matrices, $[0]$ is identity, $A_{j_1 \cdots j_n}$ are the weighted elements to be computed in a different basis, and $(j_1 \cdots j_n)$ can be treated as a number in base 4. One can show that multipliting two matrices $[j_1]\otimes \cdots \otimes[j_n]$ and $[l_1]\otimes \cdots \otimes[l_n]$ to get $[g_1]\otimes \cdots \otimes[g_n]$ is equivalent to $(j_1 \cdots j_n)$ xor $(l_1 \cdots l_n)$ = $(g_1 \cdots g_n)$ but missing the sign.

There exists a simple map between $A_{k\{j\}} \longleftrightarrow A_{j_1\cdots j_n}$.

Questions

(1) Does this algorithm already exist?

(2) Does it have an application?


texts: Domain relational calculus to relational algebra

texts:
I have an expression in DRC $\{\langle a,b,c \rangle \mid \langle a,b \rangle \in r \land \langle a,b \rangle \in s\}$, where $r = (A,B)$ and $s = (A,C)$. I want to convert it onto relational algebra and got this:
$π_{A,B,C}(σ_{r.A = s.A \land r.B = s.C}(rxs))$ and I am not sure if it is correct...

Can someone explain if it is correct? Why it is correct or why it is not?


texts:
I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is the defendant guilty?" What complexity class does it belong to?

There are results that have proven that the card game Magic: the Gathering is both NP and Turing-complete so shouldn't similar results exist for legal code?


texts: I read about RadixSort and its time complexity and the worst best and average time Complexity is O(n) , so my question is can radixSort be Ω(n log n)?


texts: Reconstruct the minimal path cost from the delta-stepping algorithm?

texts:
I was coding the delta-steppping algorithm from this paper. They describe almost everything about the algorithm but not how to get the path.
As an output I am getting the dictionary tent where tent[v] contains the minimal cost to go from $s$ to $v \in V$. How can I retrieve the path of the minimum cost based on this algorithm?


texts: Is there a way to predict rendering times?

texts:
In purpose of load balancing I need to approximatively predict rendering time my graphics software (in the specific case it's Autodesk Maya) needs to render a task given an input file (.ma/.mb) and rendering parameters.

An intuitive way to do it is to render several frames from different parts of a scene and to extrapolate the results. Is there a better way to do it?
If no, is it enough to render several separated frames or I should take short series of frames in different moments of the scene?


texts: Is pumping lemma for regular languages "closed" against Kleene star?

texts: If I have an infinite language $L$ which fulfills the Pumping lemma for regular languages, does $L^*$ also fulfill the same conditions?


texts: Who was/were the first person/people to introduce the topic of quantum complexity theory and problem classes like BQP and QMA?


texts: Is there an alternative to full factorization for testing the Polya conjecture?

texts:
The Polya conjecture is a disproved conjecture that states over half the numbers less than any number has an odd number of prime factors. It first fails at $n = 906,150,257$, thus being a good example that testing very many cases is not always enough.

I have been giving "disproving the Polya conjecture" as an exercise a few times, as the counter example is well within computational capabilities.

The simple algorithm for it is to have an incrementing $n$, factorize it, count the factors, and increment either the counter for odd numbers, or even numbers. Continue until you reach the counter example.

Factorization is however an operation to try to avoid, as even the most effective algorithms for that have a nasty computational complexity.

The amount of unnecessary information created by factorizing every number got me wondering if there are better ways. Because:

We do not have to know what the factors of a number are, just how many.
Even the number of prime factors is not needed, as we only need the parity.
We do not have to know the parity of the number of prime factors of each number in a range, it is sufficient to know how many are odd, and how many are even.

Factorization here yields a lot more information than actually needed. Is it really necessary?


texts: Comparison of constructive and local-search heuristics for TSP

texts:
In my high school class, we are currently looking at evaluating heuristic methods for intractable problems - especially TSP.

My question is what is the advantages or disadvantages of using a constructive heuristic (like Nearest-Neighbour) compared to local search (something like 2-opt from some research?)

Thank you


texts: Proof/certificate in a decision problem?

texts:
In this wikipedia article, the following comment is made:

  Consider an arbitrary decision problem in the class NP. By definition each problem instance $x$ which are answered 'yes' have a certificate $y$ which serves as a proof for the 'yes' answer. Thus, the set of these tuples $(x,y)$ forms a relation. The complexity class derived from this transformation is denoted by $\mathbf {F} (\mathbf {NP} )$ or $\mathbf {FNP}$ for short.

Why does this refer to a "certificate"/"proof" $y$? What does this refer to in an actual Turing machine for a decision problem? In my understanding, a Turing machine will simply halt if the answer to the input is "yes", without having to prove that this is so. For some decision problems, there might be such a certificate computed by a turing machine, but this seems not to be necessary (e.g. in analogy with logic: in classical logic we often don't need a constructive proof).

Moreover, there are also function problems that are not derived in this way from a decision problem, right? So it seems to me that FNP is bigger than suggested above. (i.e. it shows how to convert a decision problem into a function problem with the same complexity, but not vice versa).


texts:
Can anyone give me some hint on solving $T(n) = T(\frac{n}{2} + \sqrt{n}) + n$, with any method, master method, substitution....
I have came up with this : $T(n) = T(\frac{(\sqrt{n} + 1)^{2} - 1}{2}) + n$ and then substituting $n = 2^{m}$ but things gets really messy !

any idea?


texts: Minimum Cost Max Flow with Negative Weight Cycles?

texts:
Does there exist an algorithm that can solve the minimum cost maximum flow problem even if the residual graph contains negative weight cycles?

I have an implementation that uses shortest paths to compute the minimum cost maximum flow but this fails to find the minimum cost flow even though such a flow is well defined. This is because it uses Djikstra's to find augmenting paths and gets stuck in negative weight cycles.

I found the cycle cancelling algorithm but it seems that it will augment the flow in the graph in degenerate ways i.e. it might try to circulate flow in a cycle of negative cost even though no flow was passing through those arcs in the cycle.


texts: Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

texts:
I read on the site on how to use the pumping lemma but still I don't what is wrong with way I'm using it for proving that the following language is not a regular language:

$L = \{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

for $i\neq1$ the language is obviously regular but in the case which $i=1$ , we get that the language is $a^1b^nc^n$, now for every division $w=xyz$ such that $|y|>0 , |xy|< p$ where p is the pumping constant I get the word $a^1b^pc^p$ would be out of the language. since  $|xy|< p$
, $y$ may contains only $a's$ or $b's$ or both. if $x= \epsilon$ and $y=a$, pump it once and you're out of the language, if it contains only $b's$, pump it once and your'e out of the language, and if it contains both, pump it and you're out of the language again.

so, why does this language considered as not regular and cannot be proved for its irregularity by the pumping lemma? please point out my mistake.


texts: Minimum bits needed when representing a value in a set

texts:
I'm reading a paper entitled "Succincter" which discusses a compression scheme that involves encoding a value as a sequence of $M$ bits, along with a "spillover" value which can be recursively encoded.

The details of the encoding scheme are not really relevant for the purpose of this question.  Rather, I am specifically interested in asking for some clarification regarding this following excerpt from the paper:

  Assume we want to represent a value from a set $X$ . Any
  representation in a sequence of memory bits will use at least $\lceil \log_2|X| \rceil$ bits in the worst case, so it will have a redundancy
  of almost one bit if $|X|$ is not close to a power of two.

Okay, so I get the meaning here - the author is saying that if we want to represent any arbitrary element $e \in X$, then in the worst case we need at least $\lceil \log_2|X|\rceil$ bits.  But why is it $\log_2|X|$ and not $\log_2 \max X$?

For example, if I have a set $X = \{1, 2, 1e10 \}$, which contains 3 elements, I need at least $\lceil \log_2 1e10\rceil$ bits in the worst case, not $\lceil \log_2 3\rceil$ bits.

Or am I somehow misinterpreting the statement?  The only thing I can assume here is that the author is implicitly assuming some kind of mapping table over an alphabet $\Sigma$ which we use to map each element in the set to an increasing value starting at 0.  But this is never explicitly stated, and would seem to be a large assumption.

So am I missing something here?


texts: how one memory can be accessed simultaneously in instruction fetch and data read?

texts:
In modern computer architecture, pipeline has stage that access memory for normal data and instruction in parallel.

But datas and instructions are usually in same memory, and their access address is different.

But how pipelined cpu can access them in parallel? Are the memory has   two address port for read data and instruction respectively?

If they are in separate memory, they can be accessed simultaneously. But what if there are only one memory for them? one of them is just stalled?


texts: How is pre-computation handled by complexity notation?

texts: Suppose I have an algorithm that runs in $O(n)$ for every input of size $n$, but only after a pre-computation step of $O(n^2)$ for that given size $n.$ Is the algorithm considered $O(n)$ still, with $O(n^2)$ amortized? Or does big O only consider one "run" of the algorithm at size $n$, and so the pre-computation step is included in the notation, making the true complexity $O(n^2+n) = O(n^2)$?


texts: RDF | If something is a rdfs:subClassOf of :Q can you infer it is also rdf:type :Q?

texts:
Given:
:P rdfs:subClassOf :Q

Can you infer the following?:
:P rdf:type :Q

I do not think you can, but I am not fully sure. Whatever the answer is, could you briefly explain why?
(I am not sure if I should be asking this question here as there are no rdf or rdfs tags, but it is to do with my CompSci course :})


texts: two connected graph - find linear spanning subgrap such that subgraph is still connected

texts:
Graph  $G$ is 2-connected.  It means that for each two edges there are exists at least to disjont (in terms of edges) paths.

Graph $G$ is not directed.
Our task is to find spanning subgraph $H$ of graph $G=(V,E)$ such that $H = (V, F)$ such that $F=O(|V|)$ and $H$ is 2-connected.

So far I have came up with some idea, but I have not proved it.

Let execute DFS in order to get DFS search tree.  Now we will get every edge from this tree - then $H$ is spanning of $G$.
Additionally for each node in this tree we add back edges $e$ such that $e$ jump possibly high.

What about this idea ? Could you give me hint in case of I am wrong ?