texts: Why does coNP⊆NP∖P imply that the polynomial hierarchy collapses?

texts:
I was looking for some information on 1-in-3 SAT and came across this paper, last updated 9 days ago, which claims that the Polynomial Time Hierarchy collapses "to the level above P=NP". That's quite exciting if you ask me, although I don't have the toolkit to understand the actual proof. My question is about something much simpler.

Specifically, in the abstract on arxiv, the author writes,

  Our proof shows the structure formerly known as the Polynomial
  Hierarchy collapses to the level above P=NP. That is, we show that
  coNP⊆NP∖P.

Could anyone help me understand why these two statements are equivalent?


texts: How to build 4 codewords with a code distance of 5?

texts: I wonder how can I construct 4 (distinct) codewords given the fact that code distance is 5. As far as I know that the code distance is the number of distinct bits between any 2 codewords. How to achieve this code distance for the 6 possible pairs from the 4 codewords available(of any bit length). I named, for example, codewords u, v, w, & x so d(u,v) = d(u,w) = d(u,x) = d(v,w) = d(v,x) = d(w,x) = 5. The code words must be in binary format i.e 00100 10011. I considered a code length of 10 to achieve this but still struggling to find a solution.


texts: Finding the greatest $k$ numbers with a certainty of $p$

texts:
Given $n \in \mathbb{N}$ pairwise distinct numbers. I want to do as few comparisons per number as possible - and every number should experience roughly the same amount of comparisons as another number - and find the greatest $k \leq n$ numbers, e.g. $k = \frac{n}{10}$. In order to minimise the number of comparisons per number, I allow an error, say I am okay if I know that the result is correct with only a probability of $p$.

I study mathematics and only had a very shallow introduction to algorithms so far, and the only relevant algorithms we discussed would be sorting algorithms. QuickSort comes to mind, but firstly I am not sure how I would implement my "tolerance of an error" and secondly, I think the fact that I only need the greatest $k$ numbers and I don't want to sort them, there might be more efficient algorithms.

Any basic approach would be a great help already, I'll gladly do the maths on my own.

Thanks in advance for any help.


texts: If $A,B$ are r.e. and $A\cup B,A \cap B$ are recursive, then so are $A,B$

texts:
Let be $A, B \subset \mathbb{N}$ are recursively enumerable, $A\cup B$ and $A \cap B$ recursive. I want to show that $A$ and $B$ are recursive.

By negation theorem $X \subset \mathbb{N}$ is recursive iff $X$ and $X^c$ are recursively enumerable.

How do I complete the proof using that?


texts: How to discern devices based on their traces?

texts:
I would greatly appreciate your advice on following machine learning problem:

I need to train a classifier to learn a device's behavior. The device itself can be observed under different operating/input conditions through a set of sensors. A sensor yields time series data and we call all observations during an interval a trace. More formally, a device is indirectly described through its emited traces of parameters $P$ (each having a domain $D_{P_j}$). A trace is a sequence of observations taken during a certain time interval:

$$
T_1 = \{ <t_1, p_1,\dots, p_k>, \; <t_2, p_1,\dots, p_k>, \; \dots \}
$$
$$
...
$$
$$
T_n = \{ <t_i, p_1,..., p_k>, \; <t_{i+1}, p_1,..., p_k>, \; \dots \}
$$

$$
with \; t_x \in \mathbb{R} , \; p_j \in D_{P_j} $$

The set of all traces, i.e., the training data for the machine learning system is $T = \{T_1,...,T_n\}$.

The question is now, how can I construct a machine learning system, that - given a trace $T_q \notin T$ - it can determine, if the trace $T_q$ has been emitted by the trained device or not?

What is the problem class?
What would be an appropriate algorithm to solve this problem?


texts: Is there a language that can be Turing-reduced from all languages?

texts: I don't think so, because $A_{TM} = \{<M,w>\mid \text{M accepts w}\}$ is not Turing-decidable. Is this the right way to think about?


texts: Models of Computation and What they can model

texts:
Some days ago i've discovered that in most of what we call "models of computation ", we can possibly model tasks other than computation itself . For instance, in lambda calculus we can model control flow tasks ( modeling if, while, forif controls) with function applications, whereas in Turing Machines the control flow possibility is already embedded.

A couple hours ago, i discovered that we can model tasks other than computing and control flow with a Turing Machine . For instance, we can model the task of writing and reading data from a register ( the register actually becomes a region of the tape ) .

I have two questions.

1 - Are there any other important task other than computation ( as in calculation ) , control flow and reading/writing that can be modeled by "models of computation" ? Can all models of computation ( lambda calculus, u-recursive functions ) implement all those tasks ? For instance, can we model reading/writing of data not only with Turing Machines but also in lambda calculus ?

2 - I don't understand why we call all those models, "models of computation", when in fact they can model more than computation. Someone suggested to me that these tasks are all the same and should be all considered as "computation". But are these tasks really the same thing ? Can the kind of "computation" that we deal with in computability theory really be about control-flow and/or reading/writing of data ? Would it have any sense in talking about whether reading/writing data or doing control flow admits an algorithm ? It seems to me that the only real computation would be those tasks that when executed could provide information to us : solving a system of equations, finding whether a number is prime, calculating the best path between two points, finding the integral of a function, doing simple arithmetic or boolean logic .

In summary :

In the first question i wonder whether you can identify on the top of your head any other task, other than computation, control flow ( modelling an if,while,forif controls ) and reading/writing that can be modeled by models of computation, and whether Lambda Calculus can model reading/writing of data, just like a Turing Machine can.

In the second question, i wonder if there are any links between the tasks of calculating ( finding whether a number is prime, calculating the integral of a function ) , controlling flow ( implementing while,forif, if ) and reading/writing of data that is sufficient enough for us to consider all three of them simply as "computation".

Thanks a lot in advance.


texts: Importance of indexes in Type(i) in calculus of inductive constructions

texts:
So I am reading about the calculus of inductive constructions. And I see here and here that there hidden indexes that the user does not know about in the $Type$ sort. It says that they are instantiated with proper values at the time of type checking. I am wondering, what is the importance of this? Looking at the rules it seems like I could just as well have not specified the indexes and for the user nothing would ever be any different.

So what difference would the user see if I simply had the rules $Type : Type$ and $\frac{E[Γ] ⊢ T : Type \,\,\,\, E[Γ::(x:T)] ⊢ U : Type}{E[Γ] ⊢ ∀ x:T,U : Type}$ in place of the rules that talk about the indexes?


texts: Unification Algorithm without Occur Check

texts:
I have been reading about Unification algorithm here https://en.wikipedia.org/wiki/Unification_(computer_science)#A_unification_algorithm
. And I wonder about the importance of occur check.

I know that without occur check an unsound inference may occur. But OTOH, does the algorithm always terminate without occur check? If the two literals to unify have no variables in common I feel like the algorithm should at least always terminate right?


texts:
I'm working on some questions to bone up on my knowledge of DFA's for a computing class and I've run across the following problem that is giving me some issues. If we have some
DFA M = (Q, Σ, δ, q0, F) and some other DFA M' = (Q, Σ, δ, q0, F') where F is a proper subset of F', are the following relations possible or not between the two produced languages?

