texts:
I have built a heuristic algorithm for approximately solving an NP complete graph problem by recursive linear relaxations. In each recursion, the algorithm returns a reduced graph, with number of nodes $N_{k+1} \leq 0.5N_{k}$.

I think this means that the overall complexity should be order $\log N \times T(N)$ where $T(N)$ is the complexity of the FIRST linear relaxation. since the problem size gets at least cut in half each iteration. But there's two issues.

1) The complexity of the inner problem is reduced each iteration, so we're not doing $\log N$ iterations of $T(N)$ complexity, but something like $\sum_{i=0}^{\log N} T(N/2^i)$ or something. But is this the same as $\log N \times  T(N)$ asymptotically or can I tighten my bound?

2) How do I find the complexity of my linear program? I've heard the figure $O(n^{3.5})$ where $n = $ number of variables for interior point methods and $n^3$ for average case Simplex, but I can't find a good source.


texts:
Consider the language $A=\{(\phi_1, \phi_2) | \phi_1 \in SAT, \phi_2\in \overline{SAT}  \}$. What is the smallest class that $A$ is known to belong to?
Apparently, the answer is $\Pi_2$, although I thought it was $NP \cap coNP$, since if we have a non-deterministic machine $M_1$ that decides $SAT$ and another non-deterministic machine $M_2$ that decides $\overline {SAT}$, then we can define a machine $M_3$ that on input $(\phi_1, \phi_2)$, runs $M_1$ on $\phi_1$ and $M_2$ on $\phi_2$, and only accepts if both machines return True. If the input does belong to $A$, then for some set of nondeterministic choices, we know $M_3$ will accept. If the input doesn't belong to $A$, then either $M_1$ or $M_2$ always return False, and so $M_3$ always rejects.
My first question is whether my explanation correctly shows $A \in NP \cap coNP$. More importantly though, why is $\Pi_2$ smaller than $NP\cap coNP$!?


texts: Concrete/theoritical center of a cluster in a general metric space

texts:
What i call center is the point which minimize the distance to every points of a specific cluster.

From what i know we can look for a concrete point in the cluster get an approximation of the center.

For any space  with a metric $d$, look for point which minimize the sum of distance to all others points

$argmin_{x \in Cluster}(\sum_{x_i \in Cluster}{d(x, x_i}))$

Unfortunately this approach has a $O(n^2)$ cost.

I'm sure that this problem is a common one but i didn't succeed to find something and i would be happy to know :

Cool references
The complexity of this problem in the general context
If some sweet heuristic exist to find an approximate concrete or not point satisfying the problem in less than $O(n^2)$.


texts:
I plot several arrays containing xy-coordinates of points (using plot(x,y)) and obtain a plot with some curves. The curves form some very distinctive closed shapes (that is, the points describing the curves lie close to each other).

Now I need to find the (possibly approximate) centers of the closed shapes. Alternatively, it's good to "recognize" the closed shapes and to fill them. I don't know what is easier given the coordinates of points forming the shapes.

A possible example with 3 closed shapes to detect is given below.

Points can be also added along the image's borders, thus, closing all open shapes. Then all "regions" in the figure will be closed, but the question persists.


texts: Lower-bound complexities for finding common elements between two unsorted arrays

texts:
I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the worst-case and, eventually, what are these lower-bounds.

The problems are pretty simple:

  Given two unsorted arrays of distinct integers, $A$ and $B$, of size
  $m$ and $n$, determine all the common elements between the two
  arrays(the output must be sorted)

Which I believe has a lower-bound complexity of $\Omega((m+n)\log(\min(m,n)))$
(and $O(1)$ space complexity, if we exclude the input arrays),
even though I cannot find any proof of this fact. [I found an algorithm with this complexity, so I(hopefully) am not underestimating the complexity.]

The other problem adds some restrictions(and hence I'd expect to be able to lower the complexity):

  Given two unsorted arrays of distinct integers, $A$ and $B$, of size
  $m$ and $n$; knowing that common elements between the arrays have the
  same relative order in both arrays and that for every couple of
  consecutive common elements, their distance is at most $k$(constant),
  determine all the common elements between the two arrays maintaining
  their relative order and using at most $O(k)$ memory in addition to
  the input arrays.

I've tried to think about this second problem but I cannot see how the restrictions change the complexities. What puzzles me is that I believe that finding a single couple of elements between two unsorted arrays is $\Theta((n+m)\log(\min(n,m)))$, and since this is a special instance of this second problem then the restrictions do not add anything to the problem itself.

Are my guesses correct, and if so where can I find proofs for these lower-bounds? Do the restrictions change anything at all or the solution for the first problem is the best we can achieve in both cases?

Probably my questions can be summarized by the following:

  Given two arrays of distinct integers $A$ and $B$ of size $m$ and $n$,
  what is the lower-bound complexity for finding one common element?

Because, once a common element is found, the second problem can be solved in linear time.

Edit

The algorithm(s) that I thought are pretty simple:

For problem 1: Build two heaps for $A$ and $B$(which takes linear time and can be done in-place), then compare the minimum of the heaps, if they match print it and remove both, otherwise remove the smallest one and continue until the heaps are empty(this clearly takes $O((m\log(m) + n\log(n)) = O(\max(m,n)\log(\max(m,n)))$).

An other solution is to sort one array in-place, scan the other array and use bisection search to find matches. If we sort the smallest array (with size $m$) then the complexity is $O(m\log(m) + n\log(m)) = O(\max(m,n)\log(\min(m,n)))$. This technique yields the values in the other in which their are found in the biggest array, and it can be used to solve the second problem.

But, as you can see, I'm not using the extra restrictions at all and both algorithms use $O(1)$ space instead of $O(k)$(yes, it's still constant but $O(k)$ should give a bit more freedom).


texts: Why would you use a monitor instead of a semaphore?

texts:
I am currently attending the concurrent programming course in my university and we recently started talking about the concept of a monitor. While I understand the necessity of mutual exclusion, I do not understand why I would use a monitor for that.

As I understand it, a monitor guarantees that exactly one or no process is in the critical section at all times. We can achieve exactly that with a semaphore. Furthermore we implement monitors (or at least one possibility to implement them is) with semaphores.

So why would I implement something that does exactly the same thing as a semaphore with a semaphore? What benefits do I get?


texts: k-disjoint pair paths where any source can pair with any sink

texts:
I have a question regarding a problem I'm working on.

The problem is given an MxN grid with k sources and sinks, find non intersecting paths (vertex disjoint) such that all sources are paired with a sink. Each source must be paired to a single sink, and each sink must be paired to a single source, however all of the sources are compatible with all of the sinks. This could be imagined as k identical locks and k identical keys, all that matters is that its possible to move the keys into locks without having paths that intersect.  By contrast in the original problem, sink Si must be paired with source Di and this is an input parameter of the problem.

The underlying problem is NP-Hard but according to a vague comment I found, with the given restriction it can be solved in polynomial time. Unfortunately I can't find any relevant literature that could help.

https://stackoverflow.com/questions/19404033/all-pairs-maximally-disjoint-paths-algorithm/19411277#19411277

If anyone could point me towards proofs or papers that discuss this problem I would appreciate it.


texts:
Quantum computers are going to have enormous number of operations per second (in some situations exponentially more than classic computers).

Does it also hold for memory size? Are QC going to have exponentially increased memory?


texts: Preprocess data such that locations within a rectangle drawn on a map can be found in less than O(n) time

texts:
I came across this problem online and found no solutions or insight. The problem is stated as:

  Given a map as a square, and a set of locations on the map, users are able to select a rectangle on the map and all of the locations on the map are returned
  How would you preprocess the map data so that the find operation for the locations in the inner rectangle can be done in less than O(n) time?

I'm really stumped on this as the only thing I could think of is to create a hashmap that contains every single possible rectangle within the map with values that are lists of locations within said rectangle. However, it would not be practically feasible to store that much data.

Any help would be appreciated!


texts: Algorithm For Random Distribution of Prizes Over A Given Time Period

texts:
I have been assigned a task to come up with an algorithm for evenly distributing prizes over a given time frame, I am looking for advice as I am a bit stumped on where to start.

Here are my requirements:

Prize Types:

Prize types are types of prizes which can be added by a user, there can be any number of prize types
A prize type should last for a set period of time i.e 30 days
A prize type has a limited quantity i.e 10

Scope:
When a user signs on to our site, they have the opportunity to win a prize.
You need to distribute prizes throughout the course of the time period randomly in a way that ensures the prizes never run out 3 days before the end period ends.

My Thoughts:
I understand that I will need to factor in prize quantity over the time remaining from the initial period at the point in time a user registers, and generate a probability from these figures but I am stuck on finding a reliable way to do this that keeps the distribution random

Any suggestion appreciated


texts: How to create a subset with a given length and mean?

texts:
I have a set of numbers $P=\{p_1,\dotsc,p_{|P|}\}$, where $|P|$ is the length of the set. I want to select a subset, $S$, from $P$ such that its mean is approximately equal to a predefined value $\mu_s$ .
$$\sum_{x \in S} x \approx \mu_s * |S|$$
My problem:

$|P|$ = 5000
$|S|$ = 1500
$\mu_s$ $\approx$ 90 $(target$ $mean)$
$\mu_p$ = 95
$min(P)$ = 0
$max(P)$ = 300

I am looking for algorithm suggestions so I can implement this in Python. I would also like $S$ to include a range of values, rather than just the naive approach of sorting from smallest to largest first, then applying a greedy algorithm.
Additional question is whether dynamic programming could be used for this type of problem (i.e. we have to select a certain number of items from a list such that the sum is as close as possible to the capacity limit)?


texts: Language described by inverting accepting states of NFA

texts:
Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean that rejecting states become accepting states and accepting states become rejecting states.

Is there a nice expression for such a language reference to the original NFA language?


texts:
I am working with some tournament software where i need to generate pairings based on the swiss system. Some of the ideas i have came up with are as follows:

1)Create all permutations and choose best
  -This is O(n!) which is not possible when n can be up to 1000.

2)Create a weighted graph and choose best pairs somehow
  -I feel this is best but was hoping to find some similar examples

3)Find api where players(objects) can be passed in and paired based on typical elo/swiss pairing rules.

4)Generate initial result with no logic then try to improve with swapping until no more improvements can be made(not sure how one would know when no more improvements can be made)

So for pairings players are paired with others with same scores and staggered. So for example in a 16 player tournament the first round would have top seed paired with 9 seed and 2nd seed paired with 10 seed and so on. This gets complicated when you take into account teams(players on same team will only play each other when forced), players can't play each other twice, alternating colors is optimal which is what is meant by the above #1 creating all permutations to see which is best. This will not work if tournament is large.

I would like to do this client side(javascript) so wanted to keep that in mind.

Thanks in advance for any suggestions


texts: Why do reviewers always want to compare the method with deep learning baselines and Big data?

