texts: Complexity of Self avoiding walks in unary

texts:
In this paper http://eccc.hpi-web.de/report/2001/061/ by Maciej Liskiewicz, Mitsunori Ogihara, Seinosuke Toda the complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes it is mentioned that counting number of self avoiding walks of length $n$ is $\#P$ complete and that counting number of self avoiding walks of length $n$ specified in unary is in $\#P_1$.

I understand what unary means and what specifying $n$ in unary means.

However I do not understand the class $\#P_1$ very well.

For $\#P$-complete problems it suffices to show reduction from permanent and it is conjectured that if input length is $O(m)$ we need $2^{\Omega(m)}$ arithmetic operations compute exactly any $\#P$ complete problem.

For $\#P_1$-complete problems which is the central candidate problem from which reduction is done?

In input $n$ is specified in unary what is the conjectured number of arithmetic operations needed $\#P_1$-complete problems?


texts: Problems unsolvable by an oracle machine?

texts:
Are there classes of problems that cannot be solved by an oracle machine? If so, are there specific problem examples of that class of problems?

Even the Omega number, at least the first N digits, could be computed as the Oracle could just return TRUE or FALSE for each {0,1}-digits...


texts: Possible partitions, for k-means problem(k=2)

texts:
I have this brute-force algorithm to solve the problem:

Generate all possible partitions of P into two subsets of P1 and P2

For each partition P1, P2 generated in Step 1, compute the cost of the partition

Report the partition with the lowest cost found in Step 2.

How can I analyze the number of possible partitions and use that to determine the running time?


texts: Recursive definitions over an inductive type with nested components

texts:
Consider an inductive type which has some recursive occurrences in a nested, but strictly positive location. For example, trees with finite branching with nodes using a generic list data structure to store the children.

Inductive LTree : Set := Node : list LTree -> LTree.

The naive way of defining a recursive function over these trees by recursing over trees and lists of trees does not work. Here's an example with the size function that computes the number of nodes.

Fixpoint size (t : LTree) : nat := match t with Node l => 1 + (size_l l) end
with size_l (l : list LTree) : nat := match l with
    | nil => 0
    | cons h r => size h + size_l r
  end.

This definition is ill-formed (error message excerpted):

Error:
Recursive definition of size_l is ill-formed.
Recursive call to size has principal argument equal to
"h" instead of "r".

Why is the definition ill-formed, even though r is clearly a subterm of l? Is there a way to define recursive functions on such a data structure?

If you aren't fluent in Coq syntax: LTree is an inductive type corresponding to the following grammar.

$$\begin{align}
  \mathtt{LTree} ::= & \\
  \vert & \mathtt{list}(\mathtt{LTree}) \\
\end{align}$$

We attempt to define the size function by induction over trees and lists. In OCaml, that would be:

type t = Node of t list
let rec size = function Node l -> 1 + size_l l
and size_l = function [] -> 0
                    | h::r -> size h + size_l r


texts: Is the union of NP Complete language and a finite language (in P) NP Complete?

texts: Let there be a language $A$ which is NP complete and language $B$ which is a finite language, is the union of $A \cup B$ NP complete language?


texts:
Is it true to say that $\Sigma^* \cdot$ {$a^nb^n: n>=0$}  =  $\Sigma^*$

Becuase if we take $\Sigma^*$ and concatenate it to {$a^nb^n: n>=0$} we don't get any "new" words than those we had in $\Sigma^*$ in the first place.


texts: Misunderstanding SS22 Sequencing to Minimize Tardy Tasks

texts:
I was reading "COMPUTERS AND INTRACTABILITY. A Guide to the Theory of NP-Completeness", and I am stuck at this part (page 236, SS22):

In the second paragraph, 3rd line, the authors said that: "The general problem can be solved in polynomial time if $K=0$ [Lawler, 1973], or if $\lessdot$ is empty [Moore, 1968], [Sidney, 1973]. The $\lessdot$ empty case remains polynomially solvable if "agreeable" release times (i.e., $r(t)<r(t')$ implies $d(t)\leqslant d(t')$) are added [Kise, Ibaraki, and Mine, 1987], but is NP-complete for arbitrary release times (see previous problem)."

At first I thought that the problem is in P if $\lessdot$ is empty, since the authors said : "The general problem can be solved in polynomial time if $K=0$ [Lawler, 1973], or if $\lessdot$ is empty [Moore, 1968], [Sidney, 1973]. " but then they said: "... but is NP-complete for arbitrary release times (see previous problem).", which confuses me.

If $\lessdot$ is empty, is the problem in P or not? Or is it only in P if the release times are not arbitrary?

For clarity, I will state the problem as given in the reference book.

[SS2] SEQUENCING TO MINIMIZE TARDY TASKS

INSTANCE: Set $T$ of tasks, partial order $\lessdot$ on $T$, for each task $t\in T$ a length $l(t)\in Z^+$ and a deadline $d(t)\in Z^+$, and a positive integer $K\leqslant T$.
QUESTION: Is there a one-processor schedule $\sigma$ for $T$ that obeys the precedence constraints, i.e., such that $t\lessdot t'$ implies $\sigma(t) + l(t) < \sigma(t')$, and such that there are at most $K$ tasks $t\in T$ for which $\sigma(t) + l(t) > d(t)$?


texts: Determine wether a set of sets contains a partition of a given set

texts:
Consider the following problem :

  Given a set of sets of integers, $\Sigma = \{S_i, i \in I\}$, and a set G, determine wether $\Sigma$ contains a partition of G, i.e. a set $J \subseteq I$ such that $G = \bigsqcup_{j\in J} S_j$.

