texts:
Thank you for looking into this, I have a problem regarding direct cache mapping, My problem really though is with the question formation itself and the problem I am about to present seems to have inconsistency and has unclear description. So the problem is as follows ( I am presenting exactly as given )

32 bit architecture
Main memory size = 8GB
cache size = 512KB
Block size = 32 words
To Find

Number of bits required for Byte Offset = ?
Number of bits required for main memory address = ?
Number of bits required for main memory block number = ?
Cache Index bits = ?
Tag-bits = ?
Size of Tag Directory = ?

Now My Interpretation of the solution is as follows

As it is 32 bit architecture which means Word size is 4 Byte ( I am confused about this part the most as the question states cache block size in Words but expects to calculate Byte offset ) but for the sake of this problem, moving on main memory size is 8GB that's 233Bytes, cache size ( blocks only, this does not include tag directory which is part of cache controller ) Block size of 32 Words or 128 Bytes, now If you agree with me on this much, or else this is probably where I am wrong so please correct me right here. Now assuming I am correct so far, I will first calculate main memory address bits, that will be, first let's calculate it's size then let's do binary log, that will be  233Bytes / 4 Bytes per word this comes out to be 231 Words means 31 bits for memory address and our second answer, next I calculate number of main memory blocks that will be  233Bytes / 128 Bytes per block this comes out to be 226 Blocks of main memory so the number of bits required for main memory block number would be 26 bits, so this gives our third answer, moving forward as I assume a single cache/main memory block to be of 128 Bytes and not Words. So for byte offset within a block it must be 7 bits ( Point of highest concern ) and this should be our first answer according to the question. Now let's calculate number of cache blocks that will be 219Bytes / 128 Bytes per block which is 212 Blocks so cache index size will be 12 bits which is our fourth answer, we're almost done ! Now Tag bits should be and since it's direct mapped it should be memory address size - ( cache index + Word or Byte offset ) that is ( 31 - (12 + 7)) = 12 bits that is our fifth answer and finally size of tag directory will be  212Cache Blocks * 12bits per tag, Now not going into exact answer in KB's is this approach right or have I made a mistake or is the problem formulation incorrect ( as I think the mistake must be with cache blocks being in bytes or words ) ?


texts:
Why can't arbitrary base conversion be  as fast as converting from base $b$ to base $b^k$ ?

Seems to be a big time complexity difference! I am also interested in reading material about it.

Old. Original detailed question

Conversion between power-2-radix can be done faster than between non-power-of-2 radix, they can be even done in parallel, as every digit (or some groups of them) can be decoded independently of the rest.

For example the binary number 00101001 can be converted to hexadecimal 0x29 nibble by nibble (0010 and 1001), and vice versa (i.e. every hex-digit can be parsed to 4 bits independently of the rest), but doing that conversion from decimal (or any other non-power-of-2 radix) to binary, it's not so easy because digits affects each other!.

I've seen time complexity of maths operations in wikipedia, and there is also a related question in stackoverflow saying time complexity of conversions of arbitrary digit length to be $\mathcal{O}(M(n) log(n))$

I'm not interested in a "general time complexity bounds for any base conversion" but I would like to know more about these big differences in time complexity between "power-of-2 conversions" vs "any other base conversions".

I think there is a general fact about conversions that can be done faster if they are done between numbers where its bases are power among themselves, not only for 2, but the same to a base 10 to base 100.

Is there any known proof or materials around this ?


texts: What exactly (and precisely) is "offset"?

texts:
Just like my previous question concerning 'hash'; what exactly is an (or the) "offset?"

Is it a value or data type? Or is it an address location? I have heard it used in different contexts within the computing world. Of course, I have come across it while mounting a disk image; but does it have any other usage than that. I ask this because I have come across the word at other places. Does it have to do anything with memory registers?


texts: Is natural semantics a total or partial function

texts:
I have the following def's

Sns : Stm → (State ֒→ State)

Sns[S] = s' (if <S,s> -> s') else undefined

I'm wondering if Sns is a partial or total function. I think it's total since it always returns a partial function, given any statement.

But the book I'm reading (semantic with application by wiley, pg 41) says:

  Note that Sns is a well-defined partial function because of
  Theorem 2.9. The need for partiality is demonstrated by the statement
  while true do skip that always loops.

I'm very confused.


texts:
I got a matrix of integers of size $3\times n$. Of each one of the three rows, for each column I got to choose one number, with the restriction that, for each $i$, the numbers chosen in the $i$th and $(i+1)$st rows cannot come from the same column.

The problem asks to make an algorithm such that the summation of all the numbers I've chosen  is the minimum possible, has time complexity $O(n)$ and space complexity of $O(1)$.

I know how to do this with dynamic programming, in a more classical way: I calculate the sub-problems, store the results in a matrix of size $3\times n$ until the matrix is complete, then the result is the minimum value of the last row.

The problem is that will have space complexity of size $O(n)$, what I'm not seeing?


texts: Substitution of monomorphic type variables in generalized Hindley–Milner

texts:
I am trying to understand the constraints-based Hindley–Milner type inference algorithm described in the Generalizing Hindley-Milner paper. The function $\text{S}\small{\text{OLVE}}$ is defined as follows:

$$
\begin{array}{l}
\text{S}\small{\text{OLVE}} :: Constraints → Substitution \\
\text{S}\small{\text{OLVE}} (\emptyset) = [\ ] \\
\text{S}\small{\text{OLVE}} (\{ \tau_1 \equiv \tau_2 \} \cup C) = \text{S}\small{\text{OLVE}} (\mathcal{S} C) \circ \mathcal{S} \\
\quad \quad \quad
\text{where}\ \mathcal{S} = \text{mgu}(\tau_1, \tau_2) \\
\text{S}\small{\text{OLVE}} (\{ \tau_1 \leq_M \tau_2 \} \cup C) = \text{S}\small{\text{OLVE}} (\{ \tau_1 \preceq \text{generalize}(M, \tau_2) \} \cup C) \\
\quad \quad \quad
\text{if}\ (\text{freevars}(\tau_2) − M) \cap \text{activevars}(C) = \emptyset \\
\text{S}\small{\text{OLVE}} (\{ \tau \preceq \sigma \} \cup C) = \text{S}\small{\text{OLVE}} (\{\tau \equiv \text{instantiate}(\sigma)\} \cup C) \\
\end{array}
$$

Most of this is clear, but where I am confused is around how substitution is defined for the monomorphic set $M$. The paper explains that

  For implicit instance constraints, we make note of the fact that the substitution also has to be applied to the sets of monomorphic type variables.

$$
S(\tau_1 \leq_M \tau_2) =_{def} \mathcal{S} \tau_1 \leq_{\mathcal{S} M} \mathcal{S} \tau_2
$$

but I don't find any details of how $\mathcal{S} M$ is defined. Based on Example 3, I think we should get something like:

$$
\text{S}\small{\text{OLVE}} (\{\tau_4 \leq_{\{ \tau_1 \}} \tau_3, \text{Bool} \rightarrow \tau_3 \equiv \tau_1 \}) \\
= \text{S}\small{\text{OLVE}} (\{\tau_4 \leq_{\{ \tau_3 \}} \tau_3 \}) \circ[\tau_1 := \text{Bool} \rightarrow \tau_3]
$$

In this step, unifying $ \text{Bool} \rightarrow \tau_3 $ and $ \tau_1 $ gives a substitution $ \mathcal{S} = [ \tau_1 := \text{Bool} \rightarrow \tau_3 ] $, and $ M = \{ \tau_1 \} $, and so apparently $ \mathcal{S} \{ \tau_1 \} = \{ \tau_3 \} $, but how do we arrive at that? Maybe there is something obvious I have overlooked here.


texts: Skip List estimate number of elements less than (or greater than) a value

texts:
I am looking for a thread safe data structure where

an element can be searched in $O(\log n)$,
for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,
an element can be inserted in $O(\log n)$, and
an element can be removed in $O(\log n)$.

Can a skip list or some modification of it be used?  Is there an alternative data structures (Parallel Red-Black Tree for example) that can be used?


texts: Monograph or survey paper on smoothed analysis of algorithms

texts:
The paper by Spielman and Teng, Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time (JACM 51(3):385–463, 2004), won a Gödel award in 2008.

Since then, has there been a monograph or substantial survey paper written on the subject?

The best I could find was a book chapter in Algorithm Engineering by Müller-Hanneman and Shirra.


texts: Skolemization with multiple arguments -- how to unify

texts:
Edit:  answerers keep finding (valid!) problems with my example.  I'll try again.  The older version is below the horizontal line.  Thanks to Klaus below for pointing out the last problem.

My question is how to unify skolemizations that have differing numbers of arguments.  As he points out, there is rarely any need for this.  For example, if the statements are

Some homes are blue.
There is a home with two stories.

The skolemizations here should not unify, because we can't know from this if a blue home is two-storied.

If we're going to ever need to unify one skolemization with another, we'll need to know we're talking about the same home.  This would do it:

Jane's and Mark's home is blue (their only home).
Jane's home has two stories (her only home).

Here it is in FOPC:

$$
    \exists x: has(Jane,x) \wedge has(Mark,x) \wedge home(x) \wedge blue(x) \wedge
