texts: Relaxed graph coloring, with penalties for assigning adjacent vertices the same color

texts:
Consider a set of $N$ nodes. There is a $N\times N$ non-negative valued matrix $D$ where the $(i,j)$th element $d_{ij}$ gives the "positive metric" between node $i$ and $j$, where $i,j\in [N]$. Thus the diagonal entries of $D$ are all zero and $d_{ij}=d_{ji}$ so $D$ is symmetric.

Then there is a set of  $k$ colors. I want to assign these colors to the $N$ nodes such that the minimum  metric of a common color between any pair of nodes is maximized. So if $c(i)$ is the color assigned to $i\in [N]$ by the assignment $a\in A$, where $A$ is the set of all possible color assignments, we are looking for $$\max_{a\in A} \min_{i,j} \{d_{ij}:c(i)=c(j)\}.$$

Is this problem NP-hard?  If it is, what sort of reduction can be used to show that this problem is NP-hard?


texts: Amortized analysis of resizing array implementation of a stack

texts:
Here is an excerpt from the book Algorithms, 4th edition by R. Sedgewick and K. Wayne:

  Proposition E. In the resizing array implementation of Stack
  (Algorithm 1.1), the average number of array accesses for any sequence
  of operations starting from an empty data structure is constant in the
  worst case.

  Proof sketch: For each push() that causes the array to grow ( say from
  size N to size 2N), consider the N/2 - 1 push() operations that most
  recently caused the stack size to grow to k, for k from N/2 + 2 to N.
  Averaging the 4N array accesses to grow the array with N/2 array
  accesses (one for each push), we get an average cost of 9 array
  accesses per operation.

It is unclear to me why 4N array accesses are required to grow the array. From my understanding, in the proof they describe the case when the array grows from size N to 2N, and for that it should require only 2N array accesses (copy the first N elements, 2 array accesses per element).


texts: Distinguishing between uppercase and lowercase letters in the "move-to-front" method

texts:
Is it not necessary to encode both the uppercase and lowercase letter while encoding a message with the move-to-front transform? From an old computer science course exam, the problem was to encode Matt_ate_the_mat starting with an empty list.

Using the author's solution methodology of not taking into account M versus m one arrives at

$C(1)C^∗(M)\\
C(2)C^∗(a)\\
C(3)C^∗(t)\\
C(1)\\
C(4)C^∗(\_)\\
C(3)\\
C(3)\\
C(5)C^∗(e)\\
C(4)\\
C(3)\\
C(6)C^∗(h)\\
C(4)\\
C(4)\\
C(6)\\
C(6)\\
C(6)$

Seeing that move-to-front works best with items that are repeated this works to one advantage as long as the difference between M and m in the original message is not important, correct?

Though would it not change the last encodings if taking into account m to $C(7)C^*(m)$ or was this done for the sake of brevity within the exam?


texts:
How should I show that ${\sf P}$ is contained in ${\sf NP} \cap {\sf CoNP}$?

I.e., all polynomial time solvable problems and their complements are verifiable in polynomial time.


texts: What is the difference between a block and a procedure?

texts:
A procedure is a sequence of program instructions that perform a specific task, packaged as a unit (Techopedia).

We use block structure to make our code more readable by using indentations and spaces.

Now, is one block the same as a procedure and is vice versa true?


texts: If a CNF contains only Horn and Xor clauses, then what is the complexity of determining Satisfiability?

texts: If a CNF contains only Horn and Xor clauses, and does not contain clauses of other types, then can its Satisfiability be determined in polynomial time?


texts: Understanding why the polynomial $p(n) = \sum_{i=0}^{k} a_in^i$ is in $\Theta(n^k)$

texts:
Hi I've read this lemma in my book:

  Lemma 2.1. Let $p(n) = \sum_{i=0}^{k} a_in^i$ denote any polynomial and assume $a_k > 0$. Then $p(n) \in \Theta(n^k)$

  Proof. It suffices to show that $p(n) \in O(n^k)$  and $p(n) \in \Omega(n^k)$. First observe that for $n > 0$,
  $$p(n) \leq \sum_{i=0}^{k} |a_i|n^i \leq n^k \sum_{i=0}^{k}|a_i|,$$
  and hence $p(n) \leq (\sum_{i=0}^{k}|a_i|)n^k$ for all positive $n$. Thus $p(n) \in O(n^k)$.

  Let $A = \sum_{i=0}^{k-1}|a_i|$. For positive $n$ we have
  $$p(n) \geq a_kn^k -An^{k-1} = \frac{a_k}{2}n^k + n^{k-1}(\frac{a_k}{2}n - A)$$
  and hence $p(n) \geq (a_k/2)n^k$ for $n > \frac{2A}{a^k}$. We choose $c=a_k/2$ and $n_0 = 2A/a^k$ in the definition of $\Omega(n^k)$, and obtain $p(n) \in \Omega(n^k)$.

Can anyone explain me the part $p(n)\in \Omega(n^k)$ of the proof? Why should we divide $a_k\cdot n^k$ by 2? Why can't we take $a_kn^k$ as coefficient of $n^k$? And how do we obtain that $n>2A/a_k$?


texts:
I'm just curious about the pseudocode (or real source code, doesn't matter) of the recursive version of this algorithm. In almost every book chapter/paper when describing this topic, they mention that the recursive version takes exponential time and then they give the code for the dynamic programming approach. I understand how the iterative version (dynamic programming ie. memoization) works. But i just wonder about the recursive version.
For the info, the key part in the iterative code is:

  $\ell$ ... left
  $r$ ... right
  $a$ ... apex
  $T$ ... triangulation

  $T_{\ell,r}= \min\{T_{\ell,a} + \text{perimeter}_{\ell,a,r} + T_{a,r}\}$

So how does the recursive function findOT() seem in
pseudocode or one of these languages (C#, Java, C/C++, PHP, Javascript, SML)?


texts: $A$ nonregular language, is $A\cup B$ nonregular?

texts:
I was reading this question; regarding whether $L=A\cup B$ is nonregular if $A$ is. As is rightly pointed out in that answer, there is no simple rule. But what if we imposed the following conditions:

$A \cap B=\emptyset$
$A\neq B^C$ and $B \neq A^C$

The examples I know of where $L$ fails to be nonregular is where $B$ somehow "makes up" for the nonregularity of $A$, such as setting $B$ as the language of all strings, or the complement of $A$.

But with these new conditions, is there any way for $B$ to turn the union $A\cup B$ into a regular language?

EDIT: Actually, if $L=\{0^n1^m|n,m\geq 0\}$, then

$$L=\{0^n1^n|n\geq 0\} \cup \{0^n1^m|n\neq m\}$$

and both the conditions above are fulfilled. So $L$ can still be regular. Sorry :)


texts: Enumerate all solutions to integer programming problem

texts: How can I list all feasible solutions to an integer program?  Is there an algorithm whose running time is reasonably related to the total number of such solutions?


texts: Has the graph isomorphism problem been solved?

texts:
Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not sophisticated enough to follow the reasoning in the paper.

I do have my own very rough attempt at a polynomial time algorithm without anything like proof, but I'd like to know whether or not this problem has been successfully tackled before proceeding.

So, is the graph isomorphism problem solved?


texts: Subtracting an integer from an ASCII number

texts:
Theoretically, if I were to subtract the number 10 from the ASCII character 10 (which is really 00110001 00110000), what would I get?

Does the computer add both ASCII characters and subtract?


texts:
Problem Statement :

You are situated in an N dimensional grid at position (x1,x2,...,xN). The dimensions of the grid are (D1,D2,...DN). In one step, you can walk one step ahead or behind in any one of the N dimensions. (So there are always 2×N possible different moves). In how many ways can you take M steps such that you do not leave the grid at any point? You leave the grid if at any point xi, either xi≤0 or xi>Di.

Input Format

The first line contains the number of test cases T. T test cases follow. For each test case, the first line contains N and M, the second line contains x1,x2,…,xN and the 3rd line contains D1,D2,…,DN.

Output Format

Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000000007.

Constraints

1≤T≤10

1≤N≤10

1≤M≤300

1≤Di≤100

1≤xi≤Di

Sample Input

1

2 3

1 1

2 3

Sample Output

12

If this was in 1D the solution can be like this : solve(i+1)+solve(i-1);

in 2D : solve(i+1,j)+solve(i-1,j)+solve(i,j+1)+solve(i,j-1);
How can i program it for N Dimensions?
Is their some general steps for making recursion statements like above which could help in making recursive statements

Most solutions which i saw are in bottom up or top down manner i am not able to understand them ? is their any way to understand them ,as i have always practiced dp using recursion + memoization  i find it hard to understand them


texts: Should I keep a relevant constant in the Time Complexity?

texts:
I designed an algorithm, and the Time Analysis provided next time complexity:

$\mathcal{O}(2^p \cdot (\frac{t}{2}/2^p) \cdot \frac{n}{4})$

what must be simplified to:

$\mathcal{O}(2^p \cdot \frac{n^2}{16})$ = $\mathcal{O}(2^p \cdot n^2)$

That constant factor is quite relevant in this case, and the only reason I'm considering keeping it, is because represents an important fact of the algorithm behavior.


texts:
I am given a set of 3D boxes {$B_1$, $B_2$...$B_n$} and each box have length, width and height. But these values are interchangeable since I can rotate the box. I need to find out the maximum sequence of nested boxes.

I have tried this problem using sort. But I still get stuck. I used built in sort function to sort all boxes by length in ascending order. I read the reference about this question and learned that people used radix sort. I have know idea how radix sort is applied here because all sorts I am familiar is comparison sort.


texts: Fractional vertex cover number may not be feasible? Very confusing!

texts:
For my project, I try to use minimum fractional vertex cover number (MFVC). (Please find below definition details) MFVC can be formulated as optimal solution of a linear program relaxation.

However I find that every linear program relaxation is either infeasible, unbounded, or has an optimum solution.