This problem is (if i'm not mistaken) in NP.

I'm trying to determine wether this problem is in P (Or maybe NP-complete).

Do you know if this problem is treated anywhere in the litterature (Algorithm or NP Completeness) ?
Do you know any problems that are close to this one ?

I have tried to design a polynomial algorithm for the problem, but nothing working so far.


texts: Are fractions more computationally "expensive" than whole numbers?

texts:
I have a problem where the values are represented to humans as [0, .5, 1, ..., 8]

But the function is massively recursive (game trees for a set of increasingly intractable problems) so I'm wondering is it more computationally efficient to use the values [0, 1, 2, ..., 16] and only divide by 2 when outputting for humans?

(Possibly this is a non-issue with high level languages and modern processors.  The hardware we'll be running on is smartphones, but everything has to be local.)


texts: Is there a set of NP-hard problems that are most commonly used for proving NP-hardness?

texts: Are there any NP-hard problems that are considered kind of the standard for reductions? There's so many but it feels like some come up more often than others (for example Vertex Cover, Independent Set, 3-SAT, etc.). I'm sure people just pick whatever is most convenient, but where's the boundary between "more useful" and "too obscure" when choosing a problem to reduce from?


texts: Naive Bayes' Classification and Using the Entire Vocabulary in the Denominator

texts:
I am working through the NLP notes for Naive Bayes' classification here: https://web.stanford.edu/~jurafsky/slp3/6.pdf

Below $c$ is the class of the observation and $w_i$ is the $i$th word of a text document.

In developing the maximum likelihood estimate for the conditional probability of the feature (word) $w_i$ given class $c$ the following expression is given for the conditional probability:

$$\hat{P}(w_i \mid c) = \frac{count(w_i,c)}{\sum_{w\in V} count(w,c)}$$

It is mentioned that $V$ consists of the union of all the word types in all classes, not just the words in one class $c$. The importance of this fact is stressed later on when add-one (Laplace) smoothing is used to avoid probability estimates that equal 0.

It is mentioned that:

It is crucial that the vocabulary $V$ consists of the union of all the word types in all of the classes, not just the words in one class $c$ (try to convince yourself that this is true).

I have thought for awhile on this aside given in the text, but it does not seem to make much sense. To me, wouldn't $count(w,c)$ always equal $0$ for any $w$ which is not contained in a document of class $c$? Why sum over all words in the vocabulary if they will just equal $0$?


texts: Find the number using binary search against one possible lie

texts:
We all know this classic problem,  "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess.

But what if the interactor may lie to us in one case? For example, the number is $3$ and the maximum number we can guess is $10$, but when we ask whether it is greater than $5$ and it replies yes and for the rest of queries it answers correctly. A simple binary search would fail.

How to proceed in this case? What is the minimum number of query in the worst case?


texts: Reference request: optimizing procedures on lists in dynamic languages by performing safety checks in advance

texts:
For my science fair project, I implemented an optimization to Python's sort routine. The idea is to move the safety checks that have to be carried out during each comparison, e.g. type checks and character-width checks, outside of the sort loop and just get them all done in one pass. An optimized comparison function is then selected from a portfolio based on the results of the checks. So, for example, if the checks determine that all the objects are of the same type, the selected comparison function can skip the usually-required "are the object types compatible" check. Etc.

I have to write this up as a paper, and am currently working on a literature review. Are there any papers describing similar techniques in other dynamic languages/generally?


texts: In the Hopcroft-Karp algorithm, what is the purpose of the breadth first search?

texts: In the Hopcroft-Karp algorithm for bipartite matching, I don't understand the purpose of the breadth first search.  I think it's used to find a set of vertex disjoint augmenting paths, but I'm not sure what the significance of that is or even what that means.  Why do the augmenting paths have to be the shortest?  And why do they have to be vertex disjoint?


texts: Are My Answers to This Hamming Code Example Correct?

texts:
I have attempted to answer this question on Hamming code but i am very new to it and would appreciate feedback on my answers, Thank you!

Question

My Answers


texts: What's the complexity of Conflict-Driven Clause Learning SAT solvers, compared to DPLL solvers? Was it proven that CDCL is faster in general? Are there instances of SAT that are hard for CDCL but easy for DPLL?


texts: Can a vectorized computation always be parallelized?

texts:
If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, Mathematica, Matlab, or seek clarification.

Are there situations when a vectorized (aka element-wise application of a function or array programming (AP)) computation cannot be parallelized?

When coding, I frequently replace loops with a vectorized computation, if possible. At times, it's an interesting exercise or (arguably) makes the code more readable. Other times, in hopes of parallelizing it in the future, if need be.

Is there a constraint that would prevent me from parallelizing a vectorized code.

Vectorization example
Note that even seemingly tight loop can be vectorized. For example, cumulative sum of vector elements (1, 2, 3) can be transformed to a matrix form ((1,1,1),(0,2,2),(0,0,3)) and then vectorization is done as column sums producing the desired (1,3,6) cumulative sum. However, vectorization of fibonacci sequence is unlikely(?).

Many thanks for your explanations and references.


texts: If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?

texts:
In my super non-rigorous class on optimization, the prof defined NP as the class of decision problems that cannot be solved in polynomial time. By definition, P is the class of decision problems that can be solved in polynomial time.

Then what is so called co-NP? Does co-NP = P in the sense of 'complement' of a set as used in set point topology?

Is there an intuitive way of explaining the meaning of co-NP in terms of problem that can be solved in _________ time? And the intersection between NP and co-NP?


texts: Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials

texts:
Let's have expressions that are composed of elements of $\mathbb N$ and a limited set of binary operations {$+,\times,-,/$} and functions {$\exp, \ln$}. The expressions are always well-formed and form finite trees, with numbers as leaf nodes and operators as internal nodes, binary operations having two child sub-expressions and the functions one. A value of such an expression is interpreted to mean some number in $\mathbb R$.

There are two limitations on the structure of the expressions: the divisor (the right-hand sub-expression) of $/$ can't be 0 and the argument of $\ln$ must be positive.

I have two questions about these kind of expressions:

Is it possible to ensure "soundness" of such an expression, in the sense that the two limitations can be checked in finite time?
is an equality check between two such expressions decidable?

These questions seem to be connected in the sense that if you're able to check equality of the relevant sub-expression to zero, you can decide whether a division parent expression is sound, and it doesn't seem hard to check whether a sub-expression of $\ln$ is positive or negative if it's known not to be zero.

I know that equality in $\mathbb R$ is generally not decidable, whereas equality in algebraic numbers is. However, I wonder how inclusion of {$\exp, \ln$} changes the result. I suspect that if there exists "pathological cases" where two expressions with dramatically different structure result to the same real number, checking the equality between them might be undecidable, as the $\exp$ and $\ln$ might hinder the normalization of such expressions.

(A side note: I posted an earlier version of a question with similar intent here, but it turned out to have too little thought behind it, and had unnecessary (= not related to the meat of the question) complications with complex logarithms.)


texts: Closure of context-free languages under left-half

texts:
The regular languages are known to be closed under the operation "left half":
$$
\operatorname{left}(L) = \{ x \in \Sigma^* : xy \in L \text{ for some } y \in \Sigma^* \text{ s.t. } |x|=|y| \}
$$
What about the context-free languages?


texts: How to find the mincut of this flow network?

texts: I am trying to find the minimum cut of this flow network, but I feel like I have the cut wrong. Based off this post, I should try to find all reachable vertices in the residual network once there are no augmenting paths, and set that to partition "A", but then I get this weird cut. Is this the right cut?


texts: Ensuring integral result from integral linear program

texts:
An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is totally unimodular.
Suppose that we have an integral LP, how can we then efficiently find an integral maximizer? After all, the optimum may be achieved by many different maximizers rather than just the integral ones.


texts:
It's not that i dont know how to remove εproduction but when complex problem arises i get confused for example

S-->Aa/aaB

A-->a/ε

B-->bbA/ε

CFG without ε production for the above question is

S-->Aa/aaB/a/aa

A-->a

B-->bbA/bb

here i replaced A,B with ε in all productions to obtain the result

But for questions like this one

S-->ABCa/bD

A-->Bc/b

B-->b/ε

C-->c/ε

D-->d

how many possabilities will occur in S production


texts: Dynamic Programming for a variant of the coin exchange problem

texts:
I am interested in solving a variant of the coin exchange problem. Recall the formal definition of the coin exchange problem:

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = {S1, S2, .. , Sm} integral-valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5. See here for further detail.

Here, one can find a tabulation-DP-based solution for this problem. This solution is based on the following recurrence relation:

count(S, m, n) = count(S, m - 1, n) + count(S, m, n - S[m - 1]);

With base cases:

count(S, m, n < 0) = 0
count(S, m, n = 0) = 1
count(S, m <= 0, n >= 1) = 0

Intuitively, this recurrence relation defines a problem as the solution to two sub-problems: Those in where we discard coins, and those for which we assume the coins a progressively used once at the time.

Question: How can I modify this recurrence relation to count the number of ways we can sum to N disregarding order and with an even number of summands? For example, for N = 4 and S = {1,2,3}, there are four solutions total (disregarding order): {1,1,1,1},{1,1,2},{2,2},{1,3}, but only 3 of them have an even number of summands, i.e. {1,1,1,1},{2,2},{1,3}.

Previous research: At first I thought I could double the requested sum for the case of discarding coins, and requesting that each coin is consumed twice for the cases in where we would use some of the coins, i.e.:

count(S, m, n) = count(S, m - 1, 2*n) + count(S, m, n - 2*S[m - 1]);

This works for some sample cases, but it does not work. Any hints?


texts: Is there any literature / results to which fragment of the modal mu-calculus the logic CTL corresponds? I know that in order to tranlsate the until operators of CTL, it suffices to use a single mu-operator. Does this imply that CTL coincides with the fragment of the mu-calculus containing those formulas that are built without using nu-operators?


texts: Runtime of sorting a partially-sorted array

texts:
I have an array of $n$ items which is partially sorted like below:

$$A[i]\le{A[i+k]}$$

where:

$$i=1,2,...,n-k$$

For sorting the array completely, I wonder what the runtime big O is.

I feel only an array of size $k$ needs to be sorted. Because if the sub-array $A[1\le{i}\le{k}]$ is sorted, then all the subsequent sub-arrays are automatically sorted: $A[1+k\le{i}\le{2k}]$ and $A[1+2k\le{i}\le{3k}]$ up to $A[n-k\le{i}\le{n}]$

Therefore the runtime big O might be just $O(k\log{k})$


texts: Why not use the channel capacity as the sliding window size?

texts:
In a sliding window protocol, if we use the maximum possible capacity of the channel as the size of the sliding window, efficiency will be theoretically 100%.
What is the logic behind not doing this?

My guess is that this is done for throttling. Are there any other reasons?

EDIT: After reading the answer by bakuriu, I come to the conclusion that using the capacity as the sliding window size can make the system unreliable:

The receiver buffer may fill up and the increased transfer rate at the sender side will become useless.
Congestion and packet loss may increase.
Reasons are pointed out in the linked answer.

But what if it is an Ethernet (preferably a LAN) using the Selective Repeat protocol for the data flow and CSMA/CD for choosing the sending station.

The receiver window would be of the same size as the sender window. So, filling up the receiver buffer should not be a concern.
There wouldn't be multiple stations competing for data transfer once the transfer has started (because of how CSMA/CD is defined).
In a wired connection (and preferably being a LAN), packet loss would be less.
Sender doesn't have to resend the whole window in case of packet loss or corrupted packet (because of Selective Repeat).

Do we usually try to use the channel capacity as the sliding window size in such (highly customized) cases?


texts:
I've got a problem at hand that's about scheduling tasks to different ressources, basically a simple job shop problem. But: my tasks "branch" dynamically, that is, there are tasks that not only have a start time parameter but also a parameter that defines how many independently scheduled series of tasks the task shall have as successor. So I kind of have a job shop problem with the number of jobs being part of the solution.

Now the question: how do you call this kind of problems? What do I have to look for to find literature about this?


texts: Decidable? If a Turing Machine M, on input w, will M ever move its read/write head to the left?

texts:
If a Turing Machine M, on input w, will M ever move its read/write head to the left?
Determine if this violates Rice's Theorem.

1.
I think the answer for Q1 is decidable because we can make a Turing Machine that decides the problem as follows:

Step 1: If M halts on w and it never moved left, reject it.
Step 2: If M ever moves left, halt and accept.
Step 3: If M loops forever (some configuration repeats) then reject it
Step 4: Otherwise, reject (M moves right, eventually encounters a
blank symbol, and moves right forever, which means that M will never
move left. So, reject it.)

2.
We proved that for some language L L(M) is decidable. So, we can say that L(M) is Turing-recognizable. The property 'L(M) is Turing-recognizable' is trivial because there does not exist a Turing-recognizable L2 such that L2 does not belong to L. Thus, our problem is decidable with the following decider:

"Step 2: If M ever moves left, halt and accept."

, and this does not violate Rice's Theorem.


texts: How to compute amortized complexity of n runs of Dijkstra's algorithm?

texts:
I'm trying to figure out how to compute an amortized complexity/ or complexity of this algorithm. We have a Graph which is oriented. And we are going to run Dijkstra's algorithm for finding a shortest path between vertices, but it has to start only in those vertices, which has no input edge going to this vertex (the vertices with red color).

So Dijkstra would be runned only from red vertices. If we run Dijkstra on all vertices, we could assume that complexity is |V|*Dijkstra but in this case we do not need such big complexity. As is one Dijkstra big, another Dijkstra from another vertex would be runned on less vertices.

The more Dijkstras we run, the less vertices could be visited.

Dijkstra from all vertices should have |V|(|E|+|V|*log|V|) complexity. This complexity should be much lower but I can't figure out where to compute.


texts: Modeling an inequality problem to a graph

texts:
Given $n$ variables : $a_1,a_2...,a_n$ and $m$ inequalities of the form $a_i<a_j$, we want to know if there's a positioning that satisfies all the inequalities.

  a. We want to modelize the problem to a directed graph $G=(V,E)$. $V=?,E=?$

$V=\{a_i|i\in[n]\}$ $E=\{a_ia_j|a_i<a_j\}$

  b. Complete the sentence: There exists a valid positioning iff...

$G=(V,E)$ doesn't contain directed cicles and parallel edges (i.e. to prevent $a_1<a_2$ $a_2<a_3\space$ $a_3<a_1\space$ and $a_1<a_2\space$ $a_2<a_1$)

  c. How do we determine if there exists a valid positioning? What would be the complexity of such action?

I guess check for directed cycles (which i don't know how) and parallel edges?

  d. If there's a valid positioning, how do we find it?

By giving the vertex with maximum $d_{out}$ the lowest number and so on?

I'd appreciate help with c and d.


texts: Extracting intersecting objects of the same colour from an image

texts:
What is the good way to extract the objects(circles) from image as shown in picture below?

respectively create two images one with lines and one with circles from source image.

I started with detecting contours in image to filter everything that may be circle from image which gives me results like this:

I'm new to computer vision and dealing with this specific task, so want thank you for any help and guidance.

Thank you all, here are some answers to questions from comments:

  Define "best"

a good way to do it

  Which techniques do you know that have something like that?

Today I looked at template matching, created a template for the black and white circle and localised them in an original image.
Once I have this extracting lines is straightforward (just subtracting circles from the original image).
This seems working well in the simplest scenario when circles are the same size as templates.

The more robust way I think will be to use Haar Cascade classifier, train it on different size circles, and continue as with results from template matching.

Correct me if there maybe a better way?

The main idea is to digitalize diagrams consisting of black and white circles connected by lines,
The size of diagrams and quality of images may vary. Also, the circles may contain numbers (Extracting those is something for future)

The lines connecting circles are axis aligned, they define position of circles in diagram (similar to cartesian plane)

I mentioned Python (js) and OpenCV languages in case there are some specific implementation details I should be aware of. I'm also learning Python while doing this :).

I don't expect the solution or code, rather pushing to right direction and strategy to deal with this kind of problems.


texts: Combinational Logic Circuits and Theory of Computation

texts:
I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything I have learned recently in Theory of Computation.

I was wondering whether combinational logic circuits can implement computations in the same way finite state machines can. They seem radically different :

Finite State Machines, however, have a well-defined memory in the form of the states that it can be in.   Combinational logic circuits, however, don't have a well-defined memory so to implement algorithms that need memory they kinda use some weird method of serial connection ( see how $C_{out}$ of previous adder is connected to $C_{in}$ of current adder in the image bellow ) .

However radically different might seem, they both seems to be doing computations. For instance, both can implement an algorithm for binary addition ( and even binary multiplication ) however different those implementations might be :

FSM :

Combinational Logic Circuit  (  C, as in $C_{in}$ and $C_{out}$, stands for Carry ) :

I'm even thinking ( although still very uncertain ) that we can convert every FSM into a corresponding Combinational Logic Circuit.

So, i'm asking myself :

Can Combinational Logic Circuits also be considered a instantaneous kind of model of computation ?  Can we apply all concepts we learn in Computability Theory and Computational Complexity Theory, like space complexity and computability, to it ?

On one hand, it seems like they don't fit as a model of computation because they don't have elementary operations ( like reading/writing of a tape,  function reduction,  steps on the proof search of logical programming paradigma ), they implement their computations instantaneously.
But on the other hand, they seem to be fit as a model of computation because we can model all kinds of computation with them ( binary addition is one example ), and they can be viewed abstractly ( by only focusing on the truth-tables and the logical gates and forgetting about the physical circuit that might implement it ).
So, what do you guys think ?

Also, if it can indeed be considered as a (instantaneous kind of ) model of computation, do you guys have any example of other similar ( also a instantaneous kind of ) model of computation ?

Thanks a lot in advance


texts:
I've only recently learned anything substantial about finite automata, and I've just come across some things I hadn't seen before. Specifically, that classic NFAs are ∪-NFA, and there are also these things ⊕-NFA , ∩-NFA and ⋆-NFA (I love unicode). These can all be seen in http://fastar.org/publications/PresentationFEW2006Geldenhuys.pdf or http://www.cs.sun.ac.za/~lvzijl/publications/fsmnlp2009.pdf

How are these different from the NFAs I'm familiar with?


texts: Efficient top eigenvalue computation for Hessian of neural networks

texts:
I train a neural network - one of the Resnet variations ($\approx 10^7$ parameters) on the CIFAR-10 dataset - and after each epoch, I would like to find the smallest/largest eigenvalues of its Hessian. Formally, we can view our NN as a function: let our dataset (training set) be $D$, let $x$ be NN parameters, and we want to minimize
$$f(x) = \frac 1 {|D|} \sum_{d \in D} \text{loss}(x, d)$$
Now, we consider Hessian of this function
$$\nabla^2 f(x) = \frac 1 {|D|} \sum_{d \in D} \nabla^2 \text{loss}_{xx}(x, d)$$
For a given NN parameters $x$, I want to find the smallest and largest eigenvalues $\nabla^2 f(x)$.
For that, I can use hessian-vector products, i.e. for any vector $v$ I can compute $\nabla^2 f(x) \cdot v$ (PyTorch has a built-in mechanism to compute $\nabla^2 \text{loss}_{xx}(x, d) \cdot v$ for any batch $d$), so, for example, I can use the power method. However, the pure power method will be very slow: one needs a pass over the entire data $D$ to compute the true Hessian-vector product.
Question: do you know of an efficient algorithm for this task? To be precise, I mean that both eigenvalues can be computed with a reasonable multiplicative error within at most 1 minute each. (The run aside from that takes 5 hours and I need to compute both eigenvalues about $40$ times per run, so it's the time I'm ready to spare. There are a lot of runs, so this is my limit.)
Note that I'm asking about an algorithm that you know to be efficient for this (or similar) problem. I tried the power method, accelerated power method, stochastic power method, Oja's algorithm, gradient-based algorithm, its accelerated version, algorithms from https://arxiv.org/abs/1707.02670. All these experiments take a lot of time and so far I didn't have any success, no matter how much engineering I used. When eigenvalues are close to $0$ (e.g. of order $-\frac 12$, when the largest eigenvalue is of order $100$), either convergence takes a lot of time or the results are unstable/unreliable.
Just in case, I'm aware of PyHessian (and the first version of my code is based on theirs).
My current best solution is the one that performs the power method with increasing batch size. In a good scenario, it looks like this:

The left plot shows eigenvalues, the right plot shows what I call "error": $\|v - \frac {H v} {v^\top H v}\|$, where $Hv$ is a hessian-vector product computed at the last iteration, and $v$ is the current eigenvector candidate of norm $1$.
Red lines separate cases when I dramatically increase batch size: I first use a lot of iterations with a small batch size (64 images), then 1000 images per batch, and in the end, I increase the batch size until it reaches the whole dataset. It can be seen that the power method with a smaller batch size always has a limit beyond which it can't grow.
The problem is that this approach takes $4$ minutes for one eigenvalue - $4$ times more than what I'm ready to spare. Decreasing the number of batches at every step is detrimental to quality when eigenvalues are small. If the eigenvalue is closer to $0$, it already doesn't finish converging to it with this number of iterations:


texts:
I'm trying to figure out how evolution strategies would work for the traveling salesman problem. I've done this with the genetic algorithm already, but am curious about how this would be done using ES.
To my understanding, the main genetic operator for the GA is the crossover, and for the ES it's the mutation. The ES can adapt its mutation step size for each gene to converge faster to an optimal solution. How would this work for a combinatorial problem like the TSP though ? Start by mutating 5 cities per mutation, and slowly progress to 1 ?
I know that ES are not primarily designed for combinatorial problems, but some papers compare different evolutionary algorithms for the TSP and ES are usually one of them, so I know it can be done. But I'm having a hard time finding some explicit implementations.
Thank you in advance!


texts: Why divide a stack into two parts and store them separately in main-memory and hard-drive a bad idea?

texts:
I'm learning data structure and trying to solve problem related to Computer Game like Chess/Go.  There is a line in my book on the section of DFS algorithm, which is implemented by two stacks: one for storing the open-list the other for current path. It says there is no good (I think it means efficient) algorithm to manage the stacks when the tree to search is skewed heavily (Say it has two depths: $D$ and $d$ where $D >> d$ so the time complexity of order $O(D)$).
I cannot understand why it's inefficient? I can just append the stack in main-memory to the one on the disk?


texts: Using Data Compression on the output of Data Compression

texts:
Context:

Lossless Data compression (source coding) algorithms heavily rely on repetitive  pattern (redundancy)

Questions

Is there a data compression method/algorithm that uses another data compression on the compressed data obtained so far?
 If such a method exists, what are its limits?


texts:
Problem Statement:
Suppose that I have a $0-1$ matrix $A$ (all of the entries are $0$ or $1$). I wish to find the tightest upper bound with $k$ many unique rows. To be more precise, let S denote the set of $0-1$ matrices $B$ such that it only has $k$ unique rows, $A_{ij} \leq B_{ij}$ for all $i$ and $j$.
Find
$$\min_{B \in S} ||A - B||$$
Example:
Suppose $k = 2$ and
$$A = \begin{bmatrix}
1 & 0 & 0 & 0 & 0\\
1 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 1\\
0 & 0 & 1 & 1 & 0\\
\end{bmatrix}$$
Then the optimal matrix $B$ is
$$A = \begin{bmatrix}
1 & 1 & 0 & 0 & 0\\
1 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 1\\
0 & 0 & 1 & 1 & 1\\
\end{bmatrix}$$
Since $B$ only has $2$ distinct rows, $A \leq B$, and $||A - B|| = 3$ is minimized.
Question 1:
This problem reminds of the minimum $k$-union, set-union, and other NP-complete problems. Is this problem an NP-complete optimization problem?
Question 2:
Is there an efficient way to obtain approximately optimal matrix $B \in S$? Instead of minimizing $||A - B||$, can we get close to the minimum possible value?
So far, I have tried to cluster each row of matrix $A$ using k-means. Then within each cluster $i$, I tried to construct a vector $v_i$. Where $j^{th}$ entry of $v_i$ is $1$ if at least p-percent of the vectors in cluster $i$ has $j^{th}$ entry to be $1$. The vectors $v_i$ served as initial potential guess for possible rows of the matrix $B$. Then I used greedy algorithm. This has decent performance, but it's not great.


texts: Help with proof involving weighted full binary tree

texts:
Given a full binary tree, $T$ (each node is either a leaf or possesses exactly two children), with $n$ leaf nodes: $v_1,v_2,...,v_n$, and weights associated with the leaf nodes: $w_1,w_2,...,w_n$, the cost of the tree, denoted by $|T|$, is defined as:  $$|T|=\sum_{i=1}^{n}w_il_i$$
Where $l_i$ is the depth of $v_i$ in $T$.

Example:

The cost of the above tree is:
$0.25\times 4+ 0.18\times 4+0.5\times 3+0.4\times 2+0.31\times 3+0.2\times 4+0.1\times 4+0.65\times 3+0.2\times 3=8.7$

Now, I need to prove two things. I'll start with the first.
1. Let $T$ be a full binary tree with $n$ terminal (leaf) nodes, then $T$ has $n-1$ internal nodes.

The proof for this is not too difficult. Using induction on the number of terminal nodes, I can easily prove it. The second is not so trivial, and this is where I need help. Before I'll move on to what I'm trying to prove, I'll introduce another concept.
Let's associate now weights with internal nodes: the weight of an internal node is the sum of the weights of its two children.
Example:

Now for the shocker:

Given a full binary tree, the sum of the $n-1$ internal nodes is the cost of the tree.

This looks surprising at first, but when you rethink about it, it makes sense (the picture above demonstrates it). My problem is proving it.
I tried proving by induction, but I got stuck in the inductive step (the base case is obvious).

Any help would be greatly appreciated.

**EDIT

Let me show exactly where I'm stuck:

Base case is easy.
The first way @Yuval Filmus suggested:
For the general case, since the number of leaves $n$ is bigger than $1$, then the tree can be split to two trees; the left subtree of the root, call it $T_l$ and the right subtree of the root, call it $T_r$, each has $n_l$ and $n_r$ leaves ($n_r,n_l\geq 1$ and $n_l+n_r=n$).
Now, according to the induction hypothesis, the cost of $T_l$ is the sum of the $n_l-1$ internal nodes in $T_l$, and the cost of $T_r$ is the sum of the $n_r-1$ internal nodes in $T_r$.
I don't know what exactly does that imply with regards to the entire tree $T$...

The second way @Yuval Filmus suggested:
For the general case: $T$ (with its $n$ leaves) is obtained from a smaller tree, call it $T'$, in which two leaves was removed.
According to the induction hypothesis, the cost of $T'$ is the sum of its $(n-1)-1=n-2$ internal nodes.
Again, how should I proceed? I feel like something is missing...
So suppose I say the cost of $T'$ is: $|T'|=\sum_{i=1}^{n-2}w'_i$, where $w'_i$ corresponds to an internal node. (it is denoted with apostrophe on purpose, to distinguish these weights from the $w_i$s - the weights of the terminal nodes).
Am I on the right track?


texts: How to draw a clearly arranged DFA of a language with modulo rules?

texts:
I know how to draw a DFA, but I have problems with this specific one:

${L = \{ w \in \{a,b,c\}^* \mid \ |w|_a \equiv |w|_b - 2|w|_c \mod \ 5 \} }$

This language is regular and there has to exist a DFA (It would be great if someone could leave a comment WHY a language like this one is regular). Finally, I got a solution, but I'm not really satisfied with my solution. How can I present the DFA in a more clearly way? (is it possible to draw a "Planar graph" of it?)


texts: Can there exist a recurrence relation for "sequential search"?

texts: I'm just confused, cause from my knowledge recurrence is applied mostly to recursive procedures or divide and conquer techniques etc.


texts: Why does a prepare message wants a promise that an acceptor is never to accept a proposal numbered less than its propose sequence value? (Paxos)

texts:
I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

On page 4 of the paper, at the bottom where they outline what a prepare request looks like it says:

  "A proposer chooses a new proposal number n and sends a request to
  each member of some set of acceptors, asking it to respond with:

  (a) A promise never again to accept a proposal numbered less than n,

  (b) ... "

Why does prepare message extract such promise from the set of acceptors that receive such a prepare message? What is the goal and what safety guarantee does it provide? How does it aid Paxos into reaching a consensus to a certain value? How is it crucial so that a majority can reach agreement?

I did some further research to try to answer this question and went to the following yale university notes:

http://pine.cs.yale.edu/pinewiki/Paxos

These notes try to justify this point by saying:

  "... proposer tests the waters by sending a prepare(n) message to all
  accepters where n is the proposal number. An accepter responds to this
  with a promise never to accept any proposal with a number less than n
  (so that old proposals don't suddenly get ratified)... "

Basically, the way they justify that step is by saying so that old proposals don't get ratified/accepted. Which I kind of see why they said that, since if a decision has happened, that rule definitively avoids the consensus from being reversed, which is nice. But, however, the reason I did not feel very convinced about it yet is because it seems to damage termination a lot. What if if a majority was about to be formed in the past and the proposer was ready to send the propose(n) and now because a different prepare(n') was sent its not able to reach agreement? I can't seem to convince myself that that this step is 100% a good idea.

Unless the only reason for that step is because they just want to guarantee that once a value has been chosen/decided, by adopting this rule, its impossible that any old proposal reverses the decision?

Again, I did some further research by reading the yale article and now it says:

  "The rule that an acceptor doesn't accept any proposal earlier than a
  round it has acknowledged means that the value v in an ack(n, v, n_v)
  message never goes out of date—there is no possibility that an
  acceptor might retroactively accept some later value in round n' with
  nv < n' < n. So the ack message values tell a consistent story about
  the history of the protocol, even if the rounds execute out of order."

However, its not obvious to me why retroactivity might be bad (unless in the case that I already mentioned). Retroactivity could be good if it somehow manages our protocol to reach consensus. Still the only reason I see for such a rule is so that one doesn't reverse a decision by accident once a value has been agreed on.

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research


texts: Difference between word logical addressing and byte logical addressing in this exercise?

texts:
I´m new here and this is the first question I´m posting (hopefully this is the correct site).

I have the exercise below:
Consider a virtual address space of 10 pages of 1024 words each (1 word = 2 bytes), mapped onto a physical memory of 32 frames. How many bits are needeed for each virtual address?

The answer they provide is:

| 4 bits for page | 10 bits for offset |

But I don´t figure out how do the 4 bits appear. The exercise explains that the logical addressing is word logical addressing (instead of byte logical addressing).

I´m confused about this two terms. How can I know if the addressing method is word based or byte based?

Thank you in advance


texts: Incremental dynamic on-disk disjoint sets (incremental on-disk dynamic forest)

texts:
Problem statement

I am looking for an algorithm to maintain a very large number of disjoint sets under node and edge additions. Due to the data size, keeping everything in memory is not feasible, so the algorithm needs to work efficiently with SSD storage.

Ideally, the algorithm should:

support link(v1, v2) operation which either merges two sets or does nothing if v1 and v2 already belong to the same set. If either v1 or v2 did not exist prior to link operation, the new vertex(es) should be added to a set
support get_set(v) operation which will return all elements in a set
be IO efficient in terms of SSD access
allow concurrent link and get_set operations

Some notes:

only edge additions are allowed, no removals
consecutive link operations 1..N operate on a small number of disjoint sets K, K << N

Why I need such an algorithm

There is a stream of events (~100M of events per day) in which each event may link to zero or several "parent" events. When a new event arrives, I need to run some aggregations on a graph that this event belongs to. Events are generated by a set of services, so this is basically a distributed tracing problem.


texts: Does the language of TM's that repeat a configuration infinite times semi-decidable or not?

texts:
Let us define the following languages:

$$ {L_1 = \{\langle M\rangle :  M  \ \text{is a TM and $\exists w\in \Sigma^*$ s.t $M(w)$ repeats a configuration infinite times}\}} $$

$$ L_2 = \{\langle M\rangle :  M  \ \text{is a TM and on all inputs there exists a configuration  that repeats infinite times}\} $$

My question is what class does this languages belong to ($\mathcal{R},\mathcal{RE\setminus{R}}, etc...$)?
I have shown that:

${H_{TM}}\le_m L_2$:
On input $\langle M,w\rangle$ return a new $TM$ $\langle M' \rangle$ such that on all inputs, runs $M$ on $w$. Keep a counter at the beginning on the number of steps (to avoid entering the same configuration infinite number of times, if it doesn't stop). If it does stop, repeat some configuration in a loop.

So that seem to prove that $L_1,L_2\notin \mathcal{R},\mathcal{co-RE}$.

But is it in $\mathcal{RE}$? I couldn't write a $TM$ that accepts those languages, nor derive a reduction from $\overline{H_{TM}}$, $\overline{A_{TM}}$ or any other relevant language.

Any ideas on solving this? Thanks!


texts: Finding containing sets in a set of sets

texts:
Suppose I have a set of sets of integers $A$, is there an efficient algorithm/data structure that will allow me to query for all sets of integers that include a given input set? That is, given input $I\subset \mathbb Z$, find $C$, the sets in $A$ that include all of $I$, that is $C=\left\{ B \in A \mid I\subseteq B\right\}$.

Looking for the best of a few solutions.


texts: End-Of-The-Line Augmented Problem of PPAD

texts:
Famous PPAD class of problems is  formally defined by specifying one of its complete problems, known as End-Of-The-Line:

End-Of-The-Line Problem:
$G$ is a (possibly exponentially large) directed graph with no isolated vertices, and with every vertex having at most one predecessor and one successor. $G$ is specified  by giving a polynomial-time computable function $f(v)$ (polynomial in the size of $v$) that returns the predecessor and successor (if they exist) of the vertex $v$. Given a vertex $s$ in $G$ with no predecessor, find a vertex $t≠s$ with no predecessor or no successor. (The input to the problem is the source vertex s and the function $f(v)$). In other words, we want any source or sink of the directed graph other than $s$.

Let's consider the slightly augmented version of End-Of-The-Line problem.

End-Of-The-Line Augmented Problem: The definition is same as for End-Of-The-Line expect that it's required to find not a vertex $t≠s$ with no predecessor or no successor, but the exact end of the path of the given source vertex $s$.

Intuitively, it seems like End-Of-The-Line Augmented Problem is not more in PPAD, just because it requires something more stronger than End-Of-The-Line Problem. How to show that End-Of-The-Line Augmented Problem is NP-hard?


texts: Resulting complexity class for allowing two passes over witness in NL?

texts:
I know that when an NL Turing machine is allowed to go back and forth freely, the resulting class of problems solvable on it is NP.

But limit of two passes over the witness tape, does not seem to add much power to the NL machine, if at all.

I am stuck on this problem. What is the resulting complexity class? Is it still NL? How do I prove this?


texts:
Input: 2 RB Trees A B, so that both values in a certain range, so that B's range is smaller than A in both sides.  Ex. B's range can be [100...200] and A's range is [0...1000]
Output: Unite A and B to one RB Tree AB.

How can I unite these 2 trees in $O(log(n))$ time and with additional space $O(1)$?

I have tried splitting tree A into 3 trees A1,A2,A3, so that:   A1 < A2 , B < A3
A2 contains all that values that are equal-bigger than Min(B) and smaller-equal to Max(B).
I did it using the RB Tree Split algorithm, and all the splitting sums up to $O(log(n))$ time.

Now I know what to do with A1 and A3 but what should I do with A2 and B?  I know I should use the fact that B contains A2's range but how does it help me?


texts: Are single-dimentional arrays better than multi-dimentional in the GPU?

texts:
I'm making simulations like Ant colony simulation, boids, and cellular automata in Go (to learn Go), but I believe this can apply to most languages.
From what I've read (this), using 1D arrays is generally better, but the post only addresses CPU processing. I want to do my simulations with the GPU and that may have some implications I'm not aware of.
In my case, a Map object is a 2D array of Cell objects.
struct Cell {...}
struct Map {
  Cell[][] cells;
}

Is it better to use 1D arrays instead of multi-dimensionals when working with the GPU?


texts: Are all data structures in the von Neumann architecture based on the array, or array-like?

texts:
I am an old Pythonista now learning C and how various data structures and types are implemented, such as binary trees and hash tables. Learning about the latter, leads me understand that the hash function servers the purpose of computing from the key the index in the array where the value is stored. I have also learned that trees may be stored as arrays. Given that arrays are said to be efficient (for lookup, if not insert/delete) due to the way they match memory addressing in the von Neumann architecture, is it generally the case that all other structures are basically "supersets" or "super-structures" of the array?

After all, the array is nothing more than a contiguous collection of memory "cells", so we can think of an int as a single cell array. And we can think of a struct as an array where elements are not necessarily of the same type. I struggle to think how any other data structure could be constructed in any other way, but I guess it's best that I ask here to be sure.

EDIT: Just to be perfectly clear and correct, I do understand that a memory cell and a data element are not necessarily the same thing, an element may occupy more than one memory cell. The distinction between the two is a minor detail that shouldn't detract from the question.


texts: Decidability of whether a language described by Turing machine is regular

texts:
I am trying to prove decidability of problem whether language described by Turing machine is regular. My idea is that I can simulate finite automaton with a subset of Turing machine instructions, namely ones that check for symbol and then move right. If the language is not regular, then simulated FA will eventually come across a string that it cannot process, and give it a FALSE. On the other hand, if the language is regular, FA will successfully accept every string. The problem is that the language has infinite number of strings, and the simulated FA will be checking then forever and never giving affirmative answer. That would make said problem undecidable. Is my reasoning here correct? And if it is, can it be considered a valid proof, or do I need to prove it some other way?

EDIT: The exact wording of the exercise translated as best as I can: You're given a problem of whether language of given Turing machine is regular. Decide whether this problem is decidable and whether is partially decidable. Formally prove your argument.


texts: Given a mechanical assembly as a graph, how to find an upper bound on number of assembly paths

texts:
The rules are that you can only build from an existing part, so in the example below, B is the only option for the first move = A.

A mechanical assembly might be represented as follows:

  E
  |
  C
  |
A-B
  |
  D
  |
  F

Where the valid assembly paths when starting from A are:

A, B, C, E, D, F
A, B, C, D, E, F
A, B, C, D, F, E
A, B, D, F, C, E
A, B, D, C, F, E
A, B, D, C, E, F

This is a fairly simple example, but providing an upper bound for an arbitrary assembly is difficult since it's related to the "connectivity" of the parts.

n! would be an absolute upper bound I guess, but I'm hopping to find something a little better.

I've also looked at representing the graph with the parts (A, B, C, etc) as the edges and doing Kirchhoff's theorem, but that doesn't work for sparsely connected graphs like the example above.

Any information about the problem would help.  I'm not sure if there's a formal description of this type of problem or not.


texts: For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

texts:
Traditionally, the traveling salesman problem has you visit a city at least once and at most once.

However, if you were an actual traveling salesman, you would want the least cost route to visit each city at least once, and you wouldn’t be bothered visiting a city 2, 3, or more times. For  given city, you might stop and hawk your wares only once, and on subsequent visits, only drive through the city without stopping.

Consider an undirected graph having a city incident to exactly two  edges. The cost on one of these edges is only 10 units, while the cost on the other is 99,999,999,999. If you insist on visiting each city at most once, then you are forced to incur the cost of the high cost edge. However, if you allow yourself to visit cities multiple times, then you simply leave the way you came in (on the low cost edge). The low cost edge leads you back to a city you've passed through before.

The traveling salesman problem is highly contrived for an actual traveling salesman. I want to give students an application for which there's a real incentive to visit each city at most once. For what applications is visiting each city a critical aspect of the problem?


texts: What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

texts:
This is a real-world application, not a student assignment.

Suppose we have some numbered boxes which are to be laid out, in order, from left to right, top to bottom, with no space between them, into a column of fixed width and infinite height.
The boxes have the same height, but variable width.
When a box doesn't fit, it should wrap to the next line (just like text).
After that, we fix the number of lines, and then lay out the boxes again so that the lines have a more balanced width, which means they try to be the same width, as much as possible.

The input is, simply:

double colWidth = …;
List<double> boxWidths = [ … ];

And the output could be:

List<int> result = [ … ]; // Number of boxes in each line.
double minWidth = …;

An example: Suppose the column has width = 11, and 5 boxes have widths [2, 3, 5, 2, 1], then the layout is this:

| ** *** ***** |
| ** *         |

This means we can fit the boxes into 2 lines, and line widths differ a lot. One is 10 and the other is only 3 (difference is 7).

Now we have to lay them out again in 2 lines, to achieve balanced width:

| ** ***       |
| ***** ** *   |

The result is 2 boxes in the first line, and 3 boxes in the second line: List<int> result = [2, 3]. Widths are now 5 and 8. Difference is 3, and minWidth is 8.

Please note, we cannot change their order. If we could, then the difference would be 1 and minWidth would be 7:

| ** *** *     |
| ***** **     |

My question:

What's the most efficient algorithm to solve this? I am interested in speed, and I don't care about memory usage.


texts: Assignment problem with symmetric matrix

texts:
I came across a problem which I think can be reduced to the assignment problem/Hungarian algorithm.

We have matrix $A$ and matrix $B$ which are both $n\times n$ symmetric matrices. We can rearrange $B$ in the following manner: column $i$ can be swapped with column $j$ provided that next, row $i$ is swapped with row $j$. This preserves the symmetry of $B$.

The problem statement is to find a rearrange of $B$ in this manner which minimizes the Frobenius norm of $A-B$.

Any guidance on an approach would be greatly appreciated. Thank you very much in advance.


texts: Undecidability of "is this CFG prefix-free?"

texts:
I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition).
Another thread has the very different question "is this regular language prefix-free". One of the answers in that thread claims to prove undecidability for CFLs (even though that did not explicitly ask for a proof of undecidability for CFLs) using the usual Post Correspondence Problem (PCP) method.
The proof in the other thread claimed (as of Oct 11, 2020) that a certain CFL with an endmarker $\#$ is prefix free if and only if there's no PCP solution. However, it seems to be possible to have prefixes in the CFL even without any PCP solutions, which would mean the proof is wrong.
I also tried using the fact that "non-emptiness of intersection of two CFGs" is undecidable. However, we are only able to use undecidability of CFGs being prefix-free to prove undecidability of intersection non-emptiness, not the other way around.


texts:
I have a pretty good handle on what recursive and recursively enume table languages mean with respect to Turing machines and how they relate to one another through my algorithms class. What I don't understand is how these languages relate to the computability of problems, and whether these languages correlate to problems or something else. I'm missing the bridge between the theory and the practical application of theory so abstract, could somebody bridge the gap?

In particular, what does the recursive nature of a language tell us about the problem being considered? Recursive nature being recursive or r.e.


texts: Approximately sorting integers by many criteria

texts:
Given $k$ functions $f_0, f_1...f_k$, a large dataset of size $n$, is there an algorithm that will "approximately" sort the dataset according to all of the functions so that "most" items of the dataset end up close to where they should be if they were sorted by any one of the functions alone.

More formally, if we have the functions $R_k(i)$ which gives the rank of item $i$ if the dataset were sorted with $f_k$, and $R'(i)$ which gives the actual rank of the item, we can define the statistic: $$r_k = 1 - \frac{6\sum_{i=0}^n{(R'(i) - R_k(i))^2}}{n(n^2-1)}$$ (this is the Spearman rank correlation coefficient of the actual against predicted positions)