texts:
I work on the topics of sparse coding (SC) and dictionary learning (DL), in which classification is not the main goal, but the discriminative power of the representation is one of the concerns. Therefore, i use classification accuracy in order to show how my method is more discriminative than other SC or DL approaches.

Also, i use typical datasets in the literature of SC which are image datasets such as Ex.YALE, Caltech101, AR-face and similars.

But so often i'm criticized (even harshly!) by the reviewers (at least one in each submission) on why i didn't compare to deep-networks or why my results are not better than the reported CNN-method in paperX.

Or even i got feedbacks like "The datasets are small sized, why not using ImageNet and similars?!"

The thing is that my method is supposed to be compared to its family of methods (SC-based baselines) and the point of my work is to improve the model/algorithm's performance in this domain and not compared to any top-classifier on any big-data on the earth! :((


texts: Good reference for average-case runtime analysis of QuickSort

texts: I'm a beginner in programming with little knowledge about the technicalities. I'm assigned to do a "reading project" on the average case analysis of quicksort. I mean I have to present it in class. Now, I need a good source from which I can read it and find the materials which I can include in my presentation. As for my existing knowledge on algorithms, one can assume that I almost know nothing except for "just codes" and nothing at all about their analysis. Any book or materials having rigorous proofs will also do. Any help will be greatly appreciated!


texts:
I'm trying to solve the following problem in the most efficient way I can find.

I want to trade my items for someone elses items, every item have a price and a value.

I want to maximize the value of the items I trade, so for example:
My items:

  Banana, P: 10, V: 5
  Pen, P: 3, V: 1
  Paper, P: 1, V: 1

Their Items:

  Phone, P: 10, V: 8
  Key, P: 1, V: 2
  Wallet, P: 30, V: 100

You can see that I can trade my Banana and Paper (with value of 6) with Phone and Key (with value of 10)

I can overpay but can not pay less and the amount I overpay is lost.
Currently my solution is to use generate all the possible combinations of my items and try to match the price with knapsack algorithm and check each result.

This is however very not efficient because I can have over 1000 items (both mine and the other person).

Does anyone have a possible solution to this problem? I need it to be efficient but also give me the best solution (best value)

The items are not infinite and they have a limit.


texts: Is it possible to create an age estimation by face program using deeplearning with my laptop?

texts:
My computer specs:
Processor type  Intel(R) Core(TM) i7-8550U CPU @1.80GHz 1.99GHz
Installed RAM   8.00 GB
System Type     64 bit operating system
i also have Intel UHD graphics 620.

I am starting an AI course in college and we have been given the project to submit by the end of the semester. i want to use deep learning but i want to make sure its possible  to do it using my laptop so i dont run into problems later on that will jeopardize my progress. Btw i will also use a GPU instance on Amazon E2c or Google laboratory.


texts: how do I find a undecidable subset of a set that's decidable?

texts: Given that Let S = {a | |a| is odd}. I know that since S is decidable, but does there exist a subset within S that is undecidable?


texts:
I read a paper which talks about "a logic formula in which each variable appears at most twice unnegated and once negated". The term "unnegated" is double-negative, which makes it slightly unclear. Is there a more positive term to denote a variable that is not negated?

I looked in an English thesaurus, but all suggestions seem out-of-context in logic.


texts: finding best n players in minimum number of comparisons

texts:
I am trying to find out if there is any generic way to find out first to nth best player in a tournament if n is less than the square root of input size i.e. 5 best players in the sample size of 25 players?
I thought of using below approach to find out 2 best players.
So for finding out the 3rd best player we can use the same approach i.e.
players lost again best best player + players lost against 2nd best player should be again played against each other to find out the 3rd best player.
Am I right if this would be the minimum number of comparisons to get 3rd best player?
Or should I divide the players in square root of input size and then play in groups as this?
Edit:
When two players play better player always wins. You can design your own tournament strategy to figure out the best n players.


texts: Quantum algorithms and quantum computation

texts:
Is my (very high-level) understanding correct here regarding quantum algorithms —

Quantum computers can process a massive amount of operations in parallel to the nature of qubits and their ability to have states that are superpositions of $|0\rangle$ and $|1\rangle$.

Yet when we measure the qubits all the possible states collapse into a single state of either $|0\rangle$ or $|1\rangle$, which seems to negate the potential benefits of parallel operations. All we really know are the probabilities that the states will end up as.

However, we can exploit quantum properties to increase the probability that we end up with a certain result. I believe Shor's algorithm is based on exploiting quantum properties too, although I'm not sure in what way?

e.g. in a quantum walk, quantum interference means the walk spreads faster than a classical random walk and hence can out-perform classical walks.

That is my very high level understanding of what is going on with quantum algorithms. Am I correct, 'sort-of' correct, or way-off? Can someone clarify my understanding?


texts: Is NP-hard closed against cartesian product with arbitrary languages?

texts:
If $L_1$ is NP-hard, $L_1 \times L_2$ is NP-hard for every $L_2 \neq \emptyset$, where

$\qquad \displaystyle L_1 \times L_2 = \{(w_1,w_2) \mid w_1 \in L_1, w_2 \in L_2\}$

Is it true or false and why?

I can't prove it but I also don't find counter example.


texts:
I am looking for an algorithm to summarize a dataset in text form. If you consider below example, which shows sales figures for specific items in years 2001, 2002,and 2003:

This has to summarized like below

  For year 2001 ERF had more sales, for year 2002 ADO had more sales and for year 2003 also ADO had more sales. Overall for all these three years AEF had more sales.

Or similar to this to explain this dataset in text form.


texts: Communication Complexity for Product Distributions

texts:
In general for the (two-party) set disjointness problem for inputs of length n, we know that the parties need to communicate $\Omega(n)$. Surprisingly, today I discovered (if I understood correctly) that this is not true for product distributions, i.e. when Alice's and Bob's inputs are chosen independently from arbitrary distributions! In this paper, for example, they provide an upper bound with communication complexity $\mathcal{O}(\sqrt{n}\log(1/\epsilon))$, where $\epsilon$ is some error term not relevant for the question here.
Now I am curious about whether gaps exist for other well known communication complexity problems.

Question: What other well-known problems exhibit a gap between the communication complexities when one considers arbitrary input distributions and product distributions. Are there similar results for inner products or intersections?


texts: What is longest string with no equidistant pairs of equal characters for a given alphabet?

texts:
Given a finite alphabet $A$ with $|A|=n$, what is the largest $l$ so that a string $s=a_1...a_l$ of length $l$ exists with $a_i\in A$ so that there is no $i,j,d$ with $i\neq j, d > 0$ so that $a_i = a_{i+d}$ and $a_j = a_{j+d}$?

Thanks to @greybeard I now know that such strings are called 2-surprising strings. More information can be found here: http://oeis.org/A008062

This problem has been described by Dennis E. Shasha on page 122 of the December 2003 issue of Scientific American.

Furthermore there exists a proof that $l<3n$: http://aleph0.clarku.edu/~djoyce/mpst/surprising/

These are known strings for small $n$:

n   l quantity  example

1   2   1       00
2   4   3       0010
3   7   4       0012102
4   10  2       0112032310
5   12  212     001232410431
6   15  770     001231452503410
7   18  1630    001231456264035102
8   21  1396    010234563742761154032
9   24  312     012334546785281076142053


texts: Is the language of words that are unbalanced in the first half context-free?

texts:
(Practice exam question in computational models)

Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s.

Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and the first half of $w$ is unbalanced$\}$. Determine whether or not $L$ is context-free and prove your answer. You may do so by drawing an NPDA which recognizes $L$, using the closure properties of CFLs, or the relevant pumping lemma.

This question has been bugging me for a while; my gut tells me it isn't context-free since any PDA that recognizes it would have to check the balance of the string read thus far while simultaneously measuring its length and non-deterministically choosing an unbalanced point to validate as the middle of the word. I also haven't been able to express it as a union or concatenation of two CFLs or find a CFG which generates it.

On the other hand, I haven't been able to either find a word in the language that can't be pumped or prove that every word can be pumped.

Does anyone have any ideas on how to proceed?


texts: Good beginner source to learn about how computers work

texts:
I am a senior year high school student. I love programming and my chosen language is Java. I'm very much into high-level programming and Object Oriented design.

Recently, I started to show first interest in the low-level side of things. Especially the most basic level of how computers work (the more theoretical level, not the hardware side).

For example, how computers make basic calculations has always been a mystery to me. How is it that a computer can even come up with the result for 5 + 2? (As a kid I used to think that every computer stores the answers for all of the possible calculations.. lol)

I am also interested in the most basic level of how computers, well, generally do things internally. Again, at the most basic and fundamental level.

As you can see it's hard for me to phrase what I'm interested in learning, probably because I know almost nothing in computer science. But I hope you get the idea.

Could you direct me to a good source that I can learn from - at the most beginner level - this kind of knowledge? (A website or a book [preferably a website]).

Thanks


texts: Solve T(n) = T(n-1)*n with repeated substitution

texts:
I'm trying to solve T(n) = T(n-1)*n using repeated substitution.

I can expand it, but I'm having trouble with geometric sequences for any problem. I find I'm just memorizing solutions to typical problems. It's sometimes hard for me to go from the expanded equation to a general equation that I can simplify.

T(n) = T(n-1)(n)

T(n) = T(n-2)(n-1)(n)

T(n) = T(n- 3)(n-2)(n-1)(n)

I'm not sure how to generalize this to ultimately find the big O. Any tips are appreciated!


texts: Load balancing. Why not use priority queues?

texts:
I have recently learned about various randomized algorithms for load balancing. The model is always that there are $m$ balls and $n$ bins and the balls arrive one at a time. The task is to minimize the maximum load of any bin.  However there is something I don't understand.

Why not just keep a priority queue of the loads of the bins and allocate any new ball to the bin with the lowest current load?  This seems to give you the optimal load without any complications.


texts: Fast solution for a combinatorial maximizaton problem

