texts: What can be said about the Halting Problem if we can include the halting status to the input?

texts:
I was reading about Turing Machines and the Halting Problem, i understand that you need an oracle to decide whether given input will halt or loop forever. But why do we need an oracle if we can include the halting status within the input itself?

What i mean is, given an input, in the encoding process of it, we can add the halting status as an Additive Identity to the input that will make it halt in a known finite time steps.

An example, assuming that a new model of computation (X) exists, (X) is a Universal Turing Machine and has the computational power to operate and halt after (N) time steps on any input, and (N) = same length of the input ... What can be said about the halting problem given the described situation?


texts: Is the kernel loaded into memory for every user simultaneously using a Multi-User O.S. system?

texts: I have a doubt about loading kernel for every user using a Multi-User system. Every user's processes and programs are scheduled to CPU in a time-sharing fashion. But, do every user on the multi-user system have their individual kernel loaded in the main memory, or is there only one kernel loaded which is sort of distributed amongst the users?


texts: What is the space complexity of Dijkstra Algorithm?

texts:
As per my understanding. The space complexity will be O(V). An array of V nodes will be created which in turn  be used to create the Min heap.

But this link is stating that It is O(V^2)? I don't understand how it can be O(V^2)?

I have search the same topic in the Book entitled Introduction_to_Algorithms by  Thomas H. Cormen  but still not able to find the answer.
I Don't understand what I am missing.


texts: Can any problem in P be converted to any other problem in P in polynomial time?

texts: Is it possible to convert any problem in P to any other problem in P in polynomial time?


texts: Does forcing TMs to change all symbols they read change their power?

texts:
If we limit a turing machine so that it is not allowed to write the symbol that it reads would it reduce its power?

For example: $( State, A, State, Z, DIRECTION)$

$A$ cannot be the same symbol as $Z$.


texts:
I've come to understand that programs are graphs on several layers. Call-graphs are an example that come to mind without a textbook handy, another is mutation flow.

So I  do understand that code is a graph, and that compilers and interpreters usually end up traversing the graph according to the rules of the language. It's magic, really, but here is my question:

Are all calculations graphs? Are there calculations that cannot be expressed as a state machine?


texts: Minimum Clique Cover - Mixed Integer Programming

texts:
I have a general (undirected) graph with a set of nodes, a set of edges, and a weight for each edge. I want to find a minimum clique cover of the vertices of the graph, that is, a partition of the graph into the smallest number of cliques. A clique is a set of nodes such that each pair of nodes is connected. I also want to maximize the sum of edge weights over the cliques. I want to use an integer programming approach for this problem.

Can any one give me some hints or some references that use mixed integer linear programming for the (maximum weight) minimum clique partition?

Thank you very much.


texts: What is the "description" of a Turing machine?

texts:
I am currently reading about the Halting Problem in my course on the theory of computation and the following was given in my lecture slides

Now my question is that if $d$ is the description of a Turing machine, what exactly is $d$ from a strictly mathematical point of view? The way that $d$ is written above seems to suggest that $d \in Q$ (i.e. that $d$ is a state of the Turing machine $T$), but I can't be entirely sure.


texts: Proof that fast broadcasts have to target larger cycles first

texts:
I am having trouble trying to formulate a simple proof. I can clearly see that what I am trying to prove is correct but to prove it I am not sure what to do.

The problem is a broadcasting problem on a graph. My graph contains two cycles. The two cycles are joined by a single vertex $v$. If the vertex $v$ contains some info that it wants to broadcast to all other vertices on the graph what is the minimum number of rounds required to achieve this.

So a proof I am trying to formulate is that in order to achieve the minimum broadcast time I would have to first broadcast on the largest of the two cycles.

I was thinking of a proof by contradiction. Something like assume that we first broadcast on the smaller cycle and somehow show that it could lead to a broadcast time that is larger than the time if we were to start on the larger cycle.

To clarify, suppose we have two cycles $C_1$ and $C_2$ such that $|C_1| \ge |C_2|$. So the minimum broadcast time from vertex $v$ denoted by $b(v)$ would require us to broadcast on the larger cycle first.


texts: How to prove that existence of one-way functions implies P≠NP?

texts:
Wikipedia:

The existence of such one-way functions... would prove that the complexity classes P and NP are not equal.

How is this proved?


texts:
The Halting Problem is defined as:

$H_{TM} = \{ \langle M, w \rangle \mid \text{\(M\) halts on input \(w\)}\}$

I'm not sure what it means. Is $H_{TM}$ a collection of Turing Machines such that all of them accept/reject the word $w$? Is that a specific word? Or does that mean any word in their alphabet?

Thanks


texts: Prove: A connected graph contains an Eulerian cycle iff every vertex has even degree

texts:
Recently, I am reading the book [1]. I am trying to solve the following problem:

  1.3 Proving Euler's claim. Euler didn't actually prove that having vertices with even degree is sufficient for a connected graph to be Eulerian--he simply stated that it is obvious. This lack of rigor was common among 18th century mathematicians. The first real proof was given by Carl Hierholzer more than 100 years later. To reconstruct it, first show that if every vertex has even degree, we can cover the graph with a set of cycles such that every edge appears exactly once. Then consider combining cycles with moves like those in Figure 1.8.

The following is my attempt to solve the problem:

Let $G$ be a connected graph and every vertex of $G$ has even degree. Let $N_V$ be the number of vertices in $G$. Let $d_i$ be the degree of the $i$th vertex for $i = 1, ..., N_V$. Then
$$ d_i = 2 n_i \tag{1} $$
for some positive integer $n_i$, $i = 1, ..., N_V$. Therefore, by walking on the edges of $G$, we can walk to and leave the $i$th vertex for $n_i$ times, with each edge being walked on exactly once. Then I don't know how to continue...

I also go to the Internet and find Carl Hierholzer's paper [2]. However, it is written neither in English nor Chinese (my mother language), so I can't read it.

Note: It is not my homework. I am just interested in solving this problem.

References

[1] C. Moore and S. Mertens, The Nature of Computation, Oxford University Press, 2015.

[2] C. Hierholzer. Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen, 6:30-32, 1873.


texts: Can Real-Time Strategy games be ever solved?

texts:
With the advent of BWAPI, many AI enthusiasts have been making amazing AIs that can compete against top players in Starcraft. This led me to wonder if RTS (Real-Time Strategy) games can ever be solved theoretically.

One of my colleague argues no, because RTS games are non-deterministic and stochastic. What does this mean exactly? For instance, in Starcraft you have a set of defined and limited moves (I.E: Units, buildings, economy) you can make in the game, so I don't see what can be so stochastic about the game.


texts: Calculate math function depend on N value

texts:
I have method with the following prototype :
R[] = method(k,n)

which :
n = ordinal value 0 <n <10^9
k = math function depend on n value : i.e n^6
R = array of computed values

For example :
n = 10^8
k = n ^2
so then :

n [index]= 1,2,3,...,10^8
R [index]= 1,4,9,..,..

I dont want to do the common solution : iterate and solve each element and aggregate the result because of bad performance.
I am looking for solution that :

is optimized solution
work for any math function (maybe genric)
well designed


texts: Speech to Text API with Unknown Language

texts:
I would like to develop an application that outputs text from the audio of 2 possible languages.

For ex: Audio might be English or Spanish, it should return the spoken words.

Most speech to text APIs strongly rely on an input language for words retrieval, I would like to know if there's any tool or research paper that could work for my use case.


texts: Are there data structures that mix a tree structure with lists?

texts:
I suppose something like this could probably be easily designed, however I was wondering if there's a data structure that somehow uses both list and tree to access data.

Something like this (I'll be informal, but I hope I can give you some idea of what I mean).

Suppose we have a tree with depth $n$. At depth 1 we would have the nodes $X_1,X_2,\ldots X_{n_1}$. For $i_1 \in \left\{1,\ldots n_1\right\}$ the node $X_{i_1}$ could have as children $X_{i_1,1},X_{i_1,2},\ldots X_{i_1,n_{i_1}}$, for $i_2 \in \left\{1,\ldots,n_{i_1} \right\}$ the node $X_{i_1,i_2}$ could have as children $X_{i_1,i_2,1},X_{i_1,i_2,2},\ldots, X_{i_1,i_2,n_{i_2}}$, and so on. However to get quick access to the nodes say at depth $k$ I could also implement a list of pointers to all the nodes $L_k := \left\{ X_{i_1,\ldots, i_k } \right\}$. So for depth 1 I could have the list

$$
L_1 := \left\{ X_1, \ldots, X_k \right\}
$$

At depth 2 instead

$$
L_2 := \left\{ X_{1,1},\ldots, X_{1,m_1},\ldots,X_{n_1, 1} , \ldots, X_{n_1, m_{n_1}} \right\}
$$

So in general the list $L_k$ would contain all the nodes with $k$ indices. I'm pretty sure something like this already exists, however I can remember if there's a specific name or not.


texts: Why not to take the unary representation of numbers in numeric algorithms?

texts:
A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits).

For example testing whether a number $n$ is prime or not, requires a loop through numbers from 2 to $n-1$ and check if $n$ mod $i$ is zero or not. If the mod takes O(1) time, the overall time complexity will be O(n).

But if we let $x$ to be the number of required bits to write the input then $x = \log n$ (binary) so $n = 2^x$ and the running time of the problem will be O($2^x$) which is exponential.

My question is, if we consider the unary representation of input $n$, then always $x=n$ and then pseudo-polynomial time will be equal to polynomial time complexity. So why we never do this?

Furtheremore since there is a pseudo-polynomial time algorithm for knapsack, by taking $x=n$, the knapsack will be polynomial as a result P=NP


texts: what is the need for valid/invalid bit in paged memory technique?

texts:
How is the valid/invalid bit in paged memory useful?
I am not able to understand the significance.
Is it also somehow used to share the processes among different users.


texts: Forward checking vs arc consistency on 3-SAT

texts: If I were to let the variables be the propositions and, constraint be all clauses being satisfied, which technique would be more effective in solving 3-SAT? Forward checking or arc consistency? From what I gathered forward-checking is $O(n)$, while Arc consistency is about $O(8c)$ where c is the number of constraints (According to this page). So perhaps forward -checking is faster somehow? How should I determine which to use?


texts: What is the difference between Abstract Data Types and objects?

texts:
An answer on Programmers.SE characterizes an essay by Cook (Objects are not ADTs) as saying

  Objects behave like a characteristic function over the values of a    type, rather than as an algebra. Objects use procedural abstraction rather than type abstraction
  ADTs usually have a unique implementation in a program. When one's    language has modules, it's possible to have multiple implementations  of an ADT, but they can't usually interoperate.