Is there an algorithm which will increase the total $r = \sum_{i=0}^k{r_i^2}$, either by outright maximising $r$, or some kind of convergent process which can increase $r$ to its maximum?

Obviously, sorting according to just one of the functions will give $r > 0$ but can we do better than this?

I am not really concerned with running time, but anything better than the naive $O(n!)$ of going through all the permutations and computing $r$ would be good.

The motivation for this is to improve branch prediction while searching a large dataset without using any extra space.


texts: Do I need to consider instance restrictions when showing a language is in P?

texts:
I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. In my proposition of an algorithm in P, I wasn't sure if my algorithm needs to verify that $G$ indeed contains no cycle or if I assume all inputs are instances of this language (assume all inputs are acyclic graphs). In general, I was wondering if my algorithm has to decide whether the input is of the desired instance ON TOP OF actually showing the properties of the language can be done in polynomial time. I'm still learning so I am confused about this part and this has been bugging me for a while.

If this question is too confusing, consider 3SAT. Must I show that verifying the input is indeed a 3CNF is in P to conclude, or can I assume we are only considering inputs within an instance?


texts: Isn't Domain of a variable nothing but a constraint?

texts:
In Constraint programming we have Variables and their Domains and then all the constraints, but if you at the concept of a domain of a variable it is nothing but another type of constraint, you are saying that this variable can take all these values.
Is there any particular reason why domain is defined as a different concept than constraints?