texts:
You are given a natural number n (n<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 (consisted of not necessarily consecutive bits). Now we have to find the maximum number from the numbers in S so that every pair of numbers is "compatible" and I want an example numbers from S with that maximum. Here is an example of the task:

n = 6;
S = { 000000, 000001, 000010, 000011, ..., 111110, 111111 };
The maximum number from the numbers in S with that property is 10.
Here is an example:
000000, 000011, 110000, 001100, 010010, 001111, 111100, 110011, 101101, 111111

I tried making some greedy solutions but they aren't working on greater n (and I think they can't be made accurate). When I thought of some graph solutions I reached an NP problem (let each binary number is vertex and we have an edge connecting them if they aren't "compatible"; now we have to find the maximum in vertices independent set). The other way I tried is making a bipartite graph with one set of vertices with the binary numbers of length n and the other with the binary numbers of length n-1. We have an edge from the first to the second set if the number from the second could be a substring of length n-1 of the number in the first. Now we have to find the maximum number of vertices from the first set so that their edges do not have any common endpoint vertex but I couldn't think out the solution of this problem and couldn't find it in the Internet.


texts: Partial Range Query on Inverted File with Combined Index

texts:
I am currently reading Multidimensional and Metric Data Structures by Hanan Samet for fun. The combined index is discussed on page 5-6. I do understand it in the sense that the inverted file itself is an index, and then we extrapolate another index by lexicographically ordering the attribute.

So, given a record with four attributes (Name, X, Y, Z), that is, the name and three dimensional point in space. If I created the inverted file such that it maps Name to the X,Y,Z attributes, then we can create another index by lexicographically ordering the attributes X,Y,Z. The possible orders would be XYZ, YXZ ZYX.

Do we order by the values of XYZ in the inverted file at all? Does the index of lexicographically ordered XYZ attributes point to the inverted index, which thus makes it combined?

Any help is greatly appreciated!


texts: minimum vertex set removal for edge-free graph

texts:
I'd like to know the name and the algorithm for the following problem which I'm guessing is a classic, but is slightly different from graph connectivity.

Consider a undirected graph G=(V,E). What is the minimum number of vertices which removal (vertices and their adjacent edges) makes the resulting sub-graph empty of any edge?

For example:
If A - B - C, then just need to remove B.
If A - B - C and A - C, then need to remove at two vertices (any pair).

For an algo, intuitively I'd proceed by removing first the vertex of highest degree and proceed the same on the remaining graph until there are no edges. Not sure if it gives the min number. For sure, in the worst case I can always go through all possible |V|! removal possibilities and take the min.


texts: Can PDA accept only by final state without finish reading input?

texts:
I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the input is read fully or not).
I can guess PDA with the new definition of acceptance is less powerful, and easy to see every language accepted by this PDA is accepted by some PDA with the conventional definition. But, can anyone give some idea how to show some languages are not accepted by the new PDA?


texts: Probability of detecting errors in codewords

texts:
I have been struggling with the below question for quite some time, and I don't have a pointer to move forward.

  A certain Error Control Coding scheme using block codes takes an input block (dataword) of 500 bits
  and appends a 50 bit code to produce a 550 bit codeword which is then transmitted across channel that
  causes individual bits to flip with a probability of 0.1 independently. The pairwise Hamming distances
  between all the codeword pairs is so large that the probability of an error occurring that converts one to the
  other can be neglected, except as follows: two codewords C 1 and C 2 have a Hamming distance of 10, and
  two codewords C 3 and C 4 have a Hamming distance of 6.
  Assuming no knowledge about what datawords may be more or less likely to be desired to transmit, what is
  the probability that a given block transmission will be corrupted by the channel but the error will go
  undetected by the receiver? You may answer with an expression, but the answer has to be completely
  numerical (no symbols).

My thought process about this question is that the probability needs to be calculated as such :
Pr(Selecting either C1 or C2) * P(error in C1 or C2) + Pr(Selecting either C3 or C4) * P(error in C3 or C4).
I feel the Pr(error) is given by a binomial distribution of 55CX(0.1)^x(0.9)^550-x where X=10 or 6.

First, am I thinking about the problem correctly  ? If yes , how do i derive the probability of selection of a particular codeword ?

Edit: I don't have the exact source per se, because this question is from a random uni final exam that I found on the internet. I am prepping for my own exam, and came across this question.


texts: Effect of value of k in K-Nearest Neighbor

texts: In K-Nearest Neighbor the value of k decides the accuracy of classification. What are the pros and cons of choosing smaller value for k and larger value for k?


texts: Does co-inductive and co-recursive types also have their recursors?

texts:
I'm new to type theory, and recently read introductory materials where dependent type are discussed. One of my friend asked me, "Those dependent types are having recursors & 'inductors'(dependent eliminators), but how about those types that is co-inductive/co-recursive?"

Some related example is much appreciated.


texts: having issue with numbers in Polymorphic Lambda Calculus

texts:
It is said that Church Numbers are encoded as following

   c0 = λX. λs:X->X. λz:X. z;
   c1 = λX. λs:X->X. λz:X. s z;
   c2 = λX. λs:X->X. λz:X. s (s z);
   c3 = λX. λs:X->X. λz:X. s (s (s z));

The church numbers are terms, right? but the terms are given by the following syntax.

  t ::=                          terms
       x                          //variable
       λx:T.t                     //abstraction
       t t                        //application
       λX<:T.t                    //type abstraction
       t [T]                      //type application

It seems church numbers do not respect the syntax of terms to me, strange.

I think it should be like

      c0 = λX<:some type here. λs:X->X. λz:X. z

So, how to write church numbers in a consistent way?

If possible provide simple examples to explain, i.e.  2 * 2, how to write this?

source1

Thanks in advance!


texts: NFA for binary words that do not end in 10

texts:
Construct an NFA over $\{0, 1\}$ whose language contains only words that do not end with $10$.

This is one of the first problems in the book, so it's supposedly easy. I just can't figure it out. It's easy using a DFA, but I'm not so sure using an NFA. Maybe I'm not understanding a particular concept in the NFA.


texts:
I was reading and learning about SIMD and AVX2 vector instruction, as I was trying to implement them for better performance.

While reading about vector instruction, I encountered the term deep pipeline. Now I understand what pipelining is from computer organization and design patterson & hennessy and Computer Architecture: A Quantitative Approach. I quickly again scanned the books mentioned and they do not explain deep pipelining with a example and just mention about it in a couple of sentences. I tried to do a google search and I encountered the same material as mentioned in the comments(which 99% talk about pipelining and not deep pipelining) which again just mention about deep pipelining in a couple of sentences (deep pipeline = more stages, splitting of instruction leads to quick execution ) . But, what I am looking for is a simple example of deep pipelining(and not pipelining) with good explanation of it as in how the instruction are split and how it leads to quicker execution.

So, the goal was to learn how to use vector instruction and later on GPU programming and while doing so, I encountered text which mentioned the use of deep pipeline with vector instruction. And, I am short of time, I spend some hours looking for deep pipeline on google and whatever I found was a couple of sentences explaining it and not a working example, to practically understand and visualize how a deep pipelining works.

So, I will appreciate if someone could point me to a resource which has a working example of deep pipelining with some explanation.


texts: What does this language notation specify?

texts:
I am given this exercise:
Let L1 ={akbk : k > 0} and L2={ck : k > 0}. For each of the following strings wi, state and explain whether or not wi ∈ L1L2.
w1=ε
w2=aabbcc
w3=abbccw
w4=aabbcccc
w5=ccaabb
w6=ab
So far I haven't seen such a notation for languages as the one that L1 and L2 are seen in. For example, I had seen other notations such as: L1={w∈{a,b}∗: every a in w is immediately preceded and followed by a b} which I could understand. A parallel between the two notations will be much appreciated.
Moreover, what does it refer by L1L2? Is this counted as a union or a concatenation?
What I could figure out from this exercise is what w1 is surely not in L1L2, as k must be over 1. Following the same logic, the other answer would be w2 as k will always be the same in both L1 and L2, hence the number of a's, b's and c's shouldn't differ.
Is the above thought correct or is it more to this notation than I have already thought of?


texts: Interactive programming language minimizing reevaluations

texts:
I'm looking for any programming language, DSL, library or pattern for live scripting but minimizing the expressions reevaluation.

Topological sorting provides non-revaluation of expressions.

Memoization provides a simple way of not re-evaluating but is a waste of memory.

A form of topological ordering can be achieved by maintaining (in each language object) a version number for each dependency but it does not seem to be easily composable/scriptable.

Which available tools would be the most suitable?

Thank you!

(I think the closest I've found might be https://www.shinoe.org/cameleon)


texts: Proving correctness and optimality of a greedy algorithm

texts:
Here is a (slightly abridged) problem from Kleinberg and Tardos:

Consider a complete balanced binary tree with $n$ leaves where $n$ is a power of two. Each edge $e$ of the tree has an associated length $\ell_e$, which is a positive number. The distance from the root to a given leaf is the sum of the lengths of all the edges on the path from the root to the leaf.

Now, if all leaves do not have the same distance from the root, then
the signals we send starting from the root will not reach the leaves at the same time, and this is a big problem. We want the leaves to be completely synchronized, and all to
receive the signal at the same time. To make this happen, we will have to
increase the lengths of certain edges, so that all root-to-leaf paths have
the same length (we’re not able to shrink edge lengths). If we achieve this, then we say the tree has zero skew.

Give an algorithm that increases the lengths of certain edges so that
the resulting tree has zero skew and the total edge length is as small as
possible.

This problem was in the "Greedy Algorithms" chapter.

I know the solution to this problem is as follows:

Let the subtrees below the root be $L$ and $R$. If the maximum sum of the edge lengths on the path to a leaf in $L$ starting from the root is greater than the maximum sum of the edge lengths on a path to a leaf in $R$, then increase the edge length from the root to the right subtree by the positive difference between the two.

Conversely, if the maximum sum of the edge lengths on a path to a leaf in $R$ starting from the root is greater than the maximum sum of the edge lengths on a path to a leaf in $L$, then increase the edge length from the root to the left subtree by the positive difference between the two.

I am having trouble proving the following:

$1)$ The resulting tree upon termination of this algorithm is a zero-skew tree (the length from the root to any leaf is the same).
$2)$ The sum of the edge lengths is minimized with this algorithm.

I have tried to prove these facts in many ways, such as induction and direct proof, but I am having a lot of difficulty doing so. The algorithm makes sense to me intuitively, but I'm having trouble explaining why it works formally.

I would greatly appreciate some help in solving this problem.


texts: Effect of mismatches on string matching finite automata

texts: I am contemplating a string matching FA algorithm (not KMP). The complexity of its transition function calculation ie the preprocessing is m(length of pattern )* (the language of the FA) . What effect would greater or fewer mismatches have on this algorithm, for example in a case where all elements in the pattern are the same, such as [ccccc].


texts: Why is it hard to show that the euclidean Steiner tree problem is in NP?

texts:
I read that for the euclidean Steiner tree problem it is known that it is NP-hard, but not known whether it is in NP or not. [Wikipedia]
Shouldn't the euclidean version obviously be in NP since the metric Steiner tree problem is in NP and a non-deterministic TM that decides the metric Steiner tree problem could also decide the Euclidean Steiner tree problem? Or am I missing something that could make the Euclidean version inherently more difficult/different?


texts: Does a Turing Machine with a 2-dimensional tape recognize RE languages?

texts:
This question is from a Computer Theory Course

  What is the category of languages recognized by a MT with a
  two-dimensional tape? The Tape is an infinite matrix. For each move the head shift belongs to the set $S$ = {stop, north, east, south, west}

My approach

I know that TM recognize Recursively Enumerable or type $0$ languages, but how to show a proof for this answer?


texts: Efficient Implementation of Boolean Lattice-Esque Operation