$$
$$
(\forall y: has(Jane,y) \wedge home(y) \implies x=y) \wedge
$$
$$
(\forall y: has(Mark,y) \wedge home(y) \implies x=y)
$$
and
$$
    \exists x: has(Jane,x) \wedge home(x) \wedge twoStories(x) \wedge (\forall y: (has (Jane,y) \wedge home(y) \implies x=y)
$$

Converting to conjunctive normal form with skolemization gives us this set:

$$
    has(Jane,skolem1(Jane,Mark))
$$
$$
    has(Mark,skolem1(Jane,Mark))
$$
$$
    home(skolem1(Jane,Mark))
$$
$$
    blue(skolem1(Jane,Mark))
$$
$$
 \neg has(Jane,y) \vee \neg home(y) \vee skolem1(Jane,Mark) =y
$$
$$
 \neg has(Mark,y) \vee \neg home(y) \vee skolem1(Jane,Mark)=y
$$

$$
 home(skolem2(Jane))
$$
$$
 twoStories(skolem2(Jane))
$$
$$ \neg has (Jane,y) \vee \neg home(y) \vee skolem2(Jane)=y
$$

Now, if I want to reason about whether there's a blue house with two stories -- which I should be able to start by resolving the first and last clauses in the set -- I can't, because the two skolemizations can't unify: they have different numbers of arguments.

Is there a good protocol of picking arguments to prevent this problem -- other than applying human intelligence after the mismatch is noticed?

Here is the old version.  It's significantly different, but as Klaus pointed out, the old version simply doesn't give us a skolemization problem (or even a skolem for the first statement):

"Everybody who has a home pays utilities on it," encoded as

$$
     \forall x: has(x,skolem1(x)) \wedge home(skolem1(x)) \implies paysUtilsOn(x, skolem1(x))
$$
or
$$
    \bar has(x, skolem1(x)) \vee ~home(skolem1(x)) \vee paysUtilsOn(x, skolem1(x))
$$
and "Jane and Mark have a home," encoded as
$$
    has(Jane,skolem2(Jane,Mark)) \wedge has(Mark,skolem2(Jane,Mark)) \wedge home(skolem2(Jane,Mark))
$$
or
$$
    has(Jane,skolem2(Jane,Mark))
$$
$$
has(Mark,skolem2(Jane,Mark))
$$
$$
    home(skolem2(Jane,Mark))
$$

I want to use resolution to prove Jane pays utilities.  The problem is that skolem1 has 1 argument and skolem2 has 2 arguments, so they don't unify.

I'm not sure if this matters -- could I just refer to skolem1 and skolem2 and forget the arguments entirely?  If it does matter, how do I resolve the problem so that skolem1 and skolem2 can unify, and resolution can work?  Not by finding a way around the problem, but by truly using skolemization correctly.  The issue is what to do with skolems that have different argument lists if they seem to occur naturally.


texts: Parallel algorithm for Chinese remainder theorem

texts:
What is the most efficient (in terms of running time) algorithm that solves the Chinese remainder theorem (CRT) on a set of integer residues. That is, given a set of moduli $\{m_i\}_{i=1}^{r}$ and set of residues $\{x_i\}_{i=1}^{r}$ such that $X \equiv x_i~mod~m_i$, find $X \in \mathbb{Z}_M$ where $M=\prod_{i=1}^{r}m_i$.

Are there any parallel algorithms to calculate $X$?

If there is a parallel algorithm, how does it account for large values of $X$ that can exceed the underlying computing machine word length?

Pointers to relevant resources are appreciated.


texts:
So I'm working on a project and I'm totally stuck right now on how to generate an nxn matrix in Matlab (where n is defined by user input).  I need to make a matrix that has ones diagonally, zeroes below it, and values of negative one above.  As a 2x2 example shown right here:
[1 -1
0  1]
I would show the code that I have, but I'm blank on how to make it actually do that.  I know how to get it to accept user input.  I also figure that nested for loops may be able to work here, because if I could generate an nxn matrix with values I can set, I can have two variables, like r and c (rows and columns).  For the diagonal, where r=c the values can equal 1, -1 where r is less than c, and 0 where r is greater than c.  Problem is I'm not sure how to generate a matrix where you can set values in it like that.  I know you can generate an identity matrix with the 'eye' command, but that just has the diagonal values equal to 1.  I can give more information, but if there's some command for that I'm missing, I could really use to know.  Thank you.


texts: "If any problem in NP is not polynomial-time solvable, then no NP-complete problem is polynomial-time solvable."

texts: This is given vertabim in my lecture slides and it seems like I'm having difficulty proving this statement mathematically. I know that P is a subset of NP and NP-Complete is also a subset of NP. But what else do we have to prove for this statement?


texts: Counting the nodes of a unidirectional graph

texts:
Suppose that we have the above graph. The graph is directed and is unidirectional; that is, we can only traverse it from top to bottom.

We want to update the count of the nodes such that the count of any given node indicates the sum of the count of the node itself and the previous nodes, avoiding any duplicate nodes.

Example

For $ id:5 $ the count will be the sum of counts of $id:1,2,3,4$.
So, the count will be calculated as
$Count(id:5) = \sum Count(ancestors) + selfCount$.

So, the $Count(id:5) = 5$ in this case.

Implementation that has been thought of

One such implementation could be traversal from top to bottom, and updating the count levelwise (breadth-first search).

We could then add the count of previous nodes, and subtract the count of the LCA(Least Common Ancestor) node.

Example

So, if we have to find the count of node $id:5$, we would get the following count:

$ Count(id:5) = Count(id:5) + Count(id:2) + Count(id:3) + Count(id:4) - 2*Count(id:1) = 1 + 2 + 2 +2 - 2*1 = 5$

Here is the final graph that we are getting.

Another example:

$ Count(id:7) = Count(id:7) + Count(id:5) + Count(id:6) - Count(id:4) = 5 + 3 - 2 +1 = 7 $

Problem

How do we remember the counts of ancestor nodes, when we are analyzing the counts of the current nodes?

It could be possible that the ancestor might not be immediately present, it could be far away at previous levels also.

Is there any algorithm that could solve the problem? I would really appreciate the help.


texts: Why is adding log probabilities faster than multiplying probabilities?

texts:
To frame the question, in computer science often we want to calculate the product of several probabilities:

P(A,B,C) = P(A) * P(B) * P(C)

The simplest approach is simply to multiply these numbers, and that is what I was going to do. However, my boss said it's better to add the log of the probabilities:

log(P(A,B,C)) = log(P(A)) + log(P(B)) + log(P(C))

This gives the log probability, but we can get the probability afterwards if necessary:

P(A,B,C) = e^log(P(A,B,C))

Log addition is considered better for two reasons:

It prevents "underflow" whereby the product of probabilities is so small that it gets rounded to zero. This can often be a risk since probabilities are often very small.
It is faster because many computer architectures can perform addition more quickly than multiplication.

My question is about the second point. This is how I have seen it described, but it doesn't take into account the added cost of getting the log! We should be comparing "cost of log + cost of addition" to "cost of multiplication". Is it still smaller after taking that into account?

Also, the Wikipedia page (Log probability) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand this, because I think you would need to take the log of every term independently before adding. What am I missing?

Finally, the justification that "computers perform addition faster than multiplication" is kind of vague. Is that specific to the x86 instruction set, or is it some more fundamental trait of processor architectures?


texts: What is the mathematical and algorithm way to represent "all possible configuration"?

texts:
I have two rigid 3D objects, where one of the object, say A, slide/glide on the other object, say B. Now what I want to do is to find all possible valid configuration/pose of A on B. How can I say this using math formula? After that, how can I write that in algorithmic way?

Thanks in advance.


texts: Computer Architecture: Hit ratio with address

texts: There is a problem that as much as I am trying to understand it, I fail. There are theoretically three cache manufacturers that each make 16 byte cache. The first has 16 blocks, 8 blocks the second, and 4 blocks the last. Then we are provided with 12 memory addresses, and we are asked the hit ratio of each cache. How does this work?


texts: "At least one" clause in Relational Algebra

texts:
I'm fairly new to the syntax of relational algebra, and I'm having a hard time understanding how I could set a "at least one" clause.

Example: I have:

a table with books (listing the title, year published and ID),
a table with authors (listing their name and ID),
a table which lists what author wrote what book (through a tuple of the IDs mentioned before).

How could I, in relational algebra, get "All the authors that have published at least one book per year between 2008 and 2010"?

I have figured this so far. At step "b", the Natural join is used since both tables have PublicationID in common. Thus, the resulting table is |PublicationID|AuthorID|Year|. So I'm simply missing the step "c", where I don't understand how to gather a sub-set of the authors that published at least one book per year between 2008 and 2010.

$ a \leftarrow \pi_{PublicationID,Year} (Publication)$

$ b \leftarrow a \bowtie AuthorPublication $

$ c \leftarrow \sigma_{something} $


texts: What is the time complexity of min-heap based solution to calendar rendering problem

texts:
Question:  You are given a set of events in a day.  Each event has a start and end time.  Find the maximum number of concurrent events

Solution:

First convert events into an array of "Event objects".  Each object has a Time field and EventType(start/End) field.  (O(N)
Min-heapify the array, with time as the key to order the elements. O(N)
Until heap is empty, do a removeMin(). if event is start increment numConcurrent, if it is a end decrement numConcurrent.  Keep track of max value of numConcurrent.  O(N*Logn)

SO, complexity is O(N * logN).  Is this analysis correct?  The interviewer told me thatI need to do it using sort to get O(N*logN).  I don't see why because above solution achieves the same.


texts:
Let $A$ and $B$ be two one-dimensional, finite collections of unsigned integers (e.g. arrays). Furthermore, $card(A) = a < b = card(B)$. Both collections are sorted in ascending order. There is at least one item ${x}$ which is contained both in $A$ and $B$.

Question: what is the fastest algorithm to find the smallest $x$ and what is its $T(n)$ in Big O notation?

Note: card() means the size of array (say: card(A) = 10 means a declaration in C/C++ would be int[10] A with indices 0...9).

Note 2: as I am new to CS.SE and learn CS as enthusiast, so far I have not been exposed to any fancy algorithm to solve this. My initial (naive) guess would be brute-search approach, but this is obviously not efficient for large $A$ and $B$. Your thoughts and pieces of advice would be then highly appreciated.

The priority is practical efficiency, so something around polynomial time-algorithm would be nice. Note, that the number of elements in both collections will be very substantial (above 10^30).


texts: Network Flow - Minimum flow in a network

texts:
I have a directed graph G=(V,E) with a source s$\in V$ and a sink t$\in V$. There is a minimum capacity (lower bound) l $_{e}$ for each edge in G. There are no upper bounds on the edges.

In a course that I took, the professor told that to find a minimum flow -

1) We need to assign a large capacity to all edges and find flow f
2) Construct G $_{1}$ where all edges are reversed and each edge has capacity f$_{e}$ - l$_{e}$
3) We need to then find the max flow from t to s in G$_{1}$ that is f$_{1}$
4) Then, the  minimum flow in G is  f-f$_{1}$

  My question is-  Why can't we find a s to t path in G with the least
  value of  l$_{e}$. The least value of l$_{e}$ would be the minimum
  flow that could be pushed through the network?


texts:
How do I test if a circle (x,y,radius) is inside a polygon ([x,y],[x,y],[x,y],[x,y]...) without touching the edges?

Update
I decided to do a point in polygon followed by a circle line collision on each edge, this let me know first if the circle was within the polygon and then told me if it was colliding with any of the edges.


texts:
Let $G=(V,E)$ be an undirected graph in which $V = \{v_1,v_2,\dots,v_n\}$.

I need to describe a reduction from the 2-coloring problem to the 2-SAT problem (in polynomial time).

I thought of splitting each vertex $v_i$ into $v_i^*$ and $v_i^{**}$, one for each color. Then I was thinking about making for each edge $(u,v)\in E$, two correspond literals: $(u^* \lor v^*)$ and $(u^{**} \lor v^{**})$.

I know I'm on the right track but I can't prove it.

any ideas?


texts: Finding a Hoare logic correctness proof for a Repeat-Until loop

texts:
How can we prove a program in repeat until using Hoare Logic?

I've found a rule like this:

{P} S {R}, {R ^ ~B -> P}, {R ^ B -> Q}

for

{P}
repeat
  S
until B
{Q}

But I still can't find any explanatiom how I can use this rule

For example in this question:

{x > 0 ^ y > 0}
     z:=0; u:=x;
     REPEAT
        z:=z+y;
        u:=u-1;
     UNTIL u=0;
{z = x * y}

How I can use the rule to prove this program?

UPDATE
I've tried to find invariant loop:

R : Z = X*Y + (Y - Y*U)

But I still confuse what is P?


