texts: I need help in this regural expression exercises

texts:
Write a regular expression for the language of words over $\{0,1,2\}$ satisfying the following requirements:

  The word has length at least 3.
  The last symbol is 2.
  The second to last symbol isn't 0.
  The combination of the last two symbols doesn’t appear anywhere else in the string.


texts:
Is it true that the set $\{ 0^{n^2} \mid n \in\mathbb{N} \}$ is not regular because it does not grow linearly?

  Regular sets are called regular because if you have a regular set then you can always pump it up (pumping lemma) in regular intervals and get other things in the set. They string out at very linear intervals. That's why anything that grows in other than linear intervals is not regular.

Therefore, $\{ a^{n^2} b^n \mid n \in\mathbb{N} \}$ is not regular, right? Also, I know that $\{ a^n b^n \mid n \in\mathbb{N} \}$ is not regular, but what about $\{ a^{cn} b^{dn} \mid n \in\mathbb{N} \}$ for any integer coefficients $c$ and $d$?


texts: Heap-like data structure allowing peek at largest & smallest

texts:
For the purpose of implementing an optimization algorithm (finding the minimum of a multivariate function) I want to create a data structure that supports the following operations:

load from array
Peek at maximum element (but don't destroy it)
Peek at next-to-maximum element
Peek at minimum element
decrease the maximum element

Once initialized, the data structure always stores the same number of elements.

Currently I'm just using an unsorted array, and searching the array each time to find the max, next-to-max, and min elements, and updating the max element when necessary.

I considered using a heap / priority queue, but those don't seem ideal, as they support adding and removing elements, which I don't need to do. They also don't natively support "decrease the maximum element", just "increase an arbitrary element" so I'd have to extract-max and then re-add it.

I also considered a sorted array in a ring buffer, which seems like it would be better than just a sorted array, as I'd only have to move at most half of the list.

Wikipedia talks about some complicated data structures (Fibonacci heaps) that I vaguely remember from my sophomore algorithms class in college, but those seem like overkill (and they also support features I don't need and don't support features I need).

Well, now I search again and I find my question is sort of kind of a duplicate of Increase-key and decrease-key in a binary min-heap


texts: Can maximum matching algorithms be used for maximum weight matching?

texts:
There are two fast algorithms for maximum matching on general graphs:

Micali and Vazirani in $O(E\sqrt{V})$.
Mucha and Sankowski in $O(V^{2.376})$.

Can these be also used for maximum weighted matching on general graphs? Note that Edmonds' Blossom algorithm can be used to solve both problems.


texts: Trying to figure out the best way to approach this problem with Computer Vision

texts:
Newbie to CV here so sorry of this is basic.  Here's the deal, I have a program that I run many times. and each run I produce a screenshot.  I need to compare screenshots from N-1 and N runs and make sure they aren't different in any dramatic way.  Of course there are some minor changes like logos and pictures getting updated, etc.
SO far I've used something as simple as absdiff from opencv to highlight the difference regions and then use some sort of threshold to determine whether something passes or not. But I want to make it slightly intelligent but I'm not 100% sure how to proceed.  Google hasn't yielded ghe best answers.
Essentially, I want to train the model on many different pairs of images and have the output be binary, yes or no depending on whether it should pass or not.  In theory, I should be able to plug in 2 images and based on previous training, it should be able to tell me whether there is significant difference or not.  What are some ways I might approach this, particularly with regards to what kinds of models to use.  Thank you!


texts: basic linear programming - how to find feasible solutions

texts:
I'm new to linear programming and can't wrap my head around something.

Let P be a LP in standard form

$$\begin{array}{ll} \text{maximize} & t x\\ \text{subject to} & r x \leq s\\ & x \geq 0\end{array}$$

I figured that the dual program is

$$\begin{array}{ll} \text{minimize} & s y\\ \text{subject to} & r y \geq t\\ & y \geq 0\end{array}$$

However I'm unsure how to find what is a feasible solution for P and not for D and vice versa. Intuitively, if $s$ is positive P should have a feasible solution, but that seems to be wrong and/or incomplete as an answer.


texts: In normative order evaluation, is there distinction between call by value, call by reference, call by sharing, etc?

texts:
Consider different ways of evaluating a procedure call and its arguments.
Essentials of Programming Languages says

  All the parameter-passing mechanisms (natural parameter passing, call by value, call by reference) we have discussed so far are eager:
  they always ﬁnd a value for each operand. We now turn to a very different
  form of parameter passing, called lazy evaluation.

What I understand it is that:

In applicative order evaluation (eager evaluation), we distinguish between call by value, call by reference, call by sharing, etc.
In normal order evaluation (lazy evaluation), is there still similar distinction  between call by value, call by reference, call by sharing, etc?


texts: How much data could I store on a Rubik's Cube?

texts:
Google tells me that a standard 3x3x3 Rubik's Cube has 43,252,003,274,489,856,000 permutations. If I wanted to store data on that Rubik's Cube, how much could I store?

The only way I see to store data on a Rubik's Cube is to assign an integer to each permutation, then convert that integer into binary. It would take 66 bits to store an integer of that size, so the Cube could theoretically hold 65 bits of information by my calculations.

Is there any way to eke out more than 65 bits of storage from a Rubik's Cube?


texts: How do I calculate the time complexity of this memoized algorithm?

texts:
The problem is: count all increasing subsequence of s.
def main():
    print(count([3,2,4,5,4]))

def count(s: list) -> int:
    n = len(s)
    counter = 0

    result = {}

    if n == 0:
        return 0

    for i in range(n):
        counter += recurse(s[i+1:], s[i], result)

    return counter

def recurse(s: list, x: int, result: dict) -> int:
    n = len(s)
    counter = 0

    if n in result:
        return result[n]

    if n == 0:
        return 1

    for i in range(n):
        if s[i] > x:
            counter += recurse(s[i+1:], s[i], result)

    result[n] = counter + 1

    return counter + 1

Can anyone help me what is the time complexity of this algorithm?
What I know is T(count()) is O(n) * T(recurse(n)). Correct me if I'm wrong, T(recurse(s1, ...)) will be O(1) if I already calculated recurse(s1, ...) and that will make T(count(s)) = O(n).


texts: Finding disjoint paths between any number of cell pair marked in nXn matrix

texts:
What should be algorithm to find all the disjoint paths between any number of pairs of cells given in matrix?

We will say two paths will not intersect if there there is no cell common between any two paths.

My approach is : I will pick first cell pair and create a path between them. Now it will work as obstacle for path between other cell pairs. But problem is how to first pick which cell pair? Because it will create problem in finding path between some cell pair in future.


texts:
I am currently working on image classification methods. One group of preprocessing methods are color space transformations. While there are "traditional" color spaces like RGB (the raw data), HSV, LUV, XYZ, ..., I see any function

$$f:[0, ..., 255]^3 \rightarrow [0, ..., 255]^3$$

as a transformation from one color space in another color space (starting from RGB). Having multiple of those transformation functions $f_i$, I would like to be able to compare them.

Is there a common way to visualize color spaces for comparison? A metric which defines how "close" color spaces are? This measure of "closeness" could be interesting to estimate how much of a difference the choice of color space makes for the classifier.

I thought I could probably take a set of images and use the average euclidean distance of them as one way to compare them. Or just some randomly sampled colors and their average euclidean distance. But I guess there are more sophisticated ways?


texts: Is the lambda calculus referentially transparent?

texts:
In an answer of this Reddit discussion somebody defines referential transparency (RT) as "a context $K[ ]$ is RT if, for all $M$ and $N$ s.t. $M = N$, then $K[M] = K[N]$". Based on this definition, Lambda Calculus (LC) (and any other language with binding constructs) is non-RT.

For example, let $\Omega = (\lambda w.ww)(\lambda w.ww)$. In the expressions $(\lambda x.K[x]) \Omega$ and $(\lambda x.K[\Omega])\Omega$, we have $x = \Omega$, so given any RT context $K[]$ both expressions must evaluate to $\bot$. However, if we define $K[] = (\lambda x. [])(\lambda y.y)$, the first expression terminates while the second does not, proving that LC is non-RT.

Is this definition of RT wrong or LC is really a non-RT language?


texts:
It is often asserted that the halting problem is undecidable. And proving it is indeed trivial.

But that only applies to an arbitrary program.

Has there been any study regarding classes of programs humans usually make?

It can sometimes be easy to analyze a program and enumerate all of its degrees of freedom and conclude that it will halt.

For example, has there ever been an effort to create a programming language (scripting really) that guarantees halting? It would not be widely applicable but could still be useful for mission critical modules.


texts: What's the point in a symbol table or AST when all the information is available in the parse tree?

texts:
This is a question I haven't worked out the answer to yet probably because I haven't done any hands on middle end compiler design. I feel like the explanation of the true purpose of an AST were lacking, just 'it helps with semantic analysis' 'it simplifies' (well yes I can see it is simplified visually but why does it need to be simplified, programmatically?). I've never really understood its place.
Is the symbol table for when you have an AST, and you've split up the information between the AST and the symbol table?


texts:
So I was watching this video https://www.youtube.com/watch?v=ZjjAbFxjxLQ and the guy was explaining why the top automaton is NFA (because the initial state doesn't know what to do if the input string begins with b) and the bottom is DFA (because the initial state points to a 'dead state' if the input string begins with b):

Okay, fair enough.
But when I went on this Automaton simulator and it generated an example of a DFA for me, I got confused because its the same as the NFA example above:

It doesn't have an option for when the input string begins with b. So what's going on?


texts: Why don't we encode church numerals like this?

texts:
I think the following encoding also works.

ZERO := λf. λx. x
ONE  := λf. f
TWO  := λf. f f
THREE:= λf. f (f f)

Note: the original encoding is

ZERO := λf. λx. x
ONE  := λf. λx. f x
TWO  := λf. λx. f (f x)
THREE:= λf. λx. f (f (f x))

Why is the original one better?


texts: Is the language TMs that accept finite languages Turing-recognizable?

texts:
I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ).  But is $L$ recognizable?

What I tried is, let $L$ have a machine that recognizes it, let it be called $H$. Then given an input $\langle M\rangle$ I would start enumerating all strings in $L$ by using $H$. As $L$ has infinite many strings at some point the string being enumerated will be equal or larger than $\langle M\rangle$ (in lexicological order), thus using $H$ I am able to decide $L$ which I know is not possible.

Is my method correct ? In either case is there a better method for example is there a  general way for proving that a language is not recognizable like for undecidability  we try to reduce an undecidable problem to the current problem ?


texts: Four Pillars of Object Oriented Programming

texts:
I'm researching object oriented programming and I've come across the term "four pillars of OOP" in a few places now.

I originally saw them listed as:

Abstraction
Encapsulation
Inheritance
Polymorphism

When I searched for the origin of this I found a Quora answer which says:

  The four Pillars of OOP are in Grady Booch’s original book on the
  topic,. Object Oriented Analysis and Design. They are:

He then lists the four principles I mentioned above. Yet when I downloaded the PDF and searched for the word "four" I came across the section which seems to outline four key principles of OOP, and they are listed as:

Abstraction
Encapsulation
Modularity
Hierarchy

When I searched further I found others listing the four pillars as they appear in the book above. For example this diagram:

Can anyone explain the discrepancy on what the four pillars are?  I'm interested in the historical perspective: what is the origin of the four pillars?  Can anyone confirm or deny Grady Booch as the origin of this phrase?


texts: Qualifications for a problem to be solved as a single source shortest path problem

texts:
What are the pre-conditions for any problem X to be qualified for being solved in a single source shortest path problem (SSSP) setting?

Lets, say we have a problem X. What should be the pre-conditions that we check in problem X definition that would allow us to formulate it as a SSSP.

Initial Idea for solution: I believe if it satisfies the property of optimal substructure. One can formulate the problem as SSSP as well.


texts: How many segmentations are possible for a string length N?

texts:
I have a string with length N. I would like to know how many segmentations are possible to it.
Consider the example abcdc the number of N = 5
All possible segmentations are

['abcdc']
['abcd', 'c']
['abc', 'dc']
['abc', 'd', 'c']
['ab', 'cdc']
['ab', 'cd', 'c']
['ab', 'c', 'dc']
['ab', 'c', 'd', 'c']
['a', 'bcdc']
['a', 'bcd', 'c']
['a', 'bc', 'dc']
['a', 'bc', 'd', 'c']
['a', 'b', 'cdc']
['a', 'b', 'cd', 'c']
['a', 'b', 'c', 'dc']
['a', 'b', 'c', 'd', 'c']

Then what will happen  when  my N tends to infinity . Any closed form equations?


texts: Sparse tables as prefix sum data structure

texts:
I am trying to understand how a sparse table can be used as a prefix sum data structure for a bit vector. In the screendump below 1 the article [2] very vaguely describes how to use a sparse table from article "Storing a sparse table" to do this is $O(1)$ with space: $O(k\cdot loglogn)$. For simplicity, we can assume that $k=n/logn$. How is this even possible? and what is $|z_i|=n^{O(1)}$?

Article [2]: https://dl.acm.org/doi/abs/10.1137/S0097539700369909
Article [16]: https://dl.acm.org/doi/10.1145/359168.359175


texts:
What publication first introduced the concept of a non-deterministic Turing machine?

Turing did not define the concept in his 1936 paper.


texts: Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$

texts:
In the sources I consulted it states that in the Baum Welch algorithm the reestimate of the initial probability of state $i$ of the HMM is $\pi^*_i = \gamma_i(1)$. But $\gamma_i(t)$ is the probability of being in state ${\displaystyle i}$ at time ${\displaystyle t}$ given the observed sequence ${\displaystyle Y}$ and the parameters ${\displaystyle \theta }$ (quote wiki)

So, then why does this probability not need to be normalised like so? :

$$\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$$

After all normalizing is what is done for the reestimate of the transition probabilities and the emission probabilities too.


texts: Rearrange pixels to maximize visually distinguishable pattern

texts:
I have a dataset full of 0s and 1s, and when I visualize it with t-SNE, which does dimensionality reduction. There is clearly some structure in it as shown below. Each color corresponds to a particular category. There are 10 categories, and there are roughly 180 data points for each category. Each data point is a 64-dimension vector, i.e. there are 64 features. The category information is NOT used by t-SNE, and the coloring is applied after t-SNE run is done.

Since the dataset is all 0s and 1s, and each data point is a 64 vector, so I thought I could plot them as 8x8 dimension binary images as shown below. I have plotted 3 examples for each category

If you compare among images in a single column, there appear to be some similarity sort of. If you compare among images in a single row, they look random to me. My question is that is there such an algorithm for rearranging the pixels, which is equivalent to reordering the elements in the original 64-dimension vector, so that  MAXimize the visual similarity among images in each column (i.e. make them look as similar as possible) while MINimizing the visual similarity among images in each row (i.e. make them look as different as possible)? The whole point to make it easy to spot visual patterns for different categories if possible.

Update:

Thank you for @aelguindy's answer. For the record, I posted what the images look like before scrambling.

This notebook shows how the scrambled version is generated. This dataset is only for experiment. I have another real dataset of 0s and 1s that have nothing to do with hand-written images, of which I was trying to find visual patterns if possible.


texts:
In the last 2 paragraphs of the paper about Hopcroft–Karp algorithm to find the maximum cardinality matching in bipartite graph:

  https://dl.dropboxusercontent.com/u/64823035/04569670.pdf

  The execution time of a phase is O(m+n), where m is the number of
  edges in G, and n is the number of vertices. Hence the execution time
  of the entire algorithm is O((m+n)s), where s is the cardinality of a
  maximum matching.

  If G has n vertices then m <= n^2 / 4 and s < n / 2 so that the
  execution time is bounded by O(n^(5/2)).

I don't understand given:

m <= n^2 / 4
s <= n / 2

why they concluded:

O((m+n)s) = O(n^(5/2))

Shouldn't it be:

O((m+n)s) = O(n^3)

Any idea?


texts: NP-hardness of covering with rectangular pieces (Google Hash Code 2015 Test Round)

texts:
The Google Hash Code 2015 Test Round (problem statement) asked about the following problem:

input: a grid $M$ with some marked squares, a threshold $T \in \mathbb{N}$, a maximal area $A \in \mathbb{N}$
output: the largest possible total area of a set of disjoint rectangles with integer coordinates in $M$ such that each rectangle includes at least $T$ marked squares and each rectangle has area at most $A$.

In Google's terminology, the grid is a pizza, the marked squares are ham, and the disjoint rectangles are slices.

We can clearly rephrase this problem to a decision problem by adding an additional input $n \in \mathbb{N}$ and let the answer be "is there a set of disjoint rectangles satisfying the conditions whose total area is at least $n$ squares".

My question: while the Google problem asked candidates to find a solution which is "as good as possible" for the computation problem on a specific instance, I think it is likely that the general problem (in its decision phrasing) is NP-complete. However, I cannot find a reduction to show NP-hardness. (NP-membership is immediate.) How to prove that this problem is NP-hard?

A few examples follow, to help visualize the problem. Consider the $4$ by $4$ grid $\{0, 1, 2, 3\} \times \{0, 1, 2, 3\}$, with marked squares $(1, 1)$, $(0, 2)$ and $(2, 2)$, represented graphically with X to indicate marked squares:

..X.
.X..
..X.
....

Set $A = 6$ (rectangles of at most $6$ squares) and $T = 1$ (at least one marked square per rectangle), an optimal solution (that covers the entire grid) is to take the following rectangles:

aaAa
bBcc
bbCc
bbcc

On the following grid, with $A = 3$ and $T = 2$:

XXX
.X.
...

One cannot do better than covering only three squares:

AAA
.X.
...

or

XBX
.B.
.b.

(remember that rectangles in the partition cannot overlap).

With other people looking at this question, we tried reductions from bin packing, covering problems, 3-SAT, and Hamiltonian cycles, and we didn't manage to get one to work.


texts: Do any one give me some hints to solve this problem. Explain is steps by steps.Thanks


texts: can every LR(k) grammer be transformed to LR(1)

texts: when i was studying compilers i came across this in Wikipedia every DCFL has a corresponding unambiguous grammar and hence can be parsed by an LR(1) parser which is the most powerful parser then what is the significance of LR(k) parsers are they more powerful than LR(1) when every DCFL can be parsed by LR(1) why do we need LR(k)?


texts: Non-existence of approximation algorithm for the knapsack problem

texts:
I am working on the following exercise: Prove that if $P \neq NP$, there cannot exist an approximation algorithm $A$ for the knapsack problem (KP) such that $\exists k \in \mathbb{N}, \forall I \in S: OPT(I) - P_A(I) \leq k$ where $OPT(I)$ is the optimal profit on instance $I$ and $P_A(I)$ is the profit calculated by $A$.

I know that there is a FPTAS $A'$ for the KP which guarantees a solution with profit $P_{A'}(I) \geq (1 - \varepsilon)OPT(I)$ on any instance $I$ and $\varepsilon > 0$.

My approach is to create a contradiction. For this I consider $A = A'$ and aim to show that $P_A(I) \geq (1 - \varepsilon)OPT(I) \geq ... \geq OPT(I) - c$ where $c \in (0,1)$ is a constant. This way, for an adequate choice of $\varepsilon$ I would show that we obtain an optimal solution within polynomial time. However, I struggle how to choose $\varepsilon$.

I need some advice on how to proceed. Many thanks in advance!


texts: What does this line mean in Brin/Page's 1998 paper?

texts:
In Brin and Page's paper "The Anatomy of a Large-Scale Hypertextual Web Search Engine", they describe the variable "d" in the PageRank algorithm as the probability that a random surfer requests a new random page. On the next line, they state:

  One important variation is to only add the damping factor d to a
  single page, or a group of pages. This allows for personalization and
  can make it nearly impossible to deliberately mislead the system in
  order to get a higher ranking.

What does this mean? Why would they add the damping factor to only a single page?

Does it mean that the random surfer will keep following links until they arrive at a specific page? I don't think this makes sense because the random surfer can get stuck in a loop and never reach that specific page.


texts: dynamic programming: longest palindromic subsequence, recurrence relation question

texts:
Moving from top left down the column then over to the right column, taking ideas from here: https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/
I want to restate the question at the top of the Excel table.
Why do I need to max from T(i,j-1) and T(i+1,j)?  Can't you just take what's in T(i,j-1)?
I changed the input slightly and I still get the right answer just taking T(i,j-1) when T(i,0) != T(0,j)
Edited:

A counterexample would be nice to see.


texts: Finite State Machine trasition possibilities

texts:
Im studying finite state machines, in particular the deterministic and the non-deterministic  versions.

What i have not understood is :

why in a non-deterministic state machine it's allowed that from a state it's possible to go nowhere ?

This is not allewed in DSM. Why ?


texts: Solving recurrence relation $T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n$ using method of guessing and confirm?

texts:
The book I am following explains the solution as,

  As we can see,the size of sub problems at the first level of recursion
  is $n$.So, let us guess that $T(n)=O(n\log n)$ and try to prove that our guess is correct.

Doubt- Does initial problem size(i.e n) give a hint to reach $O(n\log n)$ ? How it does?

furthermore ,the book says

  Let's start by trying to prove an upper bound $T(n)\le c\cdot n\log n$

  \begin{align*}
T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n  \tag{1}
\\
\le \sqrt{n}\cdot c\sqrt{n}\log(\sqrt{n}) + n \tag{2}
\\
  =n\cdot c\log (\sqrt{n})+ n \tag{3}
\\
 =n\cdot c\cdot\frac{1}{2}\log n+ n \tag{4}
\\ \le c\cdot n\log n  \tag{5}
\end{align*}
  Last inequality assumes only that $$1\le c\cdot\frac{1}{2}\cdot \log n$$
  This is correct if n is sufficiently large and for any constant c,no matter how small.So we are correct for upper bound.

I am not getting what's happening from $(1)$ to $(2)$ and that from $(4)$ to $(5)$. Also What does the last line prove ?


texts: Does this progressive image compression exists?

texts:
I want to know if this progressive image compression that I have in mind exists and it it does I want know its name and/or get some references about it.

The algorithm consists of converting one high resolution image in multiple low resolution images (all of the same size, not like in wavelet transform) with the following properties:

If you have one of them, any of them, you can reconstruct a low resolution approximation to the original image.
You can compose many of those in any order to get better approximations to the original image.
If you combine all low resolution images you get the original image or a very good approximation of it without perceptible artifacts.
Algorithm is real-time, i.e. it can display a meaningful partial reconstruction of the original image at any time of the reconstruction process (independently of received sub-images and their order).

Does this algorithm exits? Is it possible at all?

I know about image reconstruction techniques, but those use similar but different images to reconstruct a higher resolution one and the result is always noisy and full of artifacts. This is not I am asking for.


texts: Why is finding square root of perfect square $O(M(n))$

texts:
I saw this question and its answer on Theoretical Computer Science stack exchange and I can't understand why the complexity of finding the root is the same as that of a multiplication. My thought was that we may need more than $O(1)$ multiplications to find the root (using Newton's Iteration as stated in the answer, since the method may need more than $O(1)$ steps).

Is there an upper limit not depending on $n$ to the amount of multiplications we may need? Or a method to find the root with enough accuracy(which means finding the actual root) after $O(1)$ steps? Am I missing something?

Note: I didn't ask this on theoretical CS stack exchange, since it is supposed to be for professional researchers in CS and no one asked about this in the comments so assume it isn't a research level question even if it is about an explanation of one (research level question).


texts: Vehicle Routing Problem Using Simulated Annealing

texts:
Suppose I have some locations where goods are to be delivered in multiple time slots(like 7-10 am , 10 am-1 pm, time slots are continuous). All the locations are connected with each other(completely connected graph).

1.) Firstly orders of first slot are to be delivered and then only orders of other slots can be delivered.So, the last point of most optimal first slot sub-tour might not be the most optimal for the overall distance minimization. We might need to go from that last point to some other point of first slot and then from there on go to locations of slot2.

2.) Minimize distance

3.) Trip starts from a depot and ends at the depot( So sequence is something like depot -> Slot 1 orders -> Slot 2 orders -> .......... -> depot , where slot1 is 7-10 am , slot2 is 10 am - 1 pm, slot3 is 1 pm - 4 pm......).

My question is how can this problem be tackled with simulated annealing. like how to fix the starting and end points(as depot) and how to set annealing schedule for such problem.


texts: Computing the hit and miss ratio of a cache organized as either direct mapped or two-way associative

texts:
This is an example problem in a computer organization and architecture course that's giving me some trouble. It goes as follows:

  Consider a cache of 4 lines of 16 bytes each. Main memory is divided
  into blocks of 16 bytes each. That is, block 0 has bytes with
  addresses 0 through 15, and so on. Now consider a program that
  accesses memory in the following sequence of addresses:

  Once: 63-70

  Loop 10 times: 15-32; 80-95

  a. Suppose the cache is organized as direct mapped. Memory blocks 0,
  4, and so on are assigned to line 1; blocks 1, 5, and so on to line 2;
  and so on. Compute the hit ratio.

  b. Suppose the cache is organized as two-way set associative, with two
  sets of two lines each. Even-numbered blocks are assigned to set 0 and
  odd-numbered blocks are assigned to set 1. Compute the hit ratio using
  the least recently used replacement scheme.

I know that the formula for finding the hit ratio is:

hit ratio = hits / (hits + misses)

and that the LRU replacement scheme should be used for both a and b, since it's the most efficient. I know how to find and compute addresses in a cache, but this has me stumped.

Any help in understanding this is greatly appreciated!


texts: Data structure to hold and retrieve points in a plane

texts:
Definition 1: Point $(x,y)$ is controlling point $(x',y')$ if and only if $x < x'$ and $y < y'$.

Definition 2: Point $(x,y)$ is controlled by point $(x',y')$ if and only if $x' < x $ and $ y' < y$.

I'm trying to come up with data structure to support the following operations:

$\mathrm{Add}(x,y)$ - Adds a point $(x,y)$ to the system in $\mathcal{O}(\log n)$ complexity where $n$ is the number of points in the system.
$\mathrm{Remove}(x,y)$ - Removes a point $(x,y)$ from the system in $\mathcal{O}(\log n)$  complexity where $n$ is the number of points in the system.
$\mathrm{Score}(x,y)$ - Returns the number of points $(x,y)$ controls - number of points that $(x,y)$ is controlled by. Worst case complexity $\mathcal{O}(\log n)$ .

I've tried to solve it using multiple AVL trees, but could not come up with elegant enough solution.

This question appeared on my exams few days ago. The question should have relatively straightforward as it was worth $15/100$ points.
I tried to solve this by several AVL trees but couldn't come up with elegant enough solution.

Hints are welcome.


texts: Combinatory logic equivalent to System F

texts:
Simply typed lambda calculus has a combinatory logic equivalent with the same expressive power without the need of defining names via lambda abstraction.

Is there a formalism as powerful as System F but based on combinatory logic?


texts: Closure property of recursively enumerable language

texts:
I read that recursively enumerable languages are closed under intersection but not under set difference.

We know that, $A \cap B = A - ( A - B)$.

Now for LHS (left-hand side) to be closed under intersection, RHS(right-hand side) should be closed under set difference .

But we know that RHS is not closed under set difference so LHS is also not closed under intersection.

Suppose we assume that R.E is closed under intersection then,

$A \cap B = \overline{(\overline{A} \cup \overline{B})}$.

Now LHS can be closed only if RHS is closed under complement (as R.E languages are already closed under union). But we know R.E is not closed under complement, so again a contradiction.

So, R.E should not be closed under intersection right ?


texts: Do we create a programming language by writing a compiler?

texts:
Say, I wanted to create my own programming language. Assuming that I have made all of the decisions about how I want it to look and act, do I just need to write a compiler for it?

For example, is the high-level Java code anything other than just text and this text is in the correct format for the compiler to accept it and turn it into something else?

My question is, is the creation of a programming language done through a compiler? High-level is fine.


texts:
For the example below, I am trying to understand how Haskell type classes, type class instances, and data types relate to the concept of initial algebra.
There are two Haskell data types sharing a pair of operations for equality and addition. From my, perhaps incorrect, understanding the instances, which include the data types, specify two non-isomorphic initial algebras.
It seems to me that the type class permits the overloading of the operations and plays no role in the specification of the initial algebra.
Is this a correct interpretation of the given example?

data Nat0 = Zero | Succ0 Nat0 deriving Show
data Nat1 = One | Succ1 Nat1 deriving Show

class PeanoNum n where
 eq :: n -> n -> Bool
 add :: n -> n -> n

-- Two different non-isomorphic algebras.
instance PeanoNum Nat0 where
 eq Zero Zero = True
 eq (Succ0 m) (Succ0 n) = eq m n
 eq _ _  = False
 add m Zero = m
 add m (Succ0 n) = Succ0 (add m n)

instance PeanoNum Nat1 where
 eq One One = True
 eq (Succ1 m) (Succ1 n) = eq m n
 eq _ _ = False
 add m One = Succ1 m
 add m (Succ1 n) = Succ1 (add m n)


texts: Is unary language with polynomial power context sensitive?

texts:
I suppose that $\Sigma = \{a\}$.

Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ is a context sensitive language.

It seems that it is a context sensitive language. I guess making LBA or context sensitive grammar is not easy for this language.  Can I prove this with closure property of CSL for example like complement?  Can any one help me to prove for instance $L_1 = \{a^{n^7+n^5+n^3+n^2+1} | n\in \mathbb{N}\}$ is context sensitive. Maybe I can get an idea from this to prove my first question.


texts: Does it hold that $F \equiv \sigma(F)$ for a CNF formula $F$ and a permutation $\sigma$ s.t. $F \vDash \sigma(F)$?

texts:
Suppose we have a CNF formula $F$ and a permutation $\sigma$ of its literals such that for any literal $x, \sigma(\neg x)=\neg \sigma(x)$ and $F \vDash \sigma(F)$.

Does it hold that $F \equiv \sigma(F)$?

It is the case when $\sigma$ is a syntactic or even a semantic symmetry of $F$ but I don't know if it hold for any permutation that respects the hypothesis above.


texts:
I am studying Crypto and am trying to understand why discrete log creates is useful for creating a PRG. More specifically, I want to prove via reduction that  $B(x)=(x<p/2)$ is a hardcore bit for the one-way function $f_{p,g}(x)=g^x \bmod p$. So far, I have shown that if there is a polynomial-time algorithm $D$ that computes this bit perfectly, then
there is another polynomial-time algorithm $I$ that inverts the one-way function perfectly.
I want to extend the proof to the case
when $D$ is imperfect, but successful with probability $\frac12 +\epsilon$ for some nonnegligible $\epsilon$
(in this case, the probability is taken over a random choice of $x$ between 0 and $p-1$). I want to show that for this case,
it is possible to invert $f$ with nonnegligible probability in polynomial time.

Any help is appreciated.


texts: Minimum perfect matching with uneven vertices?

texts: Given this graph, what is the minimum perfect matching? What do you do, when there is an uneven number of vertices?


texts: I have n boys and n girls. I need to pair as much of them as possible for a dance in O(nlogn). Reduce this to a standard problem?

texts:
There are n girls and n boys. Each girl i has an objective attractiveness constant Pi (a natural number). The bigger the number, the more attractive. Each boy has a range in which he is comfortable asking the girl out [Ai, Bi] (inclusive). A boy will not ask someone out who is below Ai or above Bi.

I need to pair as many of them as I can for a single dance in O(n*logn) time.

I tried building some kind of a tree in O(n) and then using that three in O(logn) repeatedly against the whole list. I've spent some solid 3 hours on this problem and I'm really not getting anywhere. I've tried to build a dependency tree, I've treed weighted priority queues. I considered some constraint satisfaction algorithms, but as far as I recall they are all nowhere near  O(n*logn).

Nothing seems to work. But I do clearly see that this has to be reduced to some other standard computer science problem.

However I've had no luck looking up "load balancing" or "pair assignment". I've no idea what are the right keywords.

This seems the be the kind of problem data centers have when assigning load to virtual machines. Or web requests over the world for large web sites. For example a server can sustain a load in [Ai, Bi] range (let's say RAM in GB's 4-8GB) and our target application needs 5GB. Now let's say we have n of both of these (target applications and servers). How to pair them so as much get paired? Thanks.


texts: Have I got the right understanding of the mu operator?

texts:
I have a homework problem that says:

For $g(x,y)=xy-5$ compute $h(x) = \mu y(g(x,y))$ and determine its domain.

I was under the impression that this means the least y such that $g(x,y)=0$, so then $y = \frac{5}{x}, D=\{x \in \mathbb{N}, x \neq 0\}$

So $h(x)=\frac{5}{x}$?


texts: A simple graph $G$ with even clique number, find a subset $A$ of the vertices, subgraph induced by $A,V-A$ have equal clique number

texts:
Given a simple graph $G=(V,E)$ s.t. $2\mid \omega(G)$,
Show that $\exists S\subseteq V\text{ s.t. } f_G(S)=f_G(V\setminus S)$
where $f_G(A)$ is the clique number of the sub-graph of $G$ induced by vertex set $A$.

I'm have trouble proving this property of clique number.
Several approaches have been tried but none leads to a correct proof.

IDEA: Firstly, divide a largest clique $C$ of $G$ evenly into to subset $A,B$.
I want to continuously add vertices into $A$ and $B$ keeping the clique number of the sub-graphs induced by $A,B$ unchanged.