Does is mean that MFVC may not exist, or may not be a finite number, but MFVC is less or equal to minimum vertex cover number? Very confusing! :(

Many thanks!

Definitions:

K-uniform hypergraph:

Minimum fractional vertex cover number (MFVC): link (on page 8)

MFVC as linear programming relaxation:

The minimum fractionl vertex cover $\tau^* (G)$ in a k-uniform hypergraph $G=(V,E)$ is
 $\min \sum_{v\in V}w (v)$

such that $0 \le w(v) \le 1$,

and for each $e \in E$, we have $\sum_{v\in e} w(v) \ge 1$.


texts: What mechanisms prevent a process from taking over the processor forever?

texts: Suppose a process keeps running code (e.g. an infinite loop). How can other programs take over? What prevents the process from remaining active forever?


texts: Is topological sort of an original graph same as post-ordering dfs of its transpose graph

texts:
I have an intuition that topo-sort of an original graph

 A -> B -> C
 D -> B

topo-sort is  [D, A, B, C]   or  [A, D, B, C]

If I transpose the graph

  C -> B -> A
       B -> D

the postordering dfs of this transposed graph also gives  [D, A, B, C]   or  [A, D, B, C]

Please, I can't mathematically prove/disprove it.
If not true, an counter example would helpful.

  A postordering is a list of the vertices in the order that they were last visited by the algorithm

https://en.wikipedia.org/wiki/Depth-first_search


texts:
Why don't we consider conflicts caused due to augmented production?

This picture shows the states of a LR(0) parser.

In the above picture, why we don't consider shift reduce conflict at state I2 ? Shift on '+' and reduce on E'->E. (Augmented production).

Also what is the need of augmented production at the beginning ?


texts:
Given $n$ elements $x_1,\dots, x_n$, and algorithm $A$ which outputs $(r_1,\dots, r_n)=A(x_1,\dots, x_n)$, we say $A$ is $\epsilon$-sorting the list if $rank(x_i) \in (r_i-n\epsilon, r_i+ n\epsilon) $ for all $i$, where $rank(x_i)$ is the exact rank of $x_i$: $rank(x_i):=\#\{j:x_j\le x_i\}$.
Suppose we have a noisy comparator that with $p+1/2$ probability will give the right order between two elements. What's the optimal number of calls to the noisy comparator in order to $\epsilon$-sort a list with probability $1-\delta$?
Algorithm 1 One way to reduce the problem to normal sorting is by amplifying the comparison by using the comparator multiple times and taking the majority vote on it. If we apply it $k$ times the probability of failure will decrease as $\exp(-k/p^2)$. So with $k = \Omega(p^{-2}\log\frac{1}{\delta}\log n)$  and applying any $n\log n$ sorting on top will lead to a sorted list with $1-\delta$ probability.  This would imply a $O(p^{-2}\log\frac{1}{\delta}n\log(n)^2)$ for $\epsilon = 1/n$.
Algorithm 2 Let us assume we are applying quicksort with random pivot. Then with high probability after $O(\log(1/\epsilon))$ recursive levels all partitions are of $n\epsilon$ size, and if all majority votes so far is correct, the ranks must be correct up to $n\epsilon$ indices. This can be ensured with $O(p^{-2}\log\frac{1}{\delta}\log\frac{1}{\epsilon}n\log n)$ calls to the noisy comparator.
My main questions are:

Is the query complexity of algorithm 2 optimal in $\delta$ and $\epsilon$?
Can we avoid asking a fixed pair multiple times? Namely, can we constraint the algorithm to query each pair at most $O(1)$ times?


texts: Program equivalence with Structural induction

texts:
I recently attended my first lecture on structural induction and the professor stated that structural induction can be used to to prove that two programming languages are equivalent.

I am new to structural induction, however from what i have read so far, structural induction is used to prove properties $P$ like arithmetic or boolean expression of a particular language are deterministic. But these deterministic properties allows to define determinacy of a particular language .

How is structural induction used to prove that two languages are equivalent?


texts: Doubt on analysis on time and space complexity of creating n² tuples

texts:
This is a question from a past-yr mid-term paper from my school(using Python language). Attached below is a diagram to show how a robot will move. Don't mind if the link seems dubious as I just used an online screenshot app to make the link, can't find an online link that describes the scenario well.

From the same paper:

Basically, the robot moves forward and turns left whenever it encounters an unvisited grid square to its left. (It just keeps moving towards its immediate left in an anticlockwise direction)

The sequence of instructions given to the robot to transverse a size 3 gird is:
('F', 'T', 'F', 'T', 'F', 'F', 'T', 'F', 'F', 'T', 'F', 'F', 'F')
where 'F' means move one square forward, and 'T' means turn 90 degrees to the left. Note that the last instruction causes the robot to exit the grid.
The function gen_seq takes as input the size of a grid, and returns a sequence of instructions for the robot to transverse the grid. The sequence of instructions is a tuple containing the strings 'F' and 'T' which represent forward and turn commands.
Provide a recursive or iterative implementation of the function gen_seq .
Hint: Recall int can be multiplied with tuple.

State the order of growth in terms of time and space of your implementation and briefly explain your answer.

These are the answers suggested in the markscheme.

def gen_seq(n): # recursive
    if n == 1:
        return ('F',)
    else:
        side = ('T',) + (n-1)*('F',)
        return gen_seq(n-1) + side + side + ('F',)

def gen_seq(n): # iterative
    seq = ('F',)
    for i in range(2, n+1):
        side = ('T',) + (n-1)*('F',)
        seq += side + side + ('F',)
    return seq

Time: O(n^3). In every function call (recursion) or loop (iteration), a new tuple of the length
of the path of each “layer” of the spiral is created. Since the length of the spirals is n^2, and
there are n function calls or the loop runs n times, so the total time is n^2*n = O(n3).
In other words it is the sum of squares: 1^2+2^2+3^2+: : :+n^2 = O(n^3)

Space: O(n^2). End of the day, a new tuple of size n^2 is created and returned.

  1)Am I right to infer that the derivation for time complexity of forming a tuple seems to be sum of length of updated tuple after every recursion/iteration?

If I want to form a tuple with size n^2(size of straightened spiral), first 1^2 has to be formed, then 2^2… n^2, leading to the above sum of squares.

I saw a related post on strings instead of tuples, in this case time= 1+2+…n=n^2, which supports my inference.

https://stackoverflow.com/questions/37133547/time-complexity-of-string-concatenation-in-python

  2)Why is the space complexity O(n^2) instead of O(n^3)? For space complexity, I used to have this impression that for recursive codes that uses some kind of slicing/concatenation would take up space equal to their time, in this case O(n^3). My explanation for this case would be: Since there are n recursions that takes up space on the stack, and each recursion a new tuple of length n^2 is formed from concatenation (no slicing is seen here), space would be O(n*n^2).

I would also think the suggested space of O(n^2) only applies to iterative solutions where no stack frames are observed and only the length of the final tuple(n^2) is included in the space.


texts:
My task is to convert the following grammar to CNF: $S \to SS \mid (S) \mid \lambda$

after removing lambda productions: $S\to SS,  S\to (S),  S\to(), S\to S$

after removing unit productions: $S\to SS, S\to (S), S\to()$

I got upto this point. Do not know how this grammar will be in CNF coz I am not sure if using () makes the grammar illegal. Need help how to proceed and make this grammar in CNF?


texts: What is cold-start penalty ? What are some ways to reduce it?

texts: when a new process is created using a fork() function, there is a cold start penalty, what is this and why does it happen?


texts: Prim's algorithm: difference between brute force and PQ approaches

texts:
I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues.

Given a graph $G=(V,E)$, the former can be stated as in Dasgupta et al.:

X = {}
while(|X| < |V-1|)
  pick a subset S of V for which X has no edges between S and V-S
  let 'e' be the minimum weight edge in E between S and V-S
  X = X union {e}

It uses blue rule and builds the tree edge by edge: at the end you have the MST of the whole graph, until then $X$ is just incomplete. If we use a brute force approach, running time is $O(|V|\cdot |E|)$.

As we know, better running time is obtained mantaining a priority queue that we use to find the cheaper edge incident to the tree that we build on a step by step basis. Anyway i think that this more than just optimization, since solution with this last approach is built incrementally.

Infact, if with brute force you have a tree built edge by edge considering from the beginning the whole graph, with priority queues you instead discover nodes incrementally: at each step you have a valid MST of a subproblem. As long as the algorithm proceeds, every node is discovered and priority queue becomes empty. At this point the MST has grown to be the solution of the whole graph. I can summarize with the following simple example:

You start from node $A$, and edges to $B$ and $C$ are immediately discovered. They become part of the tree. Anyway tree changes as long as new nodes are discovered (see UPDATE label in the picture). With brute force you don't have anything similar.

Please, let me know if i'm mistaken or if my reasoning is not complete.


texts: There are polynomial time algorithms to find maximum weighted matching in a general graph. Is there any algorithm that also handles negative weights in the general graph and find maximum weighted matching for that graph with negative weights ?


texts: how can i say a given problem is in co-NP using it's definition?