texts:
I have recently started reading more about context-free parsing techniques, in particular LR parsing.

As I have read, LR state transition graph (or table(s)) used for finding handles in sentential form is created by first constructing NFA from grammar rules (with included position in the rule - dot and possibly lookahead terminal) and then by converting the NFA to DFA with powerset/subset algorithm to remove non-determinism.

LR(1) state transition graph is usually an order of magnitude larger than LR(0)/SLR(1)/LALR(1).

Is it worthy or even practically possible to use DFA minimization (either Hopcroft or Moore or Brzozowski) on LR(1) state transition graph to get a minimal LR(1) graph?
I haven't found any literature mentioning this.

Also, is there an algorithm to convert NFA directly to minimal DFA? Perhaps by constructing NFA state subsets in some particular order?


texts: categories of registers and and storage in them

texts:
The Wikipedia article on processor registers mentions:

  Address registers hold addresses and are used by instructions that indirectly access primary memory.

Which addresses does this sentence refer to?


texts: Find the n best choices while maximizing value

texts:
Given:

A list of slots (A, B, C, ...)
Every slots supports a list of choices (C0, C1, C2, C3...)
Every choice has a value

All slots must be filled with at most n different choices. The sum of the values should be maximized.

Example:

Choice-Values:

C0 = 4
C1 = 3
C2 = 2
C3 = 1

Slots:

A: C1, C3
B: C0, C1, C3
C: C2, C3
D: C0, C1, C2, C3
E: C1, C2, C3

Solution for n = 1: C3, C3, C3, C3, C3

Solution for n = 2: C1, C1, C2, C1, C1

Question

Is this a known problem?

It reminds me of a mix between the knapsack problem and of a scheduling problem, as I want to get the maximum value while filling a certain space using a limited set of items.


texts: How do context switches factor into CPU utilization?

texts: When studying operation systems, is context switch time included in CPU utilization time? For example, if 5 percent of CPU time is wasted to context switching, is CPU utilization 95 percent?


texts: Can one use the PCP theorem to prove correctness of deternimistic algorithms?

texts:
I am thinking of the equality "PCP(O(log(n)),0) = P"

Say I have a deterministic polynomial time algorithm $A$ whose correctness I can't prove immediately. But say I create a probabilistic version of this algorithm say $A_P$ such that it uses log(n) random bits.  Now if I prove somekind of (exactly what ?) expectation correctness of $A_P$ then does it imply that $A$ was correct?

If the above is not right then I would like if someone can point me to what is the closest correct thing to this!


texts: Usage of stacks and heaps in object-oriented programming. Reasons?

texts:
In object oriented programming heaps are used for to store the actual objects. Stacks are used for storing reference-variables to the objects.

What's the concrete reasons for choosing those two specific data-structures?

What benefit has a heap in the described scenario? What benefit provides a stack?


texts: Simplyfing a particular boolean expression

texts:
I'm having a lot of trouble with two problems the first is:

1) (y*w) + y + w

 What I tried here is applying the distributive law as follows

(y*w) + (y+w)
((y+w) + y) * ((y+w) + w)
((y*w) + y) * ((y*w) + w)

then applying the absorption law and getting y*w but the answer is y + w, so I'm unsure how to get it using the laws of Boolean algebra.

2) The second problem I am having issues with is

Prove that if x*y = x then ~x*~y = ~y

What I tried was negating both sides of the first expression and plugging into the second but that isn't allowed in Boolean algebra it seems.


texts: What algorithm will tell us how to divide-up a round robin tournament into rounds?

texts:
We are designing a tournament for a game such as soccer (football) or chess. The tournament is "round robin." By "round robin," we mean that every team gets to play against each other team exactly once. For example, if you are playing, and there are 8 other teams, then you will play exactly 8 matches before the tournament is over.

A single "match" is played with 2 teams competing against each other. For example, (team 3 against team 9) is a single match. Formally, a match is a set of two integers, such as {3, 9}.

The tournament is divided into rounds. All teams who are scheduled to play during the current round play simultaneously. If team 2 is playing team 5 during round 10, then team 2 cannot simultaneously play against team 3 during the same round. In different notation, if {2, 5} ∈ R10 then {2, 3} ∉ R10. In general, no round is allowed to contain the same team more than once.

Formally, a round is a set of matches. For example, $R = \{\{1, 2\}, \{3, 5\}, \{4, 6\}\}$ is a round. A valid round $R$ is a round such that for every two distinct matches, M1 and M2, in $R$, $M1$ ∩ $M2$ is the empty set. This captures the idea that no round is allowed to contain the same team more than once.

For some natural number, $n$, the tournament has:

$2*n$ teams
$(2*n-1)$ rounds
$n$ matches per round.

The algorithm we seek, for any even number of teams, will output a a description of which matches to have in each round.

For example, for 6 teams, the algorithm output might be:

round 1: {1, 2}, {3, 5}, {4, 6}
round 2: {1, 3}, {2, 4}, {5, 6}
round 3: {1, 4}, {2, 5}, {3, 6}
round 4: {1, 5}, {2, 6}, {3, 4}
round 5: {1, 6}, {2, 3}, {4, 5}

Note that every team plays at most once per round, and that every team plays every opposing team exactly once before the tournament is over.


texts: Algorithm for distributing members over activites (with individual preferences)

texts:
So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils assigned to the activity change. (So in block 1 pupil x takes part in activity a and in the second block in activity d).

Before this day starts, we give make lists in which each pupil can tell us his 3 (or 4) favorite activities (he only takes part in two of them, these again are ordered from most "favorite" to least) in which he wants to take part. Now our job is to assign these pupils in a way that we have the best overall satisfaction among the pupils (so everybody did more or less did get his/her chosen activities).

What would be a good algorithm to solve this? Is there any way to do this, apart from calculating such a "satisfaction" value for each possible solution?

An optional feature would be that if someone can't get in to his/her project, they would get into a similar one according to some predefined distance.


texts: The situation when P is a superset of NP

texts: Could it be that three languages $A, B, C$ such that $A \subset B \subset C$, and $B \in P$, but $A$ and $C$ are $NP$-complete?


texts: Vertex cover problem modification such that every vertex is connected to the set, NP-Hard?

texts:
Being new to complexity problems, I've met a question that is quite similar to the Vertex Cover Problem and I am not sure if this one is NP-Hard. We know that the vertex cover problem is the following: given a graph $(V, E)$, selecting a set of vertices $S$ such that every edge $e \in E$ in the graph is connected to some vertices in $S$. The problem of minimizing the vertex cover problem is a well-known NP-hard problem.

My question is the following: given a graph $(V, E)$, selecting a set of vertices $S$ such that every node $v \in V$ is either in $S$ or connected to the nodes in $S$. Is this problem of minimizing the set of $S$ NP-Hard? This problem seems to be quite intuitive after learning the vertex cover problem, but I didn't find a similar question after searching. I apologize if I asked duplicated questions.


texts: What is wrong with my LP exercise (longest path cost for a graph)

texts:
I have to do a linear programming exercise  but i have some problems regarding the result. I have a graph with N nodes and E edges, that is not acyclic, and each edge is associated to a cost. I have also two nodes (marked as B and E), and I have to find the maximum path cost from B to E. Also, each edge can be used at most k times and the total cost of the path must be at most C.

I have inserted also the constraint regarding the balance of each node as follow (where E are the edges and x[i,j] tells me how many times an edges is been used, and the two nodes B and E):

$\sum\nolimits_{j |(j,i) \in Edges} x(j,i) -\sum\nolimits_{j | (i,j) \in Edges} x(i,j) =0$

$\sum\nolimits_{j | (j,B) \in Edges} x(j,B) -\sum\nolimits_{j | (B,j) \in Edges} x(B,j) =-1$

$\sum\nolimits_{j | (j,E) \in Edges} x(j,E) -\sum\nolimits_{j | (E,j) \in Edges} x(E,j) =1$

The objective function is:
$max \sum\nolimits_{(i,j) \in Edges} x(i,j)*cost(i,j)$

Other constraints:

$x(i,j) <= K \forall (i,j) \in Edges$

$\sum\nolimits_{(i,j) \in Edges} x(i,j)*cost(i,j) <= C$

When i run the LP solver the solution that it gives me, of course it includes a path from B to E, but also an other cyclic path that not includes nodes B and E.

Any suggestion?


texts:
I'm looking for an $NP$-hardness proof for the following variant of $SAT$:
$$
EVEN-SAT = \{\langle \phi \rangle: \phi \text{ has an even number of satisfying assignments}\}
$$
I've been playing around with gadgets for a while, but I haven't been able to construct a reduction. Still, I feel like there should be one. Help!


texts: How to prove existance and construct finite-state transducer between two different FSM?

texts:
For example I have 2 simple FSM. I will use regular expression for clarity.
FSM1 = 1+ = [1,11,111,...]
FSM2 = 2+ = [2,22,222,...]
FST = 1/2 = [1->2,11->22,...]

What is the general way to prove that there exists finite-state transducer that maps each string from the set defined by FSM1 to a string defined by FSM2? What is the algorithm to construct such transducer?
I want to have the next properties from mapping:

((1))=(2), where (1) is the regular language accepted by the first FSM, (2) the one for the second FSM,  is some transducer

 is bijective mapping from (1) to (2)

It have to specifically map the th string from (1) to the th string from (2) using lexicographic order


texts:
I'm reading The Art of Multiprocessor programming and trying to understand their concept of inconsistent locks. Specifically, on page 37, the definition 2.8.1 of an inconsistent lock is not clear to me, as well as Lemma 2.8.1.

Definition 2.8.1. A Lock object state s is inconsistent in any global state where some thread is in the critical section, but the lock state is compatible with a global state in which no thread is in the critical section or is trying to enter.
Lemma 2.8.1 No deadlock-free Lock implementation can enter an inconsistent state.
Proof:
Suppose the Lock object is in an inconsistent state s, where no thread is in the critical section or trying to enter. If thread B tries to enter the critical section, it must eventually succeed, because the implementation is deadlock-free.
Suppose the Lock object is in an inconsistent state s, where A is in the critical section. If thread B tries to enter the critical section, it must block until A leaves.
We have a contradiction, because B cannot determine whether A is in the critical section.

What I don't understand:

Does being inconsistent just mean that if a thread is in a critical section, there's no way other threads can know about it?
What's the contradiction in a lemma proof? Say thread A is in a critical section, and the lock is in an inconsistent state. What stops another thread from overwriting the lock's state and acquiring it?


texts: Why is selection sort faster than bubble sort?

texts:
It is written on Wikipedia that "... selection sort almost always outperforms bubble sort and gnome sort." Can anybody please explain to me why is selection sort considered faster than bubble sort even though both of them have:

Worst case time complexity: $\mathcal O(n^2)$
Number of comparisons:      $\mathcal O(n^2)$
Best case time complexity :

Bubble sort: $\mathcal O(n)$
Selection sort: $\mathcal O(n^2)$

Average case time complexity :

Bubble sort: $\mathcal O(n^2)$
Selection sort: $\mathcal O(n^2)$