For every other vertex $v$, we have $f(A\cup \{v\})=f(A)\lor f(B\cup \{v\})=f(B)$, otherwise $A\cup B\cup\{v\}$ is a clique bigger than $C$.
After adding the first vertex, I can show that every other vertex $v'$ satisfy $f(A\cup \{v'\})=f(A)\lor f(B\cup \{v'\})=f(B)$ using the pigeonhole principle.
However, after adding $|A|$ vertices into $A$ or $|B|$ vertices into $B$, I can no longer have the property: $f(A+v)=f(A)\lor f(B+v)=f(B)$

IDEA: Continuously find the largest clique $C=\{v_1,\ldots v_k\}$
if $2\mid k$ split it evenly, otherwise split it into $\lfloor k/2\rfloor,\lceil k/2\rceil$
This doesn't work, adding the vertices arbitrarily can cause unpredictable increase in clique number.
other naive approaches.

I really need some hint to solve it.
btw, I don't know why the graph should be simple, I can't see a difference.


texts: Haskell type classes as ontological categories

texts:
A paper uses Haskell type classes to represent ontological categories.
A type class hierarchy is used to represent "concept hierarchies" where "functions are the units of inheritance". Here is a diagram of the Haskell type classes based on the paper:

With respect to the code below the following claim is made:

The Haskell code given so far is complete and type checked, explaining
the entire refined concept hierarchies. With instantiations for types
of boathouses and houseboats, values can be declared and axioms stated
and evaluated to demonstrate semantic properties and differences. For
example, it can be shown that a passenger on a boat in a boathouse
cannot be said to be an inhabitant, while a passenger on a houseboat
can.

The spatial prepositions in and on form part of the semantics the whatsIn and whatsOn predicates in the code below.
I have a three  questions:
(Q1) Is the claim true?
(Q2) How would go about validating such a claim.
As regards Q2, I have create 72 instances with appropriately kinded data types   as advised by the GHCI compiler (not supplied in this post).
Then I checked the types with the following type level queries

Query 1 :  A passenger on a boat in a boathouse cannot be said to be
in the boathouse  (i.e. an inhabitant)

:t whatsIn (BoatHouse (Boat People)) =t=> OK whatsIn (BoatHouse (Boat People)) :: [Boat People]
:t whatsOn (HouseBoat  People) =t=> ERROR  No instance for (Surfaces BoatHouse (Boat People))

Query 2 : A person can be both on and in a houseboat (a passenger and an inhabitant).

whatsOn (HouseBoat  People) :: [People]
:t  whatsIn (HouseBoat  People)  =t=> whatsIn (HouseBoat  People) :: [People]
:t  whatsOn (HouseBoat  People) =t=> whatsOn (HouseBoat  People) :: [People]

(Q3) Both these queries seem to be apptropriately accepted and rejected by Haskell. Is there a better or easier way to validate this claim?
Listing 1 shows the source code from paper.
class Containers a b where
 insert :: b -> a b -> a b
 remove :: b -> a b -> a b
 whatsIn :: a b -> [b]

class Surfaces a b where
 put ::  b -> a b -> a b
 takeOff :: b -> a b -> a b
 whatsOn :: a b -> [b]

class Paths a b c where
 move :: c -> a b c -> a b c
 origin, destination :: a b c -> b
 whereIs :: a b c -> c -> b

class PeopleClass p
class HeavyLoads l
class Surfaces w o => WaterBodies w o
class Containers h o => Houses h o
class (Surfaces v o, Paths a b (v o)) => Vehicles v o a b
class (Vehicles v o a b, WaterBodies w (v o)) => Vessels v o a b w
class (Vessels v p a b w, PeopleClass p) => Boats v p a b w
class (Boats v p a b w, HeavyLoads p) => Barges v p a b w
class (Houses h (v p), Boats v p a b w, Contacts w (h (v p))) => BoatHouses h v p a b w
class (Barges v p a b w, Houses v p, PeopleClass p) => HouseBoats v p a b w


texts: Find perfect matching faster than MCM, in graph that has perfect matching?

texts:
Given an unweighted bipartite graph which has a perfect matching, is there an algorithm for finding a perfect matching in the graph that is faster than the best known algorithm for finding a maximum cardinality matching (MCM)? For example, is there some way to take advantage of the fact that the graph is known to have some perfect matching to help find one faster?

If yes, could you please help to point out some references? If it is impossible, could you briefly explain the reason? Comments and suggestions are also welcomed.


texts:
I know the general concept of recursion.  I came across the concept of tail recursion while studying the quicksort algorithm.  In this video of quick sort algorithm from MIT at 18:30 seconds the professor says that this is a tail recursive algorithm.  It is not clear to me what tail recursion really means.

Can someone explain the concept with a proper example?

Some answers provided by the SO community here.


texts: What is the simplest automaton that can compute the sum of two integers of arbitrary length?

texts:
It should be obvious that a Turing machine is capable of computing the sum of two integers. However, what is the simplest automaton that can compute the sum of two integers of arbitrary length?

I have a proof scratch that the automaton in question should be no more complex than a non-deterministic PDA:

Let addition be express by $L = \{1^n0^m1^{n+m}\}$ where $1^n$ represent the first term, $0^m$ represent the second term, and $1^{n+m}$ is the sum of those terms.

Theorem:

$L$ is context free.

Proof:

It is trivial to show that a non-deterministic PDA can store $n$ and $m$ in the stack by pushing a symbol to the stack when a symbol from the first or the second term is read.

Once both terms have been read, the PDA can read the sum and remove item from the stack. The PDA accepts the string if the stack is empty after all symbols of the sum has been read. The PDA otherwise rejects the string.

Since there is a PDA that recognizes $L$, $L$ is context free.

Theorem:

$L$ is not regular.

Proof:

Suppose $L$ is regular, by pumping lemma for regular language, there is a pumping length $p$ such that $\forall w \in L, |w| \geqslant p$, $w = xyz$ such that $|xy| \leqslant p$, $|y| \geqslant 1$, $\forall n \geqslant 0, xy^nz \in L$.

Let $x = 1^n$, $0 \leqslant n < p$, $y = 0^{p - n}$, $z = 1^p$. $xy^0z = 1^n1^p \not \in L$. Contradiction.

Therefore, $L$ is not regular.


texts: Is Newton's algorithm really this much better than conjugate gradient descent?

texts:
I have a function I'm minimizing. I'm using conjugate gradient descent and the Newton algorithm.

I am experiencing that the Newton algorithm is absurdly faster. Like, it finishes it 5-6 iterations, while the conjugate gradient takes 2000 iterations (and regular gradient descent takes 5000 iterations).

I know what's causing the problem too: the learning rate. In Newton's method, a learning rate of $\alpha = 1$ works. But I can't use this in the gradient descent methods, where such a choice of $\alpha$ diverges. In these methods, I am forced to use $\alpha = 0.01$.

But anyways, 5 iterations vs thousands of iterations is still an absurd difference. Is Newton's method really this good??!


texts: Is a PDA's stack size linear bounded in input size?

texts:
I was thinking as follows: At each step, a PDA can put arbitrary many symbols onto the stack. But this number is constant for every individual PDA, so it can't be more than, say, $k$ symbols per step. Using only regular transitions, the stack can rise to maximally (more or less) $kn$ symbols in a run on an input sized $n$.

But what about $\epsilon$-transitions? Is there a simple argument why their maximum number should as well be independent of the input size?

So, in short: Is a PDA's stack size linear in the input size?


texts: Method to construct a finite state machine for a finite-size language L

texts:
I need to define a method to construct a finite automata for a finite language L (part of my proof for something else).
My idea:

Create $|L|$ accepting states.
For each input string $s$ from $L$, create appropriate transitions from a starting state to unique accepting state of s.

I don't know how to formally describe this, or if this idea is even good.


texts: Shortest path between 2 nodes subject to constraints

texts:
I am trying to find shortest path between 2 nodes in a graph similar to below:

Each edge has a weight assigned to it. Also, the graph is directional with each edge directing from left to right.

I am trying to find shortest path from Start to Stop, subject to a constraint (based on already visited nodes). If a node I1_I4 is part of the shortest path, then I cannot include I2_I4, similarly, if I1_I5 is part of shortest path, then I2_I5 cannot be.

So far, I have tried to modify Dijkstra but I am not getting any optimal solutions. Any ideas? Are there any existing graph algorithms for this? Do you have a Java solution for this?

Edit: A bit more detail: I am trying to generate pairs. There is a cost associated with each pair. I can pair I1 with {I4, I5, I6} or I1_D with {I4, I5, I6}. I can also pair I2 with {I4, I5, I6} or I2_D with {I4, I5, I6}. If I have paired I1 with I4 then I cannot pair I4 with I2. Bear in mind that I could pair I1 with I4 but joining I4 with I3 might lead to lower cumulative cost. I am trying to find the minimum cost for these.

Edit2: As depicted in the graph, I can either pair I1 with I4, I5, I6 or I1_D (I1 with a different cost) with I4, I5, I6.

Edit3: I1 and I1_D are mutually exclusive. For instance, I can only choose between I1 and I1_D to pair with I4,I5,I6. In other words, if I1 is a part of any matching pair, I1_D cannot be included in any pairs.

thanks!


texts: In this proof that sokoban+ is pspace complete, how does the gadgets register the fact that a cell of the turing machine has changed?

texts:
I´ve been reading the paper "SOKOBAN and other motion planning problems" by Dorit Dor and Uri Zwick.

This is a link to the paper: Sokoban+ is pspace complete

In the paper, they proved that a problem called sokoban+ is pspace complete, they did it by reducing simulation of a turing machine with bounded tape to that problem.

sokoban+ is like sokoban, but the player can pull and push obstacles and all pieces are 2 x 1 rectangles (instead of 1 x 1 like in normal sokoban).

In figure 7, they show a drawing of the cell gadget, this represents a cell of a turing machine.

In the cell, the player enters, chosses a simbol (0 or 1) and if the player chooses correctly, he can go to a simbol gadgdet which will be open only if he has chosen the correct symbol. He goes through the symbol gadget, closing it, and then he goes to a gadget that forces the player to go to the next cell.

My question is, if in this cell and state the symbol of the tape has to change, how does the cell gadget registers that the symbol has changed?

Thanks for your help!


texts:
Problem
We are given 2 arrays a and b both of length n. We build a third array c by rearranging the values in b. The goal is to find the optimal c that maximizes
result = (a[0] ^ c[0]) & (a[1] ^ c[1]) & ... & (a[n - 1] ^ c[n - 1])

where ^ is XOR and & is AND.
Is it possible to do this efficiently? It's straightforward to iterate through all possible permutations of b, but this is infeasible for large n.
More details

The order of the values in a is fixed.
The order of the values in b may be rearranged to form c. That is, starting with b = [1, 2, 3], it may be that the maximum result is obtained when the values are rearranged to c = [2, 1, 3].
b may be rearranged in-place if needed.
Since the optimal c is not necessarily unique, any optimal c may be returned.
Assume all values are 32-bit unsigned integers.
1 <= n <= 10,000.

Test cases
Input:
a = [3, 4, 5]
b = [6, 7, 8]
Output:
c = [8, 7, 6] (result = 3)

Input:
a = [1, 11, 7, 4, 10, 11]
b = [6, 20, 8, 9, 10, 7]
Output:
c = [8, 6, 10, 9, 7, 20] (result = 9)

Input:
a = [0, 1, 2, 4, 8, 16]
b = [512, 256, 128, 64, 32, 16]
Output:
c = [16, 32, 64, 128, 256, 512] (result = 0)


texts: Difference between cordic algorithm and table based methods for elementary functions computation

texts: In this book both Table Based methods and Cordic iterations are explained. computationally speaking i suppose the Table based is usually faster, even though it probably requires more resource, while Cordic is probably slower, but probably less resource consuming (if my understanding is correct, it should be a specific instance of shift and adds algorithm). But are there other benefits/drawback in both approach? I suppose also the CORDIC doesn't suffer of the table maker dilemma, even though it in general requires a LUT.


texts:
Lets say we have integer variables $a \in\mathbb{Z}^n$  and  $M \in\{0,1\}^{n\times L}$. I am promised $a_i \leq L$, for some fixed constant $L$.  I want to model the constraint $$M_{i,j} \iff (a_i=j)$$
in an integer linear program.  What is the most efficient way to do this in an ILP?  In particular, can I do this without Big-M constraints and without breaking down each integer into its binary representation?

Currently I can see two ways to model this:

Option 1

We can apply the method described in the answer here to the constraint $M_{i,j} \iff (a_i-j=0)$.  This requires $1$ extra binary variable as well as  $4$ potentially large "Big M" constraints per $M_{i,j}$, thus resulting in $nL$ new binary variables and $4nL$ new big M constraints.

Option 2

We can break down $a_i$ into its bits using $\log L$ extra binary variables. We can also compute the corresponding binary bit breakdowns for each $0\leq j \leq L$. Let $bit^{(a)}_{i,k}$ be the $k$th bit of $a_i$ and let $bit_{j,k}^*$ be the $k$th bit of the integer $j$, so that
$$a_i = \sum_{k=0}^{\log L}2^kbit^{(a)}_{i,k}.$$

We now have the following logic:
$$M_{i,j} \iff (\forall k . 0\leq k\leq \log L \implies bit^{(a)}_{i,k} \odot bit_{j,k}^*)$$

Therefore

$$M_{i,j} = \bigwedge_{k=0}^{\log L} bit^{(a)}_{i,k} \odot bit_{j,k}^*.$$

We can use this post to NXOR the pairs of variables, storing their results as another variable $z=\{0,1\}^{\log L}$. We can AND these together using the constraints $$M_{i,j} \ge \sum z_i$$ $$M_{i,j} \leq  z_i \;\;\; \forall i$$

This creates $\log L$ new variables and 1 constraint for representing the binary breakdown of $a_i$. We then have $\log L$ XNOR variables, each which can be represented with 4 constraints. We can finally represent $M_{i,j}$ with  $\log L + 1$ more constraints. Therefore, we have a total of $5\log L$ constraints and $2\log L$ new variables per $M_{i,j}$, giving us a total of $5nL\log L$ new binary constraints and $2nL\log L$ new binary variables.

Is there some third option that is better than either of these two options?


texts: Reconstruct graph of N edges from a matrix of shortest pair distances (N*N) (i.e. result from Floyd-Warshall algorithm)

texts:
I want to reconstruct a graph when given the results of a Floyd-Warshall shortest pair distances matrix, similar to the problem being solved in this question:

Is it possible to reconstruct graph if we have given matrix of shortest pairs

The only difference being that, whilst the problem from the linked-to question seeks to find a graph of $N-1$ edges, I want to produce a graph containing $N$ edges.

I've already found a more efficient way of solving the problem from the question linked above. Instead of using the solution offered there, I have found that building a minimal spanning tree also yields the correct result, namely a graph of $N-1$ edges that, when given as input to the Floyd-Warshall algorithm, produces exactly the matrix of minimum distance pairs with which we started.

Now we have one edge left to add. This is the part I am unable to figure out. It boils down to this:

I have a graph of $N-1$ edges, which is represented by a matrix of shortest pair distances. Out of a list of candidate edges, how can I efficiently (i.e. without brute forcing) find which edge to add that does not change even a single value in the matrix, preserving all minimum distances?

Thanks!


texts: Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$

texts:
Let be $(I_n)_n$ a set of $p$ intervals each contained in $[0, L]$ for $L \geq 1$.

I define $(J_n = [a_n, b_n])_n$ the set of intervals which have empty intersection with $I_n$ for all $n \in [[1, p]]$.

I'd like to efficiently compute $\max_n (b_n - a_n + 1)$.

A basic idea I'd try would be to:

(1) Create a segment tree for $(I_n)_n$ in $O(p \ln p)$

(2) Iterate over $[0, L]$ and count the longest line before encountering an interval covered by $(I_n)_n$ (resetting the "max value" to 0 until the next of a certain $J_q$)

Which could give me an algorithm in $O(L + p \ln p)$, the problem is that $L$ is really big in my instances, I'd like to have an algorithm which does not depend on $L$.


texts: Why, intuitively, is Lob's theorem true?

texts:
Lob's theorem states that:

Let $\textbf{Prov}(n^A)$ be the arithmetic statement such that $PA\vdash$ $A$ iff $\textbf{Prov}(n^A)$, where $PA$ is peano arithmetic, and $n^A$ is the godel number of $A$.
Then

  $$PA \vdash\textbf{Prov}(n^A)\rightarrow A\quad\quad\text{
implies} \quad \quad PA\vdash A$$

Where the same applies to any system that is at least as powerful as peano arithmetic.

My question is: Is there an intuitive explanation of why this is true? I've read an $n$ step proof in modal logic, but my intuition is not improved by it.


texts: Given 3 disjoint Turing-recognizable languages prove that one of them is decidable

texts:
Let $A$, $B$, $C$ be Turing-recognizable languages over an alphabet $\Sigma$. Assume that

$A\cup B\cup C = \Sigma^*$, and
$A\cap B = A\cap C = B\cap C = \emptyset$.

Prove that $A$ is Turing-decidable.

So far I've tried the following but it really hasn't gotten me anywhere.
Suppose $A$ is recognizable but not decidable then, $\overline{A} = B \cup C$ so $B$ or $C$ is undecidable, since decidable languages are closed under union.
In the case that only one is decidable you can show at least that its in $A$ or $B$ (or $A$ or $C$ in the other case). Then, ... ?
In the case that both are recognizable, ... ?


texts: Construct matching for half of the vertices, in linear time

texts:
Suppose we have a graph $G=(V,E)$ connected and $K_{1,3}$-free.
Sumner proved that every claw-free connected graph with an even number of vertices has a perfect matching (so, it is maximum matching).

Describe an algorithm to construct one matching of cardinality $|V|/2$ in $G$ in time compelxity $O(|V|+|E|)$.

I thought it in this way: the BFS tree of $G$ is acyclic so a topological sort (postorder traversal) on it may solve the problem (via https://en.wikipedia.org/wiki/Claw-free_graph). But, looking some examples, I realized that there may exist edges that don't belong to $E$.


texts: Does my solution converge to O(N) for worst-case time complexity?

texts:
Forgive me if this should be in StackOverflow or Mathematics instead!

I was given the following question at an interview:

Given an array of unique integers, find the first missing non-negative integer that is missing to form a consequence sequence of non-negative integers.

For example, the input [3, 4, -1, 0, 1] should give 2.
The input [1, -3, 2, 0] should give -1 (i.e no missing numbers).
The input of [-2, -3, -5] should give 0

I came up with a solution that is something akin to here: https://play.golang.org/p/b2pXr9kZYxM:

func findMissingNumber(nums []int) int{
    j := 0
    for i, num := range nums {
        if num < 0 {
            nums[i], nums[j] = nums[j], nums[i]
            j++
        }
    }
    if j >= len(nums) {
        return 0
    }
    count := 0
    for i:=j ;i < len(nums);{
        count++
        if nums[i] == i-j {
            i++
            continue
        }
        if nums[i]+j >= len(nums) || nums[nums[i]+j]+j >= len(nums) {
            nums[i] = -1
            i++
            continue
        }
        temp := nums[nums[i]+j]
        nums[nums[i]+j]= nums[i]
        nums[i] = temp
    }
    fmt.Println(count)
    for i := j; i < len(nums); i++ {
        if nums[i] == -1 {
            return i - j
        }
    }
    return -1
}

Both the interviewer and I agreed that my solution could've been slightly more optimized (GeekForGeek seems to agree) but we were unsure if the worst-case for my solution was $O(N)$ or $O(N^2)$.

It seems like my solution has $$ O(N) + O(N/2) + O(N/4) + O(N/6) +\cdots+ O(1) $$ which becomes essentially:
$$\frac{N}{2}\sum_{n=1}^{N} n^{-1}$$

My calculus is a bit rusty (as are my algorithm skills) but I know this is a series diverges for $N \to \infty$. But can I say that for N sufficiently smaller than infinite (i.e Integer.Max), my worst-case becomes simply $$O(kN) = O(N)?$$


texts: Finding pairs of numbers in array whose reciprocals sum to 1

texts:
Given an array of numbers. Find all pairs of numbers satisfying the condition $1/a + 1/b < 1$.

For example:

Input: $2, 3, 1, 0.5, 3, 1.6$.
Output: $(2,3), (3,2), (3,3), (3,1.6), (1.6,3)$.

We can compare each element with each other but it takes $O(n^2)$ complexity. How to  improve that algorithm? Maybe use special structure? Maybe use sorting?


texts: When represented as a function, why is the input of a decision problem a natural number?

texts:
Our professor explained that all programs can be thought of as the set of natural numbers, while decision problems can be thought of as the set or rational numbers.

Our notes say a decision problem can be represented as a function which takes a natural number as input and maps it to either 0 or 1.
That the range is 0 or 1 is obvious but why is the input a natural number?
What does it represent? I understand that a program can be represented by a natural number but a program isn't the input for a decision problem, is it? What is the input of a decision problem and why is it represented by a natural number?


texts: Binary Indexed Tree(Fenwick Tree) - Range update and point Query

texts:
With the help of TopCoder Tutorial and this post, I was able to understand the basic idea of how basic the cumulative frequency sum is stored in the left subtree of a BIT node.I was successfully able to understand the point update and range query for which BIT is famous for.

Then I came across this post which explained the range update and point query.Applying the idea which I understood for the point update,I couldn't understand the range update.

Is the idea for range update/point query different from point update/range query? Please help with the intuition behind range update/point query.


texts: Suppose I am about to use SVM for learning a classification or ranking function. Suppose that my feature vectors are two dimensional and that values for one dimension are, say, natural numbers and the values for the other dimension are real numbers in $[0,1]$. Can this difference in magnitudes somehow negatively affect learning? Are there some guidelines for scaling feature values? Any references appreciated.


texts: Which transducer models replacement in regex?

texts:
I am looking for the right transducer which allows to translate a sequence of literals into a sequence of same literals (or a subset of them) in arbitrary order.
For example: ABC => CAB, which, with simple production rules:
A->a, B->b, C->c, results into output: cab.

I am not sure if the pushdown automata is enough to resolve such problem.

Note: My question corresponds to understand which automaton model lies under the implementation of the widely used regex replacement strategy in common libraries such as: back reference in java(link) or replacement part in sed of bash  (link).


texts: Is it possible to design a Turing Machine without extra symbols for this language?

texts: Is it possible to design a Turing Machine for the language defined as L = {0n1n | n >= 0} with only the symbols in the set of {blank, 0, 1}?


texts: Algorithm: How to find the number of independent sets in a tree?

texts: I'm thinking that there are two cases for each sub-tree: the root is in the independent set and the root is not in the set. How to write a recursive algorithm for finding the number of independent sets in a tree? The tree is n-ary.


texts: Efficiently finding "unfounded edges" in a strongly connected graph

texts:
While implementing a debugger I've encountered a problem I need to solve concerning dependency graphs. I've simplified it as follows:

Consider a strongly connected graph G = (V,E).

We define a subset of vertices S ⊆ V as source vertices.
We call an edge e = (a,b) unfounded if there is no simple path from any source vertex to b that includes e. In other words, all paths from a source vertex that include edge e, must include vertex b at least twice.

The problem:

Find all unfounded edges in G.

There are some obvious ways to solve this inefficiently (e.g. a depth-first traversal for each edge in G), but I was wondering if there was any O(|E|) approach. I've been struggling with this for a while and I keep "almost" solving it in linear time. Perhaps that's impossible? I have no idea what the lower bound on efficiency is, and I was hoping some readers here could help me discover some efficient approaches.

An illustrative example is a simple 3-cycle.  Pick any one vertex as the source vertex. The edge coming into the source vertex is unfounded.


texts:
Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly?  Given the entropy of the Gaussian distribution, it should be possible to store any value $x$ using $$\frac{1}{2} \mathrm{log}_2(2\pi\sigma^2)+\frac{x^2}{2\sigma^2}\rm{log}_2\rm{e} \;\text{ bits.}$$
Arithmetic coding should provide perfect compression.  In principle it's not too hard. I can calculate the interval boundaries from the cumulative distribution function of the Gaussian.  In practice, I hit considerable difficulties because when using floating point operations I cannot achieve perfect reproduction of the results, and I have no idea how to do this without FP operations.  Perfect reproduction is necessary because the uncompressing code must come up with exactly the same interval boundaries as the compressing code.

So my question is:  How do I compute the interval boundaries?  Or is there any other way to achieve (near) perfect compression of such data?

Strictly speaking, the normal distribution is defined only for continuous variables.  So what I mean here are integers x with a probability distribution function $$P(x)=\frac{1}{\sqrt{2\pi\sigma^2}}\rm e^{-\frac{x^2}{2\sigma^2}}.$$
This distribution does not sum up exactly to 1.  However, for $\sigma>100$  the difference from 1 is less than $10^{-1000}$ and hence it's more precise than any practical calculation would be.


texts: Find palindrome in directed Graph where edges are either blue or red

texts:
This is the given task:
Suppose you are given an arbitrary directed graph G in which each edge is
colored either red or blue, along with two special vertices s and t.
Describe an algorithm that either computes a walk from s to t such that
the pattern of red and blue edges along the walk is a palindrome, or
correctly reports that no such walk exists.
I already know the solution involves DFS in some way but I don't know how to check if a palindromic path doesn't exist. Since it's not necessarily an acyclic graph there are infinitely many paths that can potentially form a palindrome. So how do I go about this problem?


texts: complexity of computing fractional edge-chromatic number of an edge-weighted graph

texts:
Let $(G,w)$ be an edge-weighted graph, where the weights $w(e)$ are assumed to be rational.  My question is: What is the complexity of computing $\chi'_f(G,w)$, the fractional edge-chromatic number of $(G,w)$, denoted by $\chi'_f(G,w)$.

Let $M$ be the edge-matching incidence matrix of $G$. Thus, $M_{ij} = 1$ iff the $i$th edge belongs to the $j$th matching. Then, $\chi'_f(G,w)$ can be defined to be the value of the linear program: $\min 1^T x$ subject to $Mx \ge w, x \ge 0$.

A formula for this value is given by Edmond's matching polytope theorem: Let $\Delta(G)$ denote the maximum sum of the weights of edges incident to a vertex, i.e $\Delta(G) = \max_{v \in V(G)} \sum_{e: e \sim v} w(e)$ Let $\Lambda(G) = \max_{H \subseteq G} \frac{2|E(H,w)|}{|V(H)|-2}$, where the maximum is over all induced subgraphs $H$ of $G$ of odd order, and $|E(H,w)|$ denotes the sum of the weights of edges in $H$. By Edmond's matching polytope theorem, $\chi'_f(G,w) = \max\{\Delta(G), \Lambda(G) \}$.

Computing the edge-chromatic number $\chi'(G)$, vertex-chromatic number $\chi(G)$, and fractional chromatic number $\chi_f(G)$, are all NP-hard. From what I've read, it seems $\chi'_f(G)$ can be computed in polynomial time, even though the number of matchings (or number of induced subgraphs $H$) can be exponential, by solving a maximum weighted matching problem, which has complexity $O(n^4)$ or better. Also, I'm interested mainly in the edge-weighted case.


texts: Time complexity of finding an integer between $x$ and $2x$

texts:
Consider receiving as input $x\in\mathbb N$ and computing some (any) prime $p\in[x,2x]$.

  What is the complexity of the above problem?

A natural way to approach this problem is to generate random integers in $x,\ldots,2x$ and check for their primality using Miller-Rabin or a deterministic algorithm such as AKS.

However, this may be suboptimal. What is the best-known runtime for the problem?


texts: Why is this basic language not a regular language?

texts:
L = {x in {0,1}* | x has an equal number of 0s & 1s}

Based on the recursive definition of regular languages, isn't it possible to form a single regular language set over the binary alphabet {0,1} by doing the following?

concatenating 0's and 1's to form each of the binary strings satisfying the condition, resulting in a regular language consisting of that single string
union all the single-string regular languages together into one single regular language


texts: How is segmentation different from multiprogramming with fixed partition?

texts:
As seen here:
It works same like multiprogramming with fixed partition and also the memory is contiguous as well. How is it different and especially non-contiguous? What's happening here?


texts: On the hardness of constraint satisfaction

texts:
I am interested in the hardness of the following question.

Suppose we have a vector of $n$ optimization variables $\mathbf{x} = \langle x_1, . . ., x_n\rangle $ and $m$ vectors $\mathbf{v}_1, . . .,\mathbf{v}_m$ with each $\mathbf{v}_j \in \{-1,1\}$.

Our objective is to maximize the number of nonnegative dot products between $\mathbf{x}$ and each $\mathbf{v}_j$, where each $0\leq x_i\leq 1$.

That is

$$\max_{\mathbf{x}}\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$$

$$\text{such that} 0\leq x_i \leq 1$$

These constitute linear constraints and I know in general that maximizing the number of satisfied linear constraints is NP, but these constraints differ in two main ways. The first is that none have a bias term, and the second is that each coefficient of the optimization variables is either 1 or -1.


texts: Generating constraints to solve dependently-typed metavariables?

texts:
In dependent-types, Miller pattern unification is used to solve a decidable fragment of higher-order unification. This allows dependently-typed languages to contain metavariables or implicit arguments.

There are many papers which describe, given a unification problem in the pattern fragment, how to find a solution if one exists. Examples include are (Gundry-McBride), (Abel-Pientka), and the original Miller paper.

What I'm wondering is, given a dependently typed program containing metavariables (or implicit arguments), how does one go about generating the problems that are passed to the unification solver?


texts: What is a Black Box attack against Machine Learning algorithms?

texts: And is there an attack strategy that you can use to approximate the architecture of a machine learning system with the knowledge of class labels and some data points?


texts: H_max() algorithms work by considering a state in the planning graph, and using all applicable actions to make every atom in that state true. The h_max() for a given state is the cost of the most expensive atom in that state. Lets say that we have a relaxed planning task and it's heuristic (h+) then c*h_max()


texts: Is $a^n b^m$ never regular if n and m have some relation between them?

texts:
I know what regular and context free language are and how regular language needs finite memory and other stuff.

What concerns me is that I think if $a^nb^m$ such that $n$ and $m$ have some relation between them then they can not be regular. But I can't find any such thing written anywhere. Am I correct to state so?


texts:
For a job several years ago I worked with a team using technologies built around Virtual Finite State Machine models for system fault analysis and remediation. Since then, I've found it to be a generally useful approach for making control decisions in instances when control logic gets complicated and/or needs to be factored out of the rest of the software.

However, besides the initial set of publications that came out in the 90s to early 2000s (with some aborted attempts at commercialization), it seems like this topic has become completely dormant, and I've been scratching my head why.  I've found it to be a very powerful method for modeling problems with an extremely compact implementation (I can write a VFSM execution platform in less than 100 lines of Python code) - are there better methods that I'm completely unaware of? Outside of one team I worked with several years ago, none of my other colleagues are familiar with the model or technique.

The Wikipedia Article gives an overview of what VFSMs are, and the publications that define the execution model.


texts: Is there a name for the class of algorithms that are the most efficient for a particular task?

texts:
This would be analogous to the Kolmogorov complexity of a string, except that in this case, I'm interested in the algorithm that solves a given problem using the least number of steps.

We would therefore have to be able to show that any other algorithm is at best of the same order of complexity as the algorithm in question.

I'm asking because I'm working on a paper that makes use of this concept, and I was surprised when I realized that I'm not aware of any name for this concept, though I'll concede I'm risking embarrassment if there is such a name that I'm simply unaware of.


texts: How to solve a knapsack problem using a modified version of DP?

texts:
Im having difficulties understanding how to solve the knapsack problem using dynamic programming, where v is value and w is the weight, where I can fill up to a maximum weight j for some Capacity_J:

                               capacity_J
                          J_0   J_1  J_2   J_3  J_4  J_5  J_6
                            0     1    2    3    4    5    6
 I_1    v(1) = 4, w(1) = 2  0     0    0    0    0    0    0
 I_2    v(2) = 3, w(2) = 1  0     0    0    0    0    0    0
 I_3    v(3) = 2, w(3) = 3  0     0    0    0    0    0    0
 I_4    v(4) = 2, w(4) = 2  0     0    0    0    0    0    0

Using the following algorithm:

        for i = n . . . 1 do
                for j = 1 . . . k do
                      if w(i) ≤ j then
                        DP[i, j] := max(v(i) + DP[i + 1, j − w(i)], DP[i + 1, j])
                      else DP[i, j] := DP[i + 1, j];
        return DP[1, k]

Where DP is the recursive formula.

My understanding of that is:

I start with i = n = I_4

For j = 1 = J_1 I check if w(i) ≤ j -> 2 ≤ 0 so I go to DP[i, j] = DP[4 + 1, 1] which does not make much sense for me since max(I) = 4

My confusion comes from the fact that most explanations on that topic uses  different version of the knapsack algortihm:

    for i from 1 to n do:
        for j from 0 to k do:
            if w[i] > j then:
               DP[i, j] := DP[i-1, j]
            else:
               DP[i, j] := max(DP[i-1, j], DP[i-1, j-w[i]] + v[i])

Resulting in:

                                 capacity_J
                          J_0   J_1  J_2   J_3  J_4  J_5  J_6
                            0     1    2    3    4    5    6
 I_1    v(1) = 4, w(1) = 2  0     0    4    4    4    4    4
 I_2    v(2) = 3, w(2) = 1  0     3    4    7    7    7    7
 I_3    v(3) = 2, w(3) = 3  0     3    4    7    7    7    9
 I_4    v(4) = 2, w(4) = 2  0     3    4    7    7    9    9

However, I suppose if using the first version of the knackpack algortihm the direction of the movement is changing regarding the starting and ending position.

Appreciate if someone could provide examples of some iterations for the first algorithm.


texts: Is the intersection of two regular languages regular?

texts: Trivially decidable problem is one in which the problem is a known property of the language/grammar. So  intersection of two regular languages is regular should be trivially decidable? But it is given as not trivially decidable.


texts:
Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$.
(We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number).
First of all of course we can calculate it via $dp[i][j]$ - number of tree with height $i$ and $j$ vertices, then we divide $dp[h][n]$ by $C_n$ and obtain the result, but it's hard to do using C++ (because $C_{40}$ is very huge and calculation will be incorrect).
Of course we can consider $dp[i][j]$ - is probability that tree has depth $i$ and contains $j$ vertices, but then dynamic step is slightly incorrect ($dp[i][j] = dp[i - k][h - 1] * dp[k][h - 1]$, but it also fail initial values of $dp[i][j]$).
Maybe I should reconsider my dp? Any ideas?


texts:
I am given that $Z$ is independent of $(X,U)$, where $Z$ and $X$ are binary random variables while $U$ is an arbitrary random variable. I need to prove the following:
$$ H(X\oplus Z|U) \geq H(X|U)$$
Am I doing this right?:
$$ H(X\oplus Z|U) - H(X\oplus Z|U,Z) + H(X\oplus Z|U,Z) - H(X|U)$$
$$ H(X\oplus Z|U) - H(X\oplus Z|U,Z) + H(X|U,Z) - H(X|U)$$
$$ H(X\oplus Z|U) - H(X\oplus Z|U,Z) + H(X|U) - H(X|U)$$
$$ I(X\oplus Z;Z|U) \geq 0$$
I manipulate the intial expression. I am not very confident about the proof. Can someone verify?


texts: Frigo's cache-oblivious algorithms paper

texts:
I am reading Frigo's "Cache-Oblivious Algorithms" paper and I need help understanding his cache complexity expressions for the base cases.

He starts on page 3 with "An $s \times s$ submatrix is stored on $\Theta (s + s^2/ \mathcal{B})$ cache lines.  I can see the reason for $s^2/ \mathcal{B}$ is because we have $s^2$ numbers in total and we can fit $\mathcal{B}$ worlds per line.  But where is the other $s$ coming from?  Is this because we need to store $s$ pointers to each of the $s$ rows of the matrix?

Matrix Multiplication

Next, we have the matrix multiplication algorithm.  First, I like to confirm when do we actually get a cache miss.

If the matrix is small, does that mean it is already in cache and we never miss?
If divide and conquer is needed, then is the matrix brought into cache when it is small enough so that is why we have cache misses at that point?

Here, in the base case (Case I), it says we need $\Theta ( (mn + np +mp)/\mathcal{B})$.  I can see the reason here being we just have the total number of entries in each matrix, divided by how many can fit in one cache line.

But after that, I don't see how the other cases come about.  For example, in Case II, if $n, p \in [\alpha \sqrt{ \mathcal{M}}, \sqrt{ \mathcal{M}}]$, then the $n \times p$ size matrix B can be brought into cache and it will occupy $np/\mathcal{B}$ cache lines, but what are the $n$, $m$, and 1 in the expression of equation (5) 's base case for?

In Case III, equation 6 shows the base case if $m \in [\alpha \sqrt{ \mathcal{M}}, \sqrt{ \mathcal{M}}]$ then the base case cache complexity is $\Theta (1 +m)$.  Is this $m$ the $m$ cache lines for this matrix?  What happened to the $n \times p$ matrix B?  Is it already in cache.  If so, didn't we also incur cache misses before loading it?

Then finally, isn't Case IV the same as Case I's base case?  Why is there a 1 in the $\Theta$?.

Matrix Transpose

Next, the paper discusses matrix transpose.  Here, in Case I, I can see $2mn/\mathcal{B}$ is the number of lines in cache needed to store a total of $m \times n$ entries in the matrix.  But what is the 1 overhead for?

Then, for Case II, it says "The output array consists of nm elements in $m$ rows"...However, I thought the output matrix $B$ defined above has $n$ rows!?  Where is the $m$ rows coming from?

Then a bit later in the paragraph, we get that since $n \geq \alpha \mathcal{B} /2$,  the cache complexity is $O(1+m)$.  Is this because

\begin{align*}
n \geq \alpha \mathcal{B}/2 \to m + nm/\mathcal{B} \geq m + \alpha /\mathcal{B} =O(1+m) ?
\end{align*}

Finally, in Case III, equation (8), when the matrix A is small, it is $m \times n$, so it will take $mn/\mathcal{B}$ cache lines...but again, why this $m$ and $n$ in $O(m +n + mn/\mathcal{B})$?


texts:
I need to proof the following by turing reduction.

Given two languages:

$Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$

$I= \{\langle M \rangle \mid \;\vert L(M) \vert = \infty \}$

Where $\langle M_1 \rangle$ is the encoding of Turing Machine $M_1$.

I need to show that $ I \le_T Q $ ($I$ can be reduced to $Q$ using a Turing Machine).

So far I came up with the following idea, which I think isn't correct.

Create Turing Machine $M'$ so that a mapping from $Q$ to $I$ is found:

$M'$ takes as input a random word $u$ for example $aab$
$M'$ removes the input ($u$) from its tape
$M'$ guesses words $v$ and $w$
$M'$ checks if $v \in L(M_1)$ and $ w \in L(M_2)$ if and only if $v = w$


texts: Does a multi cpu system not improve the first come first serve (fcfs) cpu scheduling algorithm?

texts:
I created a program that simulates the fcfs scheduling algorithm. First I implemented it for a single core, then modified it for four homogenoues cpus.

I compared the results with several datasets, and for the most part they are identical.

I understand fcfs is nonpreemtive, so there are no context switches. Then each cpu holds the process until its current cpu burst is finished, from there it either terminates or does IO (goes to wait queue).

Im guessing a multi core system only improves performance if many processes are in the ready queue at the same time, otherwise only one cpu is being used.

Here is the algorithm that I implemented:

while(TRUE)
{
    for(i = 0; i < NUM_CPUS; i++)
    {
        if(!cpu[i].idle)
        {
            if(cpu[i] is finished executing current burst)
            {
                //either move the process from the cpu to the waitQ, or terminate process if finished all bursts
                if(terminatedPrs == numberOfProcess)
                    break;
            }
        }
        if(waitQ->front != NULL)
        {
            //Check if waitQ->front is finished io
            if(waitQ->front finished IO burst)
            {
                //insert waitQ->front to readyQ, then dequeue waitQ
            }
        }
        if(cpu[i].idle)
        {
            if(readyQ->front != NULL)
            {
                //check if readyQ->front is ready to be executed (that is, arrival time < elapsedTime)
                if(readyQ->front ready to be executed)
                {
                    //move readyQ->front to CPU (begin executing), and dequeue readyQ
                }
            }
        }

    }
    elapsedTime++;
}

Is my algorithm fine? I am getting pretty much the same average waiting time, average turnaround time and average cpu utilization.


texts: Find maximal matching in tree in $O\left(\frac{n}{\log n}\right)$

texts:
As any tree can be described as a binary sequence ($i$-th bit is 0 if the edge goes down and 1 otherwise, every edge is travelled twice $-$ up and down, so such sequence's length is $2 |V| - 2$), any tree of size $n$ can be encoded as $O\left(\frac{n}{\log n}\right)$ integers (assuming an integer holds $\log n$ bits in our model).

The task is to find maximal matching in a tree given in a described form in $O\left(\frac{n}{\log n}\right)$ time (thus, linear in the integer count).

I was wondering if any simple solution exists, as for trees I can find maximal matching in $O\left(n\right)$ time using simple dynamic programming approach.


texts: Confusion in the added loop of the Halting Problem

texts:
I know there's like a thousand questions about this topic in the site and elsewhere. I'm just going to pick one that at least for me it serves as a good basis for my question. The answer by Rick Decker is the one that I understood more, so I'm just going to take it as a basis for my actual doubt.
It's not difficult to see that if one adds an if (and extra loop) into 'Halting Program '  $H$, then feeding $H$ to itself yields a contradiction. What it confuses me is why to add the extra loop to force the contradiction, if by hypothesis $H$ solves (itself?)
It doesn't seem logical to say first (of course I'm missing something), hey I give you $H$ that solves your issue, but afterwards I give you an augmented $H$ that does not and so we reach a contradiction.


texts: Linear regression: not noramalising by y's norm

texts:
I was recently reading an article on Pearson correlation, and OLS coefficients. I came across the following section.

  Finally, these are all related to the coefficient in a one-variable
  linear regression. For the OLS model yi≈axi with Gaussian noise, whose
  MLE is the least-squares problem  \begin{align}\arg\min_a \sum (y_i –
 ax_i)^2\end{align} a few lines of calculus shows a is

  \begin{align}  OLSCoef(x,y) &= \frac{ \sum x_i y_i }{ \sum x_i^2 }
 = \frac{ \langle x, y \rangle}{ ||x||^2 }  \end{align}

  This looks like another normalized inner product. But unlike cosine
  similarity, we aren’t normalizing by y’s norm — instead we only use
  x’s norm (and use it twice): denominator of ||x|| ||y|| versus ||x||2.

  Not normalizing for y is what you want for the linear regression: if y
  was stretched to span a larger range, you would need to increase a to
  match, to get your predictions spread out too.

I understand that using calculus we can arrive at an expression for finding a, the coefficient. The expression's denominator turns out to not contain y's norm. In the last paragraph of the excerpt, I could not understand the following line

  Not normalizing for y is what you want for the linear regression

Why don't we want to normalize for y? What is the physical/geometrical significance of this?


texts: Asymptotic analysis of shifting/multiplying

texts:
I am currently working on the asymptotic analysis of Karatsuba algorithm and I have this line

"return (X * B^ (2 * m)) + ((Z) * B ^ (m)) + (Y)"

where X,Z,Y are some numbers, m is in fact floor(n/2), where n is the length of the input, and B is a base(could be 10, then we would have decimal numbers).

I was wondering whether someone could help me with calculating the complexity of

((Z) * B ^ (m))

Multiplication is always Theta(n^2), but the whole algorithm has Theta(n) in the solutions.

I know that the cost of performing an addition is Theta(n), but what would be the cost of the that function, given I have already calculated Z.

I have also written a code, which instead of multiplying the numbers, just shifts them, and I believe that would have cost of Theta(n). Is this the case that I can always shift no matter what base I use?

Thanks!


texts: There are 10 Egyptian stone statues standing in a row in an art gallery hall. A new curator wants to move them so that the statues are ordered by their height. How should this be done to minimize the total distance that the statues are moved? You may assume for simplicity that all the statues have different heights.


texts: Is that true that A is decidable if A$\le_m$A complement?

texts:
A is decidable if A$\le_m$A complement

Can i think that it is true because decidable is close under complement, so if A complement is decidable, so is A


texts: What happens under the hood when the process requests operating system to open a file?

texts: Suppose a process wish to open a file named test.txt. So it issues a system call requesting Operating system to find the file on disk,and to grab the handle of file to operate on it. My question is how does the operating system actually locates file on disk(Particularly sequence of actions the operating system performs to do this)? How partitions,file systems,directory structures used to accomplish this? (If possible kindly explain with an example)


texts: Does $f(n)=\theta(g(\log{n}))$ imply $f(n)=\theta(\log{g(n)})$?

texts:
I am learning about algorithmic complexities and I have this claim which I need to prove or disprove: $f(n)$ and $g(n)$ are asymptotically positive functions, if $f(n)=\Theta(g(\log(n))$ then $f(n)=\Theta(\log(g(n)))$.
Is it true?


texts: Importance of a person to another person in social network

texts:
In social network (an unweighted indirect network), is there some measure of importance of a person A on another person B, denote as I(A,B), so that (approximately):

The smaller the shortest distance between A, B in the the network, the higher the I(A,B) (closeness)
If A_1 is 1 of the 100 friends of B_1,  A_2 is 1 of the 2 friends of B_2, then I(A_1,B_1) < I(A_2,B_2) (the more friends I have, the less importance of each one)
Some other reasonable properties that resemble the importance of a friend to another friend in real society.


texts: Finding the Regular Expression of a language

texts:
I'm trying to find a regular expression for the language
$$L = \{w\mid n_a(w)+n_b(w)\equiv 2\pmod3\}\,,$$
where $n_a(w)$ is the number of $a$s in $w$.

I can see that this would generate strings of length $3n-1$ and
I can write the expression for a string of whose length is a multiple of three: $(( a + b )^3)^*$. But that's not quite what I need.

The alphabet is $\{a,b\}$


texts: Is there a sorting algorithm of order $n + k \log{k}$?

texts:
I'm given an integer vector which is said to contain many duplicate values (total of k distinct integers), for example

[1, 4, 2, 5, 5, 3, 4, 2, 2, 5]
(n = 10, k = 5)

and am asked to find a sorting algorithm that averages $O(n + k\log{k})$. I've concluded that partial quicksort (or quickselsort) might achieve this, but doesn't seem to utilise that the vector contains duplicates. Am i missing some basic algorithms here?


texts: What is the complexity of determining Satisfiability of a CNF containing both Horn and Dual Horn clauses?

texts:
If a CNF contains both horn and dual horn clauses and does not contain clauses of other types, then can its Satisfiability always be determined in polynomial time?

If the answer to the above problem is yes, then suppose we only add XOR clauses in addition to horn and dual horn clauses, can the Satisfiability of this type of CNF be determined in polynomial time?


texts: Are there any useful deterministic quantum algorithms for decision problems?

texts:
The vast majority of known interesting quantum algorithms are probabilistic.  The only deterministic quantum algorithms that I know of (which aren't trivially equivalent to a classical algorithm) are (a) Deutsch's algorithm, in which the quantum speedup is pretty trivial, (b) the Deutsch-Josza algorithm, which solves a promise problem rather than a decision problem, and (c) this algorithm (which I found by Googling): http://arxiv.org/abs/1108.5848, which also doesn't solve a decision problem.  Are there other known examples of "interesting"/"useful" deterministic quantum algorithms, especially for decision problems?

I know that this question isn't particularly well-formulated, because which algorithms you can use depends on which set of quantum gates you have available.  Are there any interesting algorithms that use only a "realistic" set of quantum gates?  (Say, only the quantum gates that can be currently purchased on Amazon for under $10 :-) .)


texts: Modern presentation of Ackermann's "Solvable Cases?"

texts:
Ackermann's book "Solvable Cases of the Decision Problem" discusses decidable instances of first order logic, particularly monadic logic, and so called "equality formulas". However, the book is from 1954, the notation is terse, full of German letters, and presented in a very non-algorithmic way (which is unsurprising, given the time). I'm having some trouble reading it.

Have any papers given the results from the book in a more modern presentation? Perhaps using modern inference-rules, pseudocode for algorithms, and better typesetting? I'm particularly interested in the section on monadic logic, since other references I have found have described it as "implementable in practice", despite giving no clues as to why this is true.


texts:
Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"?

In other words, if * would always match as much as possible and no backtracking is allowed, would I still be able to express any regular language?

Let's say that @ is the possessive * operator.

There are cases where it doesn't matter: a*b and a@b both will match any string with 0 or more $a$ followed by a $b$.

However there are cases where being possessive is relevant: a.*b will match any string that starts with $a$ and ends with $b$ but a.@b will never match any string as the greedy @ will eat any character, including the ending $b$.  The equivalent expression would be a[^b]@b.

One may be tempted to think that for any non-possesive expression there is an equivalent possessive expression and viceversa but I wasn't able to find any proof of this.

I'm limiting myself to * considering a+ equivalent to aa*.

As D.W. suggested in the comments below, I tried to start from the DFA. I didn't go much far, as this seems to have more to do with the way the non-determinism is handled, rather than with the structure of the automaton.

Could anyone point me in the right direction?

EDIT 3

I've posted an answer that I believe is correct.

EDIT 2

(REMOVED)

EDIT 1

(It has pointed out to me that the right term to use would be "possessive" (http://www.regular-expressions.info/possessive.html) rather than "greedy". Thanks.)


texts: Babai proved that there is a quasi-polynomial-time algorithm for graph isomorphism. Has anyone implemented this algorithm? I think the code will be easier to understand than his paper, because of the amount of abstract algebra one needs to master beforehand. Of course one may need to learn that after reading the code. But has it been implemented?


texts: Reducing max flow to bipartite matching?

texts:
There's a famous and elegant reduction from the maximum bipartite matching problem to the max-flow problem: we create a network with a source node $s$, a terminal node $t$, and one node for each item to be matched, then add appropriate edges.

There's certainly a way to reduce maximum flow to maximum bipartite matching in polynomial time, since both of them can be each individually be solved in polynomial time. However, is there a "nice" polynomial-time reduction from max-flow (in general graphs) to maximum bipartite matching?


texts: How do Kruskal's and Prim's algorithms compare to each other?

texts: I understand that both of them are used to find minimal spanning trees, and I've seen their implementations, but I don't understand how both of them compare to each other, and how they differ in complexity.


texts: Description of resolution algorithm as it applies to SAT

texts:
SAT [5] can be solved with resolution definitively, i.e. if the formula has a true assignment, resolution can find it, and if it cant be satisfied, resolution can show that no assignment exists (at least in exponential time/space.). [4]

  Is there a good fully-self contained description somewhere of solving SAT with resolution?

The descriptions on Wikipedia of resolution are focused on a single logical operation, not how to use it in an algorithm to solve SAT, and the Davis Putnam algorithm is described mostly in terms of 1st order logic. I am looking for a description of solving SAT with resolution that does not refer to 1st order logic, just in terms of boolean input variables. Online description is preferred if possible. The connection with DPLL would be helpful also.

[1] Davis Putnam algorithm, Wikipedia

[2] Resolution in logic, Wikipedia

[3] Davis Putnam Logemann Loveland algorithm, Wikipedia

[4] Is resolution complete or only refutation-complete?

[5] The boolean satisfiability problem


texts: Why can no task have a utilization rate greater than one?

texts:
Let $C_i$ be the execution time for task i, $T_i$ be the task period and utilization rate $U = \frac{C_i}{T_i}$

  Then $U$ must be less or equal to $1$ for the task to be schedulable

  Proof:

  Let $\hat T$ be the lcm of task $T_1,...T_n$ i.e. $\hat T = \prod_i
> T_i$. Define $\hat L_i = \hat T/T_i$ the number of times the task is
  run. Then the total number of execution is $\sum_i C_i/\hat L_i = \sum_i \frac{C_i \hat T} {T_i}$. Suppose utilization rate $U >1$, then
  $\sum_i \frac{C_i \hat T} {T_i} > \hat T$ which is impossible. End of
  proof.

I am confused about several things in the proof.

First, what is the physical quantity representing the product or lcm of all the task periods $T_i$? It would make more sense if it was the sum of all the $T_i$ which represents the total task period.

Second, $\sum_i C_i/\hat L_i$ represents the total time spent on execution, I do not get how if this time is larger than $\hat T$, then the tasks would not be schedulable. This goes back to my misunderstanding of what $\hat T$ is.

Can anyone help?


texts: Orthogonal range reporting with fixed upper rectangular corner

texts:
Consider the following special case of orthogonal range searching:

Given a set $S$ of $n$ points in $d$ dimensions, and rectangular queries with a fixed "upper-left" rectangle corner $(0,0,...0)$, report the total number of points inside the rectangle.

This is different in that all rectangles queried have a fixed corner. In this case, will we have a dynamic algorithm with a better runtime, or is the problem still as hard as general orthogonal range searching?


texts: Approach to data compression with unknown patterns

texts:
Let's say I have a file with symbols of an alphabet [0,N-1], N around 50. The actual data is a file with a lot of lines, each containing 100 of these symbols.

I want to compress this data. By doing a frequency analysis over a large amount of lines to build a probability density function and then calculate the entropy you get far better than just log2(N), but yet it is not enough. Getting to the entropy is pretty easy as I'm using arithmetic coding and it really nails it, the problem is getting the model right...

I've tried using some contexts and it gets slightly better, but it is not computationally feasible to use models with the last 1000 symbols... so I'm basically looking for another approach.

Does it make sense to use Neural Networks? what would be the approach? I can't figure out what the inputs would be... perhaps the last K symbols, and the output the predicted one, then compress the error? Truth is I've never dealt with Neural Networks before.

Also, is there any way I can know if using a NN would indeed work better? Looking at the raw data it surely seems that there is some pattern... or at least sometimes...


texts:
Imaging I am running a forum and I continuously have log in of members. A member can log in simultaneously many times

So I have :

Tom Jerry Jack Tom Joe Kay Neo Tom ...

each log in comes with a time stamp

I want to have an algorithm that can count how many UNIQUE names have logged in the past 1 minute.

How to design an algorithm like this?

My design is to use a std::map then continuously update/trim the map

I am wondering if there is any smarter solution here.

Any insight?


texts: Brute force algorithm for "Binary Puzzle"

texts:
Binary puzzle

Binary puzzle is an puzzle played on a $n × n$ grid; intially some of the cells contain a zero or a one (fixed cells); the aim of the game is to fill the remaining empty cells according to the following rules:

Each cell should contain a zero or a one.
No more than two similar numbers next to or below each other are allowed.
Each row and each column should contain an equal number of zeros and ones.
Each row is unique and each column is unique.

Decision problem:

  Input : A partially filled n×n grid with 0's and 1's.

  Question : Can we fill the
  empty cells with a zero or a one in a way that follow the above mention rules ?

For $n \times n $ this problem known to be NP-complete.

Brute force Algorithm :

If the given $n \times n$ is empty then it is an yes instance ( use the basis set of $ \mathcal{ R^{n\times n}}$).
Case I: If only one row is filled and it is an valid row  (follow the above mentions rules ) then it is an yes instance. Second row is going to be the complement of first row (make 0 to 1 and 1 to 0).
Case II : if $k$ rows are filled and they are valid then I can fill the table upto 2k rows by using trick of complement.

Question :  How to design a brute force algorithm for the problem stated above ?