texts:
I seem to be having trouble understanding the connection between the formal definition of co-NP and how problems are concluded to be in it. co-NP is defined to be the class containing the languages that are complements to languages in NP (I'm using this definition).

So, given this problem: "given a finite set of integers, is there a non-empty subset that sums to zero?" is in NP. How do i conclude that this problem: "given a finite set of integers, does every non-empty subset have a non-zero sum?" is in the class co-NP?

In other words, how do i know that the second problems corresponding language L2 is the complement to the first problems corresponding language L1?

Perhaps i'm missing something fundamental?!

Edit:
It seems I was not clear enough so hear is a clarification:
My question was why does the complement language L2 represent the second problem if it contains many seemingly random strings?

In other words, how are these seemingly random strings instances of the second problem?


texts: What is considered being proficient in a programming language?

texts: I am a college student looking to get into industry work soon and want to understand what employers consider 'proficient' when it comes to programming languages.  Right now, I understand that to mean that one can write a fully functional program without consulting any references.  However, is there a tangible project or projects that demonstrate proficiency with a language and its libraries?  Preferably projects that employers like to see in their candidates.  My portfolio is relatively weak right now so I want to build that up before I graduate.  Any recommendations are appreciated!


texts: Proof by restriction: when is it valid to restrict to a special case?

texts:
I was reading a few notes on Proof by Restriction and I am confused:
A Valid Proof by Restriction is the following:
Directed Hamiltonian Cycle Problem is NP Complete because if we look only at instances of DHC where For $G=(V,E)\quad (u,v)\in E \leftrightarrow (v,u) \in E$ then it reduces to Hamiltonian Cycle which we know is NP complete.
A wrong proof is the following:

Subset Sum problem
INSTANCE: Integers $a_1, a_2,…,a_n$ and integer B.
QUESTION: Is there a sequence of 0’s and 1’s, $x_1, x_2,…,x_n$ such that:
$$\sum_{i=1}^n a_ix_i \leq B$$

is a special case of

Real Subset Problem
INSTANCE: Integers $a_1, a_2,…,a_n$ and integer B.
QUESTION: Is there a sequence of real numbers  $x_1, x_2,…,x_n$  such that:
$$\sum_{i=1}^n a_ix_i \leq B$$

so it is NP Complete.
My notes say that the this proof is wrong since it restricts the question and not the instances but I don't seem to understand the difference.
Further, I can't really understand how Proof by Restriction works; for all I know I could be restricting an NP Complete problem to a trivial case which can be solved in Polynomial time.


texts:
Recently I have studied Kirchhoff's spanning tree algorithm to count the number of spanning trees of a graph, which has the following steps:

Build an adjacency matrix
Replace the diagonal entries with the degrees of the corresponding nodes
Replace all the other ones excluding the one's included in the
diagonal by $-1$
Then find the minor of any one of the elements to get your answer.

These all steps looks like magic to me. Can anyone explain how Kirchhoff derived this to obtain the number of spanning trees, I want to know the logic behind how this algorithm works, but all I can find in YouTube is the above steps only.


texts: How can I understand a hint for finding the lowest height of the last bulb in a Garland?

texts:
Disclaimer
This is not from an ongoing contest, this is from my course on edx of ITMO.
Also this is a paid courses so the direct link to the problem is not useful unless you also register this course.

Problem description
A garland consists of light bulbs hanging from the same wire. One endpoint of this wire is fixed at a height of $A$ millimeters ($h_1 = A$. Thanks to gravity, the garland bends down: the height of every light bulb which is not at the endpoint is one millimeter smaller than the average height of its neighbors: ($\displaystyle h_i=\frac{h_{i-1}+h_{i+1}}2-1$ for $1 < i < n$).

Determine the smallest height of the second endpoint $B$ ($B= h_n$), given that at most one light bulb is allowed to touch the ground, and for all other light bulbs the inequality ($h_i$ > 0) should be true.

Hint: to solve this problem, you can use binary search.

Input
The first line of the input file contains two numbers $n$ and $A. 3 \le n
\le 1000$, $n$ is an integer, $10 \le A \le 10000$, $A$ is a floating-point number which has at most three digits after the decimal point.

Output
Print a single number $B$ , which is the minimal height of the second endpoint. Your answer is considered to be correct if it differs from the right one by at most $10^{-6}$.

Examples

$\displaystyle\begin{array}{|l|l|}
  \hline
  \text{input.txt} & \text{ output.txt} \\\hline
  8\ \,15 & 9.75 \\\hline
  692\ \,532.81 & 446113.34434782615 \\\hline
\end{array}$

There are problems that you either get it or don't, this is the "don't get it" for me. I cannot correlate the hint to the solution. I mean what we are supposed to search, although I can understand the problem but it's like the hint is the ambiguity for me. Without the hint, I don't know how to proceed, either.


texts:
Language $L$ is trivial if $L=\varnothing$ or $L=\Sigma^*$. I'm trying to prove the following theorem:

If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$.

If $L_2$ is non-trivial the  $L_2\neq\varnothing$ and $L_2\neq\Sigma^*$. If I want to prove that $L_1\leq L_2$, then I need to show that there exists $f:\Sigma^*\to\Sigma^*$ which is total, can be calculated by a Turing machine and follows: $\forall x\in\Sigma^*$, $x\in L_1$ iff $f(x)\in L_2$. I also know that $L_1\in R$ then there is a turing machine $M_1$ that decides language $L_1$. But how do I continue from here? How $f$ should look like?


texts: Why deadlock in cigarette smokers problem

texts:
"The Little Book of Semaphores" (2nd Ed. by Allen B. Downey, section 4.5.1) as well as Wiki (link) mentioned that a trivial solution (as shown below) to the 'Cigarette smokers problem' will cause a deadlock. Somehow I couldn't wrap my head around it. Pls help me undersatnd how deadlock can occur for the below solution.
P.S. We assumed agent code cannot be modified and We're free to use semaphores and other variables as needed

Code sample (from the book):

     Agent A                 Agent B          Agent C
1 agentSem.wait()     agentSem.wait()      agentSem.wait()
2 tobacco.signal()    paper.signal()       tobacco.signal()
3 paper.signal()      match.signal()       match.signal()

     Smoker I           Smoker II               Smoker III
1 tobacco.wait()       paper.wait()           tobacco.wait()
2 paper.wait()         match.wait()           match.wait()
3 agentSem.signal()    agentSem.signal()      agentSem.signal()

    Assume semaphores 'tobacco', 'paper', and 'match' are  initialized with
    zero, and 'agentSem' is initialized with one.


texts: Shift Organization algorithms (Constraint Programming + Marriage problem)

texts:
I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition:

Daily shifts must be covered by workers, who are divided in three groups:

Trainees (Nt = 2)
Regulars (Nr = 3)
Experts (Ne = 7)

The organization constraints are:

All shifts must be covered
A Trainee must always cover a shift with an Expert
Workers covering Friday must also cover Sunday
Nobody can cover two shifts in a row
Nobody works more than M shifts every D days

The process should maximize the following output:

Workers get shifts assigned based on their preference
Experts work as less as possible, only covering unassigned gaps
Number of shifts are evenly distributed

My initial idea is to write a branch and bound algorithm to generate all possible combinations allowed by the constraints. I would then score each solution for each worker based on their preferences, and run a marriage algorithm to get the best combination.

The main problem is that the number of combinations is too (damn) high. Without constraints, there would be 6**30 (~1e24) possible arrangements. I know most of these will be bound, but currently I'm generating at a pace of ~1e8/minute.

I'm wondering if there are any heuristics I could apply to improve the process. Any ideas here? How does this whole thing sound?

Thanks!

Sample code to generate combinations:

def get_combinations(population, base, spots):
    if len(base) == spots:
        yield base
        return

    for candidate in population:
        combo = base + (candidate, )

        if is_viable(combo, population, spots):
            yield from get_combinations(population, combo, spots)

population = {'t1', 't2', 'n1', 'n2', 'n3'}
get_combinations(population, tuple(), 30)


texts: Best Fit Memory Allocation Algorithm Statistical Analysis

texts:
I've been reading book on Operating System, in which author writes :

  Somewhat surprisingly, it(Best fit) also results in more wasted memory than first fit or next fit because it tends to fill up memory with tiny, useless holes. First fit generates larger holes on average.

I want to understand how generating larger holes would be better. It would be helpful if someone can share a link of article about statistical analysis of best fit, first fit.


texts: Can a Turing Machine run for infinitely many steps and halt?

texts: Is it possible for an ordinary Turing Machine, for some input x, to run for an infinite number of steps but also halt? Or do we say that Turing Machine does not halt on x?


texts: Potential function binary heap extract max O(1)

texts:
I need help figuring the potential function for a max heap so that extract max is completed in $O(1)$ amortised time. I should add that I do not have a good understanding of the potential method.

I know that the insert function should "pay" more in order to reduce the cost of the extraction, and this has to be in regards to the height of the heap (if $ \lfloor \log(n) \rfloor $ gives the height of the heap should the insert be $2\log(n)$ or $ \sum_{k=1}^n 2\log(k) $)


texts:
Does a priority queue Queue<K,V> always sort its elements based on the value of each element or its key?

I know than the priority in the queue is based on the key, and that the element with the highest priority has the minimal key (Correct me if I am wrong) But I am not sure about wether the pq sorts based on value.


texts:
What are good approximations for computing log1pexp for single precision and double precision floating point numbers?

Note: log1pexp(x) is log(1 + exp(x))

I have found few implementations of log1pexp for double precision but they don't provide an explanation on how they arrived at the approximations. Hence, I am not able to implement log1exp for single precision numbers (without converting to double precision intermediates of course).

Reference implementation: https://github.com/davisking/dlib/blob/master/dlib/dnn/utilities.h#L16-L29


texts: How to make a Neural network understand that multiple inputs are related to the same entity?

texts:
Neural networks can have multiple inputs.
But some times two or more of these inputs can often be related to a single entity.

E.g : Height and weight of a person to predict the probability of disease or price and Volume of a stock to predict it's value.

How can we make a neural network understand that two inputs are related to the same entity?
Is there any efficient (or inefficient) way of 'tagging' them together?


texts: Is $L = \{ a^nb^nc^j \mid n \le j\}$ a context-free language? I'm getting really stuck generating a grammar for it. Any help would be appreciated.


texts: Why can Multilayer neural networks solve non-linear problems

texts: I understand what a multilayer neural network is, but what about them allows them to solve non-linear problems unlike perceptrons? Is it the fact that they can extend to any number of outputs/hidden layers? Or is it another feature?


texts: Alpha beta algorithm with Iterative Deepening analysis

texts:
I'm implementing a chess engine.

Like many engines, the search for the next best move is done with the alpha-beta algorithm. There are many improvements that can be made to make the algorithm faster and make it able to search deeper into the search tree.

I'm currently considering Iterative Deepening for move ordering so the final search tree hopefully comes close to a perfectly ordered tree. Before implementing this, I want to be somewhat assured that this approach is most likely to introduce an improvement.

It can be shown that the number of static evaluations in a perfectly ordered tree using alpha beta is:

$evals(b,d) = \begin{cases} 2b^{d/2} -1,  \text{d is even} \\
                            b^{(d+1)/2} + b^{(d-1)/2} - 1 ,  \text{d is odd} \end{cases} $

where $b$ and $d$ are the branching factor and depth respectively. This is order $O(b^{d/2})$.

It is also easy to realise that the worst ordered tree has $
b^d$ static evaluations, which is the number of leafs in the search tree (early terminations such as checkmate are ignored for the analysis).

According to wikipedia the order is $O(b^{3d/4})$ for randomly ordered trees. I assume this is the order applicable to my current algorithm (as opposed to $b^d$ evaluations in the worst case).

If I want a search tree of depth $d$ that is close to being a perfectly ordered tree, I would need to compute the perfectly ordered search tree of depth $d -1$ first (you smell the recursion).

I think it is possible to determine if Iterative Deepening is beneficial or not in two ways.

A somewhat informal way is assuming that Iterative Deepening always result in perfectly ordered trees and proving that

$\sum\limits_{i = 1}^d evals(b,d) < \text{average number of evaluations}$

I can not find a formula to determine the number of average evaluations.

A somewhat formal way is using complexity theory and proving that the order of evaluations in the Iterative deepening algorithm (which is??) is better than $O(b^{3d/4})$.

$O(\sum\limits_{i = 1}^d evals(b,d)) + O(b*\log(b)) < O(b^{3d/4})$

$O(b*\log(b))$ is the order of the sorting algorithm used to sort the moves according to their evaluations.

I don't require a full proof perse. It would be nice to hear if my thoughts are correct or not. Any references that discuss this and/or confirm the benefits of this algorithm are also appreciated.

EDIT: I've ran some numbers in matlab and found that the method above results in less evaluations if and only if $b > 2 \wedge d > 0 \vee b = 2 \wedge d \geq 5$. I've also come to the realisation that using this method requires exponential memory and is therefore wiped from the table.


texts: What is the time complexity of Summing Triples with duplicates?

texts:
Summing Triples problem is strongly $NP$-complete as shown by McDiarmid.

Summing Triples problem:

Input: list of 3N distinct positive integers

Question: Is there a partition of the list into N triples $(a_i, b_i, c_i)$ such that $a_i + b_i= c_i$ for each triple $i$?

The condition that all numbers must be distinct makes the problem interesting and McDiarmid calls it a surprisingly troublesome .

  If the input is a multiset of positive integers, What is the complexity of Summing Triples? Does it remain NP-complete?

May be I overlooked an easy reduction from the original problem.


texts: Can Description Logic be expressed by compiler type systems?

texts:
The Semantic Web defines standardised logic under the OWL DL standard.

Programming languages such as OCamel and TypeScript support type inference and algebraic types.

What are the difference between the 2 logic "structures"?

Are they equivalent in terms of being able to implement one in the other and vice versa?

References:

http://derivo.de/en/products/konclude/
https://en.wikipedia.org/wiki/Web_Ontology_Language
https://news.ycombinator.com/item?id=7235628


texts: Running Dijkstra on particular graph with negative weight

texts:
After running Dijkstra on this graph from S, which shortest paths will be incorrect?

This graph has a negative weight, so which shortest paths will be incorrect? after my first attempt I got that Y and Z have wrong shortest paths, but that's not true. Can anyone explain why?


texts: LP Relaxation of Maximum Coverage Problem

texts: So I know from some research I've done that the OPT-IP <= OPT-LP for the maximum coverage problem, however I'm having some difficulty following the explanations I find. Does an example exist where it can be shown OPT-IP < OPT-LP easily?


texts: Is $k$-CLIQUE W[1]-hard for parameter $n - k$?

texts:
It is well-known that the problem of deciding if a graph contains a clique of size $k$ is W[1]-hard with respect to parameter $k$.

Is it also known to W[1]-hard (or perhaps FPT) in parameter $n - k$, where $n$ is the number of vertices of the graph?


texts: How would you model Rust procedural macros?

texts:
In Rust programming language one can write a compiler extension function that works on abstract syntax tree, effectively modifying source code before it gets converted into machine instructions.
In other words, macro function has signature
 Abstract Syntax Tree -> Abstract Syntax Tree

Can these be thought of as higher order functions? Usually higher order functions use function composition to produce their output, not source code manipulation.


texts: Using reduction to prove that a given language is not recursively enumerable

texts:
Let  the language $L$  be as follow  ;

$$L=\{\langle M_1 \rangle \langle M_2 \rangle \mid L(M_1)  \cap L(M_2)=\emptyset \}$$

$\langle M_1 \rangle$ and $\langle M_2 \rangle$ are the encoding of the Turing machine $M_1$ and $  M_2$.

Using Reduction, I have to prove that $L$ is not  recursively enumerable.

In order to prove that I have to find a non-recursively enumerable  language $S$ so that:
$$S \leq L$$
One of the non recursively enumerable that I had in my lesson, were  those :
$${H_{\varepsilon}^\complement}=\{\langle M \rangle \mid \text{M does not halt on empty input} \}$$
 and ;
$${H_{all}}=\{ \langle M \rangle \mid \text{M halts on each input} \}$$

$$ \text{Let then } S = {H_{all}}$$

I  have to prove in this case  that  ;
$${H_{all}} \leq L $$

let then  ;
$$ f : {H_{all}} \rightarrow L  \\
 \langle M \rangle \mapsto \langle M \rangle \langle M^\complement \rangle$$

In this case $M^\complement $ simulate M in each input , when $M$ accepts/rejects, $M^\complement $ rejects/accepts.

$\texttt{case 1}$

$\langle M \rangle \in {H_{all}} \Rightarrow  \text{M halts on each input and accepts/rejects} \Rightarrow  M^\complement\text{ hatls on each input and rejects/accepts} \Rightarrow  L(M) \cap L(M^\complement)= \emptyset  $

$\Rightarrow \langle M \rangle \langle M^\complement \rangle \in L $

$\texttt{case 2}$

$\langle M \rangle \not\in {H_{all}} \Rightarrow  \text{M does not halt  on all inputs} \Rightarrow  M^\complement\text{  halts  on some inputs} \Rightarrow  L(M) \cap L(M^\complement) \neq\emptyset  $

$\Rightarrow \langle M \rangle \langle M^\complement \rangle \not\in L $

somehow  i think , the contruction of the function of is not  right, does anyone maybe have an other idea or an other S to choose ?


texts:
Assuming there is a machine which can effectively calculate functions not computable by a TM (or the Church-Turing thesis as false) What can we say about aTM solving a problem encoded by this machine...

Q1.  Is there a not trivial example of a Turing decidable problem which still remains decidable once encoded with a non-Turing computable function?

Q2. Is there a counter example?


texts: One tape nondeterministic Turing machine accepting non-palindromes

texts:
I have to design a nondeterministic one tape Turing machine that accepts only non-palindromes in $O(n \log n)$ time.
My best shot was only in $O(n^2)$ time. How can I use the properties of NTM on a single tape to find a faster solution?


texts: Are there subexponential-time algorithms for NP-complete problems?

texts:
Are there NP-complete problems which have proven subexponential-time algorithms?

I am asking for the general case inputs, I am not talking about tractable special cases here.

By sub-exponential, I mean an order of growth above polynomials, but less than exponential, for example $n^{\log n}$.


texts: Prove regular languages are closed under f(n) = 2^n and f(n) = n^2

texts: Suppose $ R $ is a regular language, let $ f(R) = \{ w \mid \exists x \text{ such that } |x| = f(|w|) \land wx \in R\}$, prove that $ f(R) $ is regular for $ f(n) = 2^n $ and for $ f(n) = n^2$. I've been on this question for a while now, and I'm not really sure how to approach it. I only really know elementary techniques like Myhill-Nerode and constructing DFA/regex, so I probably won't understand solutions using more complex logical models of regular languages.


texts: How to figure out whether two texts refer to the same object or event

texts:
Let's assume there is something happen in the world - Football world cup final. And team-1 beat team-2 with the score 3:2. So there is whole bunch of articles on every website about it, each contains slightly different wording, sometimes even on different language, but they all about the same event, and contains mostly the same info. Who won, who scored, timing, etc...

So, let's assume we have a 1000 texts about 10 different situation. What is modern approaches in cs, which could

1) group texts about the same situation together (so, instead of 1000 texts - there is 10 groups based on expressed object)

2) packing 1000 texts about the same object into 1, but which contains all new information about object. (Let's say in some text there wasn't coach interview, in some others - no timing where goals was scored, but result text should contain all unique info from each text)