texts:
Let $X = \{1,2,\dots n\}$, and $Y_i= \{T \in \mathcal{P}(X): |T| \le i\}$. I am interested in "avoidance sets" $A \subset Y_n$. We say a subset $S \subset X$ is valid with respect to an avoidance set $A$ if $T \not \subseteq S$ for all $T \in A$.
We let $f(A)$ denote the set of $S\subset X$ that are valid with $A$. It may be helpful to note that $f(A' \cup A'') = f(A')\cap f(A'')$.
Given a list of avoidance sets $A_1,A_2,\dots A_k \in Y_2$, I want to return an avoidance set $A' \in Y_2$ such $$\bigcup_{1 \le i \le k} f(A_i) \subseteq f(A')\tag{1}$$ and for any other $A'' \in Y_2$ satisfying (1), we do not have $f(A'') \subsetneq f(A')$.
Can this be done in time linear to $\sum_{1\le i \le k} |A_i|$? (you may assume that all the sets $A_i$ are simplified, i.e. if $\{a\}\in A_i$ and $\{b\}\in A_i$ then $\{a,b\} \not \in A_i$)
Context:
The physical motivation behind my question is that I am trying to "roughly" keep track of events which must be avoided.
An element $x \in X$ corresponds to an "event" occurring in a probability space. A subset $S \subset X$ correspond to the intersection all the events $x_1,x_2 \dots x_k \in S$ occurring at once.
An avoidance set $A$ is supposed to express certain events which have probability zero of occurring. (so $S \subset X$ is not valid with $A$ if the event corresponding to $S$ has zero probability) To keep the cost of space low, I have decided to concern myself with only working with avoidance sets in $Y_2$. (thus this is a heuristic representation)
Now, let's say I am keeping track of avoidance sets $A_i$ where $S$ is invalid with $A_i$ represents that $S$ has probability zero given event $i$ happens. Now, if I know at least one of the events $A_1,\dots A_k$ occurs, then I am interested in finding $A'$.


texts:
How can we solve summation of asymptotic notations like given below:
$$
\sum_{k=1}^{n-1} O(n).
$$


texts:
I'm getting confused on these both. Reject the string does a stop while loop the machine goes on and on.

My textbook has one example on a reject state and no physical one for loop:

Assume that no reject state was given. And I input a string

$1^{q_{1}}011$

After all the transitions the turing machine is now on the empty string $1011 \epsilon^{q_{8}}$ with no where else to go and its not on a accept state, so it rejects.

Now consider if its on q2 at string $0$ so $$10^{q2}11$$

And it cant go anywhere. Would that also reject? Or only if its on the empty string?

Now what is a loop? My idea is

$$1^{q_{1}}011$$

$$1^{q_{2}}011$$

$$1^{q_{1}}011$$

$\dots$

forever


texts: I think I've found a flaw in this paper: On finding a minimal enclosing parallelogram. Can someone verify it for me?

texts:
On finding a minimal enclosing parallelogram
I think the problem will occur when we only consider the first clockwise antipodal vertex. I think instead we should consider an edge when there are two possible antipodal vertices w.r.t an edge.
I give two examples here.
Can somebody help me verify it?


texts:
Suppose you are given two sets of integers L and M both having N elements. The problem is to match each number in L to a number in M. Such perfect matching has some cost given by $\sum_{i=1}^{N} l_i*m_i$.
I want to find some perfect matching with some given cost. I suspect that this is hard (i.e. NP-complete). Can you solve it quickly? (find an efficient algorithm).
Here is an example: we have three courses, credit hours are 4, 5, 8. Grade points are 4, 3, 2.  A solution is a perfect matching between the lists that result in some given GPA.
For this to be computationally meaningful, the largest grade point and largest credit hour are unbounded.
P.S. Yuval hinted the reduction from Subset sum problem. I am interested in hardness proof of strong NP-completeness.


texts: Subset of nodes such that all nodes of a graph are adjacent

texts:
We have been given a graph $G$, we need to find a subset of nodes $S$ such that each node of the graph is in $S$ or is adjacent to a node from $S$. Additionally, the elements of the subset $S$ should not be adjacent to each other neither should they share a common neighbour node.
This is an example of the given problem:
In the given graph, the subset $S = $ {2, 4} is a valid solution as $3$ and $5$ are adjacent to 2 while $1$ and $6$ are adjacent to $4$. Further, $2$ and $4$ are not adjacent neither do they share a common neighbour.
The subset $S = $ {4, 5} is NOT valid as $4$ and $5$ have a common neighbour $1$.

I have been looking for an efficient way to do this; my attempt at an algorithm gives an exponential time complexity.
Any hints are appreciated, thanks in advance.


texts:
If you could include your thought process in determining why it's regular it would help me a lot.

$L_1 = (0^*(10)^*11)$
$L_2 = \{ \langle M \rangle \mid M \text{ is a Turing machine that halts on all inputs from }L_1 \}$
$L_3 = \{ x \in \{0,1\}^* \mid \exists y \in L_2. xy \in L_1 \}$

Why is $L_3$ regular? It's a set of strings, I need to determine if there's a DFA that can accept it. Do I even care about $L_2$ and $L_1$ in this case?


texts:
I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof.  Look at my proof.

Induction for height.
Let's assume that it is truth for each AVL tree of height at most $h$.
Let's consider AVL tree $T$ of height $h+1$.  Now, let's consider two subtree of $T$ - $L$ and $R$. We know that $height(R)\le h$ and $height(L)\le h$.   Hence using induction hypothesis we conclude that $L$ and $R$ may be colored such that $L$ and $R$ will be red black tree.  Then we may paint root - of course black color.   Now $T$ is AVL and black tree.


texts:
I'm having troubles understanding the following proof:
$$
\begin{align*}
&\text{Proof: } \forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log_a(n) \\
&\Longrightarrow \ln(a(n)) = \log_2(e)\ln^2(n) \ll n^{0.01} = \ln(d(n)) \\
&\Longrightarrow a(n) \ll d(n)
\end{align*}
$$
The topic is Big O comparisons. The proof is about $a(n)= n^{\log_2 n}$ and $d(n) = e^{n^{0.01}}$. The proof is very heavy in mathematical notation. I'm not sure what ∈ means in the example.  I know that it denotes set membership in a more usual case, but have never seen it in the exponential position.


texts: Find Vector in set A furthest from any Vector in set B

texts: Given 2 sets of Vectors in 3 dimensional space: A and B, what are the fastest algorithms to find the vector in set A furthest from any in set B?


texts: maximum flow with all or nothing through each edge

texts: Consider a maximum flow problem, where each edge has a small integer capacity. Now, I want a solution that for each edge uses the entire capacity, or no flow through that edge at all. To avoid the subset-sum problem, the capacities are small. Is this solvable in polynomial time or is it NP-Complete?


texts: Quantification in pumping lemma for regular languages

texts:
The Wikipedia article on the pumping lemma
states:

  We now pump $y$ up: $xy^2z$ has more instances of the letter $a$ than the letter $b$, since we have added some instances of $a$ without adding instances of $b$. Therefore, $xy^2z$ is not in $L$. We have reached a contradiction. Therefore, the assumption that $L$ is regular must be incorrect. Hence $L$ is not regular.

But this formal version of the lemma seems to differ:
$$
\begin{align*}
&(\forall L \subseteq \Sigma^*) \\
&\quad (\text{regular}(L) \Rightarrow \\
&\quad ((\exists p \geq 1)((\forall w \in L)((|w| \geq p) \Rightarrow \\
&\quad ((\exists x,y,z \in \Sigma^*)(w=xyz \land (|y| \geq 1 \land |xy| \leq p \land (\forall i \geq 0)(xy^iz \in L))))))))
\end{align*}
$$
I thought there only has to "exist a combination of $x,y,z$" in order to be regular (as stated in this answer as well).

As far as I can see, the Wikipedia example only takes a look at one possible combination/example. Am I missing something obvious here?


texts: Using Marching Squares to connect curve ends in adjoining squares

texts:
I'm learning Marching squares for a graphic program I'm working on and, while I understand how to connect points along an edge of a single square depending on the vertex values, I am unclear about how to connect two curves belonging to adjoining squares.

The part I'm trying to understand is this:

Say I'm linearly interpolating along edge (a, b) of Square X and there is a zero crossing somewhere after the midpoint c - let the zero crossing be at 0.75 along edge ab. This is point f.
To get rid of the ambiguity, I divide square Y into four squares - Y1 through Y4. Now say while I interpolate along the smaller edge ca, I encounter a zero crossing before the midpoint of ca - let the zero crossing be at 0.25 of edge ca. This is point g.

How should I resolve the vertex values (0 or 1) of the squares?
How can I connect the two curve ends (in green)?


texts: Is there an algorithm for determining whether a element is Prime?

texts:
Is there an algorithm that can take an element on an arbitrary integral domain, and determine whether or not it is prime on that ring?

It is pretty trivial to do so on a finite integral domain, because no finite integral domains have primes (all elements are units).  It is also pretty simple on the ring of polynomials of a finite ring where you can check all the polynomials of smaller order, however I am struggling to come up with an algorithm that works on all integral domains, let alone an efficient one.


texts: Betweenness centrality measurement ignoring inverse paths?

texts:
I'm implementing the Betweenness Centrality algorithm proposed by Brandes (first algorithm on this paper - also below), and I'm running into a very weird issue: it seems to be ignoring some paths (i.e. for vertexes v-w, it may count the path v-e-w, but not the inverted path w-e-v). I'm not sure how to prove or debug this issue, but I'm pretty certain that's what happening. The precise issue that I can see in the debugger is that two nodes that should have the same BC value are off by roughly three units. I'm using the double type to store the values.

Am I missing something about this algorithm? The graph I'm examining is unweighted and undirected btw.

Also, on a totally unrelated note: the value being computed on each step is the following:

Shouldn't the value be between 0 and 1?

Algorithm:


texts: If $L\in\mathrm{NP}$ is $\mathrm{coNP}$-complete, then $\mathrm{coNP}=\mathrm{NP}$

texts:
The problem in the title is to be proven, and while proving $\mathrm{coNP}\subset\mathrm{NP}$ is rather clear given the assumptions (see below), I fail to see a way to prove $\mathrm{NP}\subset\mathrm{coNP}$.

My main idea is to prove that $L$ is also $\mathrm{NP}$-complete (or rather $\mathrm{NP}$-hard, as it is in $\mathrm{NP}$), but I don't really see a possibility to prove this, as it is not sufficient that a subset of $\mathrm{NP}$ is reducible to $L$; thus I would be very thankful for some idea for a proof.

Addendum 1:

I am aware of if $L\in NP\cap Co-NP$ is NP-Hard, then $NP=Co-NP$, but in this source only the obvious implication is proven.

Addendum 2 - My proof of the first subset-relation:

All languages $K\in\mathrm{coNP}$ are reducible to the $\mathrm{coNP}$-complete language $L$, thus if $L\in\mathrm{NP}$ every $K$ is reducible to a language in $\mathrm{NP}$ and the implication $K\in\mathrm{coNP}\Rightarrow K\in\mathrm{NP}$, and thus $\mathrm{coNP}\subset\mathrm{NP}$, holds.


texts: What are some undecidable problems for recursive languages?

texts:
When we say a class of languages is decidable we mean that the membership problem can be solved. However even though the membership problem is solvable for the class, there may exists some problems for the same class which are undecidable. For example Context free languages are decidable yet the problem of determining whether the language generated by context free grammar is unambiguous is undecidable.

I want to know some undecidable problems for recursive languages. Please don't problems related to context free and context sensitive language and then say that these languages are also recursive. The problems I want must be for only recursive languages and not for any proper subset of this class.


texts: Explanation of algorithms used by NAS benchmark kernels

texts:
I'm not sure if this is the appropriate forum for asking the following question. Please guide me to the right forum.

I am trying to understand the algorithms used by kernels(such as Integer Sort) in NAS parallel benchmarks. I could not find any source online that explained the algorithms used by the kernels. I could try to infer the algorithms from the code, but that would be really messy. The algorithms are not explained in the paper published by the authors of the benchmark either.

Please point me to some tutorials/documents describing these algorithms. Thanks


texts: Does a never-halting machine always loop?

texts:
A Turing machine that returns to a previously encountered state with its read/write head on the same cell of the exact same tape will be caught in a loop. Such a machine doesn't halt.

Can someone give an example of a never-halting machine that doesn't loop?


texts: This paper on memcomputing seems like a really big deal, but it doesn't seem to be particularly popular.  They prove that their UMM can solve NP problems in P, although they don't claim P = NP.  In their next paper, they go on to build a physical model of this UMM with moderate success. Does this mean P=NP?


texts: Why cannot Operand forwarding remove all RAW hazards?

texts: I read a statement in the textbook that : Operand Forwarding cannot remove all RAW Hazards in Pipelined Processor but am unable to conceptualize that in my brain. Can you please explain it with an example where Operand Forwarding will not be able to remove RAW Hazard .


texts:
Let $A\in NP\cap co-NP$. Then, $NP^A = NP$.

At first, I thought: Easy, let $L\in NP^A$ s.t. $A\in NP\cap co-NP$. Let $M_L$, an $NDTM$ to decide $L$ and $M_A$, an $NDTM$ to decide $A$. Then, we could create a new $NDTM$, $M$ which acts the same as $M_L$, but instead of calling the oracle, it simulates $M_A$ on the oracle's input.

That is wrong as far as I understand; We can't simulate an $NDTM$ that way since $M_A$ may have some computation paths which rejects and some which accepts and we wouldn't know how to act.

What should I do instead?


texts: Asymptotic equivalent of the recurrence T(n)=3⋅T(n/2)+n

texts:
The questions is to find the running time $T(n)$ of the following function:

$$T(n)=3\cdot T(n/2) + n \tag{1}$$

I know how to solve it using Master theorem for Divide and Conquer but I am trying to solve it by expanding:
$$\textstyle
T(n) =  n+\frac{3}{2}n +(\frac{3}{2})^2n + (\frac{3}{2})^3n + \cdots
\tag{2}$$
which implies
$$T(n)=n\sum_{k=1}^{n}({\textstyle \frac{3}{2}})^{k-1} \tag{3}$$
and so
$$T(n)=2n\cdot(({\textstyle\frac{3}{2}})^n-1) \tag{4}$$

The right answer to this problem is $\Theta(n^{\log3})$.
How can I reach to right answer through my approach as shown above.Is my approach wrong ? How can I solve it without using Master theorem.

Any help is appreciated.


texts: Practical importance of interval / circular-arc graphs in resource allocation

texts:
A graph is called a circular-arc graph if each of its vertices can be assigned to a circular arc such that two vertices are adjacent iff their respective arcs have a non-empty intersection. Analogously, a graph is an interval graph if we can assign each of its vertices to intervals on a line in the above fashion. Note that interval graphs are a subclass of circular-arc graphs.

Wikipedia states that interval/circular-arc graphs are important in the modeling of (periodic) resource allocations problems in operations research. Can you provide a concrete example of such a problem and how it is modeled to CA/interval graphs? The problem should conceivably occur in practice.


texts: How to prove the emptiness of intersection of two context free languages is undecidable?

texts:
Where can I find a proof that the emptiness problem for the intersection of two context free languages is undecidable? I searched on the internet but could not find anything helpful.

Do you maybe have a book or paper I should investigate?


texts: Would removing the branch delay slots change the instructions set architecture?

texts:
I am trying to study for an exam and I noticed a lot of the questions follow the idea of  "Changing the ISA". From my understanding the ISA dictates the structure and format of instructions, so changing instructions or the format (32 to 64 bit) would change the ISA. However I ran into a question which I am not sure how to answer.

"If we remove the branch delay slots, will the ISA be changed?"

My guess would be no, because we're not changing any instructions (right?), but I would like to get an answer from someone more knowledgeable.


texts: Why computer take long time to open huge text files?

texts:
Im not sure if this the right place to ask but I'm wondering why a computer takes forever to open huge text file like 1GB but if I open a video file (mkv) for example with 10GB like a movie it will be opened very fast.

Why the computer doing this ? What is the difference between the two operations?


texts: NP-complete and polynomial time reduction

texts: A decision problem is NP-complete if it is in NP and all other problems in NP can be reduced to it by a reduction that runs in polynomial time. Why it is important to require that the reduction runs in polynomial time, as opposed to accepting any computable reduction.


texts: Solving problems related to Marginal Contribution Nets

texts:
So, I encoutered this problem in examination:

  Consider the following marginal contribution net:

  $\{a \wedge b\} \to 5$

  $\{b\} \to 2$

  $\{c\} \to 4$

  $\{b \wedge \neg c\} \to −2$

  Let $v$ be the characteristic function defined by these rules. Give the values of the
  following:

  i) $v(\emptyset)$

  ii) $v(\{a\})$

  iii) $v(\{b\})$

  iv) $v(\{a, b\})$

  v) $v(\{a, b, c\})$