texts: What is the point of delimiters and whitespace handling

texts:
I see that language specifies reserved words, delimiters and whitespaces in the lexer section. Are delimiters just like reserved identifiers in the punctuation space or they have additioinal function regarding skipping the whitespace?

Namely, spec says

  Each lexical element is either a delimiter, an identifier (which may
  be a reserved word), an abstract literal, a character literal, a
  string literal, a bit string literal or comment. In some cases an
  explicit separator is required to separate adjacent lexical elements
  (namely when, without separation, interpretation as a single lexical
  element is possible). A separator is either a space character (SPACE
  or NBSP), a format effector, or the end of a line.

I also see a definition

relative_pathname ::= { ^ . } partial_pathname

where . is a delimiter but ^ is not. I do not understand why the difference. Moreover, ^ is a special character that can be only a part of "string literal", 'char literal' or /extended identifier/ and I don't understand how to deliver this character to the path parser.

Anyway, I wonder what to do with pieces of text smashed to each other like 11'c' or "this is string litral"with_some_identifier. Mine current lexer produces string_literal followed by identifier. However, I feel that others don't do that. What is the common practice for lexing and whitespace skipping -- when whitespace is it mandatory and when is it optional? How do you specify that to the parser/lexer?
I ask because do not see that parsers/lexers specify a lot of whitespace or separators in the production rules. Despite this stuff must be ubequitos, in practice, I do not see it at all. In JavaCC, for instance, you just specify whitespace chars in SKIP and it does the rest itself. What is the convention? I see that parser combinators support lexical.reserved words and lexical.delimiters. What is the purpose?