1) L(M) ⊂ L(M')

2) L(M) ⊃ L(M')

My current theory is that the first one is not possible, due to the fact that the first machine has fewer finish states than the other, thus the language must be larger and cannot be subset to M'. This would of course mean that the second relationship is possible, since M must contain M'. Am I on the right track here and if so, how could I prove this?


texts: Regular expression for words where the same symbol can repeat at most two times consecutively?

texts:
Having the alphabet $\{a, b\}$, how can I generate a regular expression for the language that does not have substring of three or more consecutive same symbol?

For example, I can't have ${baaab}$ nor ${abbba}$, but I can have ${abbaabba}$.


texts: Finding path with specific length in weighted graph

texts:
Given a weighted, cyclic, directed graph and two nodes I am looking for a connecting path which total weight comes as near as possible to a specific value which is greater than the shortest path.
Example in a real world scenario: Find a route from Washington D.C. to New York City which is 400 miles long, despite the shortest path is ~230 miles. All my considerations so far failed for one of the following reasons:

Most routing algorithms like Dijkstra are not working in this case because there is nothing to minimize or maximize (the divergence of given weight to path weight should be minimized, but you need the finished path to calculate it)
DFS and BFS can be used to find a path with a specific number of hops (edges), but it doesn't consider weighted edges

EDIT:
Cycles are forbidden to avoid the simple solution shortest path + cycles until distance is reached. The algorithm doesn't have to find the optimal solution, a route with length in a given threshold is acceptable.


texts:
I'm a beginner and I don't understand what an Instruction Set Architecture is (I read the wikipedia page related to it).
Can anyone explain it to me in a simple manner please?


texts: Compare 2 video files (could be in different formats and quality) by content

texts:
I'm interested - is it possible to implement algorithm which could compare 2 video files and answer, are they the same with some level of precision.
Is currently exist some methods which allow to solve that problem effectively?

The same - means like this. Let's assume we have a video file. All files created from this by different encoding (mpg, avi, m2v etc), quality change, removing some small parts (less then 5% for example) this is the same.


texts: Is any State Space Tree always Binary Tree?

texts:
A backtracking algorithm generates, explicitly or implicitly, a
state-space tree.
Introduction to the design & analysis of algorithms / Anany Levitin

I wonder that whether the saying always holds. If yes, is it always binary tree?  For any problem which can be solved by backtracking, skeleton of the solution can be generalized?


texts:
Is there any situation that bidirectional search on a graph is not applicable? for example is there any classes of graph that we can only use ordinary Dijkstra's algorithm, and can not use its bidirectional variant.

The graph may be a dynamic graph.


texts:
I'm trying to create a TM that changes all $a$'s to $b$'s and all $b$'s to $a$'s in a given string and then halts on the first blank space it encounters. What I have is:

$$ \langle q_1,a,b,q_1\rangle \\
\langle q_1,b,R,q_2 \rangle \\
\langle q_2,a,L,q_1 \rangle \\
\langle q_2,b,a,q_2 \rangle \\
$$

I'm new to Turing machines, so I'm wondering if it makes sense to convert $a$'s to $b$'s and then send $b$'s into a different state; is there a sort of temporal sequencing here that will send the $q_1$-manufactured $b$'s (former $a$'s) into $q_2$ as well? If so, how can you get around this problem to construct a suitable machine?


texts:
I wanted to know that based on Kleene's theorem (a language is regular iff some FSA recognizes it), does every regex have a TM (Turing machine) that halts on exactly the same language?
Is this implication valid or are we not entirely sure about this? (ambiguous/unclear given the theorem). Kind of like the Church-Turing thesis about computation in the future and all computation in general.


texts: I am kind of new to timed automaton domain. I am trying to understand in which way they are different to Markov Decision Process. First I know there objectives is to solve the non-determinism of a MDP. However, is there anything else? Are they still memoryless? I am not able to find any information about this topic.


texts: Deleting useless (dead) states from a finite automaton

texts:
A useless state in a finite automaton is one from which no path leads to a final state, hence no (piece of a string) is recognized out of this state. Theoretically, the algorithm to determine the useful states is trivial: Let $G$ be the set of good (useful) states and let $\Omega$ be the set of all states. Initialize $G$ with all final states. Check all states $\Omega\setminus G$ for those that have a transition to a state in $G$ and add them to $G$. Repeat until nothing is added to $G$ any more.

A straightforward implementation mimicking the above, however, can be quite costly, looping over states and transitions over and over again. The number of loops checking $\Omega \setminus G$ is limited by the depth.

In a degenerate automaton containing transitions $a_0\to a_1 \to\dots\to a_n\to f$ where $f$ is a single final state and an additional transition $a_n\to u$ such that $u$ is useless, there would be around $n$ loops if you always loop over the $a_i$ in the order of $i$. But if you loop in decreasing order of $i$ shuffling found good states immediately into $G$, a single loop would suffice.

But this may lead to other degenerate situations (I am guessing).

I am looking for an algorithm to mark useful states, or remove useless states, that is not recursive (to prevent stack overflow, since I am looking at FAs with millions of states) and as efficient as possible.

Extra question: are there theoretical limits known for this algorithm?


texts: How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$

texts:
Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s.

Also, I have a hint
HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s odd 1’s, even 0’s odd 1’s, odd
1’s, even 0’s – and combine them ...

But I can't understand how it works

Who can help?


texts: A context-free grammar for a language of strings with occurrence properties?

texts:
Creating a context-free grammar for the language

$L_1 = \{ 0^{n} 1 ^{m} \mid m,n \in \mathbb{N} \wedge  m \equiv n \mod 3\}$

is quite easy. A grammar is

$$ S \rightarrow \epsilon \mid 0A $$
$$    A \rightarrow 1 \mid 0B $$
$$    B \rightarrow 11 \mid 0S $$

But I am now trying to create a context-free grammar for

$L_2 = \{ w \in \{0 ,1 \}^{*} \mid |w|_1 \equiv |w|_0 \mod 3 \}$

Here, $|w|_1$ denotes the number of occurrences of the character $1$ in the string $w$, and $|w|_0$ is defined similarly.

How does one construct a context-free grammar? All my attempts have lead to completely wrong results. At the moment I am stuck.


texts: Extreme instancing for computer graphics

texts:
Instancing in GPU's, from my little knowledge, simply draw the same object at multiple locations. Each "instance" is just a copy of the same model at a different location. Any local effects, such as animation, would effect all instances. The performance improvement comes from gpu being able to deal with virtually all the instance aspects.

One could create several variations of the same object and instance each one. This would be very useful to create variations(say for leaves on a tree) but, while allowing for rather large number of instances(basically limited by the gpu) and variation increases the the cpu's involvement by the number of variations(from the previous case).

If we could send the changes to the gpu then we could get back to the first case(or very close) and achieve very high levels of variations with limited cpu involvement.

For example,

Suppose we wanted to populate a jungle with a lot of animals. Each animal object will have many instances(many tigers and birds but all using the same template). If we had one long animation containing all the possible animations of each animal and send it to the gpu we then would simply have to tell the gpu which part of the animation each instance was in(and we could have a default animation to limit cpu-gpu communications).

This would effectively let us control all the instances with just a animation position indicator(and possible a few other parameters such as scale) and coordinate position. The gpu would take care of all the rest.

The problem, of course, is that that each instance would not have any logic associated with it. This is not a big deal though for most computer objects. The cpu generally has to take care of the logic anyways but in this case, instead to tell send all that information to the gpu we can just send it a few bytes for each instance.

For example, suppose in our jungle we have a few cheetahs and on our cpu we are keeping track of which ones are doing what and simply sending which animation we want them to use to the cpu(instead of sending all the vertex data and/or telling it how to transform them).

This seems like it would be much faster and essentially just boils down to moving some of the code from the cpu to the gpu(which as been what is happening all along).

Using such a method is not ideal because of the lack of physical modeling per instance but for far enough away objects were intersecting objects won't be seen it won't matter.

We could have thousands of birds, for example, all seemingly moving individually but generated from one model with a few animations.... the cpu doing very little but sending which animations to use to the gpu. (and of course deciding what each bird should do)

Anyways, this is a thought but it seems to me the goal of future gpu's is to deal with all the visual aspects while the cpu deals with the logic(and the communication between the too is to be minimized).

Is my interpretation of instancing with animation's flawed or could it be implemented and be useful to 3d games?


texts: Classification of job shop scheduling problems

texts:
I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory.

The factory has several types of machines (say, locksmith, miller, welding)
There are few machines of each type. (say, 3 locksmiths, 2 millers, 3 welders)
There are several types of operations (some machines do more than one operation on the job, say, locksmith does soldering and assembling).
The jobs on the machines have different times, all known beforehand.
The jobs have dependencies on jobs done before (say, a product's made of 10 screws and 4 subparts, each of which needs 4 screws).

From what I searched, this looks sort of like a Flow Shop problem. The difference is in the dependencies and in the same machine doing different operations with different times on a job.

My main question is:

Is there some kind of a classification of these problems? A summary telling the differences?

For example, I don't understand much of how do these differ: Open Shop, Job Shop, Flow Shop, Permutation Flow Shop. And whether or not I missed something similar that could fit better to my problem.

As a side question, what approach do you think could help me best with the unusual requirements I've posted above? I'm writing my current approach below.

So far I've been able to work with the tree of dependencies without regard to the makespan times: just making a plan - a list of IDs, really - of what comes after what, from looking at the tree of what's been done so far and what are the leaves (nodes having done all their dependencies).

This allows for fast creation of meaningful individuals in the Genetic Algorithm population, but there seems to be no computationally cheap way to learn the individual's makespan time (which I have as the fitness function).

For that I have to create a calendar, or Gantt chart, if you will, to which I put the operations on the jobs in the earliest place possible, in the machine queue that's free at that moment, etc. The whole plan has to materialize and that seems the most costly computation of the whole problem.


texts:
I was looking at my teacher's notes and came about the following recurrence equation :

$$
T(n) =
     \begin{cases}
       1 &\quad\text{if } n\leq 1\\
       4T\left(\frac{n}{2}\right) + n^3 &\quad\text{if } n\gt1 \\
     \end{cases}
$$
In order to solve it I proceeded as follows :
$$
T(n) = n^3 + 4T\left(\frac{n}{2}\right) = n^3 + 4\big( 4T\left(\frac{n}{4}\right) + \left(\frac{n}{2}\right)^3 \big) = \\
n^3 + 4\left(\frac{n}{2}\right)^3 + 16T(\frac{n}{4})
 = \cdots
$$
I'll spare some latex and state that we can see from unwrapping the equation that at the generic level $i$ the incurred price is :
$$
T_i = 4^i\left(\frac{n}{2^i}\right)^3
$$
In order to compute the overall price we can sum all the prices incurred at all levels, obtaining :
$$
T(n) = \sum_{i=0}^{log^n -1}{\big(4^i\left(\frac{n}{2^i}\right)^3\big)} + 4^{log^n}T(1) = \\
n^3 \sum_{i=0}^{log^n-1}{\big(2^{2i}\frac{1}{2^{3i}}\big)} + n^2 = \\
n^3 \sum_{i=0}^{log^n-1}{\big(\frac{1}{2^{i}}\big)} + n^2
$$
My problem begins here. In order to solve it I'd say that the series in questions can be solved as :
$$
 {\displaystyle \sum _{k=m}^{n}x^{k}={\frac {x^{m}-x^{n+1}}{1-x}}\quad {\text{with }}x\neq 1.}
$$
which applied to my scenario would yield
$$
n^3 \left(\frac{1 - (\frac{1}{2})^{log^n}}{1 - \frac{1}{2}}\right) + n^2 = \\
2n^3 - 2n^2 + n^2 = 2n^3 - n^2 = \Theta(n^3)
$$
But my professor says :
$$
n^3 \sum_{i=0}^{log^n-1}{\big(\frac{1}{2^{i}}\big)} + n^2 \leq n^3 \sum_{i=0}^{\infty}{\big(\frac{1}{2^{i}}\big)} + n^2 = \\
n^3 \frac{1}{1 - \frac{1}{2}} + n^2 = 2n^3 + n^2
$$
And thus $T(n) = O(n^3)$ instead of $\Theta(n^3)$ since we proved only an upper limit.

My question is thus, why can't I solve the summation as I did instead of extending it to infinity?


texts: Ideas on how to approach the construction of a probability-heavy algorithm

texts:
Definitions

Assume we have a Shopping List $L$ which is a list of pairs of Items and Quantities: $L = [(i_1, Q_1), (i_2, Q_2), (i_3, Q_3) ...$

We also have a Stock List $S$ which is a list of pairs of Containers and Prices: $S = [(C_1, p_1),(C_2, p_2), (C_3,p_3)...]$

Each container is a list of 3-tuples of Items, Quantities, and Probabilities: $C_n = \left[\left(t_1,q_1,\frac{a_1}{b_1}\right), \left(t_2,q_2,\frac{a_2}{b_2}\right), \left(t_3,q_3,\frac{a_3}{b_3}\right)...\right]$

Purchasing a container for a given price gives you a chance of getting each item within it. The chance is equal to each item's probability. The probabilities are independent of each other (two items with a probability of 1/2 are treated as two coin flips, it isn't "one or the other"), and their quantities are absolute. If we had $C_1 = \left[\right(x, 2, \frac{1}{2}\left)\right]$, then there is a one-in-two chance of getting two $x$s, and no chance of getting only a single $x$.

The Goal

I'm trying to come up with some algorithm which has the ultimate goal of satisfying a given shopping list from some stock list. Due to the random nature of the problem, it is impossible to construct a definite chain of purchases to make. Thus, I was thinking that foo(L, S) should return the best next purchase -- the container to buy which satisfies the most items in the shopping list for the lowest price. Purchasing this container can affect the shopping list in a variety of ways, so upon purchasing, the list will be run through the algorithm again and again until it is empty.

My Attempts

If I could construct a function which outputs some "instantaneous value" of each container, I could then calculate and sort each container by this value and purchase the one highest-valued one.

This value of a container would be its benefit minus its cost. Calculating the cost of containers which contain only one needed item is simple enough, but I'm stumped on containers with multiple items. Consider this example:

$L = [(x, 1), (y, 1)]$

$S = \left[\\
\left(\left[\left(x, 1, \frac{1}{2}\right)\right], 10\right),\\
\left(\left[\left(y, 1, \frac{1}{2}\right)\right], 10\right),\\
\left(\left[\left(x, 1, \frac{1}{3}\right),\left(y, 1, \frac{1}{3}\right)\right], 20\right)\\
\right]$

(The first container costs \$10 and has a 1/2 chance of giving an $x$. The second container costs \$10 and has a 1/2 chance of giving a $y$. The third container costs \$20 and has a 1/3 chance of giving an $x$, and a 1/3 chance of giving a $y$.)

The cost of getting an $x$ from the first container is \$20. This would satisfy one out of two of our list's requested items. If our strategy for satisfying the list was to brute-force the first container, then the second, the total cost of the list would be \$40.

What gives me trouble is that third choice. There is a 1/9 chance of spending only \$20 and getting both of our $x$ and $y$ in one move. There is a 4/9 chance of spending \$20 and getting either our $x$ or $y$ -- we could then get the remaining one for \$20 and be done for \$40. Finally, there is another 4/9 chance of getting nothing.

I suspect that the best path in this case is to buy the third container until at least either an $x$ or $y$ is obtained, then buy the remaining one from the first or second container. (Edit: A simulation shows that solely buying containers 1 and 2 leads to an average cost of \$40 to satisfy the list, as expected, but buying the third container then one or two leads to an average cost of \$52 to satisfy the list. Besides simulating, I'm unsure of how to derive that 52)

Any ideas on how to approach this?


texts:
I am amazed by the many discussion regarding the existence of any linear and in-place sorting algorithm, and variants, see e.g.
is-this-implementation-of-bucket-sort-considered-in-place
is-counting-sort-in-place-stable-or-not
sorting-in-linear-time-and-in-place
can-a-counting-sort-be-considered-in-place-when-the-problem-constrains-the-numbe
fastest-in-place-sorting-algorithm-for-epochtime
in-place-and-out-place-sorting-meaning
fast-stable-almost-in-place-radix-and-merge-sorts
sorting-in-place-stable-in-linear-time
I am even more amazed by the lack of a clear and definitive answer, due in part to the fact that "in-place" is loosely defined.
I would therefore like to give it one more try, aiming at being more precise and rigorous, with your help.
Sorry if this is too redundant; if so, please do not hesitate to tell me where.
Problem statement.
Input: $n$ positive integers of values lower than $k$, with $k\le n$.
Output: the $n$ integer in non-decreasing order.
Proposal.
This is the closest to in-place and linear sorting algorithm that I could find. It relies on a variant of counting sort that parses the original array and counts occurrences of integers in-place, within this array. To do so, it swaps the content of cells that it modifies, and encodes cells that contain a counter by a negative integer. Then, it prints the result without storing it.
This is a python implementation, with comments explaining the details:
import random,sys
random.seed()

# create input
n = 30
k = 4
l = [random.randrange(0,k) for i in range(n)]

# for debug: print original list and its native sort
print(" ".join([str(x) for x in l]))
print(" ".join([str(x) for x in sorted(l)]))

# "in-place" counting sort
i = 0
while i<n:
  x = l[i]      # the value to count
  if l[x]<0:    # there alreaty is a counter for it
    l[x] -= 1   # (negatively) increment it
    l[i] = -1   # set current cell to 0, encoded as -1
  else:         # first occurrence of x
    l[i] = l[x] # store the value in l[w] before erasing it
    l[x] = -2   # new counter in l[x], init to 1, encoded as -2
  while i<n and l[i]<0: # go to next non-counter cell
    i += 1

# print result
# l[i]=-x-1 means there are x occurrences of i
for i in range(k):
  for j in range(-l[i]-1):
    sys.stdout.write("%d "%i)
sys.stdout.write("\n")

Remarks.
This algorithm seems to be in-place, since it seems to only use a constant amount of memory in addition to its input.
However, it is not really in-place, because:

It uses negative numbers to encode counter information within the input array, which actually costs $n$ bits.
Its output is just printed, not stored (not even in the original array) and so it is not available for further computations.

Questions.
A first set of questions is about possible improvements:

Is it possible to save even more space? For instance, only $k$ bits are really needed, as there are $k$ counters. Anything else?
Is it possible to write the sorted values in the input array? or may we prove that this is not possible?
Is it possible to extend it to more general inputs? Clearly, any other integer interval of length at most $k$ is possible. Anything else?

A second set of questions is about possible uses:

Are there cases where one wants to print the result, without storing it? It seems related to streaming algorithms.
Does this algorithm help in finding better solutions to other problems, like median or cumulative distribution computations? or removing duplicate values?


texts: Why does backtracking work the way it does?

texts:
I just recently started learning in a CS context (as opposed to a programming context) about simple recursive functions, along with the combinatorial applications, and techniques such as Backtracking and Divide et Impera.

The example problem that I chose for my questions is the n queens problem (given n queens and a n*n chessboard, how do you position the queens such that they can't attack each other?).
I understood that the basic idea is to generate all possible placements (by generating a cartesian product) and then simply discarding them as they come along if they are invalid (through the validation function).

Here is my sample implementation:

    int valid (int k)
    {
    for (int i = 1; i < k; i++)
    {
        if (sol[i] == sol[k]) return 0;
        if (abs(sol[i] - sol[k]) == abs(i - k)) return 0;
    }
    return 1;
}

void print ()
{
    for (int i = 1; i <= n; i++)
    {
        cout << sol[i];
    }
    cout << endl;
    how++;
}

void backtrack (int k)
{
    if (k == n+1) print();
    else
    {
        sol[k] = 0;
        while (sol[k] < n)
        {
            sol[k]++;
            if (valid(k)) backtrack(k+1);
        }
    }
}

Why is it that in the validation function, the checking of the solution is done progressively by checking 1 with k, 2 with k and so on. I think that the solution can be correct in pairs of (i, k) but wrong overall (for example 1 and 2 relative to 3 are placed correctly, but 1 relative to 2 is placed incorrectly)?


texts: How to model equality in Integer Linear Programming

texts:
How to implement v=(a==b) using Linear Programming?
$$
v=
\begin{cases}
True, a=b\\
False, a≠b\\
\end{cases}
$$

Until now I tried the big M-Method.

To show a≤b:
$$a-b+Mv≤M$$
$$-a+b-Mv≤-1$$

To show b≤a:
$$-a+b+Mv≤M$$
$$a-b-Mv≤-1$$

When they are equal everything is okay, but when a≠b it doesn't work.


texts: What Does The Notation of Union Over K represent?

texts:
I am currently studying about polynomial time in Comp Theory. The definition for polynomial time given in my textbook as follows:
$$P= \bigcup_{k}TIME(n^k)$$
I have not seen the Union over k notation before. K is a constant. A quick introduction to the meaning of this notation would be enormously helpful.

Thank you


texts: Operation on a regular language and context free language

texts:
Given $L_1$ and $L_2$ over some alphabet:

$L_1@L_2 = \{uv \mid u \in L_1 \land v \in L_2 \land |u|=|v|\}$

The question is: if $L_1$ is regular and $L_2$ is context-free, is $L_1@L_2$ context free?

I've been trying to disprove this but to no avail. So I've been thinking to prove this by buiding a PDA but I can't seem to figure this out.


texts:
Here is one discussion that says, "every DCFL has an LR(1), an LALR(1) and even an SLR(1) grammar."
And wiki says, "a language can be generated by an LR(k) grammar if and only if it is deterministic [and context-free], if and only if it can be generated by an LR(1) grammar"
Is the first statement in that discussion forum is correct?
I found wiki statement at many places but nowhere I found the first statement except in that discussion.
Please tell me if first one is correct or not, and If possible provide some source that confirms this statement. Thanks in advance.


texts: Relation between witness and problem statement

texts:
Are there any known upper/lower bounds on the size of a witness of some np-complete/hard problem, or more precisely the relation between the problem size and the witness size.
For example, I'm interested in subset sum, set cover, SAT, hamiltonian cycles. If there is something known for other problems, I'd also be interested.
To be a bit more clear, I'll explain what I mean in detail for two of those problems.

UPDATE:
I assume the problem has a solution. So I am not interested in the decision version, but rather I assume there does exist a (positive) solution and I'm trying to find it.

For example, I give you a SAT problem and I tell you there is a solution, please find at least one. This should also be NP-complete. Now if the SAT Problem has 3 literals, it's easy to solve. If it has n/2 literals and n clauses, it's probably not easy. So my question is at what point it becomes easy and why.

In the case of subset sum. I give you a subset sum problem instance and ask you to find me one of the solutions, which I tell you exist. This is still hard to do, but is it also hard to do if I tell you that the/a solution will be a subset of number of size n/2 for a list of length n?
Again, I'm interested in understanding at which sizes of the solution the problem becomes easy.

For hamiltonian cycles, I ask you to find a cycle of size $k$ in a graph of size $n$, for which $k$ is the problem hard and so on...

I looked at the analysis of Fixed Tractable Problems, but they seem to focus on parameters that are fixed to constants, which is not necessarily what I want to know I think.

My intuition would be that most (NP-hard) search problems become easy once the witness size is smaller than $log(n)$ or bigger than $n-log(n)$, but I don't know how to actually support this claim formally.

I hope my question is a bit clearer now.


texts: One algorithm for turnpike reconstruction problem?

texts:
In << Data Structure and Algorithm Analysis >>,  turnpike reconstruction problem is given for demo of backtracking.

Suppose we are given n points, p1 , p2 , . . . , pn , located on the X -axis. Xi is the x coordinate of pi . Let us further assume that X1 = 0 and the points are given from left to right. These n points determine n ( n - 1)/2 (not necessarily unique) distances between every pair of points. It is clear that if we are given the set of points, it is easy to construct the set of distances in O ( n^2 ) time.  The turnpike reconstruction problem is to
reconstruct a point set from the distances. This finds applications in physics
and molecular biology (see the references for pointers to more specific
information). Nobody has been able to give an algorithm that is guaranteed to work in polynomial time.

I feel there is  space for optimization.

Given D = [1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10]

len(D) = n(n-1)/2 = 15, so n = 6.

Let X1 = 0, X5 = 8, X6 = 10 , delete 10, 8, 2 from D. (same as book described)

Instead guess X4 = 7 or X2 = 3, separate D = A + B,

B = [(3,7),(4,6),(5,5)],  ((x,y): x+y = max(D))

A = [1,2,2,3,3,5],  (x,y: x+y != max(D))

If len(B) < n-3,  then no solution for this problem.Luckily,it not happen here.

else if len(B) == n-3, then X2 = X(n-1) - max(A) = 3 is necessary. It happens here!

else try to fix X2 by backtracking.

After fix X2 (it means D has been separated properly), separate A = E+F

E = [(2,3),(2,3),(5)],  ((x,y): x+y = max(A))

F = [1],  (x,y: x+y != max(A))

If len(E) < n-3,  then no solution for this problem.Luckily,it not happen here.

else try to fix X3...

If problem has no solution, then this algorithm will know it in advance most probably, no need to check every corner.

If it has solution, when search, only search in special sub-list, and has more conditions to be a sieve to stop early in a wrong direction.

I guess it should work much faster when n is big.

Could it be optimized further ?


texts: Formal language properties and finite state machines

texts: What are properties of a formal language? Which and how would they be needed to prove that some Non-Deterministic finite state machine can accept a given language?


texts: Difference between multimethods and overloading

texts:
Context

I've been programming in java for a few years now. And atm i'm learning something totally different: Clojure.
There the expression problem can be solved by using multimethods whereas in java you will need something like the visitor pattern or something alike.

The question

I've been reading about multimethods and got quite confused with the actual difference with method overloading.

The only difference I spotted so far that a multimethod doesn't depend on the runtime type of the object on which the method is called.


texts:
I have a question regarding optimal mistake bound for learning algorithm

There is a famous fact that $VC(C) \leq Opt(C)$,

where $C$ - set of learning concepts,

VC(C) - VC dimension of C,

$Opt(C)$ - the smallest mistake bound (of the best learning algorithm) on the hardest learning concept $c \in C$ .

I don't understand why $VC(C) \leq Opt(C)$, in my opinion the notion of best algorithm $A$ is so vague that you cannot for sure say that $VC(C)$ is not more than $Opt(C)$

For example,  $VC(line\ on\ the\ plane)$=3 , it means that $Opt(C) \geq 3$ in words it means for the hardest concept $c \in C$ (represented as a line on the plane) the number of mistakes of the best learning algorithm is more than 3.

Why the above fact is so strong?


texts:
While studying master method at recurrences topic I'm stacked at a point. It is written in the book as:

  $T(n) = 3T(n/4) + n \log n$,

  we have $a = 3, b = 4$,

  $f(n) = n \log n$, and

  $n^{\log_b(a)} = n^{\log_4 3} = O(n^{0.793})$.

  Since  $f(n) = \Omega(n^{\log_4( 3)+\varepsilon} )$, where  $\varepsilon \approx0.2$ ....

The authors means that the $n\log n = \Omega(n)$. How will we know this? Is $n \log n = \Omega(n)$ true? Or
something is wrong?


texts: Showing a linear program is infeasible or finding a feasible solution

texts:
I'm aware that for any given maximize/minimize LP problem, if its dual is unbounded then the primary is infeasible and vice versa. But what if there is no maximize/minimize objective function? For instance, if the problem were simply as follows:

$$x_1+x_2+x_3+x_4\geq 12 \\
2x_1-6x_2-3x_3+2x_4\geq 4 \\
-x_1+x_2-x_3-x_4 \geq 1 \\
x_{1,2,3,4} \geq 0$$

And we were supposed to either provide A feasible solution, OR show that that it is infeasible?

I suspect one might have to first turn the above into equality constraints by introducing surplus variables, but then what? I think intuitively that there is probably no feasible solution here, but how might one prove it?


texts:
I have a real world problem where I have a list of nodes. Each ones contains a name and the name of the node before it in order. I am trying to devise an algorithm to sort these in order. The problem is that any two random nodes will not tell me anything about their order unless they happen to lie next to each other, so I can't use a traditional sorting algorithm.

When I try to work through ideas everything basically comes down to "grab" the node at the start and then place it after the correct node" then repeat with the next node at start of the list. The problem is this has worse case running time of $O(n^2)$ complexity if the items are reversed. Any ideas of how to efficiently solve a problem like this?


texts: Can type information be encoded in the untyped lambda calculus?

texts:
I'm going to take the few pieces of knowledge I have about lambda calculi and ask a pair of very uninformed questions :-)

Is it possible to "embed" the corners of the lambda cube within the untyped lambda calculus?

It would seem that this might lead to a language where the programmer implements the type system in the language, rather than having it already implemented in the compiler.  Also, maybe the concept of type system could be generalized to "any arbitrary compile-time or run-time constraint checking".  Does such a language already exist?


texts: Difference between fixed-to-variable length codes and variable-to-fixed length codes?

texts: I am a bit confused by the difference between the two. Can someone clarify the difference between the two?


texts: How to interpret "Windows - Virtual Memory minimum too low" from a CS student point of view?

texts:
On my old 256MB RAM, pc I get this message. (I guess it is quite common)

  Windows - Virtual Memory minimum too low
  Your system is low on virtual memory. Windows is increasing the size of your virtual memory paging file. During this process, memory requests for some applications may be denied. ...

Please explain from a CS student point of view-

"Windows is increasing the size of your virtual memory paging file." and
"during this process...". what is this process called?

Thanks, I am currently studying virtual memory management in OS.


texts: Isn't software needed from programs to run?

texts:
I am a student who has entered a game programming competition called FBLA at school, and I sent them an email because I had a few questions about how the competition is ran.

The main question I had, since I'm a Java programmer was in short:
"Does the program need to be an executable, and if a java update/install is needed to run my program, will they install it?"

Their response was (quote):
"The file does need to be a .exe and the entire program needs to be able to run independently on the judges’ machines. Installing JAVA then running your program is not the intent of this competition. I understand your concern as a JAVA programmer, but this competition is set specifically to this format so that all the programmers know, up front, what is expected."

I can understand the file needing to be an Executable file, but when they said, "Installing JAVA then running your program is not the intent of this competition." really angered me.

If I'm going to make an application in C++, doesn't it require a version of C++ Redistributable? What about DirectX, that's software needed for some C++ programs, isn't it? What about programming in C, and C#?

My argument to them is doesn't all programming languages have a necessity to some form of software in one way or another? Without it, wouldn't applications be very limited, or not run at all?

If someone could please help me settle this issue for installing Java on a machine being no different to making game applications in other languages, I would really appreciate it.


texts: Is Bresenham's Line Drawing algorithm still used today?

texts:
If so, I cannot find any examples of this.

Edit: By "used", I mean are they still used in rendering in games or whatever. I haven't seen it used anywhere except in MS Paint because Wu's algorithm looks way better (yet is still not expensive as far as I know).


texts: Efficiently compute parallel matrix-vector product for block vectors?

texts:
I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I now want to compute the matrix-vector product
$$w = (E\otimes I_N)v$$
in parallel, where $\otimes$ is the Kronecker product, $v = (v_1, ..., v_P)^T$ is the stacked vector consisting of all local vectors $v_p$, $E = (e_{pj})_{p,j}\in\mathbb{C}^{P\times P}$ some dense matrix and $I_N$ is the identity matrix of size $N\times N$.

So, to do this, each processor $p=1, ..., P$ has to compute
$$w_p = \sum_{j=1}^P e_{pj} v_j$$
and for this, all $P$ vectors $v_p$ have to be sent to all $P$ processors.

Now, $N$ is pretty large (say, $10^8$), in particular much larger than $P$ (which is only 10-100) and so large that $NP$ (the size of $w$ and/or all vectors $v_p$ together) does not fit into each processor's memory. Also, sending all these vectors $v_p$ in an all-to-all fashion seems pretty hard on the network.

Is there a standard and/or particular efficient way to compute this sum for a general matrix $E$? What would be the complexity of this approach?

Any help, suggestions or links to publications are appreciated!


texts: Matching k-partite graphs where all sets may only share edges with one of the sets

texts:
I'm not terribly well-versed in CS (I only just a few moments ago learned what a k-partite graph is), so forgive me if this is an obvious question.

I'm wondering how to determine if a given graph matches a specified pattern, where this pattern is an example graph that is a k-partite graph where all inter-set edges must be between one special "central" set and some other set.

I hope I'm explaining this correctly. I imagine an algorithm to take care of this (or most likely a more general case) already exists, so just a link might be the most appropriate response.

Thanks!

(P.S.: This isn't a homework problem or some made-up situation. I'm trying to do a matching of ligand-to-amino-acid graphs for a biological search tool; in my real-life case the "central" set is the ligand, the edges are bonds or interactions, and the other sets are amino acids.)


texts: Does this context-free grammar generate a regular language?

texts:
Does the following set of production rules produce a regular language or not?

$S \to AB \mid b $
$A \to SB$
$B \to AS \mid a$

I have generated following words with above grammar

$b , baa , baaaa , baaaaaa, .....$
$bbaba , babab , bababaa , bbbabba ,.....$

But I am not able to create a language using it.
Is this grammar just context free or is this regular also ?
If yes, how to prove that ?


texts: Reduction from Exact Cover to Fixed Exact Cover

texts:
I am trying to reduce Exact Cover to Fixed Exact Cover to show that Fixed Exact Cover is NP-Hard.

Exact Cover

Input

S = {x1, x2, ..., xn} (set)

P = {P1, P2, ..., Pm} (subsets of S)

Decision problem: Is there a subset {Pi1,Pi2,...,Piq} of P such that every element of S belongs to exactly one of the Pij:s?

Fixed Exact Cover

Input
S, P from Exact Cover, and an integer K

Decision problem: Is there a subset {Pi1,Pi2,...,Pik} of P of size K such that every element of S belongs to exactly one of the Pij:s?

Given hint: K = n + 1

My initial reaction is to iterate through each element in S, and for each element create a subset for P. However, that will result result in K being one too small. I have tried many things, but I just can't seem to figure it out.

EDIT

Sorry I should have added this in the original question:
(All the Pij :s are assumed to be distinct.)
Furthermore, (we can define an instance (S′,P′,K=n+1) of FSEC. S′ will be S ∪ A and P′ will be F ∪ G where A and G are ”dummy” sets disjoint from S and P and such that the elements of G are subsets of A. If A and G are chosen in a clever way (S,P) will have an exact cover if and only if (S′,P′) has a n+1 size cover)

Example

S = {1,2,3,4}

P = {{1}, {2,3}, {2,4}, {4}}

Solution

{{1}, {2,3},{4}} (size 3)

K = 5

S' = {1,2,3,4,5,6,7,8}

P' = {{1}, {2,3}, {2,4}, {4}, {5}, {6},{7},{8}, {5,6},{5,6,7}, {5,6,7,8}}

Solution = {{1}, {2,3}, {4}, {5,6,7}, {8}} (size 5)


texts:
I'm learning for my exam in theoretical computer science and I'm not sure about it, because I got different sources with different answers. So I wanted to ask here:

If I draw a NFA/DFA and I maybe don't need the transition from a state $z_k \rightarrow z_{k+1}$  with  a $0$ above the alphabet $\Sigma = \{0,1\}^*$ so I only need there a $1$, do I always need a failure state $z_F$ so that $\delta: z_k (0) \rightarrow z_F $. Or can I omit that in the drawing? Or is there a difference between DFA and NFA, so that I need to write this failure function if its an NFA but I can omit it if it's an DFA? In my exercises my prof deducted one point because I had no failure state but just one or two times..

Hope somebody can help


texts: $U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP complete

texts:
I'm trying to prove $U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP-complete. Showing it is NP is trivial. NP-hardness is the hard part. One way to do it would be to reduce a known NP-complete problem to $U$. Another way would be to find a general way to reduce any NP problem to $U$ in polynomial time.

I've found some online proofs for doing this. They all seem to reduce some arbitrary NP problem, say $A$, to $U$ by using the polynomial bound for the nondeterministic polynomial-time decider for $A$. So let $A$ be some NP problem, and let $N$ be its non-deterministic decider which runs in $n^{k}$ time for some $k$. Then output $\langle N, x, \#^{k} \rangle $. The issue I have with this solution is, how do you know what $k$ is? You know that $A$ is NP, so there is a non-deterministic polynomial time decider for it, but how do you know the actual degree of that polynomial? It seems false to assume it is already known, surely one should have to compute it manually to obtain a reduction. How could you compute the degree of this polynomial in polynomial time? The existing proofs seem to gloss over this critical fact.


texts: Comparing the big-$O$ of these four functions

texts:
Sometimes you can substitute values for $n_0$ and $c$ in the big-$O$ equation and compare two functions. Or take limits and compare two functions.
But for the following functions, for example, taking the limit in infinity for
$f_3$ over $f_2$ requires using l'Hôpital's rule which doesn't simplify anything. $f_3$ is technically the product of a polynomial and an exponential function. And I don't know how to go with comparing functions like that with others.
Firstly, I know that $f_4$ is the most efficient because it is $O(n^2)$. ($f_4(n) = n + \frac{n(n + 1)}{2}$) and the rest are exponential.
But for the rest, I really don't know what to besides using my intuition which could be really far from the correct answer anyway. Please help me compare these rigorously.
$f_1(n) = n^{\sqrt{n}}$
$f_2(n) = 2^n$
$f_3(n) = n^{100}2^{\frac{n}{2}}$
$f_4(n) = \Sigma_{i=1}^{n}i + 1$


texts: Grover's algorithm on probabilistic classical machines

texts:
As a starting point for this question, I came across this question, which AIUI is citing a construction showing how to simulate quantum circuits with a $PP$ algorithm, i.e. implying quantum computation in general is in $PP$.

However,  it struck me as counterintuitive to say that the only way to implement a specific example of QC, like Grover's algorithm, would be to do so by emulating a quantum computer and running it in there. I then tried to imagine what implementing it more naturally might look like, e.g. operations in terms of list items directly rather than transforming them into a quantum state vector.

For background, I understand that non-$BPP$ algorithms in $PP$ are allowed to be arbitararily close to random, and so we potentially need to repeat them exponentially many times to arrive at any particular confidence in their answer. I'm specifically interested in what a single iteration (that then needs to be repeated exponentially many times) of a Grover-like algorithm looks like. I presume, from the fact that the translation in the linked thread is 1-1, that this single iteration would be expected to take $O(\sqrt n)$ time, but please let me know if this inference is incorrect.

(I'm also presuming that this Grover-like algorithm is not in $BPP$, because otherwise search theory would be very different. It being outside $BPP$ means we're talking about a search algorithm that in practice takes $O(2^\sqrt n)$ time, which isn't going to revolutionize anything.)

Also, since $PP$ is generally defined in terms of binary decision problems and Grover's algoritm is not one, I had to extrapolate slightly about what the success criteria looks like in a $PP$ rather than $BQP$ context. The criteria I tentatively came up with is that the algorithm should be create and pick from a probability distribution over the $N$ items of a list, with the property that the most likely item to be selected is the (a, if more than one) item marked by the oracle function, i.e. it has the pluarity, but not necessarily majority, of probability mass.

That has the obvious caveats that because the list in general contains more than two items, it is not more likely than not that that item gets selected, only that no single item is more likely. The difference in probability between the most and second-most likely items being chosen is also allowed to be arbitararily small. An algorithm that returns the marked item from a list of $N$ with probability $\frac{1}{N}+2^{-N}$ would be allowed so long as all other items were less likely.

Is there any existing work on algorithms that achieve the corresponding outcome as Grover's (or similar specific quantum algorithms), but in more direct/natural terms?


texts: If $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$

texts:
How to prove if $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$ ?

it means every recursive set is mapping reducible to set $B\neq \aleph$. I really have no idea to prove this.

UPDATE

$A,B$ are sets, $A \leq_m B$ if there is a computable function $f$ such that

$A = \{ x \in N | f(x) \in B\}$

Since we have $A \leq_m B$ and $A$ is recursive, it means checking membership (characteristic function) in $A$ is recursive, so it means checking $f(x) \in B$ is recursive, right?

I guess it means $B$ must be recursive too and it means every recursive set is mapping reducible in to every other recursive set. Am I right?


texts: What is the runtime of Quantum Fourier Sampling

texts:
I have seen estimates for the runtime of Shor's Algorithm,, which relies on Quantum Fourier Transformations. What is the runtime of those transformations themselves?

Either big-O or more accurate estimates are welcome.


texts: Multiple Cores vs Single Core Power Efficiency Equations

texts:
I was searching for OpenMP tutorials and I came up a video that showed some simple equations that promotes multiple core hierarchies against single core ones.
The equations used are

  Capacitance = Ability to store energy

  C=q/V ⇒ q=CV

  Work = Moving charge across voltage

  W=Vq ⇒ W=CV^2

  Power = Work over a period of time

  P=Wf ⇒ P=CV^2f

It then proceeds to calculate power requirement of a single core processor as

  Ps = CsVs^2fs

where Xs stands for X used on single core system.

It then goes on to calculate it for a dual core system responsible for doing the same work. But it uses following parameters (Not exactly 2 or 0.5 multipliers but they just make the problem more easier to understand):

  Cd = 2Cs
  Vd = 0.5Vs
  fd = 0.5fs

Power is calculated as

  Pd = 0.25Ps

I don't get why voltage and capacitance are altered.

The video is over here youtu.be/cMWGeJyrc9w?t=3m45s, if time link doesn't work for you. It starts about 3:45.


texts:
Suppose one wants to uniformly sample a string $w$ of a given length over a finite alphabet, such $w$ satisfies a set of structural constraints (such as - "the third character has to be equal to the first character and the last character has to be equal to the second one").
The obvious method is to uniformly sample $w$, check if the constraints hold and return it if so. However, I am dealing with the case where there are many constraints, and the probability of random string to satisfy them is extremely low. Is there a way to sample uniformly from the set of all strings satisfying the set of constraints?


texts: Somewhat-hardware-conscious algorithm for top k-of-n with $k=\Omega(\sqrt{n})$

texts:
The "top k of n" problem: You have n (not necessarily distinct) elements in an array, and you need to return another array containing the k elements with the highest value.

So, I'm going to need a top-k-of-n implementation for something I'm working on. Never mind exactly which programming language and hardware I'm going to use - but do mind that it's going to actually run on actual hardware. Thus there is multi-level caching so dereferencing pointers to arbitrary places should be minimized; there's the balance between computation and memory bandwidth to consider; there's multithreads/SIMDizing/whatever so I would like something parallelizable without too much communication... that's what I meant by somewhat-hardware-conscious.

Anyway, for a really small k I would probably just use a priority queue which fits in cache (or even linear search through several registers). But - what if your k is large? Large that the top k elements won't just be hiding at the top end of an estimated distribution? In this case I was thinking of estimating k using sampling, then (sort of) partitioning on that guess k; seeing how badly I missed; and iterating that, either partitioning my more-than-k or my more-than-n-minus-k. On one hand the length decreases quickly, and on the other hand I get closer to the really-small-k case, until I can settle for a priority queue (say for each core even) for the last bit.

So, my questions are:

Can someone describe known algorithms for this variant of the problem,  meeting my "vague hardware consciousness" constraint?
Does the algorithm sketch I described sound like something you know?
If not, does it sound like a good idea or can you describe shortcomings of this kind of an approach?

Notes:

You may assume the data are non-negative integers if it helps in any way (I don't think it should), or make any any other reasonable assumptions.
This problem is different that the partial sorting problem in that the output does not need to be sorted. Of course, for small k = $o(\sqrt{n})$ there isn't that much of a difference.
The data is in memory, i.e. this is not a streaming algorithm and you can read data multiple times. You can't alter the input; you can make a full copy but hopefully that should be overkill.


texts: consider the policy iteration algorithm for a finite state MDP. Suppose the initial policy is a stochastic policy. Now, can the optimal policy be deterministic after improvements ? Or, can we say that always the optimal policy will be a stochastic one ? Confused about this. Any ideas will be helpful. The reason I am asking this question is that in the absence of model i.e. when we need to need to use Monte Carlo methods then each of the improved policies must be a stochastic one to make sure action-value function estimates are near equal to the mean.


texts: Practical computation time, counting spanning trees and selecting spanning trees uniformly at random

texts:
I am doing a project in applied math, which involves counting spanning trees and selecting spanning trees uniformly at random for near-maximal planar graphs with ~430 vertices, as part of a larger Markov process. Though I am aware of theoretical methods for both of these tasks, I was unable to find even rough estimates to complexity coefficients for any process.

My question is, for graphs with 400 vertices, could anyone hazard a guess as to how much faster it is to create a random spanning trees than to count possible spanning trees?

I believe Wilson's algorithm is fastest to create trees uniformly at random. For methods to count spanning trees, there are a few methods, detailed here. (I should note, for the first method, involving matrix factoring, I'm only worried about the time it takes to factor everything, and not the numbering which comes beforehand, because the numbering can be reused. The reason for this is these processes are occurring on subgraphs of a larger 2800 vertex graph, so we can number once and be done with that.)


texts: Big Theta Proof: May I chose any constant?

texts:
I have the following assignment:

  Prove that $\sum^n_{i=1} i2^i \in \Theta(n2^n)$

My current approach thus far is the following:

Since we need to prove $k_1 \cdot n2^n \le \sum^n_{i=1} i2^i \le k_2 n2^n$ I chose $k_1 = 1$ and $k_2 = 2$. This holds true to my condition. However I'm unsure whether I can just freely decide on using those two.

Therefore my question is:

  Am I allowed to chose any constant factor I want in a $\Theta$ proof (given that the condition holds true)?


texts: monotone min-3-sat polynomial algorithm?

texts:
I know that 3SAT is npc but i wonder why my little algorithm won't solve this problem:

given positive 3SAT - meaning: each of the m clauses is a disjunction of 3 literals over the variables $x_1,\dots,x_n$ ($n$ variables) and each literal is a positive appearance of a variable (no $~x_i$).

for example: $(x_1 \lor x_3 \lor x_7) \land (x_5 \lor x_4 \lor x_2)$

What is wrong with this "greedy" algorithm?:

run through all left clauses and find the variable that appears in most of them (can be implemented by counters array..).
take this variable, give him truth assignment, remove all clauses which he appeared in, zero the counters array and do again the previous step.
stop when no clauses left.
it looks like this algo runs in $O(m^2n)$ time.

why isn't it not an optimal algorithm?

UPDATE:
Sorry for the vague question, The problem is probably called MIN 3SAT, which every literal is positive but you must find minimum integer k such that there exists a truthful assignment of the variables which sets k variables to TRUE.

UPDATE 2:
Can someone give me an example to why the greedy algorithm won't give the optimal solution?
I read what rus9348 wrote but I still can't figure why the greedy approch is not good..


texts: Why is the set of NFA that accept all words in co-NPSPACE?

texts:
In Sipser's book there is a section describing how to decide

$\qquad\displaystyle \mathrm{ALL}_\mathrm{NFA} = \{ \langle N \rangle \mid N \text{ is an NFA}, L(N) = \Sigma^*\}$

in polynomial space. To do so, it shows $\overline{\mathrm{ALL}_\mathrm{NFA} }$ is in NPSPACE.

I don't understand this part: If $M$, the NTM deciding the language, rejects any strings, it must reject one of length at most $ 2^q $ where $q$ is the number of states in $M$. For any longer string that is rejected, some states would repeat. But why? Is there any alternative explanation that helps in understanding this part?


texts: Theory of computation introductory curriculum

texts:
I want to study theory of computation on my own, so I am looking for books.

What set of books would you recommend for the equivalent of a one-semester course that introduces theory of computation?

Please post answers that describe a complete curriculum, explaining which chapters of each book are relevant at which stage of the course or self-study.


texts:
I need to verify the type for the lambda expression: $\lambda f.\lambda x.f (f x)$

My method gives me: $(a\rightarrow c)\rightarrow b\rightarrow c$

Im trying to define it in Haskell (on Hugs) like this:

h= \f x -> f (f x)

When i call the :type comamnd it gives me:

(a -> a) -> a -> a

Is mi function correctly defined in Haskell?, or my method gives me a wrong result?


texts: Prove that the Kolmogorov complexity function cannot be approached from below

texts:
How would one go about proving that Kolmogorov function $K(x)$ cannot be approached from below by any computable function?

After some research it seems I must show the function $K(x)$ is not lower semi-computable.

Instead, I can do this by showing $-K(x)$ is not upper semi-computable

Intuitively it seems that $K(x)$, the length of the smallest program computing $x$, can always get smaller, but could be approached using a convergent function... but this is clearly not the case, so I'm obviously a bit lost.

I would be very grateful if someone could explain how I might approach such a proof. I'm more interested in the approach, I might encounter similar questions in an upcoming exam.

Thanks a lot.


texts: Problem in computational complexity (superior class)

texts:
Say that a class $C_1$ is superior to a class $C_2$ if there is a machine $M_1$ in class $C_1$ such that for every machine $M_2$ in class $C_2$ and every large enough $n$, there is an input of size between $n$ and $n^2$ on which $M_1$ and $M_2$ answer differently.

Is DTIME($n^{1.1}$) superior to DTIME($n$)?

Is NTIME($n^{1.1}$) superior to NTIME($n$)?

This is an exercise from book Computational Complexity: A Modern Approach. But I have no idea to handle it. Does it have relationship with theorem that DTIME$(n)$ $\subsetneqq$ DTIME($n^{1.5}$)?


texts: Longest palindrome size with suffix trees

texts:
Suppose that I want to get the size of the biggest palindrome in a string s, and I am restricted to do it using suffix trees what is the best complexity I will get and why? I checked other answers but I find them highly confused.
EDIT:
I tried create a suffix tree with the string and the inverse of the string and use a BFS to find the biggest levels that are common to the two strings and if the suffix starts at the same point the suffix string will have the same size to the longest string of.

I think this solution is based on others found in the Internet I said that is $O(n)$ as creating suffix trees and doing a BFS in a tree are bouth $O(n)$, but I don't believe in the correctness of this.

Thanks for your time.


texts: Estimating (c-1) from approximation of c

texts: If we have a FPRAS for approximating the quantity c, can we get another FPRAS for estimating (c-1) using the estimation of c?


texts:
How we can prove that:
$$
\sum_{k=1}^{c \log n-1}\:k\cdot \left(\frac{1}{2}\right)^{\frac{k}{3}}\in O\left(1\right) \quad \mbox{?}
$$


texts: Is this proof for showing that $EQ_{CFG}$ is co-Turing-recognizable incorrect?

texts:
I have been searching for proofs that show that $EQ_{CFG}$ is co-Turing-recognizable. When searching for proofs I can only find proofs on the following form:

  Construct a TM $M$ which recognizes the complement of $EQ_{CFG}$, M =
  "On input ⟨G,H⟩":

  For each string $x \in \Sigma^*$ in lexicographic order:
  Test whether x ∈ L(G) and whether x ∈ L(H), using the algorithm for $A_{CFG}$ .
  If one of the tests accepts and the other rejects, accept; otherwise, continue.”

(From: http://cobweb.cs.uga.edu/~potter/theory/6_reducibility.pdf)

Isn't this proof incorrect?

Say that my language is $\Sigma=\{a,b\}$ and that I have $L(G_1) = \{b\}$ and $L(G_2) = {bb}$. $M$ should accept $\langle G_1, G_2\rangle$ since $L(G_1) \neq L(G_2)$. But if we run $M$ with $\langle G_1, G_2\rangle$ the TM will first generate $x=a$, which isn't in either languages so the machine will go back to step 1 and then generate $x=aa$, then $x=aaa$ and so on forever. The machine will never get to $x=b$. Hence, the machine will loop on input that it should accept. Therefore $M$ isn't a Turing recognizer.

Would the proof be correct if step 1 instead would state "For each string $x \in \Sigma^*$, ordered by increasing size and then lexicographic order:"? This should generate strings in the following order: $x=a$, $x=b$, $x=aa$, $x=ab$, $x=ba$, $x=bb$, $x=aaa$, and so on. So in the case above $M$ would reject when $x=b$.


texts:
I have tried to solve the following exercise but I got stuck while trying to find all the critical pairs.

I have the following questions:

How do I know which critical pair produced a new rule?
How do I know I found all the critical pairs?

  Let $\Sigma= \left \{ \circ, i, e \right \}$ where $\circ$ is binary, $i$ is unary, and $e$ is a constant.
  $$
E=\left \{  \begin{gather}
( x \circ y ) \circ z \approx x \circ\left ( y \circ z \right ) \\
x \circ e \approx x \\
x \circ i(x) \approx e
\end{gather} \right\}
$$

My work so far:

  $x\circ e >_{\textsf{lpo}} x$   (LPO 1)   $x$ is a variable
  $x\circ i(x)>_{\textsf{lpo}} e$   (LPO 2b)   there are no terms in the right hand side
  $(x\circ y)\circ z\approx x\circ(y\circ z)$
  $s=\circ(\underset{\large s_1}{\circ(x,y)},\underset{\large s_2}{\strut z})\qquad t=\circ (\underset{\large t_1}{x\strut}, \underset{\large t_2}{\circ(y,z)})$     (LPO 2c)

  check that $s>t_j$, $j=\overline{1,m}$
  $s>_{\textsf{lpo}}t_1$     (LPO 1)
  to prove that $s>_{\textsf{lpo}}t_2$ (LPO 2c) we prove that
  $$s>_{\textsf{lpo}} y \;\;\text{(LPO 1)};\qquad s>_{\textsf{lpo}}z \;\;\text{(LPO 1)};\qquad \circ(x,y)>y\;\;\text{(LPO 1)}$$
  find $i$ such that $s_i>_{\textsf{lpo}}t_i$     $i=1$
  $$\circ(x,y)>_{\textsf{lpo}}x\;\;\text{(LPO 1)}$$

  $(x\circ y)\circ z>_{\textsf{lpo}} x\circ (y\circ z)$
  a. $(x\circ y)\circ z\;\rightarrow\; x\circ (y\circ z)$
  $x_1\circ e\;\rightarrow\; x_1$
  $x\circ y \mathrel{\,=?\,} x_1\circ e$
  $\theta\{x \;\leftarrow \;x_1;\; y\;\leftarrow \;e\}$
  $$\require{AMScd}
\require{cancel}
\begin{CD}
(x_1\circ e)\circ z @>>> \cancel{x_1}\circ z\\
@VVV @VVV\\
\cancel{x_1}\circ(e\circ z) @>>> e\circ z\approx z
\end{CD}\qquad\text{left identity?}$$
  b. $(x\circ y)\circ z\;\rightarrow\; x\circ (y\circ z)$
  $e\circ x_1\;\rightarrow\; x_1$
  $x\circ y \mathrel{\,=?\,} e\circ x_1$
  $\theta\{x \;\leftarrow \;e;\; y\;\leftarrow \;x_1\}$
  $$\begin{CD}
(e\circ x_1)\circ z @>>> x_1\circ z\\
@VVV @VVV\\
e\circ(x_1\circ z) @>>> ?
\end{CD}$$
  c. $(x\circ y)\circ z\;\rightarrow\; x\circ (y\circ z)$
  $x_1\circ i(x_1)\;\rightarrow\; e$
  $x\circ y \mathrel{\,=?\,} x_1\circ i(x_1)$
  $\theta\{x \;\leftarrow \;x_1;\; y\;\leftarrow \;i(x_1)\}$
  $$\begin{CD}
(x_1\circ i(x_1))\circ z @>>> e\circ z\\
@VVV @VVV\\
x_1\circ(i(x_1)\circ z) @>>> ?
\end{CD}$$

As a support document I have "Term Rewriting and All That" by Franz Baader and Tobias Nipkow.

(original image here)

EDIT1

After searching for the critical pairs I have the following set of rules(assuming 2.a is corect):

$$
E=\left \{  \begin{gather}
( x \circ y ) \circ z \approx x \circ\left ( y \circ z \right ) \\
x \circ e \approx x \\
x \circ i(x) \approx e \\
x \circ (i(x) \circ y) \approx y \\
x \circ ( y \circ i(x \circ y) ) \approx e \\
e \circ x \approx x  \\
e \circ (x \circ y) \approx x \circ y
\end{gather} \right\}
$$


texts:
Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult.

My Regular Expression experience is profoundly in JavaScript and I'm concerned that it poisoned my thinking of Regular Expressions. For the life of me I can't figure this out. Answer A and Answer B I can rationalize, though my logic might be inherently flawed somehow. Being unable to understand how Answer C works brings me to the conclusion that I am profoundly missing something.

The Problem:

Consider the string abbbaacc Which of the following lexical specifications produces the tokenization ab/bb/a/acc ?

Answer A
a(b + c*)
b+

Answer B
ab
b+
ac*

Answer C
c*
b+
ab
ac*

The two ways that I have tried to resolve Answer C

removing tokens(which I assumed is the correct way.)

abbbaacc

c* passes and returns token **cc**  //abbbaa
b+ passes and returns token **bbb** //aaa
ab passes and returns no token //aaa
ac* passes and returns no token //aaa
ending tokens:
[cc, bbb]

Keeping String Whole:

abbbaacc

c* passes and returns **cc**
b+ passes and returns **bbb**
ab passes and returns **ab**
ac* passes and returns **acc**
ending tokens:
[cc, bbb, ab, acc]

I've tried other random ways as well but nothing turns out. I really am frustrated with this problem and I've been working on it for quite some time. I've reviewed the coursework that I have and I'm just at a loss. I am convinced that I must be conflating the more common Regular Expressions with this but I don't see where I'm doing so in any way that would make this answer correct. If anyone could provide any assistance I would greatly appreciate it!


texts: Is there a formal definition for iteration?

texts: I wanted know if there is a formal definition of iteration. In the sense that, this definition will say that after the 4th iteration is termination or the 5th iteration and not the 2nd iteration. Basically a rigorous definition of iteration.


texts: Does the OS create its own bootstrapped stack frame when running a program?

texts:
I've been doing nand2tetris exercises and I'm quite interested in how compilation actually works. In nand2tetris when creating the VM language I had to create a "bootstrap" which called the main method of the program.

In other languages such as C, Java or even interpreted languages like PHP, does the OS/interpreter/VM automatically create its own first frame on the stack, and then invokes the main method of the program as a new second stack frame?

I'm trying to think about how initial arguments are passed to a program, and how programs are able to return values. Does each OS have a standard way of creating this initial stack frame which all languages adhere to? When I run a program from command prompt and pass it arguments, what is actually creating that initial stack frame that pushes these arguments onto the stack and that invokes my main method?


texts: Which is the best approach to solve Turing machines exercises?

texts:
I've this exercise of which I'm not very sure about my solution.

Exercise:

  Define the transition table about a Turing Machine that accepts words
  on the {a, b} alphabet where each a is followed by only two b.

My proposed solution is:

(f stands for transition function)

f(q0, a) = (a, q1, R)
f(q0, b) = HALT
f(q1, a) = HALT
f(q1, b) = (b, q2, R)
f(q2, a) = HALT
f(q2, b) = ACCEPT

I came up with this after thinking in the same way as finite state machines, even if I know are different with respect to Turing Machines (no tape, no reading/writing symbols and no right/left moves).

So, my question is, which is the best way of reasoning when I have to solve these kinds of problems?

Thank for your attention!


texts:
Suppose a processor uses the big endian representation and x is a 32-bit integer stored in memory starting at the memory address 1000. The memory is byte-addressable, each location holding a byte. Specify in binary what would be in memory location 1000, 1001, 1002 and 1003 if the program has the statement:

int x = 1023;

I know that the big-endian representation has the MSB at the lowest memory location, but how to use that in this question?


texts: CSES Range Query Question: Index Compression and Updates

texts:
I'm trying to solve this problem: https://cses.fi/problemset/task/1144/
Given an array of up to 200000 elements, my task is to process up to 200000 queries, which either ask me to update a single value within the array or ask me to find the number of elements that lie in a given range.
My current idea is to first use index compression on the given array, then keep another array that contains the number of occurrences of each number. Then, processing and updating queries could be done using a sum segment tree.
However, I ran into a problem while trying to implement this approach. I realized that updating a single array value could force me to shift the compressed array.
For example, given an array [1, 5, 3, 3, 2], I would define a compression function C such that
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[5] = 3;

Then, the occurrence array would be [1, 1, 2, 1], and processing sum queries would be efficient. However, if I were instructed to update a value, say, change the third element to 4, then that throws everything out of balance. The compression function would have to change to
C[1] = 0;
C[2] = 1;
C[3] = 2;
C[4] = 3;
C[5] = 4;

which would force me to reconstruct my occurrence array, resulting in O(N) update time.
Since N can be up to 200000, my approach will not work efficiently enough to solve the problem, although I think I have the right idea with index compression. Can somebody please point me in the right direction?


texts: Proof of Program Correctness - Loop Invariants

texts:
I've been reading a book on using loop invariants and induction to prove program correctness. Then I came across the following program which got me thinking...

Specification for Cube_Root(n)

Pre-Condition: $n$ is a natural number.
Post-Condition: Cube_Root returns a natural number $i$ that is the cube root of $n$ or it returns $-1$ if no such root exists

Cube_Root(n)
  i = 0
  while i < n
    if i * i * i = n
      return(i)
    else
      i = i + 1

  return(-1)

In the book, the proof proceeds by finding a loop invariant.
So for example let us define the following as our loop invariant:

Loop Invariant $P(i)$: $i$ is either the natural number cube root of $n$ or $i \geq n$.
The proof is then supposed to proceed by induction on $i$.
So we need to prove that $P(0)$ is true, assume that $P(i)$ is true for some $i$ and then establish that if $P(i)$ is true then $P(i+1)$ is true.

$P(0)$ is trivial to prove true:
    if $n = 0$ then $i$ is a natural number and the the cube root of $n$
    otherwise $n > 0$ (since $n$ is a natural number) and hence $i < n$.

However, the problem arises when you try to infer $P(i+1)$ from $P(i)$. it doesn't look like you can because if $i$ is not the cube root of $n$, it doesn't tell you anything about whether $i+1$ is or is not the cube root of $n$.

So my question(s) are:

Has it been proven that for any program there exists a loop invariant on which you can
use induction to prove the program is correct?
The loop invariant chosen for Cube_Root is obviously true after the loop terminates
which proves that the post-condition of the program is satisfied. Hence, that proves
partial correctness of the program. However, we did not need to use induction to prove
that. Is that an acceptable proof? If not, how do we use induction to prove Cube_Root
correct?


texts: I know that proving context free grammars equivalent is undecidable. I also know that proving if a context free grammar recognizes a regular language is undecidable. Here is my question: is proving that two regular grammars recognize the same language decidable?


texts: Prove, a^2+b^2=c^2,there exists only 1 case such that a,b,c are consecutive non negative integers(3,4,5)

texts:
I want to prove, $a^2+b^2=c^2$,there exists only 1 case such that a,b,c are consecutive non-negative integers(3,4,5).

I have no clue to prove this lemma. Please help me to prove this lemma.


texts:
Is there any scientific work about deep copying? So far I have only found source codes (Java, Python, ...). However, there are various approaches and nobody seems to evaluate them.

Reflection-based (Python)
Auto-generated shallow-copy-based (Java)
Compiler-generated polymorphic deep copy (anybody?)

The last one seems to be the most efficient one, but I do not know if it is implemented anywhere.


texts: Is there any programming system that enables reversible computations?

texts:
Better explained with examples, I need a programming system with the following characteristics:

f = λ a b c -> a + b + c
g = apply f 1 2 3 = 6
h = unapply g _ 2 _ = λ b -> 4 + b

Or, to explain with words, f is a function, g is that function applied to 3 arguments, and h is g "unapplied" to one argument. That is, I need a programming system where you can define functions and apply them to arguments, like the Lambda Calculus. But I also need this system to have an unapply operator, with which you can recover a partially applied function from the value of its argument.


texts: Why is it best to use a prime number as a mod in a hashing function?

texts:
If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function

$$ H = k \bmod \ 11$$

Now all the values will be placed one after another in 9 rows. For example, in the first bucket there will be $0, 11, 22 \dots$. In the second, there will be $1, 12, 23 \dots$ etc.

Let's say I decided to be a bad boy and use a non-prime as my hashing function - take 12.
Using the Hashing function

$$ H = k \bmod \ 12$$

would result in a hash table with values $0, 12, 24 \dots $ in the first bucket, $1, 13, 25 \dots$ etc. in the second and so on.

Essentially they are the same thing. I didn't reduce collisions and I didn't spread things out any better by using the prime number hash code and I can't see how it is ever beneficial.


texts: Category theory structures to describe topics and queues

texts:
What are the category theory structures describing queues and topics? By queues and topics I mean the ones described in systems like Apache Kafka, AcriveMQ or Java Messaging Service.

Where I can find material about that?


texts: Why is low-dimensional discrete representation of input space useful?

texts:
Self-organizing maps undergo unsupervised training to produce a low-dimensional, discrete representation of the input space. Why is this useful?

I think the results of the self-organizing map would have to be combined with some other machine learning algorithm or neural net in order to solve problems. Is this the case? If so, what algorithms or neural networks would benefit from being complemented with a self-organizing map? If not, what problems does the output of a self-organizing map solve?


texts: Showing different derivation trees for same string X

texts:
So I understand how to do this with there being multiple symbols in each possible production, but when it is singular, it seems to get more complicated, or I am overthinking it? Would the left-most derivations be the exact same as the two different derivation trees for some string x in this case? Both cases lead me to S -> T -> ba and S -> V -> ba

I'm also not too sure on the second question, but I think that would be more straight forward with a) answered.

I was hoping someone could help me to understand this a bit better. Here is the grammar, thanks!

For the following grammar
S → T│V
T → bTa│ba
V → baV│Λ

a. Show that it is ambiguous (by providing two different derivation trees for some string x, and two different left-most derivations for the same x)

b. Find an equivalent unambiguous grammar.


texts: Problem with storing an existing triangulation in a DCEL

texts:
I am trying to store an existing 2D triangulation (of which I have all of the vertices and edges) in a DCEL data structure.

Using the algorithm described in this answer, I was able to store a part of the triangulation, but not the "half-edge" representative for each triangle.

The algorithm is reported below

  Algorithm

  For each endpoint, create a vertex.
  For each input segment, create two half-edges, and assign their tail vertices and twins.
  For each endpoint, sort the half-edges whose tail vertex is that endpoint in clockwise order.
  For every pair of half-edges e1, e2 in clockwise order, assign e1->twin->next = e2 and e2->prev = e1->twin.
  Pick one of the half-edges and assign it as the representative for the endpoint. (Degenerate case: if there's only one half-edge e in the sorted list, set e->twin->next = e and e->prev = e->twin). The next pointers are a
  permutation on half-edges.
  For every cycle, allocate and assign a face structure.

Instruction 5 seems to be easier said than done. How can I ensure that every triangle will have a representative, and that a representative will be assigned only once for each triangle?

Furthermore, in point 6, which cycle is it referring to?

(So far, my implementation is similar to the one provided in the answer.)


texts: What is the difference between luma and luminance?

texts:
I understand the following (correct me if I'm wrong):

Statements

Luma as the weighted sum of RGB gamma corrected components, but luminance is the weighted sum of RGB linear components.
The gamma correction has two forms: gamma compression and expansion. When we want to encode luminance into imaging systems, we turn it into luma using gamma compression (so $\gamma <1$ when we raise the RGB components to a higher power).

So in short, Luma is the stuff in the "computer world" and Luminance is exists in the "physical world", is this correct? Because Luminance is roughly equivalent to the $Y$ value in CIE-XYZ colour space.

Questions

When I have my images, are the pixel values already in linear RGB components or are they gamma corrected RGB components? That is, how is luma represented internally in imaging systems?
When we want to emit the colour in the screen, we perform gamma expansion, is this right? If so, will the light that comes out of the screen be considered as luminance?
When light waves travel, what physical property does luminance represent? Is it the amplitude of light waves?
In the CIE-XYZ colour space, is Y the only one that has physical meaning? Meaning to say X and Z are rather arbitrary factors dependent on the human visual system and nothing to do with physics itself,is this correct?


texts: Vertex cover in bipartite graph from Hopcroft-Karp Algorithm

texts:
Vertex cover in bipartite graph is polynomial algorithm: by König's theorem the number of edges in a maximum matching is the number of vertices in a minimum vertex cover.  I've implementated the Hopcroft Karp algorithm to find a maximum matching in the bipartite graph. I would like to get the minimum vertex cover from this.

Is there any way of adjusting Hopcroft–Karp so that it produces the minimum vertex cover, other than the obvious way of just computing the matching and then passing that to an algorithm that computes the corresponding cover?


texts: CFG grammar with fixed number of "distinguished" terminals

texts:
I would like to know if there is a name for CFG grammars (or grammars in general) in which there is a fixed number of "distingushed" terminals  or in which there is a terminal that appears a fixed number of times (in the generated strings).

For example:

$L(G) = \{ 0^a 1 0^b 1 0^c \mid a = b \text{ or } a = c \}$

In this case the symbol $1$ appears exactly two times in every string and "acts as a separator".

Clearly, in this family of languages, the distinguished terminal(s) forces the pumpable substrings $v$, $x$ (in $uv^nwx^ny)$) to belong to at most two distinct "segments" and forbid each one of them to cover more than one segment.


texts: Theoretical foundations of Divide and Conquer

texts:
When it comes to the design of algorithms, one often employs the following techniques:

Dynamic Programming
The Greedy-Strategy
Divide-and-Conquer

While for the first two methods, there are well-known theoretical foundations, namely the Bellman Optimality Principle and matroid (resp. greedoid) theory, I could not find such a general framework for algorithms based on D&C.

Firstly, I am aware of something that we (or rather, the prof) introduced  in a functional programming class,  called an "algorithmic skeleton", that arose in the context of combinators. As an example hereof, we gave such a skeleton for D&C algorithms as follows:

Definition: Let $A,S$ be non-empty sets. We call the elements of $S$ solutions, and the elements of $P:=\mathfrak{P}(A)$ (that is, the subsets of $A$) are referred to as problems.
Then, a D&C-skeleton is a 4-tuple $(P_\beta, \beta, \mathcal{D}, \mathcal{C})$, where:

$P_\beta$ is a predicate over the set of problems and we say that a problem $p$ is basic iff $P_\beta(p)$ holds.
$\beta$ is a mapping $P_\beta \rightarrow S$ that assigns a solution to each basic problem.
$\mathcal{D}$ is a mapping  $P \rightarrow \mathfrak{P}(P)$ that divides each problem into a set of subproblems.
$\mathcal{C}$ is a mapping $P\times \mathfrak{P}(S) \rightarrow S$ that joins the solutions (depending on kind of a "pivot problem") of the subproblems to produce a solution.

Then, for a given skeleton $s=(P_\beta, \beta, \mathcal{D}, \mathcal{C})$ and a problem $p$, the following generic function $f_s: P\rightarrow S$ computes a solution (in the formal sense) for $p$:

$f_s(p)= \left\{
  \begin{array}{l l}
    \beta(p) & \quad \text{if $p$ is basic}\\
    \mathcal{C}(p,f(\mathcal{D}(p))) & \quad \text{otherwise}
  \end{array} \right.$

where in the second line we use the notation $f(X) := \{f(x)  : x\in X\}$ for subsets $X$ of the codomain of a mapping $f$.

However, we did not further examine the underlying, "structural" properties of problems that can be formulated this way (as I said, it was a functional programming class and this was only a small example). Unfortunately, I could not find further reference on this very approach. Hence I don't think the above definitions are quite standard. If someone recognizes what I have stated above, I would be glad about related articles.

Secondly, for the greedy strategy we have the famous result that a problem is correctly solved by the general greedy algorithm if and only if its solutions constitute a weighted matroid. Are there similar results for D&C-algorithms (not necessarily based on the method outlined above)?


texts: What does ∇log mean in the Robbins-Montro algorithm?

texts:
The Robbins/Monro Algorithm is a type of stochastic optimization algorithm of the following form: (as mentioned in wikipedia)

$$x_{n+1} - x_n = a_n(\alpha - N(x_n))$$

where $M(x) = \alpha$ is a nondecreasing function whose root is at $x=\theta$, $N$ is a random variable where $E(N) = M(x)$. (E is the expectation). Furthermore, $a_n$ is a sequence of positive terms.

A paper entitled 'Bayesian Learning via Stochastic Gradient Langevin Dynamics' written by Max Welling and Yee Whye Teh wrote the same Robbins/Monro Algorithm but in a different shape and form I was not able to recognize:

$$\Delta\theta_t = \dfrac{\epsilon_t}{2}\left ( \nabla \log p(\theta_t) + \dfrac{N}{n} \sum_{i=1}^n \nabla\log p(x_{ti}|\theta_t) \right)$$

The left hand might be similar to a change in $x$ as shown above. $\epsilon$ is a sequence, which corresponds to the term $a_n$ above. What I do not recognize are the $\nabla \log$ terms. $p$ are probabilities, so maybe they are trying to apply this to bayesian statistics as is implied in the title. I am so lost here. Is someone familiar with this?


texts: Identifying problem in MIPS pipeline datapath

texts: I'm having trouble identifying a problem in this pipelined datapath. After executing an add instruction, there are 5 subsequent R-type instructions executed. However, we are assuming no data hazard, so no data dependencies that are relevant. That confuses me because that takes out the main issue with executing multiple R-type instructions. Could it be a structural hazard in which there's not enough resources to execute multiple instructions at the same time, thereby needing more hardware?


texts: How to best maintain a sorted list from a stream of integers?

texts: If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the right. This would amount to $O(N + \log N)$ time. Is there a better data structure that can help me achieve the same in better time? I know we can use a Balanced Binary Search Tree with $O(\log N)$ insertions but I would like to have efficient access on the list.


texts: Comparing Selection, Insertion, and Bubble Sorts for database application

texts:
Explain and compare selection, insertion and bubble sorts. Assume
that your application (say a data base application) deals with
large records where comparisons are performed by means of integer keys.
Assume also that your application requires a stable sorting method,
i.e. a method that does not change the relative ordering of elements
that are equal. Which of these sorting methods would you choose,
and why? (Hint: consider sorting based on the following integer keys
19, 14(1), 7, 12, 14(2), 10).

This is a question I'm studying in class, not sure which is the right one and why.


texts: If statement not capturing the conditional I'm seeking

texts:
I'm working on a hw assignment, and my if statement isn't working the way it's intended.

This is an ATM machine project. I've already gotten the program to read the csv file and stored it into a dictionary with the pin number as the key.

What I can't get it to do is find the pin number in my getUser() function. Below is the code and under that is the IDLE result. Please help!

d = {}
def startUp(fname):
    try:
        acct_file = open(fname,'r')
        for line in acct_file:
            (key,first,last,balance) = line.split(',')
            d[int(key)] = [last,first,float(balance)]
        print(d)
        getUser()
    except:
        print('Cannot get to the file')

def getUser():
    user_pin = int(input('What is your pin number? '))
    if user_pin in d.keys():
        return (user_pin,first,True)
    else:
        print('Incorrect Pin')
        return (None,None,False)

IDLE result:
What is your pin number? 9967
this returns nothing


texts: Why if $G$ has two spanning trees $A$ and $A'$, then every edge of $A'\cup \{e_i\}\in A'$

texts:
Theorem:

  Let be $G$ a weighted graph in which every edge has a different weight.

  Suppose that $G$ has two spanning trees $A$ and $A'$.
  Let be $i$ the first index such that $e_i\ne e'_i$ and $i\ge 3$.

  Suppose that $w(e_i)<w(e'_i)$ and consider that $A' \cup \{e_i\}$ has a unique cycle.

  For each edge of this cycle then $w(e')<w(e_i)$ (else we would be able to create a tree $(A' \cup \{e_i\})\setminus\{e'\}$ of lower weight than $A'$, which contradicts the fact that $A'$ has minimal weight.

  Therefore, every edge of this cycle must be in $A'$. Which contradicts the fact that A is a tree

I don't understand the conclusion in italics. This a demonstration from my teacher but it seems that it pop out without any explanation... Can you help me?


texts: Mathematical resource material accompanying TAPL

texts:
I'm currently reading Types and Programming Languages by Benjamin C. Pierce and just arrived at chapter 21 Metatheory of Recursive Types.

Prior to this chapter I found the book challenging but comprehensible, but I'm lost on this chapter. Almost none of the definition make intuitively sense to me. Are there any more accessible resources regarding the principle of (co-)induction, tree types and least and greatest fixed points as defined in chapter 21?


texts: Circuit of constant depth that takes three binary numbers and outputs two binaries?

texts:
How can I construct -- or better to say what type of circuit can be like this -- a circuit that takes 3 binary numbers (a, b, c) and then calculates two binary numbers (d, e) in a way that a + b + c = d + e The circuit should be of constant depth and furthermore, a, b, c, d, and e are as follows;

a=a_n−1…a_0
b=b_n−1…b_0
c=c_n−1…c_0

d=d_n…d_0
e=e_n…e_0


texts: About shortest cycles in undirected graphs

texts:
In an undirected (and unweighted) graph, to find the shortest cycle containing a specific vertex $s$, it is usually said to run a BFS from $s$ and the first time to find a re-visit, then that is the wanted smallest cycle length.

This does not seem to be true, quoting from https://www.cs.princeton.edu/courses/archive/spr08/cos226/exams/fin-f05-sol.pdf page 3:

  Note that if you run BFS from $s$ and stop as soon as you revisit a
  vertex (using a previously ununused edge), you may not get the
  shortest path containing $s$.

Examples where this technique seems to be suggested: An efficient algorithm to find a shortest cycle including a specific vertex

Another technique, finding the shortest cycle in the whole graph, by running BFS from each vertex, also seems to detect only the shortestLength + 1 in a special case, as mentioned in this paper: https://link.springer.com/chapter/10.1007/978-3-540-78773-0_63 in the "Unweighted case". On the contrary, here (http://theory.stanford.edu/~virgi/cs267/lecture3.pdf) it is mentioned (first and second paragraphs) that running BFS from every vertex gives the shortest length (girth) in all cases. This is also mentioned in an archive (http://web.archive.org/web/20140513212046/https://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf).

Which of all algorithms/methods is true for:

Finding the shortest-length cycle in an undirected graph?
Finding the shortest-length cycle that passes through a known vertex $s$ in an undirected graph?
Where is the pitfall in each of my above compare-and-contrasts? (I cannot believe that some of the above quoted might even be untrue...)

Note: A randomized sub-cubic algorithm seems to exist, in the paper "A shortest cycle for each vertex of a graph" by Raphael Yuster: http://research.haifa.ac.il/~raphy/papers/all-cycles.pdf


texts: The Chomsky–Schützenberger representation theorem

texts: I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give me hints how to construct proper language?


texts:
Show that if the MAX CUT decision problem can be solved in polynomial time so can the MAX CUT optimization problem by writing an algorithm that solves the optimization problem using an algorithm for the decision problem as a subroutine

MAX CUT

INSTANCE: A graph G = (V,E), a function c giving each edge e ∈ E an integer capacity c(e) and an integer B. QUESTION: (D) Does the graph have a cut of size at least B? (O) Find a cut with the maximum size.

Algorithm

Find the maxcut value k by binary search from 1 to m using decision subroutine
     where m is global maximum value
for all edge e ∈ E
  select a edge e=(u,v) ∈ E, construct G' after removing egde e from G
  if SUBROUTINE(G',k)=1 =>removal of edge has no effect on MAXCUT
    add u and v to same set S or S'(use 2 SAT to determine which group)
  else
    add u and v to different sets S or S'

This algorithm works only if there is only one MAXCUT solution in the graph(i have considered only unweighted graph). In case of a complete graph this algorithm fails as there is more than one MAXCUT solution present.

consider 4 nodes complete graph with edges (1,2),(1,3),(1,4),(2,3),(2,4),(3,4). The algorithm fails because when we remove any one edge still there is a MAXCUT of size 4.

Please suggest any other algorithm which works or any additional condition which can solve this problem.

Thanks in advance


texts:
Both $L_{REG}=\{ \langle M \rangle : L(M)\text{ is regular}\}$ and $L_{CFG}=\{ \langle M \rangle : L(M)\text{ is context-free}\}$ are $\le_m$-complete for $\Sigma_3^0$ in the arithmetic hierarchy. This of course implies that $L_{REG}\le_m L_{CFG}$. Can anyone come up with natural, intuitive, direct reduction?

[I can give a reduction that goes through
$L_{COF}=\{ \langle M \rangle : L(M)\text{ is cofinite}\}$,
which is also complete for $\Sigma_3^0$. But it's not at all clear how to extract a direct reduction from the indirect one.]