My answer is below, but I am not sure.

  i) $v(\emptyset) = -2$

  ii) $v(\{a\}) =  0 - 2$

  iii) $v(\{b\}) =  2 - 2$

  iv) $v(\{a, b\}) = 5 + 2 - 2$

  v) $v(\{a, b, c\}) = 5 + 4 + 2 - 2$

If anybody knows how to solve this kind of problem, could you confirm?

Exact same problem is shown on page 4 of following paper:
Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games (by Samuel Ieong and Yoav Shoham)


texts:
I am trying to figure out what the time complexity is for a "Look and Say" sequence generator which receives an integer n and outputs the nth term in the look and say sequence.

I'm looking at the below code. It is a tail recursion, but I can't get the summation properly. Can someone please provide an explanation along with the answer?

string LookAndSay(int n)
{
    string ret;
    if(n == 0)
    {
        return "1";
    }
    string s = LookAndSay(n-1);
    for(auto it = s.begin(); it != s.end(); it++)
    {
        char curDigit = *it;
        int count = 0;
        while(it != s.end() && *it == curDigit)
        {
            count++;
            it++;
        }
        it--;
        std::stringstream ss;
        ss << count;
        ret += ss.str();
        ret += curDigit;
    }
    return ret;
}


texts:
I have the recurrence of the form

  T(n) = T(n/2) + O(n)

This can be solved using master's theorem and if i use the results of the theorem, the recurrence evaluates to a time complexity of O(n). But if i think of it in terms of its tree, the input is reducing by half each time so we have a tree of logn height. Cost of each level is O(n). So we might have a complexity of O(nlogn). Now i am confused that is it O(nlogn) or O(n). Please help me.


texts:
For hobbyist reasons I wrote a program which takes the equations of the logic gates of a digital circuit as input, does some analysis, outputs the analysis results and generates program code for doing logic simulation.

Combinational logic is not a problem but sequential logic is:

Currently my program requires you to specify manually that a certain gate's output has a "state" (*) which must be stored in a variable.

I made the attempt to let the program detect such states automatically but the algorithm I developed often recognized too many gates as "having a state".

(For more complex circuits both gates of a flip-flop were detected as "having a state" for example although for a flip-flop the state of only one of the gates must be stored.)

My question:

Is there an algorithm that allows you to detect states in such a circuit (given by the gates' equations) automatically?

I'm planning to simulate circuits with ~20000 gates so simply trying out all combinations will not work.

(*) Please excuse me if I use the word "state" with a wrong meaning. In circuit development the word has a slightly different meaning than in computer science.

About D.W.'s comment:

Let's say I want to simulate a digital circuit which has some inputs, some outputs and n bits of RAM memory.

For simulating the circuit it is obvious that I have to store the values of the n bits of RAM memory somewhere in a variable.

The RAM memory is modeled by the equations of the logic gates the RAM memory is built of - so it's not easy to see/detect that these logic gates represent RAM memory.

So my problem is to find out which n bits represent the data stored in the RAM so I have to store these bits in variables.

  I'm going to treat every gate as having a state

This would be possible. However I fear that the simulation will cause wrong results if the variables contain contradictory information when I store more than n bits (e.g. if one variable says: "the bit in RAM has the value 0" and the other one says: "the bit in RAM has the value 1").


texts: Fundamental algorithms in formal language-automata theory

texts: I'm willing to take a course in formal languages and automata theory , where we will explore side by side a functional programming language to implement the different algorithms we will encounter ,despite i am new to the language , i am assuming i've learned what's nessecary to move to the theoretical part , so i'm wondering what are the must-knows of FL & AT to a programmmer , that is what are the most fundamentals algorithms one necesserily have to know while studying formal languages and automata theory ?


texts: Pushdown Automaton for $L = \{ w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2 \} $

texts:
So i know that $L =$ { $ {w_1 w_2 : |w_1| =|w_2| , w_1 \neq w_2} $ }

is a CFL, but i cannot make a PDA for it because it doesn't make any sense to me why this is CFL

i even know the grammar for it but i cannot draw the PDA because :

even if we determine the middle of the string, if we push every word of w1 to the stack, then how can we compare it to w2 when we can only POP??? how is that even possible?

i mean how can i compare two strings and determine if they are the same if i can only compare the last word of first string to the first word of the second??!

also it would help me a lot to understand if you could say which of these are CFL and which are not :

$L_1 = \{ w_1 w_2 : |w_1| =|w_2| , w_1 = w_2 \} $

$L_2 = \{ w_1 w_2 : |w_1| \neq  |w_2| , w_1 \neq w_2 \} $

$L_3 = \{w_1 w_2 : |w_1| \neq |w_2| , w_1 = w_2 \} $

there was a post about this but nobody answered how can we construct such a PDA?
i don't want to just convert the grammar to PDA with algorithms, i want to understand how the PDA is comparing two strings?

PDA for { xy : |x| = |y|, x ≠ y} from its grammar, and intuition behind it


texts: How to find whether a grammar is ambiguous?

texts:
$$S\rightarrow aAB$$
$$A\rightarrow bBb$$
$$B\rightarrow A|\epsilon$$

I'm choosing the string abbbb.

First left most derivation is the following:

$$S\Rightarrow aAB\Rightarrow abBbB\Rightarrow abebB\Rightarrow abebA\Rightarrow abebbBb\Rightarrow abebbeb = abbbb$$

Second left most derivation is the following:

$$S\Rightarrow aAB\Rightarrow abBbB\Rightarrow abAbB\Rightarrow abbBbbB\Rightarrow abbebbB\Rightarrow abbebbe = abbbb$$

Can someone tell me whether I'm correct in saying that the grammar is ambiguous?

This question has been taken from chapter 5 of "An Introduction to Formal Languages and Automata" by Peter Linz 5th Edition. The question states to prove that the grammar is unambiguous (however it is not). Hence, the aim of posting this question is to make sure that I've understood ambiguity and distinction between parse trees properly. I'm studying formal languages on my own and do not have the luxury of an instructor.


texts: Selecting k "special" nodes in a graph such that the min distance is maximized?

texts:
Lets say we have a graph $G$ with $|V|$ nodes. We wish to select $k$ such nodes while optimizing the following attribute:

maximize: for each $i$ and $j$, where $i \neq j$,  $min(distance(v_i, v_j))$

Hope that makes sense. We'd like to pick $k$ nodes such that the distance between the closest pair of distinct nodes is maximal.

Currently, my plan is to pick a node in random, find the node furthest away from it $v_0$ and the one furthest away from that node $v_1$. Now recursively look for nodes such that maximize the minimal distance from the selected node set. Meaning, nodes that have the greatest distance possible from the any selected node and specifically the member closest to them of the previously selected set of nodes.

The issue with this is that it's greedy and therefore possibly very inaccurate.


texts:
Given is the NFA N:

What's the language of this NFA? What's its complement?

I'm learning for a test and I'd like to know if I solved this task correctly.

The language L of the NFA N should look like this:

L(N) = {x ∈ Σ* | x mustn't include 'aba' and x mustn't end with 'ab'}

I have tried several different words and I couldn't find any word that breaks my language L(N).

Assuming this is correct, how would the complement of L(N) look like?

It needs to be the opposite, right? So something like that (~ stands for complement):

~L(N) = {x ∈ Σ* | x must include 'aba' and x must end with 'ab'}


texts: Closure properties of a non-regular language under complement?

texts:
Assume I have L1 which is a regular language, so we know since regular language is closed under complement, the complement of L1 is also a regular language.
But let's say if the complement of L1 is a non-regular language, is it safe to conclude that L1 is a non-regular language as well?

Since I'm trying to prove a language L1 is not a regular language, and the pumping lemma doesn't work well with this case. But I can easily prove the complement of L1 is not regular, I'm wonder if that option is possible.


texts: Fastest way to find the smallest interval of a number

texts:
Here is my problem : Given a range, let's say 0 to 10.000, and some numbers in that range (like 23, 1456, 280, 3586), I want to find, for any input x, the two closest numbers to x, the smaller one the greater one. For example for x=100, the two numbers are 23 and 280, for x=350 they are 280 and 1456.

Is there a faster way to do that than a binary search on the list of numbers ? I vaguely remember the existence of a data structure for this task, but in my case the numbers are dynamic and will change during the execution of my algorithm.


texts: How many floating point ops were performed worldwide over a time interval

texts: I am looking for information regarding the evolution of computing capability. Specifically I would like to know how many floating point operations were performed worldwide from, say, the deployment of ENIAC to the first moon landing... Or any other time interval before, say, the '80s. is this a question that I can estimate based on existing data?


texts: LBA for $L = \{a^nb^{2n} \mid n\geq1 \}$

texts: I want to construct a linear bounded automata for the language $L = \{a^nb^{2n} \mid n\geq1 \}$ . I know how LBA works but I don't have an idea how it can count the numbers of a's and check if the b's are 2 times more than a's. I would like to to hear some suggestions.


texts:
I made a SLAM (Simultaneous Localization And Mapping) using Extended Kalman Filter (EKF) and it works really good, but I want to see if it works better using Neural Networks.

For the EKF I used an initialization step, prediction step and update step,how can I change that to Neural Networks?

Thanks


texts: Representation of the concatenation at the type level

texts:
I would like to learn more about concatenative programming through the creation of a small simple language, based on the stack and following the concatenative paradigm.

Unfortunately, I haven't found many resources concerning concatenative languages and their implementation, so excuse me in advance for my possible naivety.

I therefore defined my language as a simple sequence of concatenation of functions, represented in the AST as a list:

data Operation
    = Concat [Operation]
    | Quotation Operation
    | Var String
    | Lit Literal
    | LitOp LiteralOperation

data Literal
    = Int Int
    | Float Float

data LiteralOperation
    = Add | Sub | Mul | Div

The following program, 4 2 swap dup * + (corresponding to 2 * 2 + 4) once parsed, will give the following AST:

Concat [Lit (Int 4), Lit (Int 2), Var "swap", Var "dup", LitOp Mul, LitOp Add]

Now I have to infer and check the types.

I wrote this type system:

data Type
    = TBasic BasicType   -- 'Int' or 'Float'
    | TVar String        -- Variable type
    | TQuoteE String     -- Empty stack, noted 'A'
    | TQuote String Type -- Non empty stack, noted 'A t'
    | TConc Type Type    -- A type for the concatenation
    | TFun Type Type     -- The type of functions

That's where my question comes in, because I don't know what type to infer from that expression. The resulting type is obvious, it is Int, but I don't know how to actually entirely check this program at the type level.

At the beginning, as you can see above, I had thought of a TConc type that represents concatenation in the same way as the TFun type represents a function, because in the end the concatenation sequence forms an unique function.

Another option, which I have not yet explored, would be to apply the function composition inference rule to each element of this expression sequence. I don't know how it would work with the stack-based.

The question is so: how do we do it? Which algorithm to use, and which approach at the type level should be preferred?


texts: Proving number of comparisons in insertion and bubble sort

texts:
I was able to come up with few examples where number of comparisons in insertion sort were fewer than that of bubble sort and some examples where they were same.

However I am not able to prove that number of comparisons in insertion sort will always be less than or equal to that of bubble sort.

For insertion sort, I am considering the standard variant which is available here https://en.m.wikipedia.org/wiki/Insertion_sort . For bubble sort, I am considering the variant available here https://en.m.wikipedia.org/wiki/Bubble_sort

Can someone please help me?


texts: Techniques to prove lower bounds on randomized algorithms

texts:
I am interested in proving lower bounds for AM-like languages. The usual techniques for lower bounds in non-probabilistic machines don't work for probabilistic machines.
Intuitively, when I think about showing lower bounds I usually think about showing for any algorithm $A$ some "bad input" that would contradict either its correctness or would take more time than the bound we want to show. But for randomized algorithms, a "bad input" for $A$ might still be correct and within the time bound, but only with some probability. This confuses me on how I should approach proving such lower bounds, as it looks much harder to show that the "bad input" is "bad" with high probability, and not only "bad" for one specific coin toss.
I would be glad if you could give me an example of a language with such a lower bound, and how to prove it.


texts:
I would like to know whether the following problem is a standard problem that has been considered in the research literature. I performed some searches, which have not produced results. I call this problem the Maximum Weighted Disjoint Set Union, which is obviously not the name by which the problem is known (if it is known).

In this post, the problem (stated slightly differently) is related to Weighted Independent Set. However, I will show below that this problem is simpler than independent set and, even if it possesses the same time complexity, it may allow for a solution with smaller run-time requirements.

The problem is as follows. We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$). We're also given a set $S=\{S_1,S_2,\ldots,S_n\}$, where $\forall_iS_i\subseteq U$. Furthermore, each set $S_i$ is assigned a weight $w_i$. The task is to find a set $S'\subseteq S$, such that the sets in $S'$ are disjoint and the sum of their weights is maximal.

One might think that this problem corresponds to weighted independent set. Namely, the vertices in the graph correspond to the sets in $S$ and there is an edge between two vertices if the corresponding sets have non-empty intersection.

Note, however, that important information is lost in the process of translation. For an example of such a loss, suppose $S_1=\{1,2\}$ with $w_1=1$, $S_2=\{3,4\}$ with $w_2=1$, $S_3=\{1,2,3\}$ with $w_3=3$. Note that we do not need to consider a cover $S'$ that contains both $S_1$ and $S_2$. This is because $S_3\subseteq S_1\cup S_2$ and $w_3>w_1+w_2$. The information needed to perform this cut-off is not present in the corresponding instance of the weighted independent set problem.

If I am correct in this reasoning, then this problem deserves attention and I am wondering whether it received any. In addition, I am hoping to get an off-the-shelf implementation in C++ which I can use (this problem happens to be a sub-problem of the research problem in a different field that I am trying to solve).


texts: Context free grammar for $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$

texts:
I try to find a context free grammar for the language  $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or }  \vert u \vert_b \neq \vert v \vert_b\}$. There is a hint in the task that one should first construct the context free grammar for cases such as
$L_1 = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a > \vert v \vert_a\}$ and later combine all of these.

I would appreciate a hint to come up with $L_1$. I do not know how construct $u\#v$ such that $u$ and $v$ are free independent from each other except of the fact that $u$ has more $a$'s than $v$. I tried to build my language around the $\#$ and also tried to move the $\#$ in the direction of the most appearing $a$'s but none of my attempts worked.

What is the proper way to tackle such constructions in general?


texts:
Given two NP-Complete languages A and B, show that the language:

$L = A\bigoplus B =\{a\bigoplus b \mid a \in A, b \in B, |a|=|b|\}$

is not necessarily NP-Complete.

Remember $a\bigoplus b$ when $|a|=|b|$ gives 0 when they have the same digit and 1 otherwise.

Example:  0110$\bigoplus$ 0101 = 0011

I have tried to solve this in my exam only was not so accurate..Help needed.


texts: Solving $T(n)=3T(\lfloor \frac{n}{3}\rfloor) +2n\log n$

texts:
I want to solve $$T(n)=3T\bigl(\bigl\lfloor \frac{n}{3}\bigr\rfloor\bigr) +2n\log n,$$
with base case $T(n) = 1$ if $n \leq 1$.
I am sure that the Master Theorem does not work. I am trying a lot with the substitution method, but I am very frustrated since I can't find a solid expression. Does any one have a good "hint" or good idea on how to solve this in a nice way?


texts: How to find longest possible identical sequence in Array A and B?

texts:
You have to arrays of single digit numbers. (0 - 9).