I guess that I can supplement every definition of identifier, delimiter and literal with optional whitespace prefix. Now, is it right that only identifiers and literals have to be separated by delimiters or whitespace? How do I ensure that?


texts: How does a wifi password encrypt data using WEP and WPA?

texts:
How does the password that we enter (to connect to a wireless network) encrypt the data on the wireless network?

Through my reading I am not sure if the password that we enter is the same as the passphrase. If that is right then how can the passphrase generate the four WEP keys?

I understand how the four keys work in WEP and how they encrypt the data. Also, I know how WPA's keys encrypt the data but the only thing I have to know is:

  what is the benefit of the password that we enter to get access to the network, and how does this password help in encrypting the data?


texts: Lambda Calculus - Call-by-name AND call-by-value reduction

texts:
I have been tasked with reducing the following lambda expression:

  (λpq.pqp)(λab.a)(λab.b)

using call-by-name and call-by-value reduction strategies.

Call-by-name

strategy: Left-most, outermost redex first but no reduction under lambda.

Step 1) alpha-equivalence

  (λpq.pqp)(λab.a)(λcd.d)

Step 2) Reduction - using the redex (λpq.pqp)(λab.a)

  (λq.(λab.a)q(λab.a)(λcd.d)

Step 3) - substitute (λcd.d) for q

  (λab.a)(λcd.d)(λab.a)