It seems to me that, in Cook's essay, it just happens to be the case that for the specific example of a set used in Cook's paper, an object can be viewed as a characteristic function. I don't think that objects, in general can be viewed as characteristic functions.

Also, Aldritch's paper The power of interoperability: Why objects are inevitable¹ suggests

  Cook’s definition essentially identifies dynamic dispatch as the most
  important characteristic of object

agreeing with this and with Alan Kay when he said

  OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.

However, these companion lecture slides to Aldritch's paper suggest that Java classes are ADTs while Java interfaces are objects -- and indeed using interfaces "objects" can inter-operate (one of the key features of OOP as given by one of the bullet points above).

My questions are

Am I correct to say that characteristic functions are not a key feature of objects and that Frank Shearar is mistaken?
Are data that talk to each other through Java interfaces examples of objects even though they don't use dynamic dispatch? Why? (My understanding is that dynamic dispatch is more flexible, and that interfaces are a step towards objective-C/smalltalk/erlang style messaging.)
Is the idea of dependency inversion principle related to the distinction between ADTs and objects? (See the Wikipedia page or The Talking Objects: A Tale About Message-Oriented Programming) Although I'm new to the concept, I understand that it involves adding interfaces between "layers" of a program (see wikipedia page diagram).
Please provide any other examples/clarifications of the distinction between objects and ADTs, if you want.

¹  This paper (published in 2013) is easy reading and summarizes Cook's 2009 paper with examples in Java. I highly recommend at least skimming it, not to answer this question, but just because it's a good paper.


texts:
Given two statement:
A:if inputs of a problem is online, then there is faster or equal
algorithm in view of time complexity for that problem when input is
offline.
B:if inputs of a problem is offline, then there is faster or equal
algorithm in view of time complexity for that problem when input is
online.
Which of the following statement is true?

I think A is true because each algorithm works for online inputs then it work for a offline inputs. Now we can say A is true.
B is false because, consider online sorting algorithm and offline sorting algorithm, online algorithm have much more time complexity in ratio of offline versions.


texts: Gate/transistor number and program length measures of computational complexity?

texts:
Are there scaling concepts regarding the number of components needed and minimum program length needed to solve a problem of some complexity?

For example, problems are characterized by O(.) measures of time and space complexity. Space complexity tells me the amount of memory needed but not the number of computational components needed. We assume a Turing machine and count the number of steps performed. But in practice, the number of instructions available, and the level of parallelism have some non-linear relationship with the amount of time needed to solve a problem. Amdahl's law deals with speeding up one part of the problem. On a more general level, there could be at least an empirical or conjectural observation of how physical hardware like NAND gates or transistors scale with problem size or speed.

Thinking in terms of program size, there is Kolmogorov complexity defined as the shortest program that will generate a sequence or other data object. But what about the min. program that will solve a problem? Has anyone defined or used Kolmogorov-like complexity to characterize a problem rather than information content?