texts: How to find contour lines for Appel's Hidden Line Removal Algorithm

texts:
For fun I am trying to make a wire-frame viewer for the DCPU-16. I understand how do do everything except how to hide the lines that are hidden in the wire frame. All of the questions here on SO all assume you have access to OpenGL, unfortunately I do not have access to anything like that for the DCPU-16 (or any kind of hardware acceleration).

I found a fairly good description of Appel's algorithm on Google Books. However there is one issue I am having trouble figuring out.

  Appel defined contour line as an edge shared by a front-facing and a
  back-facing polygon, or unshared edge of a front facing polygon that
  is not part of a closed polyhedron. An edge shared by two front-facing
  polygons causes no change in visibility and therefore is not a contour
  line. In Fig. 8.4, edges AB, EF, PC, GK and CH are contour lines,
  whereas edges ED, DC and GI are not.

I understand the rules of the algorithm and how it works once you have your contour lines, however I do not understand is what I need to do to determine if a edge is "shared by a front-facing and a back-facing polygon, or unshared edge of a front facing polygon that is not part of a closed polyhedron" from a coding point of view. I can look at a shape and I can know what lines are contour lines in my head but I don't have a clue on how to transfer that "understanding" in to a coded algorithm.

Update

I have made some progress in determining contour lines. I found these two lecture notes from a University of Buffalo class on computer graphics.

  Consider the edges. These fall into three categories.

  An edge joining two invisible faces is itself invisible. This will be deleted from the list and ignored.
  An edge joining two potentially-visible faces is called a 'material edge' and will require further processing.
  An edge joining a potentially-visible face and an invisible face is a special case of a 'material edge' and is also called a 'contour
  edge'.

Using the above two pieces of information I am able to get closer to being able to write this out as code, but I still have a long way to go.


texts: What are the best ways to find errors in a sequence of messages (strings)?

texts:
I am currently working on a thesis, where the main goal is to find errors (like a missing message, wrong sequence) in message sequences. The messages are distinguishable by their name, have further information in the message body, and are available in a database. Each message can just be thought of as string-representation of its name.

The thesis should compare different concepts for finding errors in these real-life message sequences. A big amount of these messages are being collected and the goal is to check for errors in the sequence or any missing messages. The default sequence (so the standard-case) can be defined.

Now I am just lacking any ideas on how to approach this problem.
So, my questions are as follows: Which approaches can be used to solve this problem? Are there any algorithms, that could be used in this context?

Further example to make it clearer:

Message sequence A, B, C, D, E is defined for one standard-case.
Now, the real message sequence that is observed is A, B, C, E, D (or one message is missing entirely).

I hope the problem is comprehensible. Thanks to all who take the time to read.


texts: I read up on the Perwitt operator and it detects two types of edges (vertical and horizontal). The Sobel operator on the other hand does the same as the Perwitt except that the masks are not constant and could be dynamically adjusted. Why do the Sobel and the Perwitt matrices compute horizontal and vertical gradients?


texts:
I'm learning about single source shortest path algorithms and need to clarify few doubts-

Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers.
Does Dijkstra’s assumes that the graph searched by it is free of cycles.
Relaxing an edge is same as setting its weight to 0.
Does Dijkstra’s yields only costs of shortest paths, requiring lot of extra computation to find the intermediate vertices on shortest paths.
Dijkstra's useful only when edge weights are geographical distances along paths traversed on ground or water.


texts: Consensus protocols in multiplayer video games

texts:
I'm not 100% sure this appropriate for CS. Sorry.

I'm looking for prior art on an idea I had, but either my Google fu is lacking, or it genuinely hasn't happened.

In distributed systems, there are a number of consensus protocols and implementations (Raft, Paxos, Zookeeper, etc.). There's also the Bitcoin blockchain. Both of these approaches allow the cluster/network system to recover in the face of split brains and sometimes in the face of an evil node.

In the games world, there are really only two architectures in use:

Client-server, where the server simulates the game and is the source of truth and the clients simply act as a dumb terminal. No cheating possible. (Sometimes the server runs on a client.)
Peer-to-peer, where all clients broadcast their status to all other clients. Cheating very possible.

I am thinking of a third architecture that enhances the peer-to-peer architecture with a voting-based cheat detection. Desynchronized game state would be rejected by a majority vote. A colluding majority would be required to cheat.

The practical purpose is two-fold:

To eliminate the necessity of the server-side implementation of game simulation (e.g., game state machine). In the client-server model, you need to either write the implementation of the sim twice or write it generically enough that it will run in both client and server environments. For practical reasons, a shared codebase is difficult to do.
To eliminate the computational burden of running simulations. For large online games, this burden is not insubstantial.

I'm wondering if there's any research on such a system (either similar systems having been invented and used or even a paper describing it) specifically with respect to multiplayer games.


texts:
Check if $NP ⊆ BPP $
I know that if $NP ⊆ BPP $ then $NP=RP$, which is not known fact. So, we don't know if $NP ⊆ BPP$.
Maybe some other explanation of this exercise ?


texts: Finding an substring in an infinite sequence

texts:
I'm trying to find a substring in an infinite sequence of numbers (Similar to Substring in a infinite sequence of numbers) and am a little stuck on improving my algorithm. I know there is already an answer given in the question I linked above, but I want to try and improve my brute force algorithm.

Given a sequence $S = \{12345678910...n-1n | S \in \mathbb{Z}:\}$, the algorithm tries to compute the first index of a pattern $P$ in the string. For instance, $\mathrm{find}(P = 456) == 3$ as the sequence $456$ is located at index $3$. I have a very simple algorithm that generates a sequence till the substring is found, and then goes through the sequence to return the index of the substring. This algorithm is very slow for for large $N$ and I want to improve it:

def find_position(string):

    # Build a window of size len(string) and init from 1 -> m
    windowSize = len(string)
    window = [str(i) for i in range(1, windowSize + 1)]
    result = ''.join(window)

    # Loop till match
    while string not in result:

        # Remove front and add back
        window.append(str(int(window[-1]) + 1))

        # Join window and match
        result = ''.join(window)

    return result.index(string)

This algorithm is like a very basic Rabin-Karp without any hashing but just regular string matching. I am not too sure if adding a rolling hash would speed up this algorithm in any way because the slow aspect of the algorithm is generating and appending to the sequence and then checking if the string is contained in the window.

Any ideas on how to improve this algorithm?


texts: O(n) algorithm for the connected components at most n/2 problem

texts:
I'm given a problem statement which states
"There always exists a vertex from a tree G such that the remaining connected components have size at most |V(G)|/2".

I'm trying to formulate an efficient algorithm for this and am not sure where to start.
I'd love some hints and can take it from there. Thanks.


texts: Similarity of Objects based on multiple variables

texts:
I am working on a Simple hypothetical Allocation Problem. I have some Virtual Machines(VM) placed on a Physical Machine (PM). The VMs and PMs have 3 common variables, CPU, Memory, Network. The VMs require these resources, while PMs can provide these resources.

At certain points I need to check if the VM is similar to (or larger than) other VM or a PM.

I need to score them so they can be easily sorted. A naive way (probably wrong way), I am doing it right now is, to divide the requirements and if all the ratios are less than or equal to 1, I will assign a score by multiplying all the three ratios. E.g.:

VM1 : 100CPU, 200Mem, 50Net;

PM1 : 200CPU, 300Mem, 50Net;

The total Score will be 0.5 * 0.67 * 1 = 0.335.
This works, as I am able to sort them in descending order of their total score.

But If I want to compare that two VMs equal to another VM, I cannot use this score. For Example:

VM1 : 100 CPU, 200 Mem, 50 Net;

VM2 : 100 CPU, 200 Mem, 50 Net;

VM3 : 200 CPU, 400 Mem, 100 Net;

The score of VM1 and VM2 w.r.t to VM3 will be 0.5 * 0.5, 0.5 = 0.125
If I add both the score I will only get 0.250, in fact combined, they are equal to the specs of VM3.

I am not sure the type of problem I am facing here, and some initial goolging didnt helped in identifying the problem as well.

My Question is, Is there any standard way to compare objects with different properties which have different units? so that they can also be ranked?


texts:
I read that there are 4 types of rotations:

Left rotation
Right rotation
Left-Right rotation
Right-Left rotation

What are the corresponding abbreviations: RL,LR,RR,LL? Is there a reference how to rebalance AVL trees?


texts: How are Probability and Non Determinism Related ? Alternatives to handle Non determinism?

texts:
I have been thinking about Non-determinism in any kind of state machine. Since I work on machine learning, I tend to think that probability is a means of handling non-determinism. Instead of exhaustively taking every possible transition  to arrive at a solution we prioritize the alternatives.

I just wonder if there are works that has compared both Probability and Non-determinism and the adequacy of probability based approaches in handling Non-determinism?

I am also interested in knowing are there other alternatives in handling non-determinism. For  example, if I can clone a state and add more context or features to both the states to eliminate then woudlnt that be more hlepful. I consider this from a constraint logic point of view, where we add further constraints from additional resources. So by this we add only constraints whenever non-determinism arises, thus saving us from exhaustive search which otherwise should have done.

I am sorry that this appears more like a rambling, but if anyone could direct me to some works where there are works which has studied the aspects that I am discussing in a more principled way, it would be helpful.

Thanks in advance


texts: I understand how both forward and backward data-flow analysis work but in what situations would we use them? Why do we need to be able to do it in both ways? Do compilers of certain types perform one way more efficiently than the other?


texts: does every graph have a complete, preferred, stable and grounded extension?

texts:
I was looking at graph extensions in argumentation theory and was wondering, which of those extensions does every graph have? and which of those only some graphs have? and is there a proof for each?

thanks


texts:
This problem came up in a graph network routing context, it can be expressed as follows:

  Let $n, m > 0$ be integers. Find any smallest list of positive integers $\langle a_1, \cdots, a_k \rangle$ such that:

  $$1 + \sum_{i = 1}^k \prod_{j = 1}^i a_j = n$$

  With the added condition that $a_i \leq m$ for all $1 \leq i \leq k$.

  (for a challenge, add the constraint "with the least number of $1$'s", but the above would suffice)

Graphically, if you picture a tree of depth $k$ (with a single root) with branching factors $a_i$ at each level, the algorithm asks for the shortest such tree containing exactly $n$ nodes in it, with each branching factor at most $m$. For instance, taking $n = 12$ and $m = 5$ as an example, we see that $\langle 1, 1, 3, 2 \rangle$ is a solution, since:

$$1 + (1) + (1 \cdot 1) + (1 \cdot 1 \cdot 3) + (1 \cdot 1 \cdot 3 \cdot 2) = 1 + 1 + 1 + 3 + 6 = 12$$

Which corresponds to the tree with branching factors $1, 1, 3, 2$ shown below:

But there is a shorter solution, given by $\langle 1, 2, 4 \rangle$, as illustrated by the tree:

And there is no shorter solution with $m = 5$, in fact the only other solution of length $3$ is $\langle 1, 5, 1 \rangle$. Note the solutions need not start with $1$, e.g. $\langle 4, 3, 1 \rangle$ for $n = 29$ (the order is clearly very important).

We are talking $n \approx 10^8$, $m \approx 10^4$ in my case (but asymptotic algorithms are welcome!)

I solved it quickly using a brute force approach, which is pretty inefficient, running in exponential time. Is there an easy lower/upper bound on the length of the smallest solution in terms of both $n$ and $m$, and an efficient algorithm to find one such solution? My first thought was a backtracking algorithm, but it doesn't seem to help since you usually get stuck at the leaves of the tree where you realize you can't find a branching factor that will make it add up to $n$, perhaps there is a clever number-theoretic algorithm to select good branching factors as you go?

One optimization I came up with is that if you are at depth $i$ in the tree, then you can calculate the number of nodes you've already added as $x$, then the branching factor for the next tree level must necessarily divide $n - x$, so it might be efficient to go for branching factors that lead to prime values of $n - x$, then we can build a set of optimal solutions for small primes and look them up as needed to complete the tree (going for primes with shorter solutions first). But that doesn't appear to guarantee a shortest solution...

Well, it does reduce the number of $a_i$ candidates to explore down to $O(\log(n))$, but in the absence of a better bound or a procedure to not have to explore fully the tree of possibilities for $a_{i + 1}, a_{i + 2}, \cdots$, this does not make for an efficient algorithm, even if the length of the shortest solution is (probably) upper-bounded by $O(\log(n))$.

Thanks!

PS: I wasn't totally sure what to tag this, so I filed it under combinatorics - please retag if there is a better category for this kind of problem!


texts:
A homework question asks me to a draw a DFA for the regular expression

$((aa^*)^*b)^*$

I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s many times, in terms of a DFA.

I would guess it that $(aa^*)^*$ should be the same thing as $\lambda + a^*$ but I'm not sure if I can formally say that. If I could, it would make my DFA simply


texts: How to prove this isomorphism-related graph problem is NP-complete?

texts:
Consider the following problem:  Given two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ and some non-negative integer $k \in \mathbb{N}$, is it possible to delete at most $k$ vertices from $G_1$ to obtain $G_1'$ such that $G_1' \cong G_2$, i.e. the resulting graph is isomorphic to $G_2$.

I have to show that this problem is NP-complete.

Can somebody help me with this problem? It is school homework and I don't know how to solve it.


texts: Can factorial be done in O(1) and proof?

texts: The typical way to compute the factorial would take $O(n)$ because it calls itself recursively. However, there are many other ways to compute the factorial function based off the gamma function, bessel functions and whatnot. So how would you prove factorial always takes at least $O(n)$ time, no matter how you choose to calculate it? Or can it be done in $O(1)$?


texts: Sorting an array where half of the elements are at their correct position

texts: By the statement of the question i am trying to generalize the structure of the array.for me Being at their correct position means they can't be shifted. I tried to come up with a few examples and deducted such an array has to be 2-sorted or all the sorted elements are in the first half. for a k-sorted array we can use insertion sort or heap sort with a heap of size k,  but first i need to make some generalization about the structure of the array. How do we go about proving it formally?  Intuitive explanation would work too.


texts:
What is the term for an algorithm that always requests the same sequence of pages?  I recall seeing this concept before but haven't been able to find anything on Google without more specific vocabulary.

One algorithm in this category is a linear scan to (say) find the minimum of a set of data. Each page is accessed in order, regardless of the value of previous accesses.

Most algorithms do not fall into this category. For example, a binary search chooses what page to access based on the values in the page before it.


texts: Which branch of computer science uses mathematical optimization the most?