Step 4) - substitute (λcd.d) for a

  (λb.(λcd.d))(λab.a)

Step 5) - substitute (λab.a) for b

  (λcd.d) -> (λab.b)

Which gives the same result if you were to use normal order instead.

Call-by-value

strategy: Right-most, innermost redex first but no reduction under lambda

Step 1) alpha-equivalence

  (λpq.pqp)(λab.a)(λcd.d)

Step 2) substitute (λab.a) for c

  (λpq.pqp)(λd.d)

Step 3) substitute (λpq.pqp) for d

  (λpq.pqp)


texts: Is it possible to wear-level a FAT32 file system?

texts:
Because SD cards use flash memory, they should requires wear leveling to avoid significantly shortening the life of the card. At the same time, my understanding is that they usually use a FAT32 file system.
My understanding of FAT32 is that there is a small "file system description" block at the beginning of the device, which is followed by the file allocation table (FAT) describing which files are stored where. However, because the FAT needs to be updated every time a file is moved/copied/appended/etc, then doesn't that mean the FAT gets written to many times more often than the rest of the card?
For example, if each erasable block of an SD card is 4 KB, and it uses a 32-bit address space, they each erasable block of the FAT contains 128 addresses, so the FAT should get erased and written ~128 times as often as the rest of the device. If this hypothetical device has an expected life span of >100k cycles, then should it not wear out around 1k cycles if it spends the entire time formatted with a FAT32 file system?
And, if my current understanding is true, then wouldn't FAT32 be basically the worst possible way to format a flash memory device? Or is this a problem that all file systems have, so FAT32 isn't apreciably worse than anything else?


texts: Proof of perceptron convergence theorem for ZERO threshold?

texts:
The generalized perceptron convergence theorem is for a defined threshold T.

When you do the maths it all comes to an upper bound and a lower bound.

The lower bound looks like this!

  Therefore

  $$ (x^{\ast})^T x(k) > k \delta. \qquad\qquad (4.67)$$

We can see if the threshold is equal to zero, this is still true.

But what happens with the upper bound?

The generalized theorem looks like this:

  We now have an upper bound (Eq. (4.75)) and a lower bound (Eq. (4.70))
  on the squared length of the weight vector at iteration $k$. If we
  combine the two inequalities we find

  $$ k\Pi \geq {\lVert x(k) \rVert}^2 > \frac{(k \delta)^2}{{\lVert x^\ast \rVert }^2} \quad \text{or} \quad k < \frac{\Pi {\lVert x^\ast\rVert}^2}{\delta^2}. \qquad \qquad (4.76)$$

  Because $k$ has a an upper bound, this means that the weights will
  only be changed a finite number of times. Therefore, the perceptron
  learning rule will converge in a finite number of iterations.

I am struggling to find how this is true for a zero threshold too since you can't divide by zero.

Can someone help me here get it for this special case?


texts: Regular expression for $\{a^k b^m c^n \mid k+m+n \text{ is odd} \}$

texts:
I have to make a regular expression from the following laguage:

  {$a^kb^mc^n : $ where k + m + n is odd}

Is is possible for the sum of three numbers to be odd (other than three consecutive odd numbers)?

I have this so far:

  {(abbbccccc) + (abbbbbccc) + (aaabccccc) + (aaabbbbbc) + (aaaaabccc) + (aaaaabbbc)}

but I am realizing that there are way more possibilities to this pattern... How can I formulate a string that encompasses all of this?


texts:
I have set integers that are normally distributed, and I'm trying to implement binary arithmetic encoding, as suggested in this post: Compressing normally distributed data

I'm running into trouble because the user remarks that we should try arithmetic encoding the quotient using a sequence of binary symbols. I don't understand what this means because I've only seen arithmetic encoders operate on sequences. I'm aware that BAC can work on multi-symbol alphabets, but I'm still unsure of how to implement that.

Could anyone explain a rough guideline of how a binary arithmetic coder would be implemented for this type of data or as explained in the linked question?


texts: Overall time complexity of Heuristical Algorithm for travelling salesman problem [TSP]

texts:
I am trying to figure out the time complexity of a heuristical algorithm used to solve the Travelling Salesman Problem in a more efficient way than by brute force, ($\theta(n!)$ or similar)

The first step is to compute Kruskal's Minimum Spanning Tree, which to my best knowledge is of
$\theta(E+V)$, where E is the number of edges of the graph, and V the number of vertices.
Next, the algorithm finds a minimum-length pairwise matching of the odd degree vertices from the result of the MST graph. Min pairwise matching can solved in $\theta (V'logV')$, where $V'$ represents the vertices that are of odd deg.

My question is, what is the overall time complexity of my Heuristical Algorithm, is it the sum of the two time complexities of 1 and 2?

For further reading on the heuristical algo, consult http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.6.html

Thanks,


texts: Number of multisets such that each number from 1 to $n$ can be uniquely expressed as a sum of some of the elements of the multiset

texts:
My problem. Given $n$, I want to count the number of valid multisets $S$.  A multiset $S$ is valid if

The sum of the elements of $S$ is $n$, and
Every number from $1$ to $n$ can be expressed uniquely as a sum of some of the elements of $S$.

Example.
For example if $n=5$ then $\{1,1,1,1,1\}, \{1,2,2\}, \{1,1,3\}$ are valid.

However, $S=\{1,1,1,2\}$ is invalid because 2 can be formed by both $\{1,1\}$ and $\{2\}$ (i.e., 2 can be expressed as both $2=1+1$ and $2=2$), so the second condition doesn't hold. Similarly 3 can be formed by $\{2,1\}$ and $\{1,1,1\}$.

$S=\{1,2,4$} is also invalid because all numbers from $1$ to $5$ can be uniquely made, but the sum of the elements of $S$ is not $5$.

I've tried to find a good algorithm for this problem for quite some time but cannot solve it. It is from codechef.  I've seen some of the submitted solutions but I still couldn't get the logic for solving the problem. NOTE: The time limit for the question is 10 seconds and $n<10^9$

For a multiset I will use the notation $S = \{(a_1, c_1), (a_2, c_2) ... \}$ $a_i<a_j$ if $i<j$, which means $a_i$ occurs $c_i$ times in multiset S.

Till now I have drawn some conclusions

First element of the required sorted multiset should be $1$
Let $S=\{1,a_2 \cdots a_k\} | a_1 \leq a_2\cdots \leq a_k $ be a set following the two properties then $\forall r<k \ \ a_{r+1} = a_r \text{ or } (\sum_{i=0}^ra_i) + 1$
Let $S=\{(1,c_1),(a_2,c_2) \cdots (a_k,c_k)\} | a_1 \leq a_2\cdots \leq a_k$, where $a_i$ is occurring $c_i$ times, follows the required properties then from the above conclusion we can say that $\forall i \ a_i|n+1$ and $a_i | a_j$ if $j > i$ .
Proof: $a_{i+1} = (a_ic_i + a_i -1 )  + 1 \Rightarrow a_i | a_{i+1}$
Now consider $S=\{ \underbrace{1,1 \cdots 1}_{d-1},d,d \cdots d,dm_1, dm_1 \cdots dm_1,dm_2, dm_2 \cdots dm_2, \cdots \}$ i.e. all the subsequent numbers after 1 will be a multiple of $d$. So let $f(n)$ be the count of such multiset possible then $f(n) = \sum_{d|n+1, d\neq 1} f(\frac{n-(d-1)}{d})$ where I am summing over all possible number of $1's$($=d-1$). In other terms $f(n-1)=g(n)=\sum_{d|n,d \neq n}g(d)$

Finally my problem is reduced to this - find $g(n)$ in an efficient way so that it doesnt exceed the time limit.


texts: Let G be k-reguler bipartite graph of degree at least 2. show that K(G) not equal 1?

texts: Let G be k-reguler bipartite graph of degree at least 2, for all v belong to V(G) prove that k(G-v) is connected?


texts: Difference between time complexity and computational complexity

texts:
For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them?
I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm.


texts:
GraphQL is a query language for your API, and a server-side runtime for executing queries by using a type system you define for your data.

Source: http://graphql.org/learn/

So GraphQL allows a server to implement a HTTP-endpoint that accepts queries which are only constrained by the type system defined by the server. So in some way, it can be compared to SQL. However, it does not allow nearly as complex queries as SQL does.

What I am interested in is, if the idea of having a generic endpoint that executes client-defiend queries is backed by some well known concept in computer science?

I suppose this could go in the direction of how distributed systems can communicate / exchange data but at the moment, I am having a hard time to find actual research that deals with this problem in a similar way.

So in short: Is GraphQL genuinely something new or is there some well known concept / theory behind it?

Edit:
I am very well familiar with REST. My question explicitly targets the fact, if this idea of exposing data in a generic way is new or well known.


texts: Question about the lower bound for $k \times k$-clique (under ETH) shown in "Slightly Superexponential Parameterized Problems"

texts:
I am reading the paper Slightly Superexponential Parameterized Problems at the moment and have two questions about it:

First question:
The paper gives a proof of the following statement

  Theorem 2.1: Assuming ETH, there is no $2^{o(klogk)}$ time algorithm for $k \times k$-Clique.