texts:
Given matrix $A \in \{0,1\}^{n \times m}$ with $n$ rows and $m = 2^n - 1$ columns. Where $j$-th column is binary decomposition of $j$ ($j = 1 \dots 2^n - 1$). For example, if $n = 3$:
$ A = \begin{pmatrix}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 &0 & 0& 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1
\end{pmatrix}$
This matrix calculates $Ax$ over $(\{0,1\}, \oplus)$, where $x \in \{0,1\}^m$.
For example, if $n = 3$ it calculates $(x_4 \oplus x_5 \oplus x_6 \oplus x_7,\; x_2 \oplus x_3 \oplus x_6 \oplus x_7, \; x_1 \oplus x_3 \oplus x_5 \oplus x_7)^T$
This is a Boolean function with $m = 2^n - 1$ inputs and $n$ outputs. It can be represented by boolean circuit $S$ with $m = 2^n - 1$ inputs and $n$ outputs, where only XOR gates are allowed. Each XOR gate in circuit $S$ is binary — it takes exactly two inputs.
Let us denote by $size(S)$ number of gates in $S$ (we don't count inputs as gates, but we count outputs as gates).
It is not hard to prove upper bound: $size(S) \le 2(2^n - 1 - n)$.

Problem: Prove lower bound: $size(S) \ge 2(2^n - 1 - n)$.


texts:
I'm trying to understand the category utility function in the COBWEB algorithm.

Assume you have the following data and build a set C of three clusters (three child-nodes under the root node), one for amphibian (C1), one for fish (C2) and one for bird/mammal (C3).

Using the above CU formula, I'm now trying to compute the total category utility like this.

P(C1) = 0.25, P(C2) = 0.25, P(C3) = 0.5

P(body_cover=moist_skin) = P(body_cover=scales) = P(body_cover=feathers) = P(body_cover=hair) = P(heart_chamber=3) = P(heart_chamber=2) = 0.25

P(body_temp=unregulated) = P(body_temp=regulated) = P(fertilisation=external) = P(fertilisation=internal) = P(heart_chamber=4) = 0.5

CU_C1 = 0.25 * ((1²-0.25²) + (1²-0.25²) + ((1²-0.5²) + (1²-0.5²)) = 0.84375

CU_C2 = 0.25 * ((1²-0.25²) + (1²-0.25²) + ((1²-0.5²) + (1²-0.5²)) = 0.84375

CU_C3 = 0.5 * ((0.5²-0.25²) + (0.5²-0.25²) + (1²-0.5²) + ((1²-0.5²) + (1²-0.5²)) = 1.3125

Or generally:

CU_C3 = P(C3) * (
    (P(body_cover=feathers|C3) - P(body_cover=feathers)) +
    (P(body_cover=hair|C3) - P(body_cover=hair)) +
    (P(heart_chamber=4|C3) - P(heart_chamber=4)) +
    (P(fertilisation=internal|C3) - P(fertilisation=internal))
)

CU = (CU_C1 + CU_C2 + CU_C3) / |C| = (0.84375 + 0.84375 + 1.3125) / 3 = 1

I'd like to know if my computations are correct and if 1 is actually the final CU value for that partitioning. Can you help me?

I also found the following solution, but I can't reproduce it. In my understanding the two inner loops / sums are iterating over the attribute and each attribute's value, regardless of the datapoints contained in the cluster.

CU_C3 = 0.5 * (((0.5² - 0.25²) + (1² - 0.5²) + (1² - 0.5²) + (1² - 0.5²))
+ ((0.5² - 0.25²) + (1² - 0.5²) + (1² - 0.5²) + (1² - 0.52²)) = 2.4273

... leading to CU = 1.375


texts: How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE?

texts:
Suppose you are given a polynomial-time algorithm for the following problem related to INDEPENDENT SET:

INDEPENDENT SET VALUE

Input: An undirected graph G.

Output:The size of the largest independent set in G (but not the set itself).

Show how you can use this algorithm to solve the INDEPENDENT SET problem in polynomial time: given a graph G, return an independent set which is as large as possible.

Any help would be really appreciated. I am pretty lost in this question


texts: Grammar for describing boolean expressions with AND, OR and NOT

texts:
I wrote the following LL(1) grammar to describe the set of boolean expressions involving AND ,OR  an NOT only. This, as can be seen, also reflects the precedence of the operators (ie., 'AND' is done before 'OR', etc).

Is it correct?

    1.  E   ::=  T E’
    2.  E’  ::= OR T E’
    3.  E’  ::=  ε
    4.  T   ::=  F T’
    5.  T’  ::= AND F T’
    6.  T’  ::= ε
    7.  F   ::= NF'
    8.  N   ::= NOT
    9.  N   ::= ε
   10.  F'  ::= (E)
   11.  F'  ::= id


texts: Is there a variant of Dijkstra’s algorithm for partial recalculation?

texts:
Suppose the following:

We use Dijkstra’s algorithm to find the shortest route to our destination.
The start node (current vehicle position) keeps changing, i.e. moving towards the destination along the calculated shortest path. For this reason we use the inverted form, where the cost of a node represents the cost to reach the destination from there, and the destination’s cost is 0—that way the route graph does not need to change as the vehicle moves through it.
The cost of edges may change while the vehicle is moving towards the destination (e.g. the traffic situation may affect transit times).
We want to update the route graph based on edge costs without rebuilding it completely. Rather, as a set of changes arrives, we want to determine which nodes are affected by it and set their cost.
For now, we are neglecting the fact that the cost of an edge may change again before we reach it—the route is always based on current edge costs.

Is there a standard algorithm for this kind of partial recalculation?


texts: The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

texts:
One statement of Rice's theorem is given on page 35 of "Computational Complexity: a Modern Approach" (Arora-Barak):

A partial function from $\{0,1\}^*$ to $\{0,1\}^*$ is a function that is not necessarily defined on all its inputs. We say that a TM $M$ computes a partial function $f$ if for every $x$ on which $f$ is defined, $M(x) = f(x)$ and for every $x$ on which $f$ is not defined $M$ goes into an infinite loop when executed on input $x$. If $S$ is a set of partial functions, we define $f_S$ to be the boolean function that on input $\alpha$ outputs 1 iff $M_\alpha$ computes a partial function in $S$. Rice's theorem says that for every nontrivial $S$, the function $f_S$ is not computable.

Wikipedia states that languages of bounded time turing machines are EXPTIME complete. I expect this language looks something like $\{(\alpha,x,n) : M_\alpha $ accepts $x$ in less than $n$ steps$\}$. So let $M$ be some DTM that decides this bounded language in exponential time. It seems like this DTM is deciding some property for ALL turing machines, so my intuition tells me that Rice's theorem precludes such a decision. But obviously $M$ computes a total function.

What am I missing about the relation between this language and Rice's theorem?


texts: What is responsible for the 1-1 correspondence between characters and binary?

texts: Could someone explain to me what component(s) are responsible for translating binary into ASCII/UNICODE? For example, is it an assembly program that sets up a 1-1 correspondence between characters and their binary equivalents, which is then loaded into ROM during manufacturing?


texts: What is the representation of a tree in a heap called?

texts:
Often a binary tree is represented in a particular implicit data structure packed into an array whereby the left and right children of t[x] are found at t[2x+1] and t[2x+2]. This is commonly done in implementations of heaps, for example.

Does this representation have a canonical name? I am somewhat fed up of referring to it as “a representation of a tree in an array like in a heap”.


texts: The relationship between MDP's end component and its induced MC recurrent class

texts: Let's assume that I have an MDP $M$ which has a number of maximal end components. I also have a random policy (scheduler) $\pi$ that can convert the MDP $M$ into a Markov chain $m$. Can I argue that all recurrent classes of MC $m$ has states that belong to MDP $M$'s maximal end components?


texts:
I am trying to understand ambiguous grammar in programming languages. I was given this ruleset and told it was ambiguous. If my understanding is correct, this means that it is possible to create the same sentence using different parse trees. After looking at it for a while, I can't find the sentence/parse trees that show the ambiguity.

s ::= a

a ::= a a | A | B | C


texts:
I have this question about if the decidability of an regular expression and would appreciate if someone can check my answer and see if it makes sense, and if not, what is missing.

  Be A = {(R)|R it is a regular expression that describes a language containing at least a w string that has 111 as a substring (that it is, w=x111y to some x and some y)}. Show that A it is decidible

Answer: Create a turing machine P, this machine receives a pair where R is the regular expression in question and W is the set of all the strings of the form x111y. P converts R into a NFA called NFAR. It sends the pair to a TM N that acts as a subrotine of it. N will convert NFAR into a DFA called DFAR. Then inside this machine N, there is a turing machine M inside it, also acting as a subrotine. It sends the pair to M. When M receives its input, it will first determines whether it properly represents a DFA DFAR an a set of strings W. If not, it will reject, and as a result, so will N and then P. Otherwise, It will start to simulate DFAR over the first string w(i) of W (where i=0,1,2... n° last input string). If DFAR accepts, M halts in the accept state, and so will N and then P. Otherwise M will continue to loop through all the strings of W. If it reaches the last w(i) and it is not accepted, M will halt in the refect state and so will N and then P.

My fear is that the number of strings to be tested is infinite, so M could enter in a loop?


texts: traverse direct graph with multiplicative edges

texts:
I have a graph like this one:

Each step from one node to another is a multiplication.

So for instance given the entry node TE and an entry value of 1.

TE = 1

TB = 1/10010

GB = 999/(10010*1000)

GE = (19990*999)/(10010*1000)

and so on.

I want to find the best path from TE to TE to return the highest value.

In this case is

TE TB GB GE TE = 1,993010988

I tried to apply Dijkstra's SPF but it doesn't work because each step can
increment or decrement so it's not monotone

neither Bellman–Ford algorithm is applicable here because the graph contains negative cycle. (e.g. TE TB TE).

Anyone has some clue if this problem has a solution ?


texts: Definitional equality of two propositions about propositional equality

texts:
Martin Hofmann states in Extensional Concepts in Intensional Type Theory (§1.1 p.3) that:

  It is important that definition equality is pervasive so if M and N are definitionally equal then P(M) is definitionally equal to P(N) whatever P is. In particular the proposition stating that M is propositionally equal to N is definitionally equal to the proposition that M is propositionally equal to itself.

What I don't get is how a proposition about equality of M and N propositionally can be definitionally equal to the proposition about propositional equality of M and M ?


texts: How to rank search results of short string lists

texts:
I have a tree of foods, which I'd like to search to find relevant nodes. What's the best way to rank the results?

Here's an example sub-set after a search for "apple":

|-- apple pie
|-+ apples
| |-- cooking
| |-+ eating
|   |-- average
|   |-- Granny Smith
|   |-- Golden Delicious
|-- pork and apple casserole

Currently, I'm ranking based on which results come earliest in the full name of each leaf, so a result set would look like:

0 Apple pie
0 Apples, cooking
0 Apples, eating, average
0 Apples, eating, Granny Smith
0 Apples, eating, Golden Delicious
2 Pork and apple casserole

Where the rank is the index of the first token match, lower the rank the better.

I'd like to aggregate the matches, so that I don't display the full sub-tree on the initial search, for example:

Apples... (4)
Apple pie
Pork and apple casserole

The obvious way to rank these is to count the number of matching leaves, then the higher the rank, the better the match.

But, I'm not sure how to combine these rankings, since one is larger-is-better and one is smaller-is-better. Are there standard ways to combine rankings like this? (I'm not sure what to search for, so Google is giving me results about search engine optimisation, and searching web pages, which doesn't seem to apply.)


texts: Can a lambda expression be beta-equal to beta-normal forms?

texts: Given a Lambda Expression Term T can it be beta-equal to two different  Lambda Terms T1 and T2, both T1 and T2 are in beta-normal form?


texts: Finding The Inverse of The Modulo Operation

texts:
I created an algorithm to convert a hexadecimal digit into an alphanumeric string, but now I want to create the inverse of this algorithm. The algorithm, in short, is as follows:

  hexadecimal digit % length of alphanumeric character array = index in alphanumeric character array

For example, the algorithm takes hex digit 4e (78 in decimal), mods it with the size of an alphanumeric character array (size: 62), and returns decimal number 16, which is a G. The alphanumeric character array in this example is structured like the following: (0-9, A-Z, a-z).

  In short this example is written as: (4e)78 % 62 = 16(G)

The inverse of this algorithm is what I hope to achieve and from various tests, it seems multiple results can occur, but my ultimate goal is to end up with a reversible algorithm, where, for example, hexadecimal digit 4e gets converted to letter G then back again to 4e when put through the inverse algorithm. From the example, I developed a possible description of the inverse algorithm:

  Suppose we have a modular equation. Let x be the dividend, y be the divisor, and r be the remainder. r and y are given where r=16 and y=62. Find an x such that x % y = r or x % 62 = 16.

The solution that I tried: Bruteforce the dividend

The dividend will never be out of the closed interval [0, 255] since a pair of hexadecimal numbers can have a maximum value of ff, which is 255 in decimal. Thus, if we test x's against the modular equation until we get an equal remainder, we can derive the dividend.

However, this solution will result in multiple possible x values due to the modulo operation causing a wrap-around effect in the alphanumeric array, which means multiple values can cause the equation to hold true. In the case of the provided example, the proposed solution results in the following dividends: 16, 78, 140, and 202. The second dividend is the correct one and the one that results in the algorithms being reversible. However, the issue is finding it, since the correct one isn't directly known at the time of running the inverse algorithm.

Any help in devising either a solution to my proposed method or a different one would be greatly appreciated. Thanks.


texts: What are the tradeoffs between implenting dataframes as a series of columns vs a series of tuples

texts:
I was reading the documentation for Julia's Dataframe package, and the package implements Dataframe by a series of a columns each of a single type. From reading the docs, it looks like that's how R implements Dataframes as well. Is there any reason this is a better way than having a Dataframe being a collection of tuples with elements of different types? The later seems more natural to me.

What are the trade-offs or reasons one would implement Dataframes as a list of columns vs a list of rows?


texts: Since planar TSP with n nodes is NP-hard, we cannot simply find an optimal solution with n-1 nodes and then insert the remaining node at one of the solution's edges to find the optimal solution of the original TSP problem. So, is there a planar graph with an optimal solution, such that when we add a certain extra node, the new graph's optimal solution has none of the edges of the previous optimal solution?


texts: Changing AVL's balance factor to some other $s>2 \in \mathbb{N}$

texts:
Given we change the rule to:

  $-s \ \ \leq$ height(left-subtree) - height(right-subtree) $\leq \ \ s$

I was wandering whether it's possible and how would it affect the trees' height, would it still be logarithmic?

Would the exact same balancing techniques work? (if we took those methods from a normal AVL and try to convert our modified AVL to a normal AVL running from down to top or to down).

I've tired drawing some schematics in order to find out what would be the minimal number of nodes $m$ for some tree $T$ with height $h$ like we did with a regular AVL but I had a real hard time formalizing it.


texts: Finding certain elements when only able to ask in chunks

texts:
I have a set of $n$ elements. Of these elements $b\ll n$ are blue and $r=n-b$ are red. I want to find all blue elements.
My only way to discriminate between red and blue objects is by asking a blackbox that takes a fixed number $k$ of elements (with $n \gt k \gg 1$) and returns an approximation of how many of those elements are blue. The approximation is such that the returned number $\hat N_b = N_b + u$ is the real number of blue elements $N_b$ combined with a Gaussian noise $u$ that has a Variance of $\text{Var}(u)\approx 1$ and an expected value of $E(u)=0$. $k$ is big enough that in a random sample the expected number of blue elements $E(N_b)$ greatly exceeds the variance of the noise.
Is there an efficient algorithm to determine (to a certain probability) which elements are blue?


texts: How did MacLisp's garbage collector "run in the register set"?

texts:
Olin Shivers, ‘History of T’:

  Maclisp on the [PDP]-10 had used a mark&sweep GC (one version of which famously "ran in the register set," though that is another story)

This implies, in my interpretation, that the garbage collector used no storage other than the registers of the machine. Is my understanding of this correct, and if so, how did it achieve this efficiently? Was a paper ever published on its implementation?


texts: ML Algorithm for getting top pick in each sample

texts:
I have a dataset of streets - and each street contains several houses.
street_id | house_id | number of calls | number of people living | etc...
1         | 1        | 10              | 5
1         | 2        | 3               | 1
2         | 3        | 4               | 2
2         | 4        | 15              | 19

My goal is to find for each street, the most popular house.
I have GT - streets with several houses, and for each street, which house was the most popular house.
For the data example above - the results should be (street 1 -> house 1, street 2 -> house 4) because houses #1, #4 are the most popular in their street.
Popular will be determined with classification algorithm - we have much more features than the 2 above (they are just for example). That's why we have the GT for - so our algorithm can learn what popular is.

We can find the most popular street using features about each house -

number of calls made from house
number of people living in house
etc

But we don't need to find all of the popular houses from all of the houses - we need for each street, to find the most popular house.
Do you know how can I solve this task?
I've thought about regular classification, but that would results giving all of the popular houses, and not one for each street.
Thanks in advance!


texts: How to get a base-3 representation of an integer using a stack?

texts: Assuming that a stack data structure is available, how can this data structure be used to compute a representation of an integer in base three? For example, the algorithm for printBase3 would return 12020 on input 141.


texts:
I found a pseudo algorithm which describes bit blasting: click (page 156,157). I am trying to implement it in C, but I don't understand it yet completely. Let's make an example:
Assume our bit-vectors have only a length of 2 bits (for simplicity) and they are unsigned and out bit-vector formula looks as follows: $\phi = x \,\,\,\wedge\,\,\, y\mid 2 = z \,\,\,\wedge\,\,\, 1 < 3$.
Let's describe Boolean variables with $b_0, b_1,...$ ($x,y$ and $z$ are bit vectors).
The set of atoms would be $At(\phi) = \{ x,\,\,\, y\mid2=z,\,\,\, 1<3 \}$ and therefore the initially $\beta = e(\phi) = b_0 \,\,\,\wedge\,\,\, b_1 \,\,\,\wedge\,\,\, b_2$.
The set of terms would be $T(\phi) = \{ x,\,\,\, y, \,\,\, 2,\,\,\, z,\,\,\ 1,\,\,\,3 \}$.
Algorithm
Line 2: $\beta$ is already set.
Line 3-5: We set the $t \in T(\phi)$ to Boolean variables, hence $x \rightarrow b_3, b_4\,$ - (because we said our bit-vectors only have a length of 2 bits), the same with $y$ and $z$, but what happens with constants? I would guess: $2 \rightarrow 1,0$ or more precise $2 \rightarrow b_7=1, \, b_8=0$.
So after line 5, our $T(\phi) = \{ b_3, b_4,..., b_{14}\}$.
Then I stuck, how does it go on? And how would the equisatisfiable Boolean formula $\beta$ look like after the algorithm? Other references to other algorithms would be also nice.


texts: Algorithm analysis question in growth of functions

texts:
How would I solve the following.

An algorithm that is $O(n^2)$ takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500?

Can anyone help me answer dis.


texts: Message Passing Algorithm and Implementation

texts:
I have a tree T with N nodes (Min-Span-Tree of a graph), and what I am  gonna do is to calculate for each node Vi, the number of nodes reachable from each of it's edges (Vi,Vj). So after running the algorithm, every node of degree d will have d values each on a single edge shows the number of noded reachable using that specific edge.

Here is a toy example:

I can remember an approach to solve the problem, but I cannot exactly remember the name of it so I can find it on the internet. Here is a description of the approach:

1- Pick a random node
2- Treat it as root of the tree (structure the tree)
3- Start from leaves and send 1 to the parents.
4- for each interleaving node (non-leaf), if it has received the message from all the childs, send the summation plus 1 to the parent.
5- Do the step 4 recursively until you reach the root.
6- For root set x = 1 + (sum of messages from all the childs)
7- subtract the incoming value from x and send the resulting value back to childs.
8- send down the value recursively while subtracting, until you reach the leaves.

Here are three steps of the algorithm for the toy example:

and then send back info until you reach childs:

I tought the name of this algorithm is message passing. But I found many other message passing concepts but this one through my search on the web.

So what I am exactly looking for, is the name of the algorithm, the complexity, and after all if available a python package for this.

For the complexity I beleive it must be the same as the number of edges E, which is number of N-1 so this should be O(N).


texts: Determine Intersection given only a hyperrectangle and a point-contained-in-shape-Predicate

texts:
Given only an n-dimensional hyperrectangle by its corner-point-values and an n-dimensional Predicate that corresponds to an arbitrary shape and tests whether a point is contained in said shape,

is it possible to calculate whether the box intersects the shape?


texts: Can Depth-first search (DFS) with alphabetical traversal of neighbors be run in O(|V|+|E|) time?

texts:
I feel like the answer is no but I'm not sure. I think it's commonly accepted that DFS runs in $O(|V| + |E|)$ time. I've read a few explanations and they all make sense if the neighbour traversal for any given vertex can be done in arbitrary order.

But I've noticed a commonly suggested DFS behavior is to traverse the neighbors in alphabetical order (i.e. CLRS exercise 22.3-2), and I don't see how this can be done in $O(|V|+|E|)$ time. This became evident to me when actually trying to implement this in runnable code.

I see two ways to do it:

I can keep the list of vertices and each vertex's adjacency list sorted as I'm constructing the graph. However this means $O(V)$ insertion time for each new vertex in the graph, which means a total of $O(|V|^2)$ insertion time over $|V|$ nodes. And $O(|E'|)$ insertion time for a new edge where $|E'|$ is the number of neighbours in a particular vertex's adjacency list, meaning $O(|E'|^2)$ time to construct the adjacency list for any given vertex.

OR

Construct the graph and insert the vertices and adjacency elements in arbitrary order, but then sort them before running DFS. But comparison-based sorts are $\Omega(n\log n)$ so I'd have $O(|V|\log|V|)$ sort time for the list of vertices, and $O(|E'|\log|E'|)$ for each adjacency list.

In either case it doesn't seem like the runtime is $O(|V| + |E|)$ any more. Can someone confirm or refute? Thanks.


texts: Shortest path algorithm where the path can travel through at most 2 vertices in X ⊂ V

texts:
I am trying to model a problem to enable me to use Dijkstra's Shortest Path algorithm. Given are a set of vertices V, and a set of vertices X ⊂ V.
Between these vertices are given a set of edges where:

edge(u,v) with u ∈ V \ X being weighted > 0
edge (u,v) where u ∈ X being weighted = 0
other edge combinations (i.e. u,v ∈ V and u,v ∈ V \ X) are allowed, but follow the same rules as above

At most two vertices ∈ X are allowed to be visited in the path.
How can this be modeled as a shortest path algorithm problem? I've seen solutions for at most one vertices ∈ X are allowed by splitting the graph into two copies but that doesn't quite hit my requirements.
Any help much appreciated!


texts: Proving an algorithm exists to find independent set from a graph given an oracle

texts:
This is the problem that I have been given:

Consider the Independent-Set problem, in which the input is an undirected graph $G = (V,E)$ and a
parameter $k$, and the goal is to determine if $G$ has an independent set of size $k$. Suppose we have an
oracle $O$ for solving this decision version of independent set (think of it as a library function that takes
input a graph $G$ and $k$ and answers YES/NO).
Prove that there exists an algorithm that can find an independent set of size $k$, if one exists, using a
polynomial number of calls to the oracle $O$, and possibly a polynomial amount of computation of its
own.

My first question is: Is there any way to prove that an algorithm exists without just giving a specific algorithm?

I'm sort of taking a crash course in computer science, so this is not my strongest subject. Any hints as to what direction to take this would be appreciated!


texts: Sliding Window Protocol, waiting Time calculation

texts:
With regard to this explanation in finding Round Trip Time I tried attempting the following question

Question

Frames of $1000$ bits are sent over a $10^6$bps duplex link between two hosts. The propagation time is $25$ ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

Let I be the minimum number of bits ($I$) that will be required to represent the sequence numbers distinctly assuming that no time gap needs to be given between transmission of two frames.

Suppose that the sliding window protocol is used with the sender window size of $2^l$
, where I is the numbers of bits as mentioned earlier and acknowledgements are always piggy backed. After sending $2^I$ frames, what is the minimum time the sender will have to wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time.)

  NB :  $I$ is found to be 5 bits from the link mentioned above

My Approach

Propogation TIme (given) = 25ms

Bandwidth (given)= $10^6$ bps

So, to fully utilize the channel, we must send 106 bits into the channel in a second, which will be 1000 frames per second as each frame is 1000 bits

I = 5, $\Rightarrow$ $2^I$ = 32 frames are sent.

Transmission time (for a frame of size 1000 bits) = $\frac{1000}{106} = 1$ ms.
So, transmission time for $32$ frames = $32$ ms.

$R_{TT}$ (Round Trip Time ) as calculate in the above link is 25ms. Hence the Waiting time would be $32-25=7ms$

But actual answer is given as $20$ms

What is the correct approach to this question ? please explain in detail how $R_{TT}$ should be calculated


texts: Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time?

texts:
This question came up while a group of students at my school were studying for our qualifying exams.  The question on an old exam was,

  Consider the following six classes of languages: Context free (CFL), Regular(REG), P, NP, Recursive(R), and Recursively enumerable(RE). (1) indicate the relationships between these six classes e.g., by drawing a Venn diagram. (2) name the minimum type of machine needed to recognize languages in the different classes.

OK, so we know that REG$\subseteq$CFL, either P$\subseteq$NP or P=NP, NP=RE, and P=R.

We also know that the minimum machine type for each language class is REG:DFA, CFL:PDA, P/R:DTM, NP/RE:might be NTM.

We know that a Turing machine is more powerful than a pushdown automata, but we can't find anything that actually proves that all CFLs can be recognized in polynomial time, or think of a way to prove it ourselves.  When I asked the teacher who originally wrote the problem about this, he didn't have a ready answer.


texts: Why do we discard the constant 1 in proving that $2^{n+1} = O(2^n)$

texts:
In this post
someone said:

  $n + 1$ is approximately equal to 1 for $2^{n+1} = O(2^n)$.

I don't understand this point. For example, in this example:

$$ n + 1 \leq c \cdot n $$

for some $c$ and some $n \geq n_0$, the right-hand side will always be at least the left-hand side.

But here: $$ 2^{n+1} =O(2^n)$$

the left-hand side will always exceed the right-hand side.


texts: Can all packing/covering problems be rephrased as set packing/covering problems?

texts:
Can all packing problems be rephrased as set packing problems?

Can all covering problems be rephrased as set covering problems?

In other words, I was wondering if set packing/covering problems are the most general forms of packing/covering problems?


texts: Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$

texts:
I am trying to find a context sensitive grammar for the type-1 language

$L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$

I can construct the first part with

\begin{align*}
S &\to aSbB \mid B \mid \epsilon\\
B &\to bB \mid \epsilon\\
\end{align*}

but how do I continue from there? I tried

\begin{align*}
S &\to aSbBcC \mid B \mid \epsilon\\
B &\to bBcC \mid \epsilon\\
CB &\to BC \\
C &\to cC
\end{align*}
but this does not seem to work e.g. $S \to aSbBC \to aaSbBCbBC \to aabBCbBC$


texts: Draw DFA that accepts concatenated binary string with condition

texts:
Let $\Sigma = \{0,1\}$, with $w \in \Sigma^* $ and $value(w)$ the not negative integer value of $w$. $w$ is seen as binary string, with its first index being the least significant bit:

$$value(w_1 w_2 ... w_n) =  \Sigma_{i=i}^n 2^{i-1} w_i$$

The languages is defined as:
$$L = \{a_1b_1a_2b_2 ... a_nb_n \ \in \ \Sigma^* \ \vert \ value(a_1a_2 ... a_n) = 3 \ \cdot \ value(b_1b_2 ... b_n)\}$$

The task is to draw the accepting DFA. I frankly have no idea on how to approach this question. Can someone give me a hint, not the full answer please?


texts: Finding two store typings that make the same store valid (lambda-calculus with references)

texts:
Problem 13.5.2 of Pierce's TAPL's book (page 167) asks:

  Can you find a context $\Gamma$, a store $\mu$ and two different store typings $\Sigma_1,\Sigma_2$ such that both $\Gamma | \Sigma_1 \vdash \mu$ and $\Gamma | \Sigma_2 \vdash \mu$?

I'm not getting the proposed solution:

But how can this be the case? I mean should not $l$ be of a reference type $Ref(T_1)? $ How can it be of function type?


texts:
I have been using Harwell Boeing format, also known as Compressed Column Strorage (CCS) in order to store Sparse Matrices.

Could you please suggest me some other way to store/represent sparse matrices?


texts: Clustering data for compression with PCA

texts:
If I have datapoints in a high dimensional space and want to find a (linear) subspace onto which a data-set projects well, I can use PCA and then discard less important dimensions of the new basis to get compressed datapoints. However, often the data can be projected onto lower dimensional spaces with much smaller error if one first separates them into a couple of classes and then performs PCA for each class individually. What kind of algorithm can find such clusters? Just clustering based on distance in the high dimensional space won't be very useful:
Example:

If I'd just cluster first based on distance in the high-dimensional space, I would arrive at the bad clustering. There are 5 clusters and the green and red clusters don't project very well onto a 2D subspace.
As a human looking at the data, I see however that if I separate the data as indicated, red and blue will project very well onto a plane each and green will project very well onto a line, so I can run PCA for each group individually and store the red data points with 2 values each and the gree ones with 1 value each (plus a 2bit index on each datapoint to label which group it belongs to) and get a very low error upon uncompressing.
How can I automate this clustering based on how well it will project onto as low-imensional subspaces as possible?
Something like minimize E = SumOverClusters(SumOverPoints(SquaredDist(projected_point, original_point)) * (number_dims_projected / number_dims_original)) + C * number_of_clusters
What technique is well suited to do that?
(edit: while the example shows a 3d space, I'm more interested in doing that in about 64dimensional spaces)


texts: Is there an algorithm for checking if a string is a catenation of palindromes?

texts:
Is there a linear-time algorithm to check that a sequence of characters is a concatenation of palindromes? The only thing that comes to my mind is the naive solution:

1. k = 1
2. Split string into k substrings (all possibilities) and check
3. k++
4. repeat

Note: the answer is trivially yes if length 1-strings are defined to be palindromes. Let's assume that this is not the case.


texts: How do you solve a recurrence relation with multiple subproblems of different sizes?

texts:
For instance, consider the following recurrence relation.

  T(n) = T(n/2) + T(n/3) + T(n/4) + n

Would you use the substitution method for this?


texts:
I actually have to prove the following :

$\mathbf{NL} \subseteq \mathbf{NC_2}$

I have the following approach :

I will prove that $\mathbf{PATH} = \{〈D, s, t〉 | \text{D is a directed graph with a path from vertex s to t}\} \in \mathbf{NC_2}$.
I will show that $\mathbf{NC_2}$ is closed under log-space reductions i.e:

$$(1): B \in \mathbf{NC_2} \hbox{ and } A \le_l B \Longrightarrow A \in \mathbf{NC_2}$$

where $\le_l$ is the logspace reduction defined as

$$A \le_l B :\Longleftrightarrow (\exists M \hbox{ TM}, \forall x)[x \in A \Longleftrightarrow M(x) \in B]$$

($M$ is a TM which runs in logarithmic space).

Since $\mathbf{PATH}$ is an $\mathbf{NL}$-complete problem the proof will be done.

Proving The 1st part was easy, i am stuck at the second part and have no idea how to proceed.

Any help?


texts: Show that the language of strings not in the union of two regular languages is regular

texts:
Given languages $L_1,L_2$, defines $X(L_1,L_2)$ by

$\qquad X(L_1,L_2) = \{w \mid w \not\in L_1 \cup L_2 \}$

If $L_1$ and $L_2$ are regular, how can we show that $X(L_1,L2)$ is also regular?


texts: Query regarding the structure of Graph over All (known/unknown) NPC Problems?

texts:
Let us consider the set of all NPComplete problems. Since every problem in the set is Reducible to/from at least one known NPComplete problem, lets create a directed Graph with the following conventions:

If a problem B is Reducible from Problem A, create an edge from A to B. We assume an oracle who knows all possible reductions who creates the edges.

Here are a few questions regarding the Graph.

Q1. Is the graph strongly connected (i.e. every problem in the Graph is reachable from or reducible from every other problem for every instance?

Guess: I presume the answer is yes.

Q2. For any two problems (say A, B), no matter what the distance b/w them is, there is guaranteed at most Polynomial Blowup in problem size when we reduce, from A to B?

Guess: Unsure. For any problem P, if we reduce from one of its neighboring problem, there is polynomial increase or decrease in space. But, not sure if it holds if the problems are arbitrarily large distance apart. The definition of NPC, needs one single reduction in Polynomial time, but space analogue of reduction for All NPC Problem pairs seems out of reach.


texts: Getting speed difference between signal comparison using Dynamic Time Warping

texts:
I understand that Dynamic Time Warping is an algorithm to find a matching between two signals with different length and speed

But is there a possible way to find the speed difference between the two signals being compared?

To clarify my question.
I am working on a project to find similarity between two motions.
The data being compared is in the form of Quaternion. By using DTW I was able to find the similarity/ dis-similarity between these motion signals, However I would like to know is there a way to find if one motion signal is slower/faster than the other.
Ex: both motions are actually similar, but one of the motion is slower than the other


texts: "Any problem whose domain is finite is always Decidable", is true or false?

texts:
Question no:$1$

  "Any problem whose domain is finite is always Decidable"

lets take a TM,$M$ and finite domain of problem i.e. finite set of strings for eg.  {$a,abaa,bba$}, Now the problem "whether $M$ accepts these set of strings or not is decidable or not?"

What I think is, this is Undecidable problem because, if $M$ loops forever any of these string then we not determine whether turing machine accept it or not.so according to this logic above statement is false.

Question no:$2$

Does a single instance of "turing machine's halting problem" is decidable?
As I given above example, I think this is also Undecidable.


texts: Single-source shortest path problem with diameter

texts:
Given that a graph G has only positive integer weights and its diameter D which is the greatest of the shortest paths among all pairs of vertices in G. For a single-source shortest path problem and design an algorithm runs in O(V+E+D) time.

As we know, in a single-source shortest path problem, we could use the Dijkstra Algorithm and it's running time is $O((V+E)log V)$ using a min-heap. So we can explore the minimum known distance. But the bottleneck is to insert and delete a min-heap structure.
With the information, how to reduce the running time to $O(V+E+D)$?
**Update **
From https://stackoverflow.com/questions/66570124/single-source-shortest-path-in-a-graph-with-positive-weights-and-diameter-d

We continually increment i until we find some i such that Arr[i] is not empty.

This tells where does the $O(D)$ come from. But what I don't understand is why inserting and deleting take a constant amount of time if min-heap is still using. Or is it another data structure? Many thanks


texts: How hard is finding the discrete logarithm?

texts:
The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$.

I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what approaches (i.e. algorithms) are the best for accomplishing this task.

The wikipedia link above doesn't really give very concrete runtimes.  I'm hoping for something more like what the best known methods are for finding such.


texts:
Here is the scenario: There are three chefs(A- main chef, B and C- assistant) working together to prepare a diner set. The sequence of the event is as following.

Start: The three chefs enter the kitchen together with the ingredients.
Preparation: They prepare the utensils and the ingredients(e.g cleaning and cutting).
Appetizer is ready to be served.
Main dish is ready to be served
Dessert is ready to be served.
End: All the chefs leave the kitchen together.

My question: What machine-learning method can I use to predict the event at any point of time?
Let say I can use sensors or image/video processing to collect data, what kind of data should I gather for the suggested method?

Edit:
Sorry for the unclear question. What I have in mind now is, I put some sensors(or camera) to detect the start of the event with a timestamp at: the entrance, the washing corner, the cutting corner, the appetizer corner, the cooking stove(for main dish), the oven(for dessert), and the serving counter. So I have these sensor events:

Start time (chefs enter the kitchen)
Cleaning start time (ingredients preparation)
Cutting start time (ingredients preparation)
Appetizer start time
Stove start time (for main dish)
Oven start time (for dessert)
Serving counter (the time when one of the menu is ready to be served)
End time (chefs leave the kitchen)

I collect the dataset from 20 cooking cases. Applying learning algorithm to do event prediction. For example, there's a cooking started at 8:15am, cutting started at 8:45am, based on the learned data, I want to predict when will the appetizer be ready.


texts: Show that the tree resulting from BFS is a spanning tree?

texts: Given that $G$ is some connected and undirected graph, and I want to run BFS on it from some starting vertex. How can I show that $T = \{ \{\text{predecessor}[u], u\} \mid u \text{ is a vertex}\}$ is a spanning tree of $G$?


texts: How strong "Consistent Guessing Problem" is?

texts:
I saw "Rosser’s Theorem via Turing machines" at:

https://www.scottaaronson.com/blog/?p=710

The modified halting problem (Consistent Guessing Problem) CGP is used in the proof:

CGP(M) - accepts if M accepts on a blank tape
CGP(M) - rejects if M rejects on a blank tape
CGP(M) - either accepting or rejecting if M runs forever on a blank tape

It's shown in the proof TM which solves CGP doesn't exist.
Consider I have CGP as oraculum. Does it allow me to solve halting problem?


texts: Logic gate which checks if the input is a negative number and changes its output based on that

texts:
I need to create a HDL which will use logic gates to demonstrate if something is a negative number in two's complement. The input is 8 bits, while the output is 1 bit, and if the input is a negative number then the output should be true, and in any other case, the output should be false.

I've noticed that all the negative numbers in two's complement start with a 1 in their binary notation, i.e the number -8 is written as 1000 in binary, -7 as 1001 and so on until 0, which is when it switches to 0000, 1 being 0001 and so on until +7.

I originally had the idea of using a Not gate for this, but i'm not entirely sure how it would work out. I tried something like:

Not(in=in[1], out=in[2]);
Not(in=in[2], out=in[3]);

etc but it didn't work. I also thought of using an Or gate, as if either of the inputs are true (negative number) then the output would also be true to signify a negative number, but if both of the inputs are false (not negative) then the output would also be false.

Any help?


texts: Adding a character in the middle (rolling hash)

texts:
Is there a way to support adding characters in the middle and update the hash in O(1) ?
All I have is the hash of ABBDE and I want to get the hash of ABBCDE.


texts: What is the complexity of deciding if the intersection of a regular language and a context free language is empty?

texts:
Let's say we have a context free language, the CFG that produces it.

And then we have a DFA for a regular language.

If the intersection is empty is decidable, but how and how efficiently?

And if you could be so kind, please explain the best known algorithm as simple as you can?


texts: I'm currently preparing a presentation about LTL and a book says that the language $L = (a(a \cup b))^\omega$ cannot be described by any LTL (or FO) formula which is understandable but how does the corresponding Büchi automaton $\mathcal{A}$ look like with $L(\mathcal{A}) = L$?


texts:
Problem statement: Produce an NFA that accepts the strings 0* and 1*. So 000 and 11 would be accepted, while 101 would not be.

I'm a bit concerned about my idea because not all combinations of the alphabet are producible in it. Is this NFA legitimate?

My idea (updated to include the empty string):


texts: Time complexity of the fast exponentiation method

texts:
I am trying to analyse the time complexity of the fast exponentiation method,
which is given as

$$x^n=
\begin{cases}
 x^\frac{n}{2}.x^\frac{n}{2}       &\text{if n is even}\newline
x.x^{n-1}   &\text{if n is odd} \newline
1 &\text{if n=0}
\end{cases}
$$

I tried to write it as,
$$
T(n)=\begin{cases}
T(\frac{n}{2}).T(\frac{n}{2}) &\text{if n is even}\newline
T(n-1) &\text{if n is odd}\newline
1 &\text{if n=0}
\end{cases}
$$

I think I am lacking somewhere and so not able write correct recurrence relation here.

Need help to do so.


texts: Complexity of multiplying two integers of size $n$ and $m$

texts:
The multiplication of two integers of size $n$ can be done in time $O(n \cdot \log n \cdot \log\log n)$ using FFT method.

If the two integers have different sizes $n$ and $m$, does a smaller upper bound using $n$ and $m$ exists ?


texts: NP Problem definition – verifiable on DFA vs. solvable on NFA

texts:
So in complexity theory, I've run across different definitions for NP problems --

Decision problems where a solution can be verified by a DFA in polynomial time
Decision problems where a solution can be found by an NFA in polynomial time

Is there one of the above that is generally more accepted as the "go-to" definition in the academic community? If so, is there a reason? (If these "definitions" are incorrect – please feel free to correct me).

To me, the second definition makes more sense intuitively.


texts: Mcculloch and Pitts Neurons: Is there errata in this article?

texts:
The paper A LOGICAL CALCULUS OF THE IDEAS IMMANENT IN NERVOUS ACTIVITY has the following description of neurons, which I question if there is errata or perhaps I need more information to understand this.

Looking at the picture below (b) is described as an OR gate.  I'm confused because with either threshold being met on the $N_1$ or $N_2$ neuron, with thresholds 1 and 2, there are not enough inputs to reach the threshold of 3 for $N_3$.  So how is this an OR gate?

(c) makes sense because the sum of the input to $N_3$ is 3 when both $N_1$ and $N_2$ are at their thresholds.

Any guidance appreciated.


texts: What is meant by a single-threaded kernel?

texts:
I was looking at this course but I cannot seem to understand what is meant by the term "single-threaded kernel".
Does it mean that:

only a single kernel thread is made available by the OS?
only a single kernel thread can be executed at one time?

or is there some other interpretation?


texts:
I am developing the algorithm reported in this article:

Lest square conformal mapping

Here is presented an algorithm to flat a 3d mesh on the parametric space, but i don't understand the segmentation step.

Does anyone know an alternative segmentation approach simpler than the algorithm presented in that article?

In other word, do you know a simple and efficient mesh segmentation algorithm?

The requirements are:

charts boundaries should be positioned in such a way that most of the discontinuities between the charts will be located in zones where they will not cause texture artifacts,
boundary curves corresponding to high curvature zones of the model.

Thank you for your help in advance.


texts: Correctness of a zigzag algorithm to find the most similar vector in a bounded integer lattice

texts:
I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm.

Given a real vector $u \in \mathbb{R}^n$, the most similar vector problem is to find a discrete vector $v$ from a bounded integer lattice $L \in \mathbb{Z}^n \cap [-10,10]^n$ that maximizes the cosine similarity between $u$ and $v$. That is,

$$v \in \text{argmax}_{w \in L} \frac{u.w}{\|u\|\|w\|}$$

In an earlier post on MathOverflow, someone proposed solving the most similar vector problem by "zig-zagging" across the lattice. Informally, this is a greedy algorithm that generates a sequence of lattice vectors $w^k$ by starting from the origin and taking steps of length one in the direction of $u$. On the $k^\text{th}$ iteration, the algorithm chooses $w^{k+1}$ as the most similar lattice vector that one unit away from $w^k$ in some dimension. The algorithm terminates in $K$ iterations after we hit the boundary of the lattice in each dimension.

Formally, the "zig-zagging" algorithm can be stated as follows:

  INITIALIZATION
  $$\begin{align}
w^0 &\longleftarrow (0,\ldots,0) &\text{(starting point)} \\
d &\longleftarrow \text{sign}(u) \in \{-1,0,1\}^n &\text{(step direction)} \\
\mathcal{J} &\longleftarrow \big\{1,\ldots,n ~\big|~ d_j \neq 0 \big\} &\text{(set of dimensions in which steps can be taken)}
\end{align}$$

  ALGORITHM

  $\text{while }  \mathcal{J} \neq \emptyset$

  $$\begin{align}
j^* &\longleftarrow \text{argmax}_{j \in \mathcal{J}} \frac{u \cdot(w^k + d \cdot e_j)}{\|u\|\|w^k + d \cdot e_j\|} & \text{(step in dimension $j$ that yields $w^{k+1}$ most similar to $u$)} \\
w^{k+1} &\longleftarrow w^k + d \cdot e_{j^*} \\
\mathcal{J} &\longleftarrow \mathcal{J} \setminus \big\{1,\ldots,n ~\big|~ |w_j^{k+1}|=10
 \big\} & \text{(remove coordinates at boundary from consideration)} \\
k & \longleftarrow k + 1
\end{align}$$

Here $e_j$ is a unit vector with 1 in the $j^\text{th}$ coordinate and 0 elsewhere.

Once the algorithm terminates, we can use the sequence of generated lattice points $w^1,\ldots,w^K$ to find the most similar vector, $v$ as:

$$v \in \text{argmax}_{k=1,\ldots,K} \frac{u.w^k}{\|u\|\|w^k\|}$$

My question is as follows: Does the zig-zagging algorithm described above produce the most similar vector? If so, how can I prove it? If not, is there a counter example?


texts:
I know this is a simple question but can someone show me how
$(\lambda y. \lambda x. \lambda y.y) (\lambda x. \lambda y. y)$ reduces to $\lambda x. \lambda y. y$.


texts:
According to Arden's rule, the language equation $X= AX\cup B$, with unknown $X$, has the solution $X=A^*B$, provided $A$ does not contain the empty string.

My question: what is the problem with the empty string here? Can you illustrate this with a concrete example (which lacks in Wikipedia on this topic).


texts: Binary representation of 129 when using 8bits for two's complement?

texts:
I have this confusion regarding binary representation of decimal value 129 (or even 128). If 8 bits are used to represent numbers when doing the two's complement, then we know that '00000000' to '01111111' are used for 0 to 127 and leading 1 is used for negative numbers i.e. 1xxxxxxx where x is any combination of 0's and 1's to represent the value of that negative number.
But then how is 128 represented in 8 bits because the first bit is reserved for telling the number is negative (basically a signed number)?


texts: What Complexity Classes are the following Circuit Complexity problems?

texts:
All the circuits are composed of AND, OR, NOT Gates. Moreover, the maximum depth of any NOT gate in any circuit is bounded by some constant C.
All the circuits are composed of AND, OR, NOT Gates. Moreover, the total number of NOT gates in any circuit is bounded by some constant C.


texts: Order a list of whole numbers so that no two numbers have the average of them sitting between them

texts:
Given a whole number N..

Arrange 1 to N in a sequence such that no two numbers have their average sitting between them...

Note -
If N=20.. average of 19 and 2 = 10.5 is not a whole number .. hence we do not need to worry about such numbers and their averages..
In other words, if average of two numbers is not a whole number.. we assume that their average does not exist in the list 1 to N..


texts: Finding multi word anagrams from a set of words

texts:
Finding all anagrams for a word $w$ from a set of words is a problem with many well-known solutions (for example make a hash table mapping from the bag of letters of a word to the word).

But what about finding multi-word anagrams?  For example "Eleven plus two" is an anagram of "Twelve plus one".  In other words, given a multi-word phrase $w_1,\dots,w_s$, find a set of $s$ words that form a multi-word anagram.

I've thought about this for a bit and I came up with a $O(n^2)$ algorithm for all 3-word anagrams of a string, where $n$ is the number of words in the dictionary -- it basically comes down to the 3-sum problem but for histograms instead of integers. Are there any better algorithms? Assume the set of words is valid English words and $|s| \le 30$.


texts: Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort?

texts: So this is sort of a general question but I'll limit the discussion to randomized quicksort to make it clear. Suppose generating "true" random bits is hard, e.g. because it requires measuring something in nature that can be considered essentially "random" like the 50th binary digit after the decimal point in wind speed at some location recorded in miles per hour. Or maybe quantum outcomes observed that can be considered truly random. Whatever. So we do the following: We generate $k$ "truly" random bits and then we re-use these $k$ bits over and over by using a pseudo-random number generator to permute them. In terms of $k$ (the number of initial truly random bits) and in terms of the total count of numbers to be sorted, $n$, and assuming the permutation algorithm of the $k$ initial random bits repeated over and over is known to an adversary, can we assert that an algorithm like quicksort will have good worst-case expected running time, assuming that "random" bits are used in the algorithm in the natural way to choose a pivot? How do $k$ and $n$ play into the worst-case expected running time? If we need $k = \Omega(n \log n)$ initial truly random bits to assure good worst case expected running time, that isn't very interesting. But maybe we can do somewhat ok with asymptotically fewer initial random bits?


texts: Does spectral graph theory say anything about graph isomorphism

texts:
Is there research or are there results that discuss graph isomorphism in the context of spectral graph theory?

Two known theorems of spectral graph theory are:

Two graphs are called isospectral or cospectral if the adjacency matrices of the graphs have equal multisets of eigenvalues.
Almost all trees are cospectral.
The eigenvalues of a graph's adjacency matrix are invariant under relabeling (but this is not a necessary and sufficient condition).

Furthermore, is graph isomorphism "easy" to solve?


texts:
The dwarves of the Black Forest live in houses that are each painted either red or blue. Some dwarves are friends, and some aren’t. Every so often, a dwarf will think about repainting his house. To decide whether to repaint, he looks at the colors of his friends’ houses. If his house is red, but more of his friends live in blue houses than in red houses, then he will paint his own house blue. On the other hand, if his house is blue, but more of his friends live in red houses than in blue houses, then he will paint his own house red.
Prove that after some point in time, no dwarf ever paints his house again.

Here is my attempt:  This problem can be modeled by a graph. The vertices of the graph represent the houses and there is an edge between two vertices if the dwarves of the houses represented by the vertices are friend with each other. The problem then translate to coloring the vertices with two colors. If the graph has no cycle then it is a tree, then we can look at the leaves of the tree and color them and go one layer up and color the nodes according to how many children node has the majority of colors and so on. However, what happen when there is cycle in the graph?


texts: In general, the subset sum problem is NP-Complete. However, what if we say that our set is $\{1,...,n\}$? Is there a formula/combinatorial calculation that says how many subsets of $\{1,...,n\}$ have their sum equal to $k$?


texts: Given a list of students and their courses, place them in specific classes

texts:
I could use some help coming up with the best way to solve this problem. I've been curious as to how something like this would work, as the worst case seems way too bad.

Problem

Given a group of students and the courses they are enrolled in, and a schedule with 8 class blocks in it, how could you place them in specific classes?

Keeping in mind you can have as many classes for a specific course as long as there is a teacher who is free to teach the class.

Specifics

There are 8 class "slots" where you can put any class, but a teacher can not teach two classes at once.

Inputs and outputs

The input is a list of students each with data on which courses they are taking. There is not specific data structure I have in mind, the problem is more theoretical than literal.

The output would be assigning a value 1-8 to each class, specifying when they would take it.


texts: Minimum Spanning Tree over Vertices Proof

texts:
This is the problem:

$d_{T}(v)$ denotes the degree of a vertex in a spanning tree $T$ and $w: V \rightarrow R^+$ is a weight function defined on vertices.

The goal is an algorithm that finds a spanning tree which minimizes the value $\sum_{v \in V}{d_{T}(v)*w(v)}$.

My idea is to define a new weight function on edges in the following way: $m(e_{ij})=w(v_i)+w(v_j)$, i.e. the weight of each edge is the weight of both of its vertices.

Then we run Kruskal on a graph with the given $m$ weight function. The problem is that I have no idea how to prove that it works.

I thought about starting with the expression $min \sum_{e \in E}{m(e)}$ which Kruskal yields, and then somehow change the summation to be over vertices. How can it be done?

Thanks!


texts: Why is the 'Integrity' property required in consensus protocols?

texts:
Formally a consensus protocol must satisfy the following three properties:
Termination

Eventually, every correct process decides some value.

Integrity

If all the correct processes proposed the same value "v", then any correct process must decide "v".

Agreement

Every correct process must agree on the same value.

"Termination" certifies the protocol is resilient to halting failures. "Agreement" deters any two correct processes from deciding on different values which would break consensus. But what about "Integrity", why is it required? If all correct processes propose "x" but then they all decide "y" (e.g. y = f(x)), is that a violation of consensus?


texts: Finite Automaton to Turing Machine Example

texts: I cannot seem to find an example of an NFA and Turing Machine that both accept the same languages. I am trying to understand how to convert an NFA to its equivalent Turing Machine and I think a simple example would help a lot!


texts: Finding similar high dimensional real vectors

texts:
I have a collection of vectors $v_1,v_2\in [0,1]^n$ and I want to find similar pairs quickly. For similarity, I want to use the Euclidean distance metric $L: [0,1]^n \times [0,1]^n \longrightarrow R$. $n$ will be around $200$.

I've implemented Locality Similar Hashing (LSH) for word based documents, and I'm curious if there's an adaptation of it which will work for real based vectors.

I read here on Computer Science Stackoverflow that universal hashing will work.

If I have the vector $s=(0.55, 0.34, 0.90, 0.99)$ I can break it up into two sub vectors $s_1=(0.55, 0.34)$ and $s_2=(0.90, 0.99)$ and apply a universal hash to each:

$h_n= a\cdot s_n \space mod \space p$

Where $a$ is a random vector and $p$ is prime. I can now define a space of bins, where each $h_n$ defines a bin in this space. Each vector with a subvector in $h_n$ is mapped to the bin $h_n$

The problem is that this method is too precise. The vectors $(0.57, 0.34)$ and $(0.55, 0.34)$ are very similar but will get mapped to different bins.

I'm wondering if it's there's any theoretical and practical issues with either truncating the last digit or rounding up/down such that both vectors are now mapped to a bin representing the vector $(0.5, 0.3)$

This I believe is equivalent to multiplying all the vector elements by 10 and truncating the decimals, leading back to normal LSH.

I'm quite new at all this, so please forgive the slight errors in notation or understanding.


texts: Big o notation for sublinear algorithm in streaming algorithm

texts:
Excuse me if this is obvious.
At 1:55 of this Coursera video on streaming algorithms (see pasted image below for relevant slide), the professor mentions sublinear storage. I get the $N^{\alpha}$ but I don't get the $log^{O(1)} N$. I take it that $O(1)$ is a constant which we could set it as $k$ for example.

Does he mean that we can have $(log N)^k$ or taking $log N$ a total of $k$ times? I have read the sublinear portion of wikipedia which makes me believe it it is more like $(log N)^k$
How does this relate to $N^{\alpha}$ mentioned on the same line? Is this an alternate notation or another possible space complexity for other streaming algorithms?


texts: Difference between multiprocessor and uniprocessor in terms of run-time system

texts:
In the book "Advanced computer architecture and parallel processing" (El-Rewini & Abd-El-Barr), there is a question in the exercises of chapter 1 that needs the reader to compare between multiprocessor systems and uniprocessor systems in terms of many factors including run-time system:

Compare uniprocessor systems with multiprocessor systems for the following aspects:

Ease of programming;
The need for synchronization;
Performance evaluation; and
Run-time system.

I know how to compare between these two systems in terms of the other factors (ease of programming, need for synchronization, and performance evaluation) but I can't to compare between them in terms of run-time system as I don't know what is the exact meaning of run-time system?


texts:
If we have a language $F$ and a regular language $D$ (a finite set) then can we say anything about the intersection of $D$ and $F$? Will the intersection of the languages be finite or regular?

This question arises from another question which says

Show that if $L$ is not a CFL and $F$ is finite then $L - F$ is not a CFL.

Now $L = (L - F) ∪ ( L ∩ F)$.

Now if I am able to prove that $L ∩ F$ is finite or regular than I can arrive at a contradiction as follows:

If $L ∩ F$ is finite or regular then union with $L-F$ will be a CFL, therefore $L$ will be a CFL, which is a contradiction.

But my problem is assuming anything about $L ∩ F$.

What will be the properties of this intersection?


texts: Research in realtime computational physics?

texts:
I am aware that there is a considerable amount of interest in computational mechanics for simulation of cloth, hair and other elastica, particularly for animation films. The methods developed by groups in computational mechanics (that I am aware of) are typically far from real time.

My question is if there are any departments or people specialising in real time simulation of computational physics, with potential application to computer games, realtime virtual worlds, or educational tools? I am specifically interested in research groups in the University setting.


texts: Greedy algorithms: Minimum sum number pairing

texts:
Given $n$ real numbers (where $n$ is even) find a pairing which minimizes the maximum sum of a pair.

I think the optimal pairing is obtained by sorting the original set, pairing the first element with the last one, and so on. But I get stuck trying to prove it.

I tried use the "difference reduction method", examining differences between an optimal answer and the "greedy" answer, and trying to get the greedy from the optimal without losing optimality, but I didn't reach anything. Any idea?


texts: Do undecidable languages exist in constructivist logic?

texts:
Constructivist logic is a system which removes the Law of the Excluded Middle, as well as
Double Negation, as axioms. It's described on Wikipedia here and here. In particular, the system doesn't allow for proof by contradiction.

I'm wondering, is anyone familiar with how this affects results regarding Turing Machines and formal languages? I notice that almost every proof that a language is undecidable relies on proof by contradiction. Both the Diagonalization argument and the concept of a reduction work this way. Can there ever be a "constructive" proof of the existence of an undecidable language, and if so, what would it look like?

EDIT: To be clear, my understanding of proof by contradiction in constructivist logic was wrong, and the answers have clarified this.


texts: What will happen if input is larger than required in a NFA

texts: This is my first time in the field of TOC so I am not able to provide any self-approach while asking .In the above example what will happen if input string is "1001" or "1111"?The state q4 can be reached with the first 3 inputs only ,so what will happen after that ?


texts: Can maximal number in poset be more than one?

texts:
In poset maximal number is defined as:
An element 'a' belongs to 'A 'is called a maximal number if there is no element 'c' in 'A' such that a is less than c.

but it again says that there can be more than one maximal number. How can it be possible?


texts: Assumption of a generation of the dataset by a probability distribution

texts:
Consider the following paragraph from the deeplearningbook

  The training and test data are generated by a probability distribution
  over datasets called the data-generating process. We typically make a
  set of assumptions known collectively as the i.i.d. assumptions. These
  assumptions are that the examples in each dataset are independent from
  each other, and that the training set and test set are identically
  distributed, drawn from the same probability distribution as each
  other. This assumption enables us to describe the data-generating
  process with a probability distribution over a single example. The
  same distribution is then used to generate every train example and
  every test example. We call that shared underlying distribution the
  data-generating distribution, denoted $p_{data}$. This probabilistic
  framework and the i.i.d. assumptions enables us to mathematically
  study the relationship between training error and test error.

Bolded area is difficult for me to comprehend. Here I have the following issues in interpreting.

1) How probability distribution is generating a dataset?

2) Are the generation process and probability distribution the same?

3) What is the sample space and random experiment for the underlying probability distribution?


texts: How to compare an experimental study with amortized times

texts:
I have an implementation of a data structure I have to study for a group project (Fibonacci heaps if you're interested).
I'm asked to compare the theoretical results of the operations in amortized time, with the running times of my implementation.
Now my question: since amortized times are based on the fact that we look not just at a single operation, but at a series of operations, what can I do with my implementation to receive some experimental results that support (or not) my theoretical analysis?


texts: Can we skip an input in push down automata

texts:
Hi here I'm giving a language
L3={0^m 1^(n ) 2^m  | m,n ∈ N}
I designed this stack machine in order to accept this given language.
Here I'm skipping 1 (no matter how many 1s are there) . Is it ok to skip input this way?


texts:
I was reading the question Consistency and completeness imply soundness? and the first statement in it says:

  I understand that soundness implies consistency.

Which I was quite puzzled about because I thought soundness was a weaker statement than consistency (i.e. I thought consistent systems had to be sound but I guess its not true). I was using the informal definition Scott Aaronson was using in his 6.045/18.400 course at MIT for consistency and Soundness:

Soundness = A proof system is sound if all the statements it proves are actually true (everything provable is True). i.e. IF ( $\phi$ is provable) $\implies$ ($\phi$ is True). So IF (there is a path to a formula) THEN (that formula is True)
Consistency = a consistent system never proves A and NOT(A). So only one A or its negation can be True.

Using those (perhaps informal) definitions in mind I constructed the following example to demonstrate that there is a system that is sound but not consistent:

$$ CharlieSystem \triangleq \{ Axioms=\{A, \neg A \}, InferenceRules=\{NOT(\cdot) \} \}$$

The reason it's I thought it was it was a sound system is because by assumption the axioms are true. So A and not A are both true (yes I know the law of excluded middle is not included). Since the only inference rule is negation we get that we can reach both A and not A from the axioms and reach each other. Thus, we only reach True statements with respect to this system. However, of course the system is not consistent because we can prove the negation of the only statement in the system. Therefore, I have demonstrated that a sound system might not be consistent. Why is this example incorrect? What did I do wrong?

In my head this makes sense intuitively because soundness just says that once we start from and axiom and crank the inference rules we only reach at destinations (i.e statements) that are True. However, it does not really say which destination we arrive. However, consistency says that we can only reach destination that are reach either $A$ or $\neg A$ (both not both). So every consistent system must include the law of excluded middle as a axiom, which of course I did not and then just included the negation of the only axiom as the only other axiom. So it doesn't feel I did anything too clever, but somehow something is wrong?

I just realize it could be a problem because I am using Scott's informal definition. Even before I wrote the question I did check wikipedia but their definition didn't make sense to me. In particular the part that they say:

  with respect to the semantics of the system

their full quote is:

  every formula that can be proved in the system is logically valid with respect to the semantics of the system.


texts: Concurrent Element-wise Reduction Algorithm (multi-threaded) (C++)

texts:
I'd like to implement a high-performance implementation of a multi-threaded reduction, element-wise, on x86 CPUs. Without loss of generality, assume the reduction operation is a sum of integers (so, both commutative and associative). Each of the T threads has an array of N elements, and the final element-wise sum should end up in an output array that is the same size N as the T input arrays.

I'm looking for an algorithm that would be efficient and fast with T threads running inside a single M core multicore processor (assume T is equal to M here). All threads share the same address space.

Approach 1: My sense is that some sort of tree combination would make sense to compute the total reduction in log2(T) steps. It also seems to make sense that at any given step whereby two threads' arrays are being combined, each of those threads could participate in the reduction (each taking ~half of the output array, aligned to cache-line boundaries to eliminate false sharing on the output array). The threads do span multiple NUMA nodes, and assume the algorithm should work both for small arrays (fits within L1) and large arrays (fits within L3 but not within L1). One downside of this approach, though, is that it requires a number of extra temporary arrays to handle the accumulation at each level of the tree.

Approach 2: Another approach I'm considering is that all threads take responsibility for 1/T of the final output array (aligned to cache-line boundaries). In this approach, a thread could reduce in results from the (T-1) other arrays into the final output array. This doesn't have the memory overhead of Approach 1, and I think it has the same number of addition operations ((T-1) * N) as Approach 1 (?).

Note that I'm not memory constrained, but the extra memory allocations and cache misses would take time, and I'm trying to optimize for overall runtime performance here. Also, this should be able to leverage vectorization on the CPU in either case.

My question concerns the algorithm, but FYI, I'm using C++17 and the threads are standard std::threads mostly with std::atomics for synchronization currently.

One extra complication: the threads may arrive at different times and they all need the final resulting reduction array, so they have to wait until the full reduction is done.

Side note: I found this design document for the OpenMP implementation of reduce on GPUs (NVIDIA, specifically). My guess is that something similar for CPUs would be helpful, although I haven't been able to find that yet.


texts: If a machine recognizes language L, can it also recognize L*?

texts: This is a homework question. Suppose the only accept state is the start state. My rationale for this is that L* is just the concatenations of L, so if all strings in L are accepted, then all strings in L* will be accepted as well. One problem I see with this is that a machine can only accept one language, so it might be problematic...


texts: Is my regular expression and finite automata diagram for this state table correct?

texts:
So i have some theory of computer science homework and I'm struggling with this question currently. I am given the following automaton:

$Q = \{q_0,q_1\}$.
$\Sigma = \{a,b\}$.
$q_0 = q_0$.
$F = \{q_0\}$.
$\delta(q_0,a) = \delta(q_0,b) = q_1$, $\delta(q_1,a) = \delta(q_1,b) = q_0$.

I have to do two things: draw a state diagram, and write an equivalent regular expression. For now, these are my answers. I think my diagram is correct, but I'm not sure about the regular expression.

My regular expression for now is $(a+b)^*(a+b)$. Any help is very much appreciated.


texts: I would like to know what impacts does a scheduling algorithm, let's say Round Robin or FIFO, have on an Operating System. I understand that a scheduling algorithm has the processes run in burst then switch between one another. But what does this mean for an OS. All I can figure out is that the OS has to keep track of which process is running, see if it has done/completed its operation, choose/switch to another process and run it for a given time. Am I missing the obvious here? It does not really seam to me that a scheduling algorithm really affect the OS per se but the CPU hardware.


texts: Why does Bellman-Ford algorithm use < rather than ≤?

texts:
The Bellman-Ford Algorithm uses a less-than symbol rather than a less-than-or-equal-to symbol. How does this identify that there is a negative cycle?

For instance, say I have the below example going from initialization state through the first iteration and on to the second.

Initial state

    (0)S----(1)----B(inf)
        \         /
        (1)    (-1)
          \     /
           \   /
             C(inf)

First phase

...Check edges...
S->B
D[S] + 1 < D[B] = 0 + 1 < inf => True => Update D[B]

B->C
D[B] + (-1) < D[C] = 1 + (-1) < inf => True => Update D[C]

    (0)S----(1)----B(1)
        \         /
        (1)    (-1)
          \     /
           \   /
             C(0)

Second phase when checking for negative cycles

...Check edges...
...Skipping to check B->C...
B->C
D[B] + (-1) < D[C] = 1 + (-1) < 0 => False

    (0)S----(1)----B(1)
        \         /
        (1)    (-1)
          \     /
           \   /
             C(0)

Shouldn't the last check between B->C be true to detect the negative cycle? i.e. Shouldn't we use less-than-or-equal-to (≤) rather than (<)?


texts: Algorithm to minimize surface area, given volume

texts:
Consider the following algorithmic task:

Input: a positive integer $n$, along with its prime factorization
Find: positive integers $x,y,z$ that minimize $xy+yz+xz$, subject to the restriction that $xyz=n$

What is the complexity of this problem?  Is there a polynomial-time algorithm?  Is it NP-hard?

This problem basically asks: out of all rectangular solids whose volume is $n$ and whose dimensions are all integers, which one has the least surface area?

This problem was posed by Dan Meyer, under the title The Math Problem That 1,000 Math Teachers Couldn’t Solve.  So far none of the math teachers he worked with has found a reasonable algorithm for this problem.  In his context, the definition of "reasonable" is a bit imprecise, but as computer scientists we can ask a more precise question about the complexity of this problem.

The obvious approach is to enumerate all possibilities for $x,y,z$, but that takes exponential time.  Commenters at Dan Meyer's blog have proposed many efficient candidate algorithms that unfortunately all turned out to be incorrect.  Martin Strauss suggests that this problem seems vaguely reminiscent of 3-partition, but I can't see a reduction.

Let me also clear up some misconceptions that I've seen in the comments/answers:

You can't reduce from 3-partition by simply replacing each number $q$ with its power $2^q$, as the objective functions of the two problems are different.  The obvious reduction simply doesn't work.
It is not true that the optimal solution involves picking one of $x,y,z$ to be the nearest divisor of $n$ to $\sqrt[3]{n}$.  I see multiple people who are assuming this is case, but in fact, that is not correct.  This has already been disproven on the Dan Meyer blog post.  For instance, consider $n=68$; $\sqrt[3]{68} \approx 4$, and 4 divides 68, so you might think that at least one of $x,y,z$ should be 4; however, that is not correct.  The optimal solution is $x=2$, $y=2$, $z=17$.  Another counterexample is $n=222$, $\sqrt[3]{222}\approx 6$, but the optimal solution is $x=37$, $y=3$, $z=2$.  (It might be true that for all $n$, the optimal solution involves making at least one of $x,y,z$ be equal to either the smallest divisor of $n$ larger than $\sqrt[3]{n}$ or the largest divisor of $n$ smaller than $\sqrt[3]{n}$ -- I don't have a counterexample right now -- but if you think this statement is true, it  would need proof.  You absolutely cannot assume it is true.)
"Make $x,y,z$ be the same size" does not appear to necessarily yield the optimal answer in all cases; see Dan Meyer's blog post for counterexamples.  Or, at least, for some reasonable interpretations of the phrase "make them roughly the same size", there are counterexamples showing that this strategy is not in fact optimal.  If you want to try some strategy of that sort, make sure that you state the claim precisely and then provide a careful mathematical proof.
A running time of $O(n^3)$ is not polynomial.  For this problem to be in P, the running time must be a polynomial in the length of the input.  The length of the input is something like $\lg n$, not $n$.  The obvious brute-force algorithm can be made to run in $O(n^3)$ or $O(n^2)$ time, but that is exponential in $\lg n$ and thus counts as an exponential-time algorithm.  Thus that is not helpful.


texts: Placing a point between two nearest ones

texts:
I have a closed 2D shape expressed as a list of points, like that:

[
  {0,  5}, <-- {x, y}
  {10, 5},
  {15, 6},
  ...
]

The user has a canvas: each time he clicks on that canvas, a point will be appended to the list, and he will see the updated shape on screen.

How can insert the point between two nearest points instead of appending it to the list?

Let's say I have this shape:

All points got inserted counter-clockwise, starting from the first point to the left of the red one (meaning that the red one will be the last one):

Suppose that the user wants to place a point on the yellow area:

Right now the algorithm simply appends the new point to the list of existing points, so the new point will be inserted after point number 5, resulting in this shape:

Clearly I don't want this behaviour. I'd like the point to be inserted between points 3 and 4 instead, so that the result will be like that:

I came up with a possible solution.

Find distances between tuples and subtract them. The point's nearest tuple is the one with the minimum distances subtraction

Example:

d1 = abs(pink - blue)
d2 = abs(blue - green)
d3 = abs(green - red)
d4 = abs(red - yellow)
d5 = abs(yellow - pink)

Here, d2 will be the minimum, hence the point will be inserted between 3 and 4.

This approach however is buggy: if point 5 is a bit closer to the line between point 3 and 4, d3 will be the minimum, so the point would be inserted between points 4 and 5, which would be wrong.

Calculating areas of triangles instead of distances has the same issue.

I'm thinking there should be a way to take the segment distance into account. I mean, I would need to not only calculate distances between points, but also the new point's distance from the given segment. That way, I could tell that segment 3-4 is the nearest one, so I'll insert the point between 3 and 4.

So, what is an effective way to to handle this?


texts: What's a $O(n^2 \log n)$ algorithm that decides if a distinct set is completely triangulable?

texts:
Let $P$ be a finite set of $n$ distinct   points in $\mathbb{R}^2$. The set $P$ is called completely   triangulable if for any three points $p, q, r \in P$ the area of their triangle is always positive.

An algorithm that determines if a finite set $P$ is completely triangulable returns TRUE if  $P$ is completely triangulable and FALSE otherwise.

What is an algorithm that runs in $O(n^2 \log n)$ time?

My thinking is to use breadth first search but the running time of it is $O(n^2)$, so how can I edit that to achieve $O(n^2 \log n)$?