A = [....1 billion elements....];
B = [3,5,8,1,2,5,8,3,4,9,1,0,2];

I want to find combo of as few as possible subsets that of array B in A.

So whole Array B could be in Array A by coincidence since it's very large and that would be the largest match as whole sequence is there. Or you could have subset of array B, [8,3,4,9], at index ex: i = 3800443...

Now my goal is to convert Array B to references based on Array A.

So If I give you object like this:

{
  block1: {i: 48938, len: 388},
  block2: {i: 2828, len: 3},
  ...
}

you'd be able to reconstruct array B if you had array A.

One mistake would be to go and find biggest subset only. Then the solution would have biggest subset, but not minimum amount of subsets possible.

Example:

a = [1,3,4,4,3,0,8,3,5,5,2,8,3,1,0,9];
    |^||^||^||^||^||      ^     ||^|

Although this has longest subset, but It ended up with 6 blocks. Whereas,

b = [1,3,4,4,3,0,8,3,5,5,2,8,3,1,0,9];
    |    ^    ||     ^    ||    ^   |

here each subset might not be the longest but there are fewer subsets to cover whole array.


texts:
Given an unsorted array of size n, it's obvious that finding whether an element exists in the array takes O(n) time.

If we let h = log n then it takes O(2^h) time.

Notice that if the array is sorted, a binary search actually takes O(h) time (which is polynomial) but the binary search cannot apply to an unsorted array.

Is it possible to prove that the problem to find an element in an array (yes or no) is NP complete in terms of h. What problem should I reduce from and how to reduce?

A more formal definition of the problem is given below.

We have an oracle, which is a binary tree of height h with each node having random values. I.E. a tree that DOES NOT have the property that all values in the left subtree of a node must be smaller than the value in the node or all values in the right subtree of a node must be greater than the value in the node. However all nodes in the oracle tree are guaranteed to have value between 0 and 2^h-1.

  The input is a number to be searched. The input is guaranteed to have value between 0 and 2^h-1. (The input has h bits)

(Let's say we are searching through the same array every time and hence we have the same oracle every time so the tree itself is not a part of input.)

  The output is YES or NO, indicating whether the input is in a node of the tree or not.

Question: whether this problem is NP complete or not in terms of h. This problem is NP because if a path to the YES node in the tree is given it can be verified in O(h) time.

Assuming NP != P, since the problem is in NP it must be either NP-complete or P (Apparently there is something called NP-intermediate (credited to Nicholas) so that's another possibility as well).
If it is NP-complete, what problem can be used to reduce to this problem?

Note that if the oracle tree has the property that left subtree of a node is less than the node and right subtree of a node is greater than the node then the problem is in P and NOT in NP complete because binary search can be applied.

Intuitively, this problem can be viewed as a non-deterministic turing machine and every single possible path needs to be considered but this intuition cannot be used to "prove" the problem is NP complete. I want to know if we can reduce any known NP-complete problem to it.

Reference: (Original Post)
https://stackoverflow.com/questions/28847966/array-search-np-complete


texts: Is there any specific model/theory that proposes that the universe is an oracle machine?

texts:
Is there any specific (and well known/famous) model/theory that proposes that the universe is an oracle machine?

Physicist Roger Penrose said his book "The Shadows of the Mind"

  It would be just as possible, in principle, to have a universe that runs deterministically as an oracle machine as it would to have one that runs deterministically in a Turing machine

But I could not find any specific model. Do you know of any? Did Turing himself propose that?


texts:
I am with the following question, because I do not know if what the following paragraph indicates:

Does this refer to this image?

Maybe to this other?

If not, tell me what you are referring to please. Thanks in advance


texts: Count all possible unions in a collection of sets

texts:
Say we have a collections of sets $\mathcal X = \{X_1, \dots, X_n\}$ (not necessarily disjoint), and we want to count the number of possible unions of sets in $\mathcal X$, i.e. the size of $\{\bigcup_{Y \in \mathcal Y} Y \,|\, \mathcal Y \subseteq \mathcal X \}$.

Is there a name for this problem?
What are the fastest algorithms to solve this problem?


texts: Is there C++ code that takes infinite time to compile?

texts: Is C++ as a formal language recursively enumerable? If yes, is there any invalid C++ code that takes "infinite" time to compile?


texts:
I need to solve the following optimisation problem and I can't come up with any solutions. Is there any algorithm to solve this type of problem. I tried to think of a greedy algorithm or brute force, but couldn't solve it.

Input :
$ n_1, n_2, n_3, n_4, n_5$ : Positive integers
$ a_1, a_2, a_3, a_4, a_5 $ : Positive integers
$ p_1, p_2, p_3, p_4, p_5 $ : Positive integers
$ Q $ : Positive integer

Output :
$ m_1, m_2, m_3, m_4, m_5$ : Non- negative integers

Minimize :
$ \sum_{i=1}^{5}{m_i a_i p_i}$

Constraints :
$ \forall i : m_i \geq n_i $ OR $ m_i = 0 $
$ \sum_{i=1}^{5}{m_i a_i} \geq Q$


texts: Let $m$ be the number of states (without the halting-state) of a deterministic turing-machine with $\Sigma$ = {} and $\Gamma$ = {$\square$, 0, 1}. Let $G(m)$ be the maximum number of ones, which can be generated by a deterministic turing-machine, before going into the halting-state. Prove that $G(m)$ $\in$ $\Omega(2^m)$. (This is about the so called "busy beaver" problem, with the mathematical rado-function $\Sigma(N)$ or $bb(N)$.) Who can me help with that?


texts: Flawed argument in the proof of function extensionality in cubical type theory?

texts:
I am reading the lectures about cubical type theory in this github repo. In lecture 1 the author defines function extensionality the following way:

funExt (A B : U) (f g : A -> B)
       (p : (x : A) -> Path B (f x) (g x)) :
       Path (A -> B) f g = <i> \(a : A) -> (p a) @ i

and writes

To see that this makes sense compute the end-points of the path:

  (<i> \(a : A) -> (p a) @ i) @ 0 = \(a : A) -> (p a) @ 0
                                  = \(a : A) -> f a
                                  = f

I don't follow. Specifically, when we replace (p a) @ 0 with f a in my mind we use the following fact: \(a : A) -> (p a) @ 0 = f a to rewrite (let's give names to the left and right side) fpa = \(a : A) -> (p a) @ 0 into fa = \(a : A) -> f a. But isn't this by itself using function extensionality with f = fpa, g = fa?

If I am not mistaken, this argument is circular. Can anyone clarify?


texts:
I seem to remember seeing somewhere (many years ago) a writeup of the math behind calculating the outline of Metafont glyphs.  The basic idea is you have a "pen" that is a circle or oval, that you then trace along a cubic spline.  The question then is can you define the curve that is the outline of that stroked glyph.

Anyone know where I could find such a writeup?


texts: Simple interepretation problem regarding Polynomial Hierarchy?

texts:
So $NP$ stands for problems where we have small verifiable witnesses for $YES$ instances and $coNP$ for small verifiable witnesses for $NO$ instances. How does this work for

$P^{NP}$
$NP^{NP}$
$coNP^{NP}$
and so on?


texts: Understanding the Bitcoin White Paper's Notion of "Signing" and "Verifying"

texts:
Consider from the Bitcoin white paper a graphic that includes dotted arrows, labeled "sign" and "verify":

What does it mean to "sign" and "verify", as outlined in this paper? Are the terms "private key" and "public key" used in the same way that they are in the RSA encryption algorithm?


texts: Verifying execution of code in trustless environment

texts:
Let us assume I have a Program P running on remote computer generating output O. Without trusting the remote environment and not having to verify the output O, is there is a way to validate that Program P has indeed been executed and resulted in output O ?

Let me know if the question is too vague. I will clarify.


texts:
In my program, it draws them by offsetting every other row by half of the width, as pictured above. Each tile can be referenced by coordinates, also shown above.

I want to know how many blue tiles are accessible from a certain starting tile and a series of "roads." In this example, three blue tiles can be reached.

How would I represent roads? This is what I would need to know about it:

how it is rotated (for drawing)
which hexagons it borders
which other roads it touches, if any
where it should be drawn

I assume I could use recursion to to count the accessible blue squares if the above conditions are met.


texts: Every connected graph on more than 3 vertices has two vertices whose removal doesn't disconnect it

texts:
Prove that every undirected connected graph with $|V| > 2$ has at least two vertices such that if one or both are removed (along with their incident edges) the resulting graph is still connected. Describe an efficient algorithm to find two such vertices.

How would I go about solving this?


texts: Does this pushdown automaton describe the language {$a^n b^n c^i \in \{a,b,c\}^*\ |\ n \ge 0,i\ge 0$}?

texts:
I've just been learning about pushdown automata and I'm trying to create one that describe the following language:

{$a^n b^n c^i \in \{a,b,c\}^*\ |\ n \ge 0,i\ge 0$}

What I have is the following:

(state, symbol, top of stack), (next state, what goes to stack).

$(s,$e$,$e$),(f,$e$)$

$(s,a,$e$),(s,d)$

$(f,b,d),(f,$e$)$

$(f,c,$e$),(f,$e$)$

Where $s$ is the starting state, $f$ is the final state and e is the empty word.

Do I have the right idea? My worry is sending the automata to the final state while there are still entries in the stack - is that allowed?


texts: Prove that $r$-ary entropy $H_r(s) = H(s) / \log_2 r$

texts:
Prove that $H_r(S) = H(s) / \log_2r$.

I'm not sure how to prove this. Any help would be greatly appreciated!


texts:
I'm a wannabe mathematician, whose master's thesis is (by the looks of it) going to focus on a certain "compiler", used to produce learning materials from a subset of $\LaTeX$, in the context of mathematics education. I'm of course going to have to talk about the compilation process in general, and was planning to discuss the mathematical abstractions related to it (this being a master's thesis in mathematics), and then use those to describe the compiler.

I have no experience in the field whatsoever, however, and was wondering whether the concepts of regular expressions and languages, automata and the like are actually used to model (and|or) describe the functionality of compilers in a professional setting. Is it typical (even in the industry) to use these methods of modelling compilers, or are there better alternatives available?

I simply stumbled upon these basic concepts in a certain course handout, and they seem useful, but I want to be certain.


texts: why does Register write(RW) stage of a single cycle processor takes the shortest time to execute? Explain your answer

texts: I can't seem to find the explanation for why RW stage of a single cycle processor takes the shortest time to execute. Can anybody explain why this is so.


texts: Why does x86 has explicit register definitions, and RISC's doesn't?

texts:
For example, on x86, we have a set of general registers, each named to the function it carries out.

We have an Accumulator, which is a storage for a results of different fixed point operations, we have a Base register, which is used for addressing elements in the array, a Cycle register, which holds a incremented or decremented counter for cycles, we have a Data register, which can hold an operand for arithmetic operations, and many many others (like base and stack pointers, indexes, and etc.)