They prove this statement by sophisticated reduction from $3$-coloring. They then state that this construction runs in time polynomial in $k$. They state:

  The graph $G$ has $k^2$ vertices and the time required to construct G is polynomial in $k$. [...] Therefore, the total running time is $2^{o(k \log(k)} \cdot k^{O(1)}$

Why is this not $2^{o(k \log(k)}) + k^{O(1)}$ instead? As far as I can see, we have only have to construct the graph once, and then we can run the presumed $2^{o(k \log(k)}$ algorithm.

Second question: From this theorem, it follows that $k \times k$-Clique can not have a $k^{o(k)}$ algorithm under the Exponential Time Hypothesis. This follows from the abstract, which states that $k^{O(k)} = 2^{O(k \log(k))}$. What is a good way to proof this statement?


texts: What is a "negative function" withing algorithms?

texts:
I am currently studying the book 3rd edition CLRS Algorithms textbook, Chapter 3. I had the exact same question as this post but I have one more question now:
What is a negative function?
These functions are estimates that describe the time it takes to perform a function (an algorithmic sequence) onto a list. How can the function be negative if it describes the time it takes to do work? Can an algorithm sort a list 10 seconds before it starts?


texts: Why a TM with infinite states can decide the halting problem?

texts:
Assuming we have a model of TM with an infinite number of states.
The domain and range of the transition function are also infinite.
Given a description of a TM $M$ and a string $w$ how can we use the new model to tell if $M$ ever stops when running on $w$?


texts: Reducibility: Show that SUBSET SUM is reducible to the following problem A

texts:
A: Given nonnegative integers x1,...,xn (written in binary), and an
integer k, can the net expenses be balanced using k or fewer checks? (Suppose that A is in NP).
Purpose: to reveal that SUBSET SUM reduces to A so that A is
NP-complete (since SUBSET SUM is NP-complete).

Let me construct A as follows:

We can find the balanced net expense using SUBSET SUM.

The balanced net expense = (x1+x2+...+xn)/n

There will be some algorithm to compute k.

What I wonder is that as we see the algorithm above A seems to be a harder problem than SUBSET SUM because A uses SUBSET SUM within its algorithm. Is this fact enough to support the idea that SUBSET SUM is reducible to A?
Thank you for your time.


texts: Proof problem in Haskell with take and drop

texts:
Im learning Haskell and i want to prove

take m (drop n xs) = drop n (take (m+n) xs)

and

drop m (drop n xs) = drop (m+n) xs

Somebody can help me please? :)


texts:
Consider the follow operations on a stack of size at most $k$.

Push - insert element in the stack - actual cost 1

Pop - remove top element from the stack - actual cost 1

Copy - copy whole stack (but maintain the number of elements) - actual cost is the number of elements in the stack

Prove using the potential method that each single operation (push, pop or copy) has amortized cost at most 2.

What would be a suitable potential function for this problem?


texts: When Turing Machine behaves like Finite state automaton

texts:
I read following:

  Turing Machine with finite (fixed sized) tape is essentially Finite state automaton.

Is this fact correct? My doubt is Turing Machine can go infinite loop even on finite tape if it keeps moving from left to right and finite state machine does never go in such infinite loops. So, do we also need restrictions like "only right head movements are allowed" along with finite tape to turn Turing Machine to finite state automaton?


texts:
I want to solve Problem 4.10 from Randomness by Salil Vadhan. https://people.seas.harvard.edu/~salil/cs225/spring15/PS3.pdf

Consider a bipartite expander $G$ with left degree $D$ so that every subset $S$ of the left vertices with at most $K$ vertices has at least $(1-\epsilon)D|S|$ neighbors. Then $G$ also has the property that it has $(1-2\epsilon)D|S|$ unique neighbors. Unique meaning that it has exactly one corresponding vertex from $S$.

I recognize that the new expansion factor is $(1-2\epsilon)D = 2\cdot(1-\epsilon)D -D$


texts:
Given a directed graph $G$ and a vertex $v$, how can we enumerate all simple cycles that pass through $v$?

I found a question that describes how to enumerate all simple cycles in $G$, but I want only the cycles that pass through $v$, so this question is a bit different.  The total number of cycles in $G$ can be exponentially larger than the number of cycles passing through $v$, so just enumerating all cycles in $G$ and keeping only those that go through $v$ might be inefficient.

I'm not asking to count the number of cycles; I want an algorithm to list them all. I would like an output-sensitive algorithm, where the running time is some low-order polynomial of the number of cycles that go through $v$.  I know there can be exponentially many cycles, so there is no hope for an algorithm whose running time is polynomial in the size of the graph.

Motivation: This is a cleaned-up version of Given a directed graph and a vertex v, find all cycles that go through v?.  I wanted to ask the more general version of the question.


texts:
There is a road (a planar curve) of length 1. A treasure is placed in a random spot on the road. The treasure location is a uniform random variable, so that the probability to find the treasure in an interval of the road is equal to the interval length. Our goal is to find the treasure in the shortest expected time.

We have a helicopter that can survey the road and detect the treasure when it is directly below it. The helicopter can fly to any point in the road, but cannot survey the entire road at once because it has to go back to its fuelling base once every hour. Our goal is to divide the road to intervals, such that each interval can be covered in one hour, and the expected time until we find the treasure and return to the base is minimized.

An example is illustrated below:

Here, AE is the entire road. The probability of finding the treasure in AC is 1/2 (since its length is 1/2 the total road length), and the same is true for CE.  Suppose the helicopter can cover the interval AC in one hour (e.g, it takes one hour to fly from the Base to A, then to C, then back to the Base). Similarly, it can cover the interval CE in one hour. Then, the expected time of finding the treasure in the given schedule is:

$$E[T] = 1/2 \cdot 1 + 1/2 \cdot 2 = 1.5$$

This simple schedule is not necessarily optimal. It may be possible (depending on geometry) to divide the road to 3 segments, like this:

If the helicopter can cover each of the three intervals in at most one hour, and it surveys them in the order: BD, AB, DE, then the expected time is:

$$E[T] = 6/8 \cdot 1 + 1/8 \cdot 2 + 1/8 \cdot 3 = 11/8 = 1.375$$

In general, given a division of the road to $T$ intervals, each of which can be covered in an hour, the expected time is:

$$E[T] = \sum_{t=1}^T t\cdot Length_t $$

This expression indicates that the minimum expected time is attained when we survey the intervals in decreasing order of their length. However, this is minimal only given the division to intervals; it does not tell us what is the optimal way to divide the road to intervals.

So my questions are:

A. What is an algorithm for finding an optimal division of the road to intervals?

Suppose the input is given as an oracle that, given a point $x$ on the road, tells us $l(x)$ - the maximum length that can be surveyed in 1 hour, starting at $x$. Assume that $l(x)$ is a continuous monotonically increasing function of $x$.

B. Suppose we divide the road to the smallest possible number of intervals, like the AC-CE example above, and survey them in decreasing order of length. This is not optimal, but apparently it is a good heuristic. What is its approximation factor?


texts: How to prove this language is context free?

texts:
There's lots of ways to prove a language is not context free. Going through some exercises, I'm stuck at a question that asks me to prove that a language is indeed context free.

$L = \{a^{(n+1)} b^{(m+2)}c^{(n+4)}\ |\ m, n ≥ 0 \}$

I see that the langauge is equivalent to $L = \{aa^nbbb^mccccc^n\}$, but I'm not sure if that helps at all.

Maybe breaking the language apart into a concatenation of three languages like $\{a^{n+1} | n>= 0\}.\{b^{m+2} | m >= 0\}.\{c^{n+4} | n>=0\}$ might be helpful, because we can do a rule separately for each? The n has to be equal for the left and right side though, which I'm having difficulty with.

Any help would be much appreciated!


texts: Run Length Encoding Compression With Nested Level

texts:
I am studying about some compression methods, and I'm very interested in RLE Algorithms. But are there any Nested-Level RLE methods, such as:

ABABABCABABABC --> 3(AB)C3AB(C) --> 2(3(AB)C) ?

It's easily to decompress it by using some techniques like stack, but what is the most efficient way to compress it, any formal algorithms or how to evaluate that?


texts: Why in Declarative Programming variables are not reassigned?

texts:
I've read that a Declarative language is called "stateless". This means that we can imagine that internally every variable is a constant variable, and it never get reassigned ( in contrast with what usually happens in procedural programming).
How can this work?


texts: Rice's Theorem for Total Computable Functions

texts:
Fix a Gödel numbering, and write $\phi_n$ for the function coded by $n$. Rice's theorem states that if $P$ is the set of partial computable functions, and $A \subseteq P$, then the decision problem

  Given $n$, does $\phi_n \in A$?

is decidable if and only if $A = \emptyset$ or $A = F$; that is, if the decision problem always has the same answer.

Now consider the set $T$ of total computable functions instead. Clearly, the problem

  Given $n$ with $\phi_n \in T$, does $\phi_n \in A$?

is no longer decidable if and only if $A \in \{\emptyset,T\}$. In fact, for recursive set $M\subseteq \mathbb N^k$, the problem is also decidable for
$$
A_M = \{\phi_n \in T \mid (\phi_n(0),\ldots,\phi_n(k-1)) \in M\}.
$$
So is it true that the problem is decidable if and only if $A$ is of the form $A_M$ as above? If not, can we give a different restriction on the form of $A$ that does give us a theorem?


texts:
My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below:

How many isomorphism classes of trees with n vertices are there?
What are the classical algorithms to decide if two given trees are isomorphic?
Is there a nice (computable?) isomorphism invariant?

Of course, the answers may depend on the structure used to define the trees, but I guess the correct choice of structure is part of the answer I am seeking.


texts: How is density of a substance in grams per cubic centimeter a discrete attribute?

texts: I'm going over the different types of attributes in data-mining (nominal, ordinal, discrete, etc) and there is one example in the book that states that the density of a substance in grams per cubic centimeter is a discrete attribute. Why is this? I confuses me that this is the case but it also says that the distance from the center of campus is continuous.


texts: Delete $2^{k-1}$ numbers from $(0, 2^n+1)$ interval; the maximum distance between deleted numbers at step $k$ must be $2^{n-k}$

texts:
The problem

I have two integers, $n$ and $p$:

$n \ge 1$

$1 \le p \le 2^n + 1$

Consider the sequence of numbers: $0, 1, 2, ..., 2^n, 2^n + 1$.

$0$, $p$, and $2^n + 1$ in the sequence are marked as deleted.

I need an algorithm that can mark all the elements of the sequence as deleted , in k steps (k from 1 to n), with the following restrictions:

At a certain step $k$ I must mark as deleted $2^{k-1}$ numbers.
At the end of the step $k$, the distance between 2 consecutive "marked as deleted" numbers must not exceed $2^{n - k}$.
I can't mark a number as deleted, if the number was already marked so in a previous step.

What I've come up with

At a certain step $k$, I should split the sequence into $2^{k-1}$ sequences and mark as deleted every number in the middle of every obtained sequence. However, the problem with this is that there already is a marked as deleted number $p$, which interferes with my proposed process, because I still nedd to fulfill the requirement of marking $2^{k-1}$ numbers as deleted at the step $k$.


texts: Data structures for annotations in large-scale text editor

texts:
I need to create a specialized text editor capable of handling text up to billions of characters long, with no line breaks.

I've read of multiple data structures to manage the text itself, including ropes, zippers, piece tables, gap buffers, and more.

However, I also need to support annotations on the text. Like comments in MS Word, each annotation lies over a range of positions. (Unlike MS Word comments, each annotation may lie over multiple non-intersecting ranges.)

Annotations can cover a single character or the whole text. Annotations may be created before, in between, or after text edits.

There can be tens to hundreds of thousands of annotations. Reacting to each edit by adjusting the coordinates of every single feature would incur a large, linear cost.

What are data structures that would support the following, even as coordinates change due to text editing, whose complexity does not include the number of annotations as a factor?

Finding the coordinates of features discovered by text search, in the current coordinate system resulting from text edits made after the annotations.
Finding annotations that intersect a range presented to the user, in the current coordinate system resulting from text edits made after the annotations.

For 1, one idea I've had is to store a history of coordinate-system changes, and apply all of those made after the feature's creation. However, the cost of this grows linearly with the number of edits.

For 2, one idea I've had is to create a custom R-tree of annotations which reacts to text edits by modifying its own coordinate system but not its clustering. But not sure how to handle new features, which don't necessarily lie anywhere in the original coordinate system. And again, the cost of this could grow linearly with the number of edits.


texts: Is there always a Big Oh complexity strictly between any two others?

texts:
I'm learning about asymptotic analysis, and have seen some exotic looking complexities living between other common ones. For instance "log log n" is strictly between 1 and log n. It makes me wonder if one can always find complexities between any other two.

Specifically, for any functions f and g with O(f) ⊂ O(g) does there always exist an h such that O(f) ⊂ O(h) ⊂ O(g)?

This isn't homework or anything. I'm just curious if anyone knows.


texts: Code to count number of leaves of a tree?

texts:
I've just started learning C. Can anyone tell me whether my code is correct or not, if not what's the correct version? This is code for counting number of leaf nodes. Is this efficient one if this is correct?

void Count_leaf( Tree* head)
    {       static leaf = 0;
            if(head.left==NULL && head.right==NULL)
            leaf++;
            else
            {     Count_leaf(head.left);
                  Count_leaf(head.right);
            }
    }


texts:
S -> AS | b

A -> SA | a

I get FIRST of S = {a,b} for S->AS
and FIRST of S = {b} for S->b

Hence FIRST(AS) ∩ FIRST (b) is not a disjoint
This is not LL(1)

But I checked this site http://smlweb.cpsc.ucalgary.ca/start.html
and this shows the grammar is LL(1).

Here I am confused!

Is it LL(1) or not?


texts: I am taking a programming languages course, and we have had to use the Inversion Lemma many times in our proofs of preservation. We have been given the Inversion Lemma in each of these examples, but is there a general statement of the inversion lemma that can be applied to any proof of preservation? Can someone write that out for me/explain it a little bit?


texts: What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity?

texts:
So considering CYK is O(n^3) and since we can just use LR(k) algorithms for DCFG's which they can check if a string is in the language in O(n) then whats the usage of CYK?

is it being used anywhere?

If I'm not mistaken(correct me If I'm wrong) the benefit of CYK is that since we can convert any CFG to CNF form therefore i guess we can apply this to non deterministic CFG's and also Inherently ambiguous grammars which are CFG