texts:
I am beginning with my masters degree in mathematics and I will specialize in optimization theory. My minor is computer science and wanted to know which branch of computer science fits my specialization(optimization theory) the best.
I know that machine learning involves some optimization theory (I don't know how much though...)


texts: Naming facts exported from blocks in Isabelle/HOL

texts:
I'm using Isabelle/HOL.  Isabelle exports the last fact in a block, allowing the context that contains the block to use it.  Ordinarily when I generate facts, I can give them convenient names.  How do I name facts that are exported from blocks?

Simple example:

lemma mylemma: "i=i"
proof -
  {
      fix j::nat
      have "j=j" by auto
    }

    show ?thesis using ‹⋀j. j = j› by auto
  qed

Right now I use ‹⋀j. j = j› to refer to the exported fact as a proposition literal.  I'd like to be able give it a simple name, though, as when I named the lemma mylemma.  Thanks for any suggestions!


texts: How to set parameters in Librosa's CQT function for an 88-key piano?

texts:
I am doing an automatic music recognition project with a deep learning model. For my data preprocessing, I am trying to calculate the Constant Q Transform for Polyphonic 88-key piano audio using Python's Librosa library. However, I do not understand what I should set fmin, n_bins, bins_per_octave to in Librosa's CQT method to do this. Specifically...

What exactly is a bin? Do the upper and lower boundaries of a bin correspond to the frequencies of two consecutive notes? In other words, because an 88-key piano has 7 octaves each with 12 unique notes, should I set n_bins=7*12=84 or equivalently bins_per_octave=7?  Or should several bins correspond to a single note interval?
Is fmin supposed to be the deepest note on the 88-key piano, ie the A note with a frequency of about 27.5 Hz?
Why do we need fmin? Is this some sort of reference point, similar to the equation from amp to decibels?
What are the difference between n_bins and bins_per_octave? Which one of them is better to use? I ask this because a research paper here (line 13 and 53) uses BOTH n_bins and bins_per_octave to analyze 88-key piano music. Why do they use both parameters instead of just one? What is the difference between these two values?


texts: A restatement of Moore's law that takes into account quantum computing

texts:
The first line of the Wikipedia article on Moore's law states that

  Moore's law is the observation that the number of transistors in a dense integrated circuit doubles about every two years

As scientists groan on about running into the physical limits of Moore's law, another bunch of scientists[or the media?] seems to feel like they can keep up the trend by leveraging characteristics of quantum computers.

However, a quantum computer doesn't use transistors in the same way that a traditional computer does, and adding another qubit, according to my knowledge, can double the computational power of the computer!

For that reason, is it time to restate Moore's law in such a way that it can take into account computational power as an abstract concept, and not necessarily a physical one?

Does it even make sense to ask that question?


texts: Relationship between lexicographic index of size k (tuple) with that of size(k-1) tuple

texts:
Given a non-negative integer $n$ such that $X = \{1,2, \dots, n\}$, a combination of k-tuple and its associated index $pos_k$.

How to compute the associated lexicographic index for any subset of the given tuple of size $k-1$?

For ex: if n = 5, then the associated index of given tuple {1,2,3} = 16.
Given that information how to compute the index for tuple {2,3} =? instead of computing $$
\binom nk-\sum_{m=0}^{k-1}\binom{n-i_{k-m}}{m+1}\;.
$$
where subset = $\{1_i, i_2, \dots, i_{k-1}\}$


texts: Maximize entrywise 1-norm of matrix product

texts:
I have $8$ sets $E_1, \ldots, E_8$, each one of size $256$,  whose elements are $4\times 4$ matrices of (nonnegative) integers. I'd like to design an algorithm to find:

$$\underset{M_1 \in E_1, \ldots, M_8 \in E_8}{\max} ||M_1 \times \ldots \times M_8||_1$$

where:

$$||M||_1=\sum_{i=1}^4\sum_{j=1}^4 M_{i,j}$$

A reasonable time complexity might be approximately $2^{32}$ (time complexity of the naive algorithm is $2^{79}$).

My first idea would be to look for interpretations in various mathematic fields:

geometry: matrix product in an euclidian space.
probability: it reminds me of Markov chains (but the $M_i$ are not normalized).

Is there any known work about this?


texts:
Consider a Boolean function $f(x_{1}, x_{2}, \dots, x_{n})$. The value of $f$ is defined on some set of inputs, and some inputs are undefined (let us label undefined value with $?$). It is possible to set $f$'s value on some inputs, no matter if they were initially defined.

The problem is to set some of the inputs such that:

all initially undefined inputs become defined (i. e. no $?$ in function's truth table);
$f$ is monotone in the common sense.

The optimization part is to use the minimum possible assignments. How can one find an optimal way to do so in the time $\mathcal{O}\left(p(n) \left( 2^{n} \right)^{2} \right)$, where $p(n)$ is polynomial?


texts: Determine if two grammars for the same language are ambiguous

texts:
I'm reading the book: Formal Syntax and Semantics of Programming Languages. I don't understand this exercise:

Consider the following two grammars, each of which generates strings of correctly balanced parentheses and brackets. Determine if either or both is ambiguous. The Greek letter ε represents an empty string.
<string> ::= <string> <string> | ( <string> ) | [ <string> ] | ε
<string> ::= ( <string> ) <string> | [ <string> ] <string> | ε


texts: Is possible to construct a fixed set of typeclases as powerful as unconstrainde typeclasses?

texts:
We can construct a fixed set of combinators with a computational power equivalent to lambda calculus.

Can we do the same with typeclasses (ad-hoc polymorphism)?

For example, construct a finite set of typeclasses from which we can build general ad-hoc polymorphic functions?


texts:
Is there a way to convert, i.e., C code into English? The purpose would be to convert source code into a Text-To-Speech converter which would enable someone to "listen" to source code.

EDIT: An alternative idea would be to parse C code to be more "listenable", for example parse:

#include<stdio.h>

    funcName()
    {
        printf("Hello World");

    }

as

    hash include left-angle-bracket stdio.h right-angle-bracket
    newline
    camelcase funcName open-paren close-paren
    newline
    open bracket
    newline
    printf open-paren quote-mark Hello World quote-mark close-paren semi-colon
    newline
    close-bracket


texts: NP-completeness of testing whether a SAT formula does not contain any redundant clause

texts:
This paper explains that testing the irredundancy of a SAT instance is NP-complete.
But I don't understand the theorem/reduction.
How would one reduce 3SAT or k-SAT to this problem, for example?


texts: Baileys 4-step FFT without bit reverse sorting

texts:
I'm not really sure, if this is the right place to ask this question. I would have asked on stackoverflow, but since my question is rather theoretical, I ask here. When I'm wrong, please migrate. Thank you :)

I'm trying to multiply polynomials using FFT. When doing an FFT in-place, the output is in bit-reverse order, which doesn't matter much, because when doing a convolution and an inverse FFT, the order will be reversed again.

I'm now trying to reduce memory bandwith using Bailey's 4-step FFT. While a normal FFT reads the data as often as $k$ times when the size of the transform is $2^k$, the 4-step FFT does it only two times (not counting CPU cache access). I'm implementing it as follows:

Write my data as an $n_1 \times n_2$ matrix. Do $n_2$ in-place FFTs on the columns. Reorder the columns.
Do the multiplication with the roots of unity (see paper)
Do $n_1$ in-place FFTs on the rows, do not re-order the data, because it's not needed for the convolution to work.

However, when I omit the reordering in step 1, I'll get incorrect results.  The re-ordering requires significant additional resources. Is it possible to get rid of it?


texts: What does $k$ mean in regular expressions?

texts:
From what I have learned in Introduction to Automata Theory, Languages, and Computation, regular expressions can be represented with $R^{(k)}_{ij}$.

I understand that $i$ and $j$ represent the starting state and the closing state respectively. However, I am still trying to understand the purpose of $k$.

To put it simply, what does $k$ stand for in $R^{(k)}_{ij}$?

Side note: Link to the book is here.


texts: Decision Tree Learning Deviation - Russell and Norvig

texts:
I am working through the Russell and Norvig AI book and came across the following on the top of page 706.

The section concerns Decision Tree pruning and testing a given attribute against the null hypothesis. The example at hand deals with a binary decision tree and $p_k$ denotes the number of positive ("yes") responses in the training data and $n_k$ the number of negative ("no") responses in the training data with respect to the training examples that are in the subset of values that took on the value $v_k$ associated with the $k$th attribute of a vector $\vec{x}$ of length $n \times 1$. Furthermore $p$ and $n$ simply denote the number of positive and negative outputs of the training data.

The authors state the following:

  We can measure the deviation by comparing the actual numbers of positive and negative examples in each subset $p_k$ and $n_k$ with the expected numbers
  $\hat{p}_k$ and $\hat{n}_k$, assuming true irrelevance:

  \begin{align*}
\hat{p}_k&=p\times \frac{p_k+n_k}{p+n}\\
\hat{n}_k&=n\times \frac{p_k+n_k}{p+n}\,.
\end{align*}

  A convenient measure of the total deviation is given by

  $$\Delta = \sum_{k=1}^d \frac{(p_k-\hat{p}_k)^2}{\hat{p}_k} + \frac{(n_k-\hat{n}_k)^2}{\hat{n}_k}\,.$$

My questions:

I think I understand the use of the estimators. We are basically assuming a uniform distribution on $p$ and $n$ and so within each subset of training examples that have the attribute value $A_k$ equal to $v_k$ we simply scale the overall $p$ and $n$ by the total proportion of samples in that set. In essence, we are assuming that, for instance, if $p=10$ and $n=5$, then those proportions hold in our subsets, and so the expected value of $\hat{p}_k$ is simply scaled by the size of the subset.

This leads me to also understanding the numerator of the measure of deviation $\Delta$. We use the squared deviation of the expectation from the observed value. My question then is why do the estimators appear in the denominator? This seems very close to an equation for variance, and I assume that the estimators are somehow scaling $\Delta$, but how can we justify that?


texts: How can Karger's algorithm (and other randomized algorithms) be used in practice?

texts:
Suppose I am given the following problem (the source is here):

  Disconnect two nodes in a graph by removing minimum number of edges.

I would apply Karger's min-cut algorithm. But how can I guarantee that I'll finally find the min-cut? Karger's algorithm is a randomized algorithm. If the probability of success is 1/p, I could run it p times to get the answer, right? Not necessarily! What if I am extremely unlucky, so I will never (or too much time will pass) get the answer?


texts: Complexity class for probabilistic approximation algorithms with bounded error

texts:
What's the name of a complexity class of
optimization problems that have
"bounded error probabilistic approximation algorithms"?
Bounded error probabilistic version of APX
(as BPP is bounded error probabilistic version of P),
or approximation version of BPP (as APX is approximation version of P).


texts: Turing machine VS Push Down Automaton in CFL

texts:
I want to ask that between turing machine and pushdown automaton: which abstract machine can handle context-free language (CFL) in a more efficient way, and why?

I know that a pushdown automaton can use exactly one step per input symbol, which is a tight lower bound on efficiency. (If we’re measuring in number of steps, anyway.) This is better than a single-tape Turing machine can do. But, I think that a Turing machine with an input tape and a working tape can emulate a pushdown automaton directly, using the same number of steps.

So, in the end, which kind of automaton machine promisingly can serve as a recognizer for CFL?? And why?


texts: Some points about type checking of simply typed $\lambda$-calculus?

texts:
type checking

I was preparing examples of type checking in simply typed $\lambda$-calculus. I wanted to explain it to my audience in the way of implementation. And I found a bit tricky point in the typing rule of application, which is as follows.

$$
   \frac  {\Gamma \vdash t_1:T_{11}\rightarrow T_{12} \quad \Gamma \vdash t_2:T_{11}}
   {\Gamma \vdash t_1 \, t_2 :T_{12} }
 $$

$$
   \frac  {\Gamma, x:T_1 \vdash t_2 :T_2}
   {\Gamma \vdash \lambda x:T_1.t_2 : T_1 \rightarrow T_2}
 $$

Typing rules for booleans are:

$$
   \frac  {}
   {\Gamma \vdash \texttt{true}: bool }
 $$

$$
   \frac  {}
   {\Gamma \vdash \texttt{false}: bool }
 $$

My question

As far as I know, we do not need unification for type checking in the typed $\lambda$-calculus, we need unification in type inference. However, the following type checking example seems that we need something like unification, also it seems that type checking is leading to type construction.

$$
   \frac  { \vdash \lambda x:bool.x: T \rightarrow bool  \quad \vdash \text{true}: T}
   { \vdash (\lambda x:bool.x) \text{ true}: bool }
 $$
Here, $T$ is unknown type variable. It is easy to saying that $T$ is $bool$ because of the boolean typing rules, so we can continue the left branch of the above type checking as follows.

$$
\frac {x:bool \vdash x:bool}
{ \vdash \lambda x:bool.x: bool \rightarrow bool }
$$

The premise is true, so the type checking is successful.

But how do we know the value of $T$ in an implementation?
It should take matching $ true:bool$ to $true: \text{T}$ to know $T$ is $bool$. But this seems unification to me.

Also, finding $T$ for $\Gamma \vdash t: T$ is a type inference problem. So, the above type checking is leading to type inference. Am I correct?

Does type checking of the simply typed $\lambda$-calculus need unification?

Does type inference appear when doing type checking?

Please correct me if I am wrong at any point and explain.

Other info

Type checking of ${ \vdash (\lambda x:bool.x) \text{ true}: bool }$ is given as an example in the book "types and programming languages", page 103. However, it did not specify how $T$ is obtained.
Its derivation concluded $T$ is $bool$ when using the typing rule of application, as shown below.

$$
   \frac  { \vdash \lambda x:bool.x: bool \rightarrow bool  \quad \vdash \text{true}: bool}
   { \vdash (\lambda x:bool.x) \text{ true}: bool }
 $$

I believe these details are ignored in the book.


texts: prove that the language is not context free language

texts:
Prove that the language $\{a^i b^j c^k $ $|$ $i>j>k \geq 0\}$ is non context free language without using the pumping lemma.

we could use some helpful facts to solve the question:

$A$ is a context free language and $B$ is regular, then $ A \cap B $ is context free.
$L_1$, $L_2$ are not context free languages, the intersection $L_1 \cap L_2$ is not context free as well.


texts:
Given the following statement:

  For a graph $G$, consider its minimum spanning tree $T$ and let $e = (a,b)$ be an edge that is not a light edge for a given cut $C$. Then $e$ never belongs to $T$.

Intuitively, I believe that the above statement must be true since in order to make an MST we always take (one of) the lightest edges available that cross the cut, but am I not sure how to approach a proof, or if my intuition is right.


texts: Select/Barrier statements in $\pi$-Calculus denotational semantics

texts:
A select statement waits on $n$ channels until channel $0$ or $1$ or ... or $n-1$ have data.

A barrier lock waits on $n$ channels until channel $0$ and $1$ and ... and $n-1$ have data.

These two constructs seem to mirror co-product and product, respectively, in category theory. While I know there are category theory interpretations of the $\pi$-Calculus, are there any that make this distinction? Are other concurrency tools derivable in a similar way (blocking queue, fork & join, etc.)?

It doesn't have to be $\pi$-Calculus; are there other category-based theories for concurrency can derive these everyday constructs?


texts: What is 'real time' in a Computer Vision context?

texts: Suppose you have a program which works on a stream of images. It gets an image, makes edits and stores the image. What is the maximum latency with which one can still speak of a "real time application"? (Please give a source in your answer)


texts: Can you determine rotation/camera calibration from series of images separated by pure rotation

texts:
I have a series of about 50 images, each separated by a small rotation and taken from the same camera. The images are feature-dense, and I can calculate a homography from image-to-image easily.

My question is, is there any way to determine the rotation matrix and/or intrinsic camera calibration parameters given just these images?


texts: Algorithm to Assign Values Based on Constraints

texts:
I have variables x y and z, and I have the values that they can be assigned to, I.E. x can be assigned 1,2, or 3, y can be 1, and z can be 2.  The problem is a constraint that says once a value has been taken by a variable, no other variables can have that value.

The issue that I am running into is if I start with x, how can I efficiently tell that it's value should be 3?


texts:
I checked my Mac, it shows the memory is 16 GB 2400 Mhz, does it mean that the bandwidth is $ \dfrac{16\times1024}{8} \times 2400$, is there any thing wrong with that calculation, because the value seems a little incredible, I am new to this kind of computer science, hope someone can help me.
Thank You


texts:
I am simplifying a big formula to find the big notation of a certain algorithm. The expression is:

$$\log_2(1-l)/\log_2(1-2^{nH(m/n)-n})$$

where $0.98<l< 1$, $0<m<n/2$, $n>0$ and $H$ is the binary entropy function.

In practice, I known that the algorithm is exponential, but I do not known how simplify that to get the exponential expression. Could you help me please?


texts: Average Case Analysis for finding max and min value on an array

texts:
Given the following algorithm, to find the maximum and minimum values of an array - don't mind the language:

MaxMin(A[1..n])
    max = A[1];
    min = A[1];
    for (i = 2; i<=n; i++)
        if (A[i] > max)
            max = A[i];
        else if (A[i] < min)
            min = A[i];
    print(max, min);

I need to do a probabilistic analysis for the average case of comparisons that will be made on its execution.

So far, my solution is:

Given an indicator random variable:
$$
X_i =
 \begin{cases}
   \text{1, if max $>$ $A[i]$}\\
   \text{0, if max $<$ $A[i]$}\\
 \end{cases}
$$

and assuming an uniform distribution for $A[1..n]$, the expected probability is:
$$E[x] = \sum\limits_{i=1}^{n} Pr(X_i)$$

where $$Pr(X_i)$$ is the probability of the i-th element be the $max$ element in $A[1..n]$. It's possible to determine that:
$$Pr(x_1) = 1, Pr(x_2) = 1/2, Pr(x_3) = 1/3 ,..., Pr(x_n) = 1/n$$
and thus for an array of size $n$ the expected value can be calculated as:

$$E[x] = 1 + 1/2 + 1/3 + ... + 1/n = \sum\limits_{i=1}^{n}{\frac{1}{i}} \approx \log{n}$$

And the same goes for $min$, which will give the same result $\log{n}$. (1)

My questions are: is it correct? Does the complexity for the average case of the given algorithm is $\theta(\log{n})$? Can I use the argument pointed by (1), just modifying $X_i$ so:
$$
X_i =
 \begin{cases}
   \text{1, if min $<$ $A[i]$}\\
   \text{0, if min $>$ $A[i]$}\\
 \end{cases}
$$

I already read this (unfortunately the link to the video isn't available), but it only explains for $max$ and my analysis must be for both $max$ and $min$.


texts: how does an object find the reference to its instance variables

texts:
I'm trying to understand how instance variables for a given object are stored for easy access later on.

For some background, I understand that if you have a reference to an array it is very easy for a computer to access any particular item in the array with an efficiency of $O(1)$ by just multiplying the index provided with the size of each item and adding that to the address of the array.

However it is not always meaningful to store things with just an index and so this is where things like HashMaps can come in handy because they allow someone to store a particular value based on a key and retrieve it in the same $O(1)$ efficiency.

So now imagine that we have some class that has many many instance variables

class myClass {
    int a1;
    int a2;
    int a3;
    ...
    int a500; //or some other really big number
}

and I write some code such as

myObject is new instance of myClass;
myObject.a5 = 123;
myObject.a450 = 70;
//etc

So my questions is:

How does the the .a450...etc get turned into an address?  This type of access seems a lot more like the hashMap described above where a450 is a key that stores some corresponding value... however a hashMap really only attains that $O(1)$ access by careful maintenance of things such as the load factor.  And to achieve the proper load factor you need to have a certain amount of empty items.  There is also the issue that even though both hashMap and arrays have the same $O(1)$ access time... in practice the array will be much faster because there is no need to compute a hash function.  It seems like this would not be an appropriate way to manage objects in any given language because if you have hundreds or thousands of such objects, then the overhead of having a hashmap would be very wasteful.


texts:
I know $P$ vs $NP$ is an open problem in Computer Science. However the people concerned (at least according to Wikipedia) believe $P \neq NP$.

I have two questions:

$(1.)$ Given that it is possible to prove lower bounds for problems. Does there exist any problem(s) for which the solution can be verified in polynomial time but no known algorithm can solve it in polynomial time which has a proven lower bound?

$(2.)$ Is this proven lower bound polynomial or exponential?


texts: How can any non-primitive-recursive function like the Ackermann function be implemented on hardware?

texts: If for-loops and function calls both boil down to jump instructions when implemented on a real machine, then how is "The Ackermann function isn't implementable with for-loops" a meaningful phrase?


texts:
I am attempting to make a regular grammar over alphabet {a, b, c} where there is at most one c. So far, I have the regular expression ((a|b)*|c)(a|b)* but am unsure where to go from here; my previous attempts have ended up allowing multiple c's.

The solution I has gives (N={s,t}, T={a,b,c}, s, R), s→є, s→as, s→bs, s→ct, t→at, t→bt, t→є, however I do not see how this limits the number of c's generated to at most 1.


texts: Decidable problems for which no concrete decision procedure is known

texts:
I am looking for an example of decidable problems the decision procedures of which are unknown. I believe someone mentioned one to me once, and I also have read somewhere, but my memory is corrupted. I suppose the decidability of these problems are proved non-constructively, so that they have this kind of counter-intuitive property.

I think that in graph theory, there are a number of problems in this trait. I am wondering if you are aware of any of these.


texts: Is binary tree just a two-dimension-doubly-linked-list?

texts:
We all know the structure of a binary tree:

struct binary_tree {
  binary_tree *parent;
  int          data;
  binary_tree *left;
  binary_tree *right;
};

So a doubly linked list has the following structure:

struct linked_list {
  linked_list *prev;
  int          data;
  linked_list *next;
};

But a binary tree can also be manipulated like this:

struct my_linked_list {
  my_linked_list *prev;
  int             data;
  my_linked_list *next0;

  my_linked_list *next1;
} binary_tree;

By that, I have "proven" that binary tree shares a similarity to doubly linked list. (with the addition of another next element)

So my question is here: Is binary tree really a vertically-descending graph, or just an extension to the linked list, that can be drawn horizontally?

I know this is a kind of stupid and meaningless question but it was confusing me for years and years. I am just an apprentice to the computer science...


texts: Proving correctness of the Newton's Method for finding the square root of a number

texts:
I'm trying to prove the correctness of this simple square root calculation algorithm using SPARK:

Y := X / 2.0;
while abs (X - Y ** 2) > Tol * X loop
    Y := 0.5 * (Y + X / Y);
end loop;
return Y;

The preconditions are that both X and Tol are greater then zero and the postcondition is simply the opposite of the while loop's condition.

Are there any invariants of the loop above that may help? Or maybe a different algorithm (eg. bisection) would be a better choice? So far I've tried showing that the value of the square root is always between Y and X / Y but that didn't get me anywhere.


texts: Is it possible to detect a simple negative-weight cycle of weight $N$ in polynomial time?

texts: Given a directed graph and an integer $N$, is it possible to detect a simple negative-weight cycle whose edges sum to $N$ in polynomial time? I thought about modifying the Floyd-Warshall algorithm to check if the diagonals equal $N$ as they get set, but I realized this wouldn't work if a vertex appeared in multiple negative-weight cycles.


texts: How do I prove that SAT in coNP implies NP=coNP?

texts: Is it true that if SAT is in coNP then its also coNP-complete (because it is NP-complete)?


texts:
Suppose that there are rectangles in the Cartesian plane, each aligned with the axes---the rectangles are defined by left and right x-coordinates and top and bottom y-coordinates.

There are two operations on rectangles:

SPLIT partitions a single rectangle into two adjacent rectangles
with either a horizontal or vertical cut. Splitting is parameterized with an $x$ or $y$ value indicating where to split.
JOIN is the inverse of SPLIT, turning two adjacent, non-overlapping, aligned rectangles of the same height or width into a single rectangle.

Question:  Given a set of N non-overlapping rectangles whose union is a (larger) rectangle---the set forms a partition of the larger rectangle---is there an efficient algorithm that will compute the shortest sequence of SPLIT and JOIN operations to transform the set of rectangles into the single (union) rectangle?

The smallest partition that requires using a SPLIT to transform a partition into the union is this:

(After a single SPLIT of any of the long rectangles at the obvious spot, the union can be finished with a sequence of JOINs.)


texts:
DEFINITION: A set of vertices $A\subseteq V$ in a graph $G(V,E)$ is called a module if it satisfies the following property:

  For every $v\in V\setminus A$, either $A\subseteq N(v)$ or $A\cap N(v)=\emptyset$, where $N(v)$ is the neighborhood of $v$.

GRAPH-MODULE problem:

  Input: An undirected graph $G(V,E)$ and a natural number $k$

  Output: YES if $G$ has a module $A\subseteq V$ with $|A|=k$, otherwise NO

What is the complexity of GRAPH-MODULE problem?


texts:
I've only just started researching the use of neural networks to solve differential equations (I'd like some PDEs), and I have a little background in building a neural network.
I was wondering if any free data existed for input in solving PDEs.  I'd like to stick with something basic, but I'm working on small project where I would like to do something like, solve a simple heat equation algebraically, numerically, and then with a neural network. Would I have to create an input data set?  And if so, do you know any literature to guide me on what the set could look like?  Thanks.


texts: Is the codomain/range of a hash function always $\mathbb{Z}$ or $\mathbb{N}$?

texts:
From Wikipedia

  A hash function is any algorithm or subroutine that maps large data
  sets of variable length, called keys, to smaller data sets of a
  fixed length. For example, a person's name, having a variable
  length, could be hashed to a single integer. The values returned
  by a hash function are called hash values, hash codes, hash sums,
  checksums or simply hashes.

I wonder if the range/codomain of a hash function is always the set of natural numbers or integers, because their function values seem to be always used as indices to some array?


texts: Algorithms for keeping number of backups constant

texts:
The problem is quite simple: backups are done at regular time intervals (with possible but rare exceptions). The storage however is not unlimited, and only a certain number of backups can be stored, latest ones being more valuable, and desired to be more frequent than old ones.

For example, there could be backups for each day for last two week, then once a week for the month, then once a month for three years, and the rest just once a year, the very first backup is to be saved however. Difference in backup sizes can be ignored. Before or after adding one more backup, one or more from old ones are to be selected for deletion (or further archiving).

It is actually not a problem to come up with ad hoc solution for this, but the question are:

how this kind of a problem and algorithms for it's solution are called in computer science (or operation research and related disciplines)?
what approaches are standard (may be, some notable solutions, named algorithms?) and what is the most efficient approach (time complexity-wise)?

It is clear, that this should be less complex than knapsack problem, but seems distantly related. If I am not mistaken, the problem is optimization one.

More specific problem definition:

For each step (when new backup is being added):

INPUT:

$m > 2$ (number of backups)
$\{t_i\}$ for $i \in M \subset \{1, \dots, n\},\qquad |M| \leq m$, $\qquad t_i \gt t_{i+1},\qquad t_i \in \mathbb N$ (times when backups were taken)
function $f$, which specifies a frequency scale of remaining stored backup. For example, if $f$ is constant, it means that backups are maintained evenly. There may be some artificial exceptions for the first and last backup (it is probably stupid to drop the latest backup!).

OUTPUT: $t_j$ to be deleted. The remaining timestamps $M' = M \setminus \{t_j\}$ should remain distributed with increasing frequency. The exact function $f(t)$ for normalizing desired frequencies can be stepwise or of some other form. That is, interval lengths $t_{k-1} - t_k$ should increase with $t_k$.

The good solution (ideally - optimal) minimizes the residual (for example, mean square) - difference between desired remaining frequencies $f$ of backups and actual frequencies (eg, estimated by interpolation using moving window of 3 values).

I guess, there should be no big differences between different measures of error and ways to estimate error, because we have discrete values, but the function $f$ is what mostly defines the "shape" of the distribution. It could be a $e^t$, or a rough stepwise approximation.

(It is another question, what $f$ is of practical interest. But it is more complex, and one need to go into statistics on how old backups are really needed and how often, and probably into cost of storage vs cost of losses and such.)


texts:
Definitions:
Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P_3$ as an induced subgraph (that is, the resulting graph is a disjoin union of cliques).

The class of $k$-trees is defined as follows: a complete graph with $k$ vertices is a $k$-tree; a $k$-trees with $n + 1$ vertices $(n > k)$ can be constructed from a $k$-tree $T$ with $n$ vertices by adding a vertex adjacent to all vertices of a $k$-clique of $T$, and only to these vertices.

Question:
Does exist a polynomial-time algorithm to solve Cluster Edge Deletion on 2-trees?

My idea: Let $G$ be the 2-tree.
I transform $G$ to a new graph $G'$ where, each node of $G'$ represents a $K_3$ in $G$. And two nodes of $G'$ are adjacent if and only if their corresponding $K_3$ share a common vertex in $G$.

Let $M$ be the resulting graph after removing the minimum edges from $G$.
I think that if always exist some graph $M$ contains a 3-clique $H$ which has a node with minimum degree in $G'$, then I can solve this problem on $G \backslash H$.

For example as below figure, I choose node $x$ with minimum degree 3 in $G'$, and after remove all vertices of clique $\{f,g,e\}$ in $G$, I got an union disjoint of two clique $\{f,g,e\}$ and $\{b,c,d\}$ in $G$.


texts: What is the difference between type theory and logic programming (in terms of declarative programming and specification)

texts:
How is does type theory (coq, lean, agda), and logic programming (prolog, datalog) differ from each other.
Logic programming is a way of declarative specifying an algorithm, using classical 1st order logic and the implementation of the computation of that algorithm does not have to be specified.
Type theory is a way of declarative specifying an algorithm, using constructive logic, making program synthesis possible.


texts: Can parallel downloading with many ip's possible?

texts:
I am not too intelligent,but i got this in my mind.Lets say i download a file from abc.com
and the speed is limited for an IP(say 60kbps).Can i initiate parallel downloads from multiple ip addresses which could be virtual IP's OR two diff.devices and break my download into parts,download each part at 60kbps and then join all.So that now it takes less time?IS this possible some kind of software to create Virtual Ip addresses?Or in multiple devices?


texts:
I was trying to solve a question dealing with n instructions in an uneven pipeline with k stages. I came across a generic formula for even pipelines i.e. (k + n - 1) * clock cycle. But I feel this should not work for uneven pipelines as the above formula is based on fact that the 1st instruction takes time = sum(time of k stages) and the 2nd instruction onwards takes time = maximum of stage delays.

A example: A pipeline is designed with 5 stages having execution times respectively as 3ns, 4ns, 2ns and 4ns. How much time will it take to execute 1000 instructions?


texts: Is it 100% OK to say "All software doesn't need to know the system lower than the architecture level"?

texts:
Most of you know this diagram. If this diagram is true, all software is free to not know the levels lower than ISA. But it's not true. Softwares like performance-critical programs or system softwares like OS and compilers, are often forced to understand not only ISA but also microarchitecture.

If so, what about the levels lower than microarchitecture? Is it 100% sure to say the levels lower than uArch aren't require to be understand by softwares or programmers?


texts: Cut costly functions in inter-procedural abstract interpretation

texts:
I am performing some inter-procedural abstract interpretation to capture certain program properties. Following the standard way, what I am doing is to maintain a work list of to-be-analyzed functions, and pick one from the work list to perform intra-procedural analysis until the work list is empty.

Currently, I observed that the intra-procedural analysis of certain functions would not terminate. Basically, it is just taking too much memory and become too slow to reason for even one more statement.

Of course, I can optimize my code base and improve the memory efficiency, but fundamentally that shouldn't help too much.

Now I am seeking for some strategies to bypass such obstacle. Intuitively, what I can do is to cut a intra-procedural analysis off whenever the memory usage grows too high, return a Top as the return value, and switch to the next function in my work list for analysis.

This seems very naturally, and should be sound as well! However, after some quick review of some abstract interpretation work, I don't see any related work performing such cut off.

So here is my question:

What is the standard approach in abstract interpretation if a intra-procedural analysis becomes too costly to finish?
I assume the cut off and return Top approach is sound. Then why shouldn't I find any related literature employing such approach? Is it too ad-hoc and naive?


texts: without triangle inequality, finding good approximate tours for TSP in polynomial time is impossible unless P=NP?

texts:
In the text book, Introduction to Algorithm, 3rd Edition.

In the chapter, Approximation Algorithms and for the problem Travelling Salesman Problem, the author says:

I am wondering how triangle inequality gives rise to this assertion? It seems that this property is not that important, as I searched through the rest of this section, it does not appear.


texts: Is the definition of $\textbf{BPP}$ robust for doubly exponential small (or even smaller) error?

texts:
$\textbf{BPP}$ is usually defined in terms of probabilistic polynomial-time TMs which have an error probability of at most $\frac{1}{3}$. Furthermore, using the Chernoff bound it can be proven that the definition of $\textbf{BPP}$ is robust (i.e., the class remains the same) if we require the error probability to be upper-bounded by $\varepsilon(n) = \frac{1}{2^{p(n)}}$, where $p$ is a polynomial and $n$ denotes the input length.

Do we know what happens if we require (asymptotically speaking) smaller and smaller error probabilities? In particular, do we know whether $\textbf{BPP}$ is robust if we choose the error probability to be, say, upper-bounded by $\varepsilon(n) = \frac{1}{2^{2^n}}$?

I thought this could be shown using (again) the Chernoff bound
$$\text{P}(|\bar{X} - \mu| \ge \varepsilon) \le e^{-2\varepsilon^2 m}$$
(where $\bar{X}$ is the mean value of $m$ independent samples, $\mu$ is the expectation (i.e., the PPT's error probability), and $\varepsilon \in (0, \mu]$), but I don't see a way to do so except taking $m = 2^n$ exponentially many samples.


texts: Do all the numbers belong to same slot in the Hashtable?

texts:
I was reading the CLRS. In the Hashing Chapter on page 262 a statement says: "For example, if we know that the
keys are random real numbers $k$ independently and uniformly distributed in the range $0 \leq k < 1$, then the hash function $h(k)= \lfloor km \rfloor$."

Question: Does Uniformly distributed meant all numbers have equal probability.
if so then all numbers have the same $k$ values and belong to the same slot.


texts: where is all deleted data will go from memory system/internet?

texts:
where is all deleted data will go  from a memory system ?
if it is not deleting actually where it storing ?
i am always wonder about this when we are sending something to a memory system it takes long time (depends up on usb port) and when we are deleting it not taking more than a bling of eyes and disappears actually where it goes ?
** deletion process is happening on both memory device and internet is same or different ** ? can we recover data from internet ?


texts:
Please help me! I've been asked to make a circuit using only Logic Gates to implement an 8-bit 2's complement subtractor.

I was thinking of somehow modifying an 8-bit adder, but I figured it isn't 2's complement so it won't be of much use to me.

Any help is greatly appreciated, even if it's a pointer to the right approach to take in this.


texts: Iterative DFS space complexity O(|E|)? Same vertex appears multiple times in stack?

texts:
I'm referring to a question already asked on stackoverflow: https://stackoverflow.com/questions/25988965/does-depth-first-search-create-redundancy

However I'm not quite convinced by the answers provided there.

Some iterative DFS implementations that I have seen (such as the one provided by Wikipedia) allow vertices to be pushed onto the stack more than once.

The space complexity would thus be $Θ(|E|)$ in the worst case. (While a recursive implementation of DFS would only require at most $Θ(|V|)$ space.)

Certain implementations check if a vertex has already been discovered before pushing it onto the stack, but this does not affect the space complexity of $Θ(|E|)$ since a vertex is only marked as discovered when it is popped off the stack and not when it is pushed (Thus we are not keeping track of vertices currently in the stack). This only makes sure that vertices which enter and leave the stack are never pushed onto the stack again.

Instead, one would have to mark a vertex before pushing it onto the stack and then check each time before pushing a vertex if it has already been marked (is currently in the stack) in order to avoid multiple occurrences of a same vertex in the stack (As you would do in BFS, where a queue is used instead).

My question is, why would one want to allow multiple occurrences of a same vertex in the stack and why one cannot simply apply the method mentioned above (which is used in BFS) in order to achieve space complexity of $Θ(|V|)$ ?

To illustrate the issue consider this example from the link that I provided:

  For example, consider the graph where node 1 points to node 2, which points to node 3, which points to node 4, and so on, up to node 100. Each of these nodes points to node 0. Consider applying the Wikipedia DFS algorithm to this graph, with node 1 as the start state. First, node 0 will be pushed onto the stack. Then node 2 will be pushed. Next, node 2 will be popped off the stack, and since it has not been explored, its children will be pushed onto the stack, (without checking whether they have already been added to the stack!). Node 2's children are node 0 and node 3. Next, node 3 will be expanded, pushing node 0 and node 4 onto the stack. This will continue until the stack is filled with 100 occurrences of node 0.


texts:
If k is the height of an AVL Tree, the minimal number of inner nodes is:
N(k) = N(k-1) + N(k-2) +1.

Why is this formula true?


texts: Insertion sort Pseudo code vs implementation?

texts:
So I'm trying to implement an insertion sort algorithms based on page 18 Cormen psuedocode but I'm confused by for j = 2 to A:length. Specifically, what does the j=2 mean? I'm implementing it using the below python code and it only works when the range is the entire length of the array:
def insertion_sort(arr):
    # length of array
    n = len(arr)

    # traverse through array
    for i in range(n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Could someone explain?


texts:
Now we can see that Church was associated with the Simply Typed Lambda Calculus. Indeed, it seems he explained the Simply Typed Lambda Calculus in order to reduce misunderstanding about the Lambda Calculus.

Now when John McCarthy created Lisp - he based it on the Lambda Calculus. This is by his own admission when he published "Recursive functions of symbolic expressions and their computation by machine, Part I". You can read it here.

Now we know that at the core of Mathematica is a Lisp-like system, but instead of being based purely on the Lambda Calculus, it is based on a term-rewriting system.

Here the author states state:

  Mathematica is fundamentally a term rewriting system... a more general concept than the Lambda Calculus behind Lisp.

My question is: Why did the Mathematica Language choose term rewriting instead of the Lambda Calculus as its basis?


texts:
I'm confused by the running time of the following algorithm. I've been told it's $O(n^3)$, but there are only two loops. How can that be?

for(int i = 0; i < s.length(); ++i) {
    for(int j = i; j <= s.length(); ++j) {
        String sub = s.substring(i, j);
            if(isPalindrome(sub) && sub.length() > maxCount) {
                maxCount = sub.length();
                longestP = sub;
            }
    }
}


texts:
I'm still student in university, and I need 2 years to graduate, but the thing is I still don't know anything about computer science other than problem solving, C++/Python OOP and DataStructure; I know these are heavy important subjects but I'm still lost, my university is also lost for me and I have the power to learn more and more alone but all I need is a clear plan to do that..
I think this question had been asked hundreds of times.. But still there's no good enough answers.. So let me rephrase the question and ask this :
How to know what kind of majors do I want to learn and work with in the future as graduated computer science student? AND Where to find a tree-plan of skills that I need to learn to reach my goal on that major? AND When I find that tree of skills, Where to learn those skills other than my University?
So I need to know what major I do really need, and how to learn it in a very good way..
Please give me any helpful websites, articles, tests to know what major I want (idk if that's even exist) and anything you see it could help me :D
Thanks in advance


texts: Assignment Problem -- finding the $k$ agents with the best assignment

texts: I have a question that I have been thinking about. Suppose we have $n$ agents, $m$ tasks, a cost matrix with $M_{ij}$ being the cost of agent $i$ performing task $j$, and are given a value $k \leq n$. How can we find the $k$ unique agents, who when each optimally allocated a unique task, result in a minimum total cost? Can this be related to the assignment problem? Thank you very much for any guidance or assistance.