But on typical RISC architectures, like SH4, for example, you won't find such an explicit names for registers. On Sh4, for example, there's no explicit name for register, which must hold a stack pointer, so you can store it elsewhere upon your choice from 16 available registers. Same for arithmetic operations, and so on.

So why it is that?
It is simply a matter of design, choices, taken by Intel engineers, or some significant sign of RISC processors?


texts: How can average queuing delay exceed 1 if the $La/R \leq 1$?

texts: Consider a router with a packet arrival rate of $a$ where each packet has $L$ bits, and a transmission rate (in bits/s) of $R$. My textbook describes the traffic intensity as $\frac{La}{R}$ and states that as $\frac{La}{R} \to 1$, the average queueing delay approaches $\infty$. I'm just struggling to understand why this is the case. Is it because this increases the chance that $La$ exceeds $R$ during periods of time, and that long queues can accumulate?


texts: Is the Choice operator implementable on $\pi$-calculus?

texts:
I was reading about $\pi$-calculus, and some authors include in the basic operations a Choice operator $P \oplus Q$ which means that either $P$ or $Q$ will be executed, but not both.

On page 8 of "Applied $\pi$ - an introduction" (available on http://www.cl.cam.ac.uk/~pes20/apppi.ps ), the author says that the coice operator is not necessary because it can be implemented as:

$$
P \oplus Q  \triangleq \textbf{new} \  x \  \textbf{in} \  ( \bar{x}z.0 | xz.P | xz.Q )
$$

But it did not convince me. For example, taking $P=ab.0$ and $Q=cd.0$:

$$
\bar{a}y.0 | (ab.0 \oplus cd.0) \rightarrow 0 | 0 \rightarrow 0
$$

but

$$
\bar{a}y.0 |(\textbf{new} \  x \  \textbf{in} \  ( \bar{x}z.0 | xz.ab.0 | xz.cd.0 )) \rightarrow
$$
may reduce to
$$
\bar{a}y.0 |0|ab.0|(\textbf{new} \  x \  \textbf{in} \  xz.cd.0 ) \rightarrow 0 | (\textbf{new} \  x \  \textbf{in} \  xz.cd.0 )
$$
but it may also reduce to
$$
\bar{a}y.0 |0|cd.0|(\textbf{new} \  x \  \textbf{in} \  xz.ab.0 )
$$

which will deadlock without ever sending $y$ through $a$. My question is: where are the mistakes? Is my reasoning wrong? Is this implementation of the choice operator wrong? Is the $\pi$-calculus required to backtrack and find the path with the most reductions?

I'm really sorry if my question makes no sense, I have very little formal training on this subject it is mostly curiosity so that I can implement a $\pi$-calculus simulator.


texts:
I am trying to understand the proof why Gale–Shapley algorithm is optimal, however i am unable to do so. Could you please expand the proof, since the proof on this page https://sites.google.com/site/stablemarriageproblem/intro and here
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f10/Site/Materials/Lectures/Lecture21/lecture21.pdf
relies crucially on the fact that the disagreement happens for the 1st time when a man M approaches a woman W and we are trying to prove that in no matching matching M can be paired up with W.

If possible could you also give alternative proofs.


texts:
At the moment I'm trying to understand nested word automatons but I don't get the point quiet right. Let's say I have the alphabet $\Sigma = \{c,r\}$ and I want ot recoginize the  languge $\mathcal{L} = \{ \langle  c^n r\rangle^n \}$. On slide 14 of this presentation I found the following automaton which should recognize $\mathcal{L}$.

After reading the last $\langle c$ the automaton is is state $(q_1,p_1)$ and, since $\delta_r: Q \times P \times \Sigma \rightarrow  Q$, after reading the first $r\rangle$ it switches to $(q_2)$. So how does the automaton keep track of reading the same ammount of $\langle c$ and $r\rangle$? Do we have to keep the hierarchical state in mind for each call symbol? If so wouldn't we need a stack again for that?


texts: What is the definition of$\mathcal{Mod} P$ counting complexity class?

texts:
Question : What is the definition of $\mathcal{Mod} P$ counting complexity class?

I am not getting anything relevant about this complexity class on Google search. If it is available on Wikipedia, please share a link.

$\mathcal{Mod} P$:  A set $L$ is in the class $\mathcal{Mod} P$ if there exist functions $f \in \#\mathcal{P} $ and $g \in \mathcal{FP}$ such that string $x$, and $g(x) = 0^p$ for some prime $p$ and

$$x \in L \iff f(x) \ncong 0 \pmod{p}\,.$$

I am not able to understand what it is mean by  $g(x) = 0^p$ for some prime $p$.

Reference  : Köbler and Toda, On the Power of Generalized MOD-Classes. In Proceedings of 8th Annual Structure in Complexity Conference, IEEE, 1993. PDF


texts: How to prove a LTL formula correct in a specific model?

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

$Whether\ the\ LTL\ formula\ M, q_3\ \models (X\ \lnot a) \rightarrow (F\ G\ \lnot a)\ is\ established\ or\ not\ in\ this\ model\ M?$

And there is the description of the model.
.

I think it is correct, because the next state of $q_3$ is $q_1$ or $q_2$ and the next state of $q_1$ is $q_2$. So I get an infinite loop about $q_2$, which satisfies $F\ G\ \lnot a$. But I only can give the thought of my prove in natural language not mathematical rigor way.

if not mind, could anyone tell me my thought is right or wrong and prove it in a mathematical rigor way?

Thanks in advances


texts: Constructing Turing Machine for division with 8

texts:
Can someone help me to construct a Turing Machine for this function:

$f(n) = \frac{n}{8}$. If $n \mod 8 = 0$, then
$f(n)$ is undefined.

So the machine should somehow first prove if the number (which is represented in binary) is divisible by $8$ . That means for numbers like $1000$, $10000$, $11000$ and so on. But I don't know how can I check this.

EDIT:

The result from the division is when we delete the last 3 digits in the binary representation of the number. I think this is not so hard. But I still have a problem with the first part. How can I prove if the number is divisible?


texts: Reduction from minimum dominating set to the set cover

texts:
To solve the min dominating set problem of a graph G, we can reduce it to a set cover problem.

For example to find the MDS of the graph G:

We can create an instance of the Set Cover problem by:

Introducing the universe U to be equal to all vertices of the graph: U={0, 1, 2, 3, 4}.
For every closed neighborhood of a vertex in G, we introduce a subset S:

s= {{0, 1}, {0, 1, 2}, {1, 2, 3, 4}, {2, 3, 4}, {2, 3, 4}}

A minimum set cover solution of the instance (s, U) is similar to a minimum dominating set solution in the graph G.

My first question is how we can prove that this reduction is correct, and will give the correct MDS solution for every graph. In our example, the reduction works well and give the correct result.

My second question is how this reduction is related to the reduction when we deal with NP-complete proof(for example we can prove that the MDS problem is NP-complete by reduction to the vertex cover problem).

Are those reductions related?
Thank you


texts: How to prove a bound function for a sequence of numbers?

texts:
Let $G_n$ be defined by

$$G_n = \begin{cases} 1 & n=0 \\
2 & n = 1 \\
3 & n = 2 \\
4 & n = 3 \\
2G_{n-1}-2G_{n-3}+G_{n-4} & n\geq4
\end{cases}$$

How can I prove that $f(n) = n$ is a bound function (or loop variant) for the above sequence?


texts:
Consider the following two arguments

  "For every non deterministic TM M1 there exists an equivalent
  deterministic machine M2 recognizing the same language."
  "Equivalence of two Turing Machines is undecidable"

These two arguments seem a bit contradicting to me.
What should I conclude from these two arguments?


texts: What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?

texts:
Everybody knows the Chomsky-hierarchy for describing formal languages and big-O notation for describing time and space complexity of a function.

We know, that each class in the Chomsky-hierarchy corresponds to an atomata, that can recognize any language in the corresponding class.

The question is: What is the worst-case time and space complexity of these automatas given any language of the above class?

What I found out already:

Chomksy-3 class, the regular languages can be recognized by an FSM of n-states where n is a finite number. IMO this makes it require O(n) space and O(l) time, where l is the length of the input.

Chomsky-2 class, the context free languages can be recognised by a Non-deterministic pushdown automaton. CYK algorithm run $n^3 * G$ where n is the length of the input and G is the number of rules in the grammar in Chomsky Normal form.

But how much space needed? Do we have better bounds?

Chomsky-1 class, the context sensitive languages can be recognised by a Linear-bounded non-deterministic Turing machine.

This class seem to depend on the length of the context to be recognised. Maybe in exponential time.

Chomksy-0 class, the recursively enumerable languages can be recognised by Turing machine.

Can anything stated for this class? If not, why?
Maybe the $P \stackrel{?}{=} NP$ problem is related.

Are the above statements true?

Please give citations to your answer!


texts: Basic question about 4-way set associative

texts: When the CPU writes or reads from the memory and stores the value that was read or written into L1 cache. Do the CPU store the whole block( 1 block , leaves the other three ways empty) or the whole set ( 4 blocks)?


texts: Running time analysis on computing the largest factor of an integer using Euler's subtraction-based algorithm

texts:
For the following algorithm,

$X\leftarrow \{(i, n - i) | i = 1, ..., n- 1\}$
while $\max_{(a, b)\in X}b > 0$ do
$\quad X \leftarrow \{(|a - b|, \min\{a, b\})|(a, b) \in X\}$
return $\max_{(a, b)\in X}a$

show that the algorithm does not run in $o(n \log ^k n)$ for any constant $k$.
Summary: the algorithm uses the Euler's subtraction-based algorithm to compute the largest factor of $n$ in $1$ to $n - 1$.
My work: I can prove the upper bound case that $T(n) \in O(n^2)$. Since $n = (a + b)$ is strictly decreasing, gcd computation for each tuple takes at most $n$ operations. Since there are $n-1$ elements, $T(n) \in O(n^2)$.
I can also prove the lower bound case that $T(n) \in \Omega(n \log n)$. The best case for computing gcd of a single tuple occurs if $a = c_1 \cdot b$ or $b = c_2 \cdot a$ for $c_1, c_2 \in \mathbb{N}$. Then, the running time is $\Omega{\log n}$. Therefore, the total running time is $T(n) \in \Omega(n \log n)$.
My problem: But I don't know how to proceed from here. Basically, I need to prove $T(n) \in \Omega{(n^{1+\epsilon})}$ for $\epsilon > 0$. This means I need to prove something polynomial with the gcd computation of a single tuple.
Can anyone help me out with this problem?


texts: Algorithms for two and three dimensional Knapsack

texts:
I know that the 2D and 3D Knapsack problems are NPC, but is there any way to solve them in reasonable time if the instances are not very complicated? Would dynamic programming work?

By 2D (3D) Knapsack I mean I have a square (cube) and a I have list of objects, all data are in centimeters and are at most 20m.