but are these really benefits? i mean whats the usage of using membership algorithm for Inherently ambiguous CFG's or non deterministic CFG's? where would we use a Inherently ambiguous CFG or non deterministic CFG ?!

Isn't the main usage of membership for compilers? which they already use LR algorithms?


texts:
Which is the lowest level of code (human written instruction for computers) in computer architecture? After doing minor research, I have come to the conclusion that, as far as determining a hierarchy in terms of the level of computer code, the following is the general level of code hierarchy: High-Level->Low-level->Assembly->Machine Code->Micro Code.
Am I correct?
If I am correct, is there a level of code below Micro code?
Is hardware control (in logical gates and transistors) code?


texts: Computing $n$th lexicographically smallest permutation of length up to $k$

texts:
I wonder how to tackle such problem, to be more specific:

  Given a set and an integer $k$, find the $n$th lexicographically smallest permutation (with repetitions allowed) of the set. We will say that the permutation is valid if its length is up to $k$ (inclusive).

Here's an example: $S$ = {a, b, c}, $k$ = 4, $n$ = 15

a aa aaa aaaa aaab aaac aab aaba aabb aabc aac aaca aacb aacc ab

Output should be: "ab" as it's the n-th lexicographically smallest permutation of length up to k of this set.

How to do this efficiently?


texts: Is there an example of an AVL tree that is taller than a binary heap?

texts:
I am curious because I took a quiz and answered false to the question:

"The height of an AVL tree may be greater than the height of a binary heap with the same elements."

I have been trying to think of an example, but I just cannot figure it out. Does anyone know when this is the case?


texts:
Using the Master Method, I need to prove (True, or False and why) the following (3) recurrences:

$T(n) = 3T(\frac{n}{2}) + n = \Theta(n\ln(n))$
$T(n) = T(\sqrt{n}) + 1 = \Theta(n^2)$
$T(n) = 2T(\frac{n}{3} + 1) + n = \Theta(n\ln(n))$

I understand the Master Method (I think, largely from: https://stackoverflow.com/questions/13430256/understanding-master-theorem) and from my CLRS Text.

Problem 1:
Would be case 1, but I don't understand how to use it in this case? What would my ɛ be in this case to perform the logarithmic function? I know that ultimately, my time complexity will be $\Theta(n^{1.58})$, but I don't know how to prove that without knowing ɛ

Problem 2:
I have no idea.

Problem 3:
I believe this is false, because this can be rewritten as  $T(n) = 2T(\frac{4n}{3}) + n$, which would be Case 2, and therefore give me a time complexity of $\Theta(ln(n))$.

This is my first time taking anything this granular with algorithms, and despite reading CLRS and looking at videos online, I am a bit lost, and would appreciate any help. Thanks in advance.


texts:
$n$ : length of text T

  $m$ : length of pattern P

When I study Rabin-Karp algorithm, I learned the best case of this algorithm is $\theta(n-m+1)$. Because if a hashed number is too small to modulo by some other number.

But when I'm talking with my friends about this best complexity, I was very curios that does above theta notation can be represented by $\theta(n)$ if $n$ is asymptotic to infinity?

First time, it was reasonable to me that $\theta(n)=\theta(n-m+1)$ is correct because it is asymptotic notation. But if $m$ is always $n-1$, can we use $\theta(n)$ in this situation? I'm confusing about notation concept and what I'm curious is below question.

  What is the right time complexity notation of Rabin-Karp algorithm?

  $\theta(n)$ or $\theta(n-m+1)$?


texts:
I've been given a question to solve:

Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.

For this, I used the dynamic programming approach which is not optimized and takes O(m * m * n) where n is the no. of distinct elements.

But, It's optimized time-complexity is O(m^2). Here, is the solution.

But, while going through the explanation, I encountered this written:

If n > m there will always be a subset with sum divisible by m (which is easy to prove with pigeonhole principle). So we need to handle only cases of n <= m.

I did not understand this part and want to know, how will it be proved rather than trying it by taking examples.

Also, why is the equality present with n < m and not with n > m ?


texts: Is there an heuristic for finding out the smallest height you can get when packing items in a tube?

texts:
It's sort of similar to bin packing, but instead of the minimum amount of bins,I was interested in just one infinite bin and finding out what's the smallest height you could get when you start packing items there.

I was thinking about this because of RCPSP, in case anyone's interested. I already have an algorithm to solve it, but I'm curious about this one.

As this is related to an assignment of mine, please don't give me other intuitions. Thank you for your attention :)


texts: A grammar for my context free language {xy | x, y ∈ {a, b} ∗ , |x| =|y| , x != y}

texts:
This question is given as an exercise to me . I took a look at the solution given by  the instructor which is not the same as my solution .

So I thought it would be wise to ask it here  considering I am a newbie on that topic.

My solution basically is as follow :

S -> aSa | bSb | aTb | bTa

T->   aTa | bTb | aTb | bTa | e

My apporach to the problem is as follows :
If I don't find  any differences (if both characters are the same)  , continue with S until you find  make a difference then you can do whatever you want with the string as long as you obey the rule of x having the same lenght .


texts:
I have an Euclidean, undirected graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.

The number of vertices with no edges is small in comparison to the total number of vertices.
No vertex has more than two edges connected to it.

How can I convert this graph to a closed shape, so each vertex will have exactly two edges connected to it and there will be a path between any two vertices? I want to do it with minimum change in the total weight of all the edges.


texts:
Given a directed graph $G$, we want a (simple) cycle in $G$ of maximal length. The cycle does not need to be an induced subgraph of $G$. What is known about this optimization problem?

Do we know its complexity? Is it much harder than the decision problem of detecting a Hamiltonian cycle? How well-approximable is the problem?

For the exact problem, is there a more efficient algorithm than exhaustive search using Johnson's cycle-enumeration algorithm?

Ideally, for the complexity question, I would like a description similar to here and here for related problems on undirected graphs: Longest induced cycle, Longest path, and Longest induced path. Longest cycle (for undirected graphs) is discussed in "A Structural Overview of NP Optimization Problems", although I have a harder time understanding that account.

FWIW, I'm particularly interested in (approximate) solutions for strongly connected digraphs of 100-500 vertices having average vertex degree ~10 and several induced tournaments on 5-10 vertices. I've been playing with genetic algorithms, and I'd like to know (1) whether better methods are available and (2) what level of performance I can reasonably aim for.


texts: What is the difference between Proof of Elapsed Time (PoET) and Practical Byzantine Fault Tolerance (PBFT) algorithm?

texts:
I am interested in these two consensus algorithms in the blockchain: PoET and PBFT.
I saw this question about PBFT algorithm.

But, my questions are: what is the difference between PBFT and PoET algorithm? Are they the same? If no, when to consider using PoET or PBFT algorithm?

Thank you.


texts: True or False: If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable

texts:
Question: Is the following statement true or false?

If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable

I thought that since every language is automatically of type 0, it follows that $A \in RE$, and since RE is closed under the Kleene star operator, it follows that $A^* \in RE$ and therefore semi-decidable.

However the solution says it's not true and uses the following counterexample:

If $A = \{1^n0 | 1^n \not\in H'\}$, where H' is the unaryly coded halting problem. Since $\overline{H} \leq A$, A is not semi-decidable. If $A^*$ were semi-decidable then so would be $A^* \cap \{1\}^* = A$, since $\{1\}^*0$ is semi-decidable and RE is closed under intersection, which is a contradiction.

Since I don't fully understand that line of reasoning, could someone please tell me what's wrong with my argumentation?


texts: Assuming that ATM is decidable, how to build a TM S that uses a TM R that takes as input  and decides if M accepts w, to decide HaltTM, which we already know is undecidable, hence ATM isn't decidable.   So how exactly do we go about this?


texts: Does code motion/hoisting happen on if statements/branches?

texts:
Consider the following C code:

for(int i=0; i<100000; i++) {
    if (operation == 0) {
        a[i] *= 2;
    } else {
        a[i] += 1;
    }
}

Would a real compiler (GCC) be able to do this optimization? If so, what is it called/how is it found?

if (operation == 0) {
    for(int i=0; i<100000; i++) {
        a[i] *= 2;
    }
} else {
    for(int i=0; i<100000; i++) {
        a[i] += 1;
    }
}