texts: Build PDA for a language with unknown input alphabet

texts:
$L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows:
$L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$
In this exersice I am not given any alphabet and I'm required to build PDA for $L_{12}$, but by definition $M=\left \{Q,\sum,\Gamma ,\delta ,q_0,-|,F\right\}$ and I don't have any alphabet to work with.By intuition if the alphabet is similiar can effect the solution than if it wasn't similiar.


texts: Why w ∈ A if and only if f(w) ∈ B ? Which the signification of "if and only if" ?


texts: What is the runtime to compute the ordered higher-order Voronoi diagram?

texts:
The ordered order-k Voronoi diagram (sometimes written OOKVD) partitions the plane into regions such that the k closest sites are the same and in the same order for all the points in a region.

I am interested in particular in the case k=n, the number of sites.

I would also like to know the upper and lower bounds in the worst-case of the number of faces.

I have found literature saying that these have been studied (e.g., http://ieeexplore.ieee.org/document/6222139/), but I failed to find those results in the references (mostly, they just define the OOKVD, and not discuss their combinatorial and algorithmic complexity).


texts: Is the multiplicative constant in the Big O notation are ignored because of Linear Speed-Up theorem?

texts:
I just want to know if Big O notation was used as a consequences of the Linear speed up theorem or not. For me I guess the answer is yes.
For example, if we didn't have a linear speed-up theorem, then does it mean that we would have a different measure of time/space complexity? i.e. multiplicative constants does makes different. For example, $f(n) = 100 n$ isn't the same as $g(n)=10^{82}n$. Therefore, in this regard, Big O notation is not useful. So, probably we have another way to measure algorithms.


texts: Duplicating the quotation marks in in the quotation-mark enclosed strings

texts:
There is such a grammar

string_literal ::= " { graphic_character } "

The double-quotes that you see must appear in the user program and curly braces mean "any number of graphic characters in the string". The characters are defined further

graphic_character ::= basic_graphic_character | lower_case_letter | other_special_character
basic_graphic_character ::=
upper_case_letter | digit | special_character | space_character

with special characters listed

  " # & ' () * + , - . / : ; < = > ? @ [ ] _ `

I have encountered a situation where I need the double quote to be the part of the string. This is admitted indeed: double quote is a first special character and it enters the basic graphic characters and, thus, graphic characters. So, I can legally put it into my string. But, this means that terminating quotation mark will be considered a part of the string also and parsing will fail. The language specification says that we need to double the quotation marks to produce a single qmark in the string. I do not get why this requirement it is not a part of the grammar. How should proper grammar had to look in this case?


texts: Efficient algorithms for checking non-emptiness of the language of a Turing machine

texts: I know that language non-emptiness is TM recognizable, and one can perform a BFS to find an input string that TM accepts, if there is any. But, what is the most efficient algorithm for that?


texts: answers Average case analysis of linear search

texts:
Suppose we have an array$[1..n]$ and run linear search to find $x$, on it with following specification:
probability of existence $x$ in first half of array is $p$,and probability of existence $x$ in second half is $3p$ and in each half probability of any element to be x is equally likely.Calculate Average case linear search.
Is my answer true?
$E[successful]+unsuccessful=\sum_{i=1}^{n/2}pi + \sum_{i=\frac{n}{2}+1}^{n}3pi + (1-p)(1-3p)n $


texts:
Trying to prove the following problem:

Given a graph $G=(V,E)$ and vertex $s\in V$, prove that: $\forall (u,v)\in E,\ |d_{s}(u)-d_{s}(v)|\leq1$ where $d_s(v)$ is the shortest path from $s$ to $v$ in BFS.

What I did: Let assume that it's isn't true, meaning there is $(u,v)\in E$ so $|d_{s}(u)-d_{s}(v)|>1$. Lets run BFS on graph $G$. If in BFS process there is edge $(u,v)$, this means that $d_{s}(u)+1=d_{s}(v)$ so $|d_{s}(u)-d_{s}(v)|=1$ which contradicts $|d_{s}(u)-d_{s}(v)|>1$. This means that there is at least one edge $w\in V$, in the path from $u$ to $v$.
Now I'm stuck. I don't come empty handed, I have the following theorems:

Given graph $G=(V,E)$ and vertex $s\in V$, for each edge $(u,v)\in E$ we have $\delta\left(s,v\right)\leq\delta\left(s,u\right)+1$ where $\delta(s,v)$ is the shortest path between $s$ and $v$ (or $\infty$ if no such path) in graph $G$ (note the difference between $\delta$ which on $G$ and $d$ which on BFS).
For each vertex $v\in V$ we get $d(v)=\delta(s,v)$ in BFS.

I think I might need to use those two theorems here but I don't see it. My problem is that there is at least one vertex $w$ and not exactly one. How can I prove it?


texts: Runtime of weighted interval scheduling dynamic programming algorithm

texts:
Consider this implementation of a dynamic programming algorithm for weighted interval scheduling:

M-Compute-Opt(j)
    If j=0 then
        Return 0
    Else if M[j] is not empty then
        Return M[j]
    Else
        Define M[j] = max(v_j + M-Compute-Opt(p(j)), M-Compute-Opt(j − 1))
        Return M[j]
    Endif

Here we have a set of requests $\{1, 2, \ldots , j\}$. We're assuming they're ordered by finishing time in nondecreasing order. I.e., $j$ finishes last, $j-1$ second last, etc. $v_j$ is the weight assigned to interval $j$. Also, $p(j)$ is the interval to the left of $j$ that ends as close to the beginning of $j$ as possible without overlapping. We're assuming these were also computed beforehand.

The textbook I'm looking at says the runtime is $O(n)$ because a single call to M-Compute-Opt is $O(1)$ and we call it twice for every empty entry in array M. I almost buy it except it seems to me that we could end up calling it more often for some $i \in \{1, \ldots , j\}$ if the function $p$ maps lots of elements to that $i$. For example, if there is some interval $i$ where right after it ends a ton of intervals start, $p$ would map lots of intervals to it. And of course M-Compute-Opt wouldn't be called from within those instances since the value would be stored the first time, but it seems they would run nonetheless.

I guess in general I understand the argument given in the book, but I was wondering if there is a good one way to understand the linear time from a more intuitive standpoint. I'm not used to calculating runtimes and I feel like if I saw a different problem like this one I wouldn't come up with the "trick" used.


texts: How do you have a type typed "Type" when implementing a programming language?

texts:
I am working on the base of a language model, and am wondering how to represent the base type, which is a type Type. I have heard of an "infinite chain of types", but (a) I can't seem to find it on the internet while searching anymore, and (b) I am not sure if that's what I need or what it really means in practice.
Basically, I have a system in the language like this:
type User
type String
type X
...

Internally these get compiled to something like this:
[
  {
    type: 'Type',
    name: 'User'
  },
  {
    type: 'Type',
    name: 'String'
  },
  ...
]

But actually, the type: 'Type' gets further compiled not pointing to the string 'Type', but to the actual Type object:
[
  {
    type: theTypeObject,
    name: 'User'
  },
  {
    type: theTypeObject,
    name: 'String'
  },
  ...
]

So then the problem is, I need to now define or specify the "type type" itself:
type Type

which I try represent in a similar way, so now we have:
[
  {
    type: 'Type',
    name: 'Type'
  },
  ...
]

which is:
let theTypeObject = { name: 'Type' }
typeTypeObject.type = theTypeObject

Is that correct? What is this really saying? It is a circular structure, does this even make sense conceptually?
What would be better to do in this situation? Or is this perfectly acceptable? Basically I would like to understand how to explain what this circular structure even means, because it just makes me confused.

The type "Type" is typed "Type". It is an element of itself...

That doesn't seem logically possible. So what should I do?


texts: Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points

texts:
I’m attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a heuristic that does the following:
Given a set S containing N start coordinates and a set G containing N goal coordinates, calculate the minimum number of total unit translations of the start points required to move each start points to a goal point such that each goal point is covered. The difficulty is that it does not matter which goal point each start point ultimately lands on.
Here’s a 2d example: You're given a checkerboard with 8 pieces placed randomly on the board in locations specified in set S. G is defined as the set of 8 squares in the bottom row of the board (y=0). For each move, you're allowed to move one checker piece to an adjacent square. Calculate the minimum number of moves required to cover each spot in G with a piece.
I’ve played around with exhaustive solutions to this problem such as generating all the N! ways to arrange the pieces on the goal nodes and finding the distance for each, and I’ve also tried running a search algorithm to find the optimal paths, but these approaches seem too costly to be used as a good heuristic. It’s not so important that I’m able to calculated the actual correct minimum. If I could estimate it within a small margin of error and that error was relatively consistent regardless of the points in the two sets, that would be perfectly fine.
Is there a more efficient way to calculate this than the exhaustive method I tried? A more mathematical way? Or if not, is it possible to estimate it reliably?


texts: Dynamic programming algorithm to merge two lists maintaining relative order and minimizing cost between elements

texts:
So I have a problem in which I have two lists of physical exercises (routines) and I want to merge them such that the merged list maintains the relative order of the previous lists, so for example, if the list A is [a,b,c] and the list B is [d,f,g], a valid merge between the two may be [d,a,f,b,g,c], or even just the concatenation of both: [a,b,c,d,f,g], but not [b,c,f,d,c,g,a]. I know I have in total $\binom{|A| + |B|}{|A|}$ ways of merging these lists and maintaining this property, however I have to select one based on the following constraint:

Every pair of exercises $(e_1,e_2)$ has a burnout function $\delta : (e_i,e_j) \mapsto \mathbb{Z}$ associated to them, and I want to obtain a merged list resulting from the lists $r_1 = [e_{11},e_{12},\ldots,e_{1n}]$ and $r_2 = [e_{21},e_{22},\ldots,e_{2n}]$ such that the total sum resulting of adding every pair of elements applied to the function $\delta$ in $r_3$ is minimum, that is to say, that the following sum applied to $r_3$ is the minimum possible.

$$
\sum_{i=0,j=i+1}^{n-1} \delta(r_3[i],r_3[j])
$$

I was able to solve this using a brute force approach, so basically calculating the $\binom{|A| + |B|}{|A|}$ lists that maintain relative order, and then just calculating the total sum in everyone of them and keeping the one with minimum total sum.

An example would be:

$r_1 = [\text{scissor kicks}, \text{scissor kicks}]$

$r_2 = [\text{mountain climbers},\text{mountain climbers}]$

$\delta(\text{scissor kicks}, \text{mountain climbers}) = 4$

$\delta(\text{mountain climbers}, \text{scissor kicks}) = 3$

$\delta(\text{mountain climbers}, \text{mountain climbers}) = 10$

$\delta(\text{scissor kicks}, \text{scissor kicks}) = 10$

In this case, merging these two lists maintaining relative order while at the same time minimizing the total sum would result in $r_3 = [\text{mountain climbers},\text{scissor kicks},\text{mountain climbers},\text{scissor kicks}]$, which has a total sum of 10.

I know this problem can be solved using a dynamic programming approach in polynomial time however I've not been able to think of a solution yet.


texts: Computing cross-correlation of different size vectors using FFT

texts:
I've been given this exercise as homework but I'm hard-stuck on it for a few hours now.
Basically what I need to show is that cross correlation of 2 vectors of size n and m, for m <= n, can be computed in O(n*log(m)).

say |x| = n, |y| = m.
I tried computing (∗R) because its the same vector with a shift of indexes. I zero-padded both vectors to achieve a mutual length of n+m, so I could use cyclic convolution:

⊛=〖〗^(−1) (()∙())

But now I can't compute these DFTs in O(nlog(m)). I noticed DFT(x)DFT(y) is the convolution xy, but that's like back to square one.

Would appreciate any hint for this problem . Thanks!

Edit:
For 2 vectors of equal sizes, I can zero-pad them then use the cyclic convultion relation from earlier -  ⊛=〖〗^(−1) (()∙()) , and achieve O(nlogn) time.
I failed to do it for n=2m without using 'big' DFTs. I tried breaking x into m-sized chunks. While I can compute the convolution for the first m indexes using 2 m-sized DFTs, I need info from the first chunk to compute the second one...


texts: Which function results from primitive recursion of the functions g and h?


texts: Multi-point evaluations of a polynomial mod p

texts:
Given a polynomial of degree $n$ modulo a prime number $p$, I want to evaluate that polynomial at multiple values of the variable $x$, what is the best way to do this?
I tried using Berlekamp's algorithm for factorization but it takes $O(n^3)$ just to factorize and then $O(n)$ per point evaluation. Is there any other way to bring the complexity down considerably like to  $n\log(q)$ where $q$ is the number of points I want to evaluate the polynomial at? Or possibly polynomial time? All the coefficients and the values of $x$ that the polynomial is to be evaluated at lie between the $0$ and $prime - 1$, the prime is of order $10^6$.


texts: What is the name of the word problem for free groups under straight line program encoding?

texts:
I believe that the word problem is the problem to decide whether two different expressions denote the same element of a suitably defined algebraic structure. For simplicity, let us focus on free groups here. (Because I'm only interested in free algebras, and for groups one might indeed call this a word problem.) The expressions $(b^{-1}c)^{-1}b^{-1}(ab^{-1})^{-1}$, $(ab^{-1}c)^{-1}$, and $a^{-1}bc^{-1}$ are examples of such expressions. The first and second expression denote the same element of the free group, while the third expression denotes a different element.

The straight line program encoding is basically the same concept as arithmetic circuits, without implicit commutativity. It is one of the natural encodings of elements for a free algebra. One way to define the straight line program encoding is like in definition 1.1 from one of the google results for straight line program: The straight line program encoding of $f$ is an evaluation circuit $\gamma$ for $f$, where the only operations allowed belong to $\{()^{-1},\cdot\}$. More precisely: $\gamma=(\gamma_{1-n},\dots,\gamma_0,\gamma_1,\dots,\gamma_L)$ where $f=\gamma_L$, $\gamma_{1-n}:=x_1,\dots,\gamma_0:=x_n$ and for $k>0$, $\gamma_k$ is one of the following forms: $\gamma_k=(\gamma_j)^{-1}$ or $\gamma_k=\gamma_i\cdot\gamma_j$ where $i,j<k$.

The application of the operation $()^{-1}$ can easily be restricted to $\gamma_k=(\gamma_j)^{-1}$ for $j\leq 0$ without increasing $L$ to more than $2L+n$. This means that we are basically talking about words over the alphabet $\{x_1,\dots,x_n,(x_1)^{-1},\dots,(x_n)^{-1}\}$, hence the name "word problem" makes sense. But it seems a bad name for the general problem to decide whether two elements of a free algebra given by straight line programs are identical. It might be called identity testing.

  Does the problem (to decide whether two elements of a free algebra given by straight line programs are identical) already has an established name, or is there a good name for this problem?

Maybe a better idea would be to give a name to the complementary problem, i.e. the problem to distinguish two different elements of a free algebra. So calling it slp distinction problem for free groups (commutative rings, commutative inverse rings, Boolean rings, ...) could work, because straight line program (slp) is a long name (but good and descriptive nevertheless). The advantage of naming the complementary problem is that we get problems in RP and NP, instead of problems in co-RP and co-NP.

The computational complexity of this problem is not worse than that of identity testing of constant polynomials over $\mathbb Z$ in straight line program encoding (no variables, i.e. $n=0$, but the straight line programs allow to compactly encode huge numbers): Using the same approach as in the dlog-space algorithm for the normal word problem, the problem can be reduced to deciding whether the product of integer 2x2 matrices equals the identity matrix. (The word problem over $n$ letters easily embeds into the word problem over $2$ letters, for example you can replace $a$, $b$, $c$, $d$ by $aa$, $ab$, $ba$, and $bb$.) So the problem is in randomized polynomial time (RP) (or rather co-RP). However, I didn't manage to show that it is actually equivalent (in complexity) to identity testing of (constant) polynomials over $\mathbb Z$, as I initially hoped. (This is unrelated to the answer by D.W., which rather shows that the significance of straight line encoding is currently not widely appreciated.)


texts:
I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the classical problems. I have started with 3-SAT problem.
3-SAT problem — was shown to be NP-complete:

Input: A boolean Formula F in CNF where each clause contains at most three variables.
Question: Is that formula satisfiable?

Show now that the simple 3-SAT problem is also NP-complete:

Input: A boolean Formula F in CNF where each clause contains at most three variables and only clauses of length two may contain negated variables.
Question: Is that formula satisfiable?

Can any please explain the main idea? Thank you in advance.


texts: Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently?

texts:
First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and references to study it well.

As I have understood it, whether integer factorization can be done in polynomial time is still an open question and, as this article in wikipedia (https://en.wikipedia.org/wiki/Integer_factorization) puts it,

  When the numbers are very large, no efficient, non-quantum integer
  factorization algorithm is known; an effort by several researchers
  concluded in 2009, factoring a 232-digit number (RSA-768), utilizing
  hundreds of machines took two years and the researchers estimated that
  a 1024-bit RSA modulus would take about a thousand times as long.

So, trying to see that for myself, I have written a very naive code in MATLAB checking it with prime numbers up to 15 digits; the reasoning being that if I can check if a number is prime fast, I can easily modify the code to give me the factorization fast.

The time it takes the code to check if a number is prime doesn't grow exponentially with the input.

function[]=prime(n)
tic
f=floor(sqrt(n));
for i=2:f
    if rem(n,i)~=0
        b=0;
    else
        b=1;
        disp(i)
        break
    end
end
if b==0
    disp('prime')
else
    disp('not prime')
end
toc
end

And so I go back to the question in the title. What is wrong with my reasoning?


texts: How to prove greedy algorithm is correct

texts:
I have a greedy algorithm that I suspect might be correct, but I'm not sure.  How do I check whether it is correct?  What are the techniques to use for proving a greedy algorithm correct?  Are there common patterns or techniques?

I'm hoping this will become a reference question that can be used to point beginners to; hence its broader-than-usual scope. Please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!


texts: Overfitting in Machine Learning Algorithms

texts:
I am new in the ML. I know that overfitting is memorizing the data while training. Like in Neural Network, if we make lots of layers and lots of hidden nodes, we can memorize all the data, but it can be bad because train data would not cover the whole space.

Like this, is there any way to overfit in SVM and Logistic Regression? Since they are linear algorithms, they cannot be something curvy, I guess, so I am guessing the answer would be no. But I am not sure.

Any help is appreciated.


texts: MMOGs as an example of distributed systems

texts:
In the book "Operating System Concepts and Principles" , the authors mentions massively multiplayer online games as an example of Distributed Systems. They mention that as an example of architecture used for this application :

Other MMOGs adopt more distributed architectures where the universe is
partitioned across a (potentially very large) number of servers that
may also be geographically distributed. Users are then dynamically
allocated a particular server based on current usage patterns and also
the network delays to the server (based on geographical proximity for
example).

What is the exact meaning of partitioning the universe ? Does this means that partitioning the map of the game for example and in this case the user will be connected to different servers based on his location in the map or this means that there is a multiple copies of the universe and the user will be assigned to certain server based on network delay and loads ?


texts: How to show {n:U(n,x) is defined for all x} is not enumerable

texts: U(n,x) is Gödel universal function, and we need to show {n:U(n,x) is defined for all x} is not enumerable. I do not have any clue right now. Anyone can give me some hint about this question.


texts: Behavior of non-deterministic Turing Machines after $t_i$ seconds

texts:
Suppose that I have a non-deterministic Turing Machine $M_1$ and its clone $M_2$. Given a string $x \in \Sigma^*$, it is possible that after $t_i$ seconds $M_1$ accepts $x$ and $M_2$ does not halt ? What happens if i run $M_2$ $2t_i$ seconds?

My approach

It is possible because the transition function $\delta_N$ is a partial function and the machines do random guesses, but it can't be that a machine reject and the other accept. If i run $M_2$ for $2_i$ seconds, the outcomes may be different.


texts: Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

texts:
Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$.
I have an algorithm in which I will run a DFS(Depth First Search) but if DFS finds $t$ then it will not change the color(from white to grey) of any of the nodes which comes in the path $s \rightsquigarrow t$ so that if this is the subpath of any other path then also DFS goes through this subpath again.For example consider the adjacency list where we need to find the number of paths from $p$ to $v$.
$$\begin{array}{|c|c c c|}
\hline
p &o &s &z \\ \hline
o &r &s &v\\ \hline
s &r \\ \hline
r &y \\ \hline
y &v \\ \hline
v &w \\ \hline
z & \\ \hline
w &z \\ \hline
\end{array}$$
Here DFS will start with $p$ and then lets say it goes to $p \rightsquigarrow z$ since it doesnot encounter $v$ DFS will run normally.Now second path is $psryv$ since it encounter $v$ we will not change the color of vertices $s,r,y,v$ to grey.Then the path $pov$ since color of $v$ is still white.Then the path $posryv$ since color of $s$ is white and similarly of path $poryv$.Also a counter is maintained which get incremented when $v$ is encountered.

Is my algorithm correct? if not, what modifications are needed to make it correct or any other approaches will be greatly appreciated.

Note:Here I have considered the DFS algorithm which is given in the book "Introduction to algorithms by Cormen" in which it colors the nodes according to its status.So if the node is unvisited , unexplored and explored then the color will be white,grey and black respectively.All other things are standard.


texts: How is the optimal number of hashes is derived in bloom filter?

texts:
As mentioned in several resources such as Wikipedia the optimal number of hash functions for a bloom filter is known to be $$k=\frac{m}{n} \ln 2$$ but how is this number derived? It seems that it's the number that minimizes the false positive rate which is equal to $$(1-(1-\frac{1}{m})^{kn})^k$$
Can anybody explain the steps to find the argmin of the FP rate?


texts: A data structure that makes finding close objects easy

texts:
I’m working on a project that involves a robot and a very large number of reference points. The robot moves around, while the reference points are fixed in space. I would like the robot to be able to tell which reference points are within a fixed distance of it at any point in time. This must be done in an online fashion. There are a very large number of reference points, so iterating through the list is impractical.

This is in many ways similar to a priority queue, but I don’t see any way to adopt that data structure to this context. Every move would require recalculating the distances which appears to require iterating over the entire list of reference points after every move.

Is there a data structure that works for this context? I can allow for a large amount of precomputation if necessary, though the robot’s path isn’t known in advance so I can’t precompute all the relevant distances or something like that. Iterating over the list of reference points can be done during precomputation, just not online because [number of points] * [number of moves] is too large. A solution that is linear in points and sublinear in moves may be feasible, but I would be highly surprised to learn it exists.

I would also be interested in a data structure that tracks the closest waypoint, if that is feasible but the general question is not.


texts:
The problem is:

$$\exists x \forall y (x \ge y)$$

With a domain of all real positive integers.

The negation is:

$$\forall x \exists y (x < y)$$

so, if $y = x + 1$, the negation is true.

That means the negation of the negation (i.e. the original problem) is false.

My question is, that if the original problem is $\exists x \forall y (x \ge y)$, why can't I take $x = y$ and prove the problem true?


texts: Project to nearest point in convex polytope

texts:
Is there a reasonably efficient algorithm for the following task?

Input: a point $x \in \mathbb{R}^d$; a convex polytope $\mathcal{C} \subseteq \mathbb{R}^d$
Find: a point $y \in \mathcal{C}$ that is as close to $x$ as possible

Assume that $\mathcal{C}$ is specified by a collection of linear inequalities, that the dimension $d$ is fairly high, and "close" is measured using $L_2$ distance, i.e., we want to minimize $||x-y||_2$.  is there an efficient algorithm for this problem?

I can see how to solve this in polynomial time using linear programming if "close" were measured using $L_1$ or $L_\infty$ distance, but I'm more interested in the $L_2$ distance metric.  I keep thinking there might be some algorithm based on identifying the set of inequalities that are violated by $x$ and then doing something, but I can't quite put together a working algorithm.

I found the following paper which describes an algorithm (exponential-time in the worst case but often efficient, like the simplex method):

Philip Wolfe.  Finding the Nearest Point in a Polytope.  Mathematical Programming, vol 11, 1976, pp.128--149.

However, that paper requires $\mathcal{C}$ to be presented as a list of vertices rather than a list of inequalities, so it can't be used for my problem.  (Converting from inequalities to a set of vertices will cause an exponential blowup; typically the number of vertices is exponential in the number of inequalities.)


texts: How to answer multiple queries for a tree?

texts:
I encountered an interesting  problem based on tree-data-structure.

We are given a tree which has N nodes, with 1≤N≤105.
Time starts from second 1 and it continues for q seconds.
At each second, the value of each internal node is transferred to all of its child nodes. This happens with all the nodes, except leaf nodes.
Sometimes, at a given time p (seconds), we are asked to return the current value of node x.

There is this O(logN) approach: just find the pth ancestor of the given node x, and output its value.
A harder version of the same problem

Sometimes, at a given time p (seconds), we are asked to return the current value of node x, or we are said to update the value of node x to y.

How to solve this problem for q queries (seconds) efficiently, where 1≤q≤105.
Example
Input
N=5, q=8
Edges of the tree:-
4 3
3 1
5 2
1 2

Values of nodes 1 to 5:-
1 10 4 9 4

Queries:-

1st second:- Add(1,6). Add the value 6 to node 1.
2nd second:- What is the current value of node 3? (?,3)
3rd second:- Add(3,5)
4th second:- (?,3)
5th second:- Add(2,2)
6th second:- Add(5,10)
7th second:- (?,5)
8th second:- (?,4)

Expected Output

6
0
33
25

Explanation

1st second: 6,1,1,13,14 (Values of all nodes)
2nd second: 0,6,6,14,15
3rd second: 0,0,5,20,21
4th second: 0,0,0,25,21
5th second: 0,2,0,25,21
6th second: 0,0,0,25,33
7th second: 0,0,0,25,33
8th second: 0,0,0,25,33


texts: Introductory books on nature sciences behind bioinformatics

texts:
My question goes to those who are concerned with computational biology algorithmics. I'm going to take a course on bioinformatics this fall; the problem, however, is that I have too little background in biology and chemistry to feel prepared for that cycle of lections (I was rather weak at these subjects at school).

Could you recommend any books that would provide a good introduction to the questions of natural sciences that bioinformatics focuses on?


texts: Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one

texts:
What is the complexity of this problem

EULERIAN ARC REVERSAL
Input: a directed graph $G(V,A)$ and an integer $k$
Output: YES if $k$ arc reversals are enough to transform $G$ into an Eulerian graph, otherwise NO

Given an arc $(u,v)\in A$, an act of reversing it will result in the opposite arc $(v,u)$ while the original arc $(u,v)$ will disappear as well.

There are related meta-results on node and edge deletions by Yannakakis. So, I wonder what we can do if the actions are changed from deletion to reversals.
If instead of using Eulerian property, we use Hamiltonian property then we immediately get an NP-complete problem by setting $k=0$.


texts: Why does the Θ-class survive adding a constant only for positive, monotonic, and non-decreasing functions?

texts:
I know that for positive monotonically non-decreasing functions, f(n) and g(n),

f(n) = O(g(n) + c) entails
f (n) = O(g(n))

Why is this always true only for positive monotonically non-decreasing functions? $\Theta$

If there exists one, give a counter-example that shows that the above Big O rule is not necessarily true for functions that are not monotonically non-decreasing.

I'm really confused why the rule specifies only positive, monotonic, non-decreasing functions. Thanks for your help!


texts:
I'm following
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec04.pdf

Last 3 lines of heapify pseudocode are:

if largest =! i
    then exchange A[i] and A[largest]
    Max_Heapify(A, largest)

What is the aim of the last line?
Since largest still holds value of largest leaf, which is now root, what would the recursive run achieve? Just an empty run, it seems.Max-heap is already built.


texts: We are given the 2D coordinates of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a point of intersection? I would like to know the general algorithm and its explanation, don't mind about the extreme cases (e.g. when the rays have the same starting point). P.S. I saw a similar question on another stack exchange, but the answers did were not backed up by explanation.


texts: Why are states called locations in Timed Automata?

texts: I started reading about timed automata lately. In the definition, they have locations instead of states as in automata theory. Can anyone explain why is this?


texts: Validity of CTL formula $s_0 \models EG\ AF\ p$ in given model

texts:
I have been learning Verification by model checking recently and I get the following question:

  Is the CTL formula $s_{0} \models EG\ AF\ p$ valid in the following model?

I think it is incorrect because there is a deadlock or infinite loop about $s_0$ after the state is starting from $s_0$, which make it invalid under $EG\ AF\ $ condition.

Am I correct? How can I prove it (or give a counterexample)?


texts: Does there exist a data compression algorithm that uses a large dataset distributed with the encoder/decoder?

texts:
If my goal were to compress say 10,000 images and I could include a dictionary or some sort of common database that the compressed data for each image would reference, could I use a large dictionary shared by the entire catalog and therefore get much smaller file sizes?  Could this be expanded to work with images in general, i.e. to replace something like JPEG?

Are there existing compression systems that operate like this, where there is a large common set of bits transmitted and loaded before decompression, that has been built by analyzing many images?

For example, is there an existing computer science/machine learning research effort using sparse autoencoding over a large set of images and this concept of distributing a network derived from that encoding with the decompressor?

Note:  Coming back to this question and the answers, I see that it was primarily not understood because those that read it did not understand enough about new types of machine learning.

New techniques in machine learning, particularly deep learning or other advanced neural network systems, do have the potential make many existing data compression techniques outdated.  Or rather, we should expect that some more extensive research will result in these types of powerful encoders.  As of yet this is mainly speculative, and data compression scientists cannot conceive of them without fully understanding the power of the new neural network techniques.


texts:
Hello I am trying to understand the GBN protocol and I encountered the following question during my homework.

Assume that we have GBN protocol with a window size of 20. The sender sends 15 packets one after the other with seq numbers from 1-15. After that, the sender is waiting to get acks from the server (the sender  doesn't have any more info yet).

Now Firstly ack #3 arrives then ack #7 arrives and then ack #11 arrives.
after that, we get a TIME-OUT.

the question is: in response to that T.O mentioned above the the sender will send ----- packets

As I understand after we get the 11th ack we know that everything before has been working just fine.

But I'm getting confused with the window size and the sequence number of the messages.

Please anyone can explain and help.

Thanks.


texts: Are there any known lower-bounds for complexity on Non-determinsitic machines

texts:
For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time.

Are they any problems where we have known lower bounds for the complexity of a problem when using non-deterministic machines?

$NP$-hard or -intermediate problems are probably the most interesting, but others would be interesting (for example, an $\Omega(n)$ lower bound on non-deterministic sorting).

Obviously, there are no known exponential lower-bounds for $NP$ problems, since that would imply $P\neq NP$, but are they any known polynomial bounds?


texts:
The reverse of a string, introduced informally above, can be defined more precisely by the recursive rules $$a^R=a,$$ $$(wa)^R=aw^R,$$ for all $a \in \Sigma$, $w \in \Sigma^*$. Use this to prove that $$(uv)^R = v^Ru^R,$$ for all $u, v \in \Sigma^+$.

This is exercise 3 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. I am not used to this type of exercise, so I would like some help to get the hang of it.
My attempt: Suppose $u = u_1...u_n$ and $v = v_1...v_n$. So, $$(uv)^R = (u_1...u_nv_1...v_{n-1}v_n)^R = v_n(u_1...u_nv_1...v_{n-1})^R \implies (uv)^R = v^Ru^R.$$
Is it correct? If not, any hint? Thanks in advance.


texts: How does an image classifier select relevant features?

texts:
I am trying to understand cascade classifiers for computer vision. I use OpenCV Traincascade for now and successfully trained some cascades.

However I am trying to grasp the whole process. One thing I do not understand about the cascade training is how the features are selected on each stage.

How does an image classifier select only relevant features?


texts: Efficent deterministic algorithm to sort n numbers with many duplicates ( distinct integers $O(\log n)$)

texts:
I seek to sort a sequence S of n integers with many duplications, such that
the number of distinct integers in S is $O(\log n)$. Give an $O(n \log \log n)$ worst-case time algorithm to sort such sequences.
I tried quick-sort, Merge-sort, selection-sort but not getting the required running time. So the question is to design a deterministic algorithm for the problem described.

It is from the book Algorithm Design Manual by Steven Skiena (2nd Ed) problem no 4-23, page no- 154 with some modification.


texts:
This grammar is supposed to give priority to multiplication:

E -> E + T | T.
T -> T * F | F.
F -> x.

A derivation for "x + x * x" would be (unless I'm wrong):

E => E + T => T + T => F + T => x + T => x + T * F => x + F * F => x + x * F => x + x * x.

So how is multiplication given priority over addition? It appears that the addition is produced first.


texts: What are some of the best practices when implementing system call functionality for handling/avoiding "Time of check to time of use" (TOCTTOU) security issues?


texts: Why is heap insert O(logN) instead O(n) when you use an array?

texts:
I am studying about the arrays vs heap for make a priority queue

For check the heap implementation I am reviewing this code:  Heap

, but I have the following question.

Heap is based on array, and for creating an array you need O(n), for inserting into a heap you need O(logN), so if you have a unordered list of task and you want to create a heap, you need O(NLogN).

If you use an array, you need O(n), to create the array, and O(NlogN) to sort the array, so you need O(NLogN).

So if you need implement some similar to this:

function priorityQueue(listOfTask l)

There isn't a diference betwen use an Array or an Heap right? So, why I should use a heap instead an array for solve this function?

Thanks


texts: Lambda calculus :difficulty in getting hang of induction and conversion

texts:
I am going through the book on lambda calculus by Hindley and Seldin .
They introduce the syntactic equivalence of expressions and proving them by a technique named "induction" , which has not been directly defined in the book .

(a) $[N/x]x \equiv N$
(b) $[N/x]a \equiv a$ for all atoms $a \not \equiv x$
(c) $[N/x](PQ) \equiv ([N/x]P)([N/x]Q)$
(d) $[N/x](\lambda x.P) \equiv (\lambda x.P)$
(e) $[N/x](\lambda y.P) \equiv P$ if $x \not \in FV(P)$.
(f) $[N/x](\lambda y.P) \equiv \lambda y. [N/x]P$ if $x \in FV(P)$ and $y \not \in FV(N)$.
(g) $[N/x](\lambda y.P) \equiv \lambda z. [N/x][z/y]P$ if $x \in FV(P)$ and $y \in FV(N)$.

The above are the rules given for substitution in the book. I have some difficulty in understanding (d).
Why is it so that $$  [N/x] ( \lambda x . p) = ( \lambda x . p) $$ ? How to justify this ? Why can't this be defined to be or equal to  $$( \lambda N . p) $$ ?


texts: Show that recurrence is $O(\phi^{\log n})

texts:
I have a function whose time complexity is given by the following recurrence:

\begin{equation*}
    T(n) = \begin{cases}
               \mathcal{O}(1) & \text{for } n=0\\
               T(k)+T(k-1)+\mathcal{O}(1)  & \text{for } n=2k\\
               T(k)+\mathcal{O}(1) & \text{for } n=2k+1\\
           \end{cases}
\end{equation*}

and I have to prove that $$T(n)\in \mathcal{O}(\phi^{\log_2 n}),$$

where $\phi$ is the golden ratio, $(1 + \sqrt5)\over2$.

I think I could prove it by induction but, how would I go on about it if I didn't know that $T(n)\in \mathcal{O}(\phi^{\log_2 n})$ in the first place?


texts: Is an irregular language concatenated with a language with which it has no common symbols irregular?

texts:
Here's an example of what I'm talking about. Suppose I have a languages
$$
L_{1} = \{a^ib^i \mid  i>0\},\\
L_{2} = \{c^i \mid i>0\}
$$

and
$$
L_{1}L_{2} = \{a^ib^ic^i \mid i>0\}
$$

Is it true that if $L_{1}$ is irregular and $L_{1}$ has no common symbols with $L_{2}$, then $L_{1}L_{2}$ is irregular? How would you prove this?


texts:
Not sure if this is the right exchange for this question. But you could definitely answer it. Note professor said this was “wrong” on their quiz.
Question: Identify a daily activity that can be speed up with  parallelization.
My answer: People driving their own car vs people taking a bus.
My reasoning: When people all take a bus they have to wait for all the destinations before theirs to pass. When people drive a car they go directly to their destination.
The professor said this isn’t a good example of a serial processor made parallel. I’m not convinced. Where am I wrong? I plan to argue my case..


texts: Maximizing sum of numbers within a sequence

texts:
Write an algorithm that, given sequence seq of n numbers where 3 <= n <= 1000 and each number k in seq 1 <= k <= 200, finds maximum sum by repeatedly removing one number from seq, except for first and last number in seq, and adding its value to sum of two adjacent numbers. Algorithm ends when there are only two numbers left.

For example:
[2, 1, 5, 3, 4], sum = 0
[2, 1, 5, 3, 4], sum = 1 + 2 + 5 = 8, 1 removed
[2, 5, 3, 4], sum = 8 + 3 + 5 + 4 = 20, 3 removed
[2, 5, 4], sum = 20 + 5 + 2 + 4 = 31, 5 removed
[2, 4] only 2 numbers left so algorithm ends

So far I've written brute force algorithm checking all possible combinations but it's not well suited for large sequences.

My question is, is there more efficient algorithm solving this problem?


texts: Can this algorithm still be considered a Binary Search algorithm?

texts:
While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as follows:

If i have a sorted array of lenght 100 and I see its starting field contains the number 200 and its ending field contains the number 400, me, as a maths studying human, would be likely to start searching around field 35 if I was searching the number 270, and not the field 50 like in a normal binary search algorithm.

Then, if the number on field 35 of the array is 270, 35 is the index I was searching for.

If that isn't the case I can compare the number I got (say 280) and repeat the operation taking the lower part of the array (so I have 35 fields with the starting field containing 200 and the ending field containing 280) if the number I found is greater than what I'm searching for, or the upper part of the array (say I got 260: now I have 65 indexes, the first one containing 260 and the final one containing 400. Orientatively, I would head torward index 4 of this sub array, which is index 39 of the entire array) if the number I got is smaller than the number I'm searching for.

The question is: can this algorithm be considered a binary search algorithm? If not, has it got its own name?


texts:
I am trying to solve a question from the exercise of this book, pg. 46,section 7.4.

Let $M$ be a deterministic Turing machine that only queries oracle strings
that are shorter than the input string. Show that if $A = L(M^A)$ and $B = L(M^B)$ then $A = B$.

I think I have to apply induction. Does it involve self-reducibility concept? Just hints would be sufficient.


texts: Compression of a complete Directed Acylcic Graph

texts:
Consider a DAG $g$ as a label $l$ with a list of sub-nodes $\bar{g}$:

$g ::= l \enspace \bar{g}$

This is an "unfolded" representation of the DAG, i.e. it contains double entries, when two paths reach the same node.

When $g = l \enspace (l_1 \enspace \bar{g_1}, \ldots, l_n \enspace \bar{g_n})$ is ordered-complete, i.e.

$\bar{g_1} = (l_2 \enspace \bar{g_2}, \ldots, l_n \enspace \bar{g_n})$

$\bar{g_2} = (l_3 \enspace \bar{g_3}, \ldots, l_n \enspace \bar{g_n})$

$\ldots$

It can be represented as a list:

$ g \equiv l \enspace l_1 \ldots l_n $

This is, of course, a somewhat more efficient representation (in-memory, sharing the sub-lists wouldn't be that costly) but first of all this is a much more concise notation.
I have to write some such graphs where this is a common pattern and I wonder if there is a name for this kind of compression. Also, is there a generalization of this compression?


texts: Given an n-state TM, can we construct an m-state TM (m>n) to determine if it halts?

texts:
BB(n) is roughly the maximum number of new states an n-state TM can run into without halting. So for a particular n, if we know BB(n), then we can find out if an arbitrary n-state TM halts by running it for BB(n) steps.

So given some n-state TM, can we construct an m-state TM, where m>n, to calculate BB(n) and thus decides if it halts?

Now some might say that this is equivalent to solving the halting problem, but I don't think so. Because given an arbitrary TM, we don't in fact know how many states it has. And if we don't know n, we certainly can't find m.

If the answer is in the negative, then how is it that we can in fact find out the values of BB(n) for small n? What's the connection between incomputability and unknowability?


texts: Is, beta reduction in type theory being considered as counit for hom-tensor adjunction in category theory, a denotational or operational semantic?

texts:
In the article at nlab about the relation between type theory and category theory, it is said that "beta reduction" in type theory corresponds to "counit for hom-tensor adjunction" in category theory and also "substitution" corresponds to "composition of classifying morphisms / pullback of display maps" correspondingly.

Are these considered denotational or operational semantics?


texts: Recognizability of $\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $

texts:
Determine whether the following language is decidable, recognizable but not decidable, co-recognizable but not decidable or neither recognizable nor co-recognizable. Prove your answer.
  $$L=\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $$

[Where $\mathcal{L}(M)$ is the set of words accepted by $M$ and $A_{TM}\leq L$ if there is a mapping reduction from $A_{TM}$ to $L$]

So if I understand correctly the question is whether the set of all $\mathcal{RE}$-hard languages is recognizable/co-recognizable. It seems an easy corollary of Rice's theorem that it is not decidable, and my intuition tells me it is neither recognizable nor co-recognizable but I'm having issues contradicting any reductions.

My approach was, to show it is not recognizable, to assume it is and therefore there is a reduction $L\leq A_{TM}$, where given a TM $M$ recognizing it we would run $M(<M>)$ where I hoped to get some diagonalization argument, but I failed.

Edit: I was able to show that $L\not\in co\mathcal{RE}$, using a reduction $A_{TM,\varepsilon}\leq L$. Given an encoding of a Turing machine $\left\langle M\right\rangle$  define $f\left(\left\langle M\right\rangle \right)$ to be the Turing machine which on input $\left\langle M',w\right\rangle$ :

For $i$ from $1$ to $\infty$:

Run $\left\langle M',w\right\rangle$  for $i$ steps.
Run $\left\langle M,\varepsilon\right\rangle$  for $i$ steps.
Accept if both accepted.

I wasn't able to modify this to show $L$ is not recognizable though, wanted to do a similar reduction using $\overline{A_{TM,\varepsilon}}$, but I have issues either getting a recognizable language when $M$ doesn't halt, as the "common" method of running for $|w|$ steps only produces decidable languages.


texts: How is memory address applied to address pins in RAM chips

texts:
I'm reading this book about assembly however I got stuck on one part, I can't seem to comprehend how memory address is 'applied' to the address pins

This is the image from the book

What I know here is the data pin applies voltage on the memory cell's input or output pin. And for the select pin the book explained that a binary code address is applied to the address pins, I imagined this part where there is only 1 address pin and 'something' is encoding the address to it, however looking at the diagram there are a lot of address pins for a few memory locations and they are connected to each other.

So my question here is how is the address "applied" to the address pins?
Which part of the chip applies the address to the address pings because the book only said "You apply this address to the address pins"

btw, the book is titled "Assembly Language Step-by-Step - Programming with Linux 3rd edition" in case somebody who might've read it before can explain it to me.. Thanks in advance!


texts:
I'm undertaking Theory of Computation Classes. I came across this sentence while studying Recursively Enumerable Grammar:

  Type-0 grammars generate recursively enumerable languages. The
  productions have no restrictions. They are any phrase structure grammar
  including all formal grammars.

What is difference between Formal Grammar and Phrase Structure Grammar?


texts: Assigning one variable to another in 3 address code?

texts:
3 address code is a very common topic in many of the CS theories. I encountered it while studying Compiler Design. According to the Wikipedia article, it says -

  Each TAC instruction has at most three operands and is typically a combination of assignment and a binary operator.

Now my query, does that mean I can assign a variable to another variable(operand) even if it doesn't changes any thing, as this action doesn't violates the exact meaning of TAC(at most three operands). Example for clarity:

a = b*c - d*4

TAC

t1 = b
t2 = c
t3 = d
t4 = t1*t2
t5 = t3*4
t6 = t4 - t5
a = t6

In all the above lines, I haven't violated the TAC rule of at most 3 operands, but in the first 3 lines, I have assigned three variables to three different operands even if it isn't required.

Now technically will that be considered wrong? I know it's inefficient but is it wrong in technical terms? What I think is it's not wrong because the code optimization stage which comes after this will do the filtration if required. Still I want to know the opinions.


texts: In CDC 6600 6-bit encoding, why does it matter what value space character is given?

texts:
How does this affect sorting such that sort function result in:
FOO BAR
FOO

while expecting:
FOO
FOO BAR

Reference
https://en.wikipedia.org/wiki/CDC_display_code#Display_code_characters_(64-character_character_set_version)


texts:
At the midterm there was a variant of the following question:

  For a decidable $L$ define  $$\text{Pref}(L) = \{ x \mid \exists y \text{ s.t. } xy \in L\}$$
  Show that $\text{Pref}(L)$ is not necessarily decidable.

But if I choose $L=\Sigma^*$ then I think $\text{Pref}(L)$ is also $\Sigma^*$, thus decidable. Also $L=\emptyset$ gives the same result. And since $L$ must be decidable I cannot pick the halting problem or such..

How can I find $L$ such the $\text{Pref}(L)$ is not decidable?
Which conditions on $L$ will make $\text{Pref}(L)$ decidable, and which will make it undecidable?


texts: Language of TMs that accept some x in less than 50 steps. Is it in co-RE?

texts:
L = {M | M is a TM and there exists an input that the TM M accepts in
less than 50 steps}

I need to find a minimal
class it belongs to between R/ RE/ co-RE/ not in RE∪co-RE. I managed to show that it is in RE with a TM. I think its not in co-RE, because it has to check every input to know wheter a TM M belongs to L. and there are an infinite amount of inputs. I tried to use mapping recursion with ATM, but that failed. Would appreciate any advice, thanks.


texts: Sampling from a set of numbers with a fixed sum

texts:
Let $s = \{x_1, x_2, \ldots, x_n\}$ be a set of $n$ random non-negative integers where $\sum_i x_i = n$. And let $\{y_1, y_2, \ldots, y_{\sqrt{n}}\}$ denote a subset of size $\sqrt{n}$ of $s$, chosen uniformly at random. Defining $y$ to be $\sum_i y_i$ I am interested in calculating the value of $y$.

By linearity of expectation, I know $E[y] = \sum_i E[y_i] = \sqrt{n}$. But can I prove with high probability that $y$ is close to its mean?

I tried using Chernoff bound but unfortunately since $x_i$'s and therefore $y_i$'s are not independent, I can't apply it here.

I also tried using Chebyshev's inequality since $y_i$'s seem to be negatively correlated but I can't calculate the variance of $y_i$ and the proof would be messy even if I do.

Does anyone have any idea for a simpler proof?


texts: Implementing primitive recursive functions in a programming language

texts:
I started studying Design Concepts in Programming Languages by Turbak, Gifford and Sheldon. In the first chapter, they define a language called POSTFIX, similar to a postfix calculator's input language. This one also has a conditional command and a subroutine-like struct. So, it seemed like it could implement a looping  construct like while. But later, the book gives proof that POSTFIX is not able to encode infinite loops, programs always terminate.

In an exercise, the book wants me to implement a factorial program in POSTFIX, if possible. I tried and failed miserably for hours. I looked up on primitive recursive functions, which factorial is one. Found a language called LOOP, designed by Uwe Schöning that can compute only the primitive recursive functions. I tried implementing in POSTFIX a looping construct that always terminates but could not do it. Because the language does not have any naming or abstraction facilities, I could not see how I can do it.

What I ask is this:

Using the POSTFIX definition given on the below link, can someone implement a language construct that can be used to implement primitive recursive functions, like implementing a looping construct that always terminates? Or give a proof that it is not possible maybe.

Note: There is a draft of the book (thanks @YuvalFilmus) where you can find the description of POSTFIX language (section 1.4, pp5).


texts: How Babbage's Analytic engine made calculations of unlimited extent?

texts:
Brian Randell, in his article The COLOSSUS, explains how computing ushered in the 20th Century, by the development of the Colossus computer. He cites a passage from the Passages from the Life of a Philosopher, illustrating how Charles Babbage described the Analytical Engine :

  That the whole of
  the conditions which enable a finite machine to make calculations of unlimited extent are fulfilled in the Analytical Engine.

I couldn't get how calculations of unlimited extent can be performed by the Analytical engine as described by Babbage. An example would be helpful too.