texts: Is there a name for the 'scope tree' organization?

texts:
I could describe JQuery as a library that allows you to easily select elements on and traverse the DOM, the DOM would be the name of the tree or organizational structure of the HTML.

When you are describing what JS (or any other language) scope bubbles up from the local scope, to its parent scope, to its parent scope, to its parent scope, ...., until there are no more parent scopes, where you have reached the global Object scope, what would you call this scope organization?


texts:
Most of the computers available today are designed to work with binary system. It comes from the fact that information comes in two natural form, true or false.

We humans accept another form of information called "maybe" :)

I know there are ternary processing computers but not much information about them.

What is the advantages / disadvantages of designing and using ternary or higher levels of data  signals in computers?
Is it feasible?
In which domain can it be better than classic binary systems?
Can we give computers the chance to make mistakes and expect to see performance
improvements in most situations by this way? (I think performance gains can be observed if computers are not so strict about being absolutely correct)

EDIT: Are there difficulties differentiating between 3 levels of signal? Would it be too hard to keep data in memory since memory voltage is frequently released and loaded, (maybe hundreds of time a second?).


texts: Count nodes with more than 3 neighbours in distributed computing, initiating by one site

texts:
I have an algorithm that visit all the nodes on a graph in distributed computing , the initiator is one site only , I want to change it so that the initiator can in the end of the execution know the nodes that have more than 3 neighbours ,
So the initiator is one site and the result expected is the list of the nodes that  have more than 3 nodes


texts:
I finally started working on my Master's thesis, and have a problem with literature sources.

My thesis is about distributed system built on top of custom library implementing actor model. But I can't find any good literature that goes deep into this side of distributed software. I've found quite a lot of literature that deals with distributed filesystems, databases, etc... But not a lot of articles/books that focus on object-oriented distributed systems and actor model.

Any recommendations ?


texts: Counting number of binary trees with given node values and root

texts:
I came across following problem:

  Find number of binary trees possible with 2 as roots. Nodes={1,2,3,4,5}

There was no solution given. I knew number of binary trees for given preorder is given by Catalan number as $\frac{1}{n+1}\binom{2n}{n}$, where $n$ is number of nodes. So does the above question same as asking: how many binary trees are possible for all preorders starting with 2? If yes, does the answer is $\frac{1}{n+1}\binom{2n}{n}\times 4! = 336$ as there are $4!$ pre orderes starting with 2.


texts: Better algorithm for determining if a vertex is on any cycle in a graph

texts:
The problem I'm facing is the following:

  Given a simple undirected graph $G=(V,E)$ and a vertex $u \in V$, answer if $u$ is part of any cycle of $G$.

The algorithm I can think of is to remove an edge from $u$ to one of its neighbours $v$ at a time and ask if there is still a path from $u$ to $v$ in the resulting graph, placing $(u,v)$ back before the next iteration.

I estimate the time complexity as $O(\Delta\cdot(m+n))$, with $\Delta$ being the greatest degree of the graph and $(m+n)$ for using a BFS on each iterarion.

Is there a better algorithm than this one? Does a simple DFS solve this problem and I'm just losing time with this?

BFS: Breadth-First Search
DFS: Depth-First Seatch


texts: Average number of comparisons to locate item in BST

texts:
This is a GRE practice question.

If a node in the binary search tree above is to be located by binary tree search, what is the expected number of comparisons required to locate one of the items (nodes) in the tree chosen at random?

(A) 1.75

(B) 2

(C) 2.75

(D) 3

(E) 3.25

My answer was 3 because $n=8$ and $\lg(n)$ comparisons should be made, and $\lg(8) = 3$. But the correct answer is 2.75. Can someone explain the correct answer? Thanks!


texts:
I am currently taking a class called Logic for Computer Scientist. During the first four weeks or so now we have been studying a concept Datalog with subsections Syntax and Formal Semantics and Fixed-Point Semantics. In these weeks we have looked at several definitions atoms, ground atoms, herbrand interpretations, herbrand models, and herbrand base, and these concepts make complete since to me. We are currently looking at something called the Single Step Operator(Immediate Consequence Operator), and I am having a hard time understanding what it actually does. It appears to be in the form of a set builder notation which simply builds a set based of certain rules. This operator appears to take input and filter out some results based of the rules in the Definition of the Single Step Operator

I am looking to see if somebody can actually explain what this is doing. When it comes to understanding what the symbols mean I get it. But I can understand how exactly it affects the data being passed to it/used by it. If anybody has some guidance I would really appreciate it or any good links everything I have found on Google has the same sort of layout as what I show in the image so it doesn't offer any benefit to understanding the concept.

Thanks in advance.


texts: How to draw NPDA for language $L = \{ a^i b^j c^m \mid m \ge \min( i,j) \} $

texts:
$L_1 = \{ a^i b^j c^m \mid m ≥ min(i,j) \}$

$L_2 = \{ a^i b^j c^m \mid m ≥ max(i,j) \}$

Which language is CFL ?

ANS : $L_1$ is CFL but $L_2$ is NOT.

My understanding :

  For Language $L_1$ :

( Here I am also interested in checking whether the language is DCFL or not. )

Checking DCFL or not :

By looking at language $L_1$, it is not possible to construct PDA as it contains 2 conditions ( i > j or i < j  And m ≥ min (i,j) )

But there is a way of checking language is DCFL or not. (By Prefix Property)

No Proper Prefix ⇢ Prefix property ⇢ DCFL

But there is No Proper Prefix getting for this language, So $L_1$ is  DCFL  ( but there is no DPDA for $L_1$ as per my 1st conclusion ( i.e. 2 conditions -> No PDA )

It means somewhere I am wrong. Please correct me.

Checking CFL or not :

We will have to check whether it is accepted by NPDA or not.

I don't know correct way to construct NPDA but I tried in following way.

At some point the PDA will assume that $i < j$ or $i > j$.

Condition 1st : $i < j$

We are interested in min , so consider only i, ≥ means accept "a" and skip all "b" and for each "c" , pop each "a"

Condition 2nd: $i > j$

We are interested in min , so consider only j means skip all "a" and accept

"b" and for each "c" , pop each "b". So it is CFL.

Please correct me if it is wrong.

If the above NPDA is right, then we can also construct an NPDA for $L_2$.

But the Answer part says $L_2$ is not CFL.

So is the above NPDA is right or wrong ??


texts: Do Stephen Wolfram and Gerard 't Hooft propose that literally every cellular automaton is a universe?

texts:
Both Stephen Wolfram and Nobel laureate Gerard 't Hooft think that the universe is a cellular automaton.

As far as I know, 't Hooft developed a series of frameworks to build different models of cellular automata and Wolfram also proposed a framework where network nodes could produce different cellular automaton universes.

Both of them proposed specific models of cellular automata to describe our universe (or rather they are working in a cellular automaton description that can be applied entirely to our universe), but since they proposed a framework to create different cellular automaton models, this makes me think that these authors think that literally every type of cellular automaton corresponds to a universe.

For example, apparently Stephen Wolfram in his book "A New Kind Of Science", chapter 9, he defines a series of network nodes that could be capable of reproducing all models of cellular automata. But I am not sure about this and I would need someone that knows better this field to confirm this to me.

So, does anyone here know of this is correct? Does anyone here know these works well enough to tell me if these physicists think that every cellular automaton model corresponds to a universe?


texts: Algorithm favours CPU bound or I/O bound processes

texts:
Some scheduling algorithms favour CPU bound processes while others favour I/O bound processes.
Which algorithm favours which type of process?
My answers:

SJF favours I/O bound processes.Explanation: Short CPU burst processes(I/O bound processes) are given higher priority.
SRTF favours I/O bound processes.Explanation: Same as SJF
Round Robin?  Not able to decide categorically
LRTF favours CPU bound processes.Explanation: Large CPU burst processes(CPU bound) are given higher priority.
HRRN?  Not able to decide categorically
Multilevel feedback Queue favours I/O bound processes.Explanation: Short CPU burst processes(I/O bound processes) are given higher priority. While processes that have large CPU bursts(CPU bound) will slowly have decrement in priority. A process in lower priority queue can only execute when higher priority queues are empty. A process running in a lower priority queue is interrupted by a process arriving in a higher priority queue.
Multilevel Queue favours I/O bound processes.Explanation: Similar to multilevel feedback.
Priority Scheduling?  Not able to decide categorically
FCFS?  Not able to decide categorically

 Please verify above answers and explanations.
Correct me if I'm wrong somewhere and provide answers with explanation for the omitted ones.


texts: Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy?

texts:
Let $\mathrm{L} \in \mathrm{NTIME}(n^3)$. Since $\mathrm{NTIME}(n^3) \subseteq \mathrm{NP}$, we have that $\mathrm{L} \le_p \mathrm{3SAT}$. However, $\mathrm{3SAT} \in \mathrm{NTIME}(n)$. Hence, $\mathrm{L} \in \mathrm{NTIME}(n)$. Thus, $\mathrm{NTIME}(n^3)\subseteq \mathrm{NTIME}(n)$ which implies the non-deterministic time-hierarchy is false.

But we all know that time hierarchy is true. Where am I going wrong? The statement seems to be correct but I know it's wrong. How?


texts: How the Abstract DPLL Algorithm Works in SAT Solving

texts:
I have come across many definitions of the DPLL algorithm but haven't been able to follow them. The ones that are closest to making sense to me are the ones based on state-transition systems with transition rules such as defined here:

$F$ is a CNF formula, $C$ is a clause, and $M$ is a model. A description of it is as follows:

  Here, a DPLL procedure will be modeled by a transition system: a set of states
  together with a relation, called the transition relation, over these states. States
  will be denoted by (possibly subscripted) $S$.... A state is either fail or a pair $M \parallel F$, where $F$ is a finite set of clauses and
  $M$ is a sequence of annotated literals.... We will not go into a complete formalization
  of annotated literals; it suffices to know that some literals $l$ will be annotated
  as being decision literals; this fact will be denoted here by writing $l^d$
  (roughly, decision literals are the ones that have been added to $M$ by the Decide rule given
  below). Most of the time the sequence $M$ will be simply seen as a set of literals,
  denoting an assignment, i.e., ignoring both the annotations and the fact that $M$
  is a sequence and not a set.

I understand that a literal is an atom or its negation, but I don't understand what an annotated literal is, which is a core part of understanding what a model $M$ is in $M \parallel F$. I also don't understand what the decision literals are.

Two examples are as follows.

This is as much as I can gather. This:

$$\emptyset \parallel 1 \lor \bar{3}, \bar{1} \lor \bar{4} \lor 5 \lor 2, \bar{1} \lor \bar{2}$$

Is essentially an implementation of this:

$$M \parallel F$$

Also, the commas are really $\land$, as in:

$$\emptyset \parallel (1 \lor \bar{3}) \land (\bar{1} \lor \bar{4} \lor 5 \lor 2) \land (\bar{1} \lor \bar{2})$$

So each of the blocks between the commas or $\land$ are clauses. On the left is a growing list of literals (atoms or their negation). On the right are the rules being applied (like Decide). But I don't understand (a) how the rules are being applied / why they are chosen at the time they are chosen, (b) how it results in an annotated literal for $M$ on the left, and (c) why some of them are marked in bold as the "decision" literals.

The final result, from my understanding, is the model $M$ (on the left) that satisfies the formula $F$ on the right. Essentially, it's a valuation.

Wondering if one could clarify how the first example works, how the annotated literals get added to the model $M$ on the left.


texts:
What is a good textbook for a seminar about

virtual environments,  virtual worlds,  augmented reality  and
similar topics?

The seminar is at the graduate studies level and is supposed to give introduction to virtual environments, technologies and applications as well as  current research directions.

A creative commons license and availability online would be a plus.

Here are my own results after some search:

Augmented Reality - open access book at Intechopen

I was suggested these books (no online access) at another source (ResearchGate):

"Virtual Reality Technology" (Grigore C. Burdea, Philippe Coiffet)
"Understanding Virtual Reality: Interface, Application, and Design" (William R. Sherman, Alan B. Craig)
"Developing Virtual Reality Applications:Foundations of Effective Design" (Alan Craig , William R. Sherman)
"Stepping into Virtual Reality " (Mario Gutierrez, F. Vexo, Daniel Thalmann)

In your answer please comment, why do you suggest a particular source and why it is fundamental or current in the field.


texts: Computational Complexity of Solutions of the Traveling Purchaser Problem on a Small Data Set

texts:
I have encountered a problem that is essentially the textbook statement of the Traveling Purchaser Problem.  I don't know if this is the proper place to put this, if not then I will delete it.

Also a note is that while I have done some studying on my own of computer science, I did not have much formal education in it.  I do have a reasonably strong math background though.

Now on to the background of the problem:

I know the Traveling Purchaser Problem is NP-Hard, and thus there is no optimal solution algorithm known.  I know that as such, there are many different solution algorithms, of varying efficiency.  The (admittedly few) papers that I have seen though use this on sets of 100s of nodes,  and don't explicitly state the complexity of the algorithm in terms of big-O notation or similar functions.  Since my data set is relatively small (7 nodes and about 50 items to purchase).  I was wondering if it might be a waste of time to implement a complex, if efficient, algorithm.  But that is not my question, as I think such questions would be out of place here, it is just the background.

My question is the following:

What are some of the common algorithms for approximating the solution to the Traveling Purchaser Problem along with their computational complexity in terms of the number of nodes and the number of items to purchase.


texts:
I need to determine all the trees on 25 vertices for which there exists an integer m ≥ 2, such
that the degree of each vertex gives the same remainder when divided by m.

Can somebody help ?


texts: Algorithm for animating/morphing convex polygon diagrams

texts:
I am trying to find an algorithm to smoothly morph a (given) diagram made of convex polygons into another (given) diagram of the same type.

The target diagram is usually generated from the source, where all kind of operations may happen (new polygon popping up, polygon gets deleted etc.)

So for example I may want to go from

To

with the following constraints:

Morphing between the two diagrams should be smooth (e.g: new polygons should not pop up but kind of grow)
In all intermediate diagrams the polygons should be simple and convex

I tried looking around for papers and/or previous work on that, but failed spectacularly in finding anything, so...

Does anyone here have any idea/references?

(Heck, I'm not even sure this is the right stack exchange board to ask for it)


texts: Understanding reductions for NP-completeness

texts:
Let's I have to make the following reduction:

$$\text{CLIQUE}\le_p \text{VERTEX-COVER}$$

The technique of building the reduction is -

Assume you can find a $\text{VERTEX-COVER}$ of size $k$, in polynomial time.
Building a new graph, in which I say that if a $\text{VERTEX-COVER}$ exists of size $k$, then in the original graph, a $\text{CLIQUE}$ of size $k$ exists?

I just want to understand the technique of these proofs.


texts:
If we extend the allowed bases for a numerical system to the complex numbers, is e still the most economic base? If not, what would it be?
There's the well-known formula for radix economy:
Where b is the base, and N is a given number.
I don't know if this formula is still valid for complex numbers. Nonetheless, the only local minimum this function seems to have, even extended over the complex numbers, is at b = e + 0i.


texts:
What's the complexity of the above? It's part of a larger problem where the (1/2) comes from the probability of that happenening, so the worst case is:

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

but the average case is:

T(n) = (1/2)T(n/2) + (1/2)c

Our professor told us that the answer to the worst case is O(n), and that the average case is O(n) as well. This doesn't sit right with me because if you have 10,000 coin flips, you're saying you're expecting 10,000 heads (recurse on heads, break on tails). I said it was O(1) on our midterm, anyone else have any insight?


texts: Why is the opcode 0 for all r-type instructions? Please explain your answer

texts: I can't seem to find the explanation for why all r-type instructions have opcode 0 always. Can anybody explain why this is so.


texts: Finding a path between 2 points passing through N points

texts:
Given a graph/plane with N points each at a given coordinate how could I find a path between 2 points via N other points where each point is weighted on how likely it is to be passed through.

Distances between points can be calculated
Path must be less than a given distance

Apologies if the vocabulary isn't quite right or I've posted this in the wrong place


texts: Is there a polynomial time algorithm to tell if an NFA over an unary alphabet is universal?

texts:
Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?

I would not expect this would work over an alphabet of size two or more, since it is PSPACE-complete to check whether a regular expression is universal. However, since regular languages over unary alphabets have nice characterizations, I would expect there would be some way to check the universality of an NFA over an unary alphabet.


texts: Open source implementation of Multiscale Combinatorial Grouping

texts:
I would like to use Multiscale Combinatorial Grouping for my PhD research. However, I am restricted to use open-source implementations and this one runs on Matlab.

Does anyone know of an equivalent contour detection method that works on large images that is implemented open-source, preferably in Python?

Here some more background info. Equivalent methods would be:

Contour detection and hierarchical image segmentation -> cannot handle images of more than 1000x1000 pixels and runs on Matlab
SLIC Superpixels -> creates too many redundant segments

I am interested in detecting contours of visible objects in drone imagery with a resolution of 2-5cm per pixel and extents of up to 1kmx1km for the purpose of automating cadastral mapping. Here an example of what the contour detection output should look like:


texts:
Given two large directed graphs (may have loops and lonely nodes) A and B. They are structurally similar.

If we give a node in Graph A, how to find the corresponding one in Graph B?

Finally, we need to find all the node mappings.

Of course, there can be more than one possible mapping. We need to find the similarity (ranking) percentage.

How to design such an algorithm?

The graphs are Control-flow Graphs (Call Graph) extracted from program binaries. However, due to compiler difference (optimization, inline, etc.), the graphs can be a little different.

UPDATE:

To be more clear, as shown in the figure below, we also need to find the matching like B and B',B1' ("->" means a node match):

A -> A'

B -> (B' , B1')

C -> C'

D -> D'

E -> E'

F -> F'

As this is not a sub-graph matching, I cannot find good library APIs or algorithms.


texts:
the question goes as follows:
In a B-tree (d,2d) of height h, what is the minimal and maximal number of inner-nodes (excluding leaves)?

My idea:

Minimal: The root is 1, it has a minimum of 2 children, therefore we have 1 + 2, and then for any level below each node will have the minimum nodes allowed which is d. We get $1 + 2 + 2d + 2d^2 + ... + 2d^{h-1}$ including the leaves, therefore making $1 + \sum_{i=1}^{h-2} 2d^i$ (note that the final index is $h-2$ since we dont count the leaves).

Maximal: Pretty similiar but each level will have $2d$ children, thus making $ 1 + 2d + (2d)^2 + .... + (2d)^{h}$ including the leaves, therefore making $ \sum_{i=0}^{h-1} (2d)^i$.

However, the answer sheet goes $1 + \sum_{i=1}^{h} (2d)^i$ for maximal and $1 + \sum_{i=1}^{h} 2d^{i-1}$ for minimal.

I'll note that the height is defined as the numbers of edges from top-to-bottom, and for example; a tree of root only is of height 0. Tree of root + one set of children is of height 1.

Am I missing something or is there a mistake in our answer-sheet?

Thanks!


texts: Is anything known about the structure of sets of valuations representable by 3CNF formulas?

texts:
Let's suppose we have propositional variables $x_1 ... x_n$.  A valuation is an assignment $v$ s.t. $v(x_i)$ is an element of $\{false, true\}$ for $1 \leq i \leq n$.  So, there are $2^n$ possible valuations.  The number of sets of valuations is then $2^{2^n}$.  If we associate to each formula $\varphi$ the set of valuations that satisfy it, we see that there are many sets of valuations that do not correspond to any 3CNF formula.  This is because there are only polynomially many possible 3CNF clauses and any formula is a subset of such clauses.

Is there any theory about the structure of the sets of valuations representable by 3CNF formulas?


texts:
I develop an open source power systems software and I would like to include a simple collaborative mode so that more than one person could work on building a power system model.

So far I have a table-based file format which is composed of many csv files bundled into a .zip file.

My thinking is that when a synchronisation event is triggered the following should happen:

Import the remote file into a model
compare the imported model with the current model

Omit the equal fields
Omit the additions from the current model to the remote
Flag the conflicts
Flag the additions in the remote model that are not present in the current model.

Ask the user about what to do with the conflicts (overwrite theirs, overwrite mine, omit for now)

I would like to know about other approaches about how to do the comparison part and corrections and suggestions to what I have came up with.

thanks.


texts:
If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP.

I am struggling with figuring this out. I know this means Y can be reduced to X, so if I could solve X I could solve Y. I can't solve X, but I have a certifier for X and complement(X). I am having trouble combining the reductions and certifiers to find a certifier for complement(Y).


texts: Status of Research Problems in Motwani and Raghavan

texts:
One nice aspect of Motwani and Raghavan's classic textbook, Randomized Algorithms, is that the notes for many chapters include open questions marked as "research problems." However, the textbook is ~20 years old at this point, and it's unclear what progress has been made on these problems in that time.

My question is whether there's a resource listing progress and resolution status of these problems, preferably with citations.


texts: Algorithm to calculate average weight from every pair of nodes

texts:
I'm trying to solve a puzzle where I need to calculate the average weight between every node in the graph.

For example, for the following graph:

The results is calculated like this:

1 -> 2 = 3;

1 -> 3 = 7;

1 -> 4 = 5;

2 -> 3 = 4;

2 -> 4 = 2;

3 -> 4 = 7;

Average = 3+7+5+4+2+7 / 6;

NOTE: I'm visualizing the problem as a Graph, I might be wrong. The following constraints apply to this problem:

There is exactly one path between any two nodes, but all nodes are connected to every other node.

So we can assume that in the example, there will not be a path from 1 -> 4 directly

I'm looking for a recommendation of an algorithm that I can study in order to solve this type of problems. Not the actual solution.


texts:
I have a menu of n items, with each item having a value. Given the total amount spent, I have to figure out all the possible combinations of items purchased. Example, I have three menu items:

item 1: $4

item 2: $5

item 3: $8

with the total purchase price = $14

There is only one solution in the case, 1 purchase of item 1 and 2 purchases of item 2.

How do I go about solving this?


texts: Question about handwritten numbers recognition with limited data set

texts:
I have a an assignment to make a classifier for hand-written numbers with a limited data set of 500 samples.
I am currently using python, I tried sklearn SVC with linear classifier and I got an accuracy of about 80%. I also tried KNN with 13 neighbors and got a max of 81% accuracy.
I need to get to at least 90% accuracy. What are your suggestions that would help with training (adding noise? what distribution? / tilting the pictures with 90 degrees? Maybe cross validating over different parameters... etc).

Edit:
To clarify the main challenge:
I have to reach an accuracy of more that 90% with only using 500 samples, I can play around with the samples however I want to extend the data but I am not allowed to use external samples.


texts: If a language is not Turing reducible to two languages, may it still be Turing reducible to their "union"?

texts:
Consider a language $L$ that is undecidable relative to $L_1$ and is also undecidable relative to $L_2$. Suppose, however, that there is a "multi"-oracle Turing machine $M$ that can query both the $L_1$ oracle as well as the $L_2$ oracle such that $M$ decides $L$. In other words, $L$ requires both the $L_1$ and $L_2$ oracles to be decided, but neither one alone suffices to decide $L$. I would like to come up with such languages $L$, $L_1$, and $L_2$. At first, I was hoping that the oracles for the rejecting and the accepting problems for Turing machines together could be queried to decide the halting problem (but neither oracle alone could be used decide it), but that turns out to be a dead end.

Now I'm wondering if I can approach the problem by trying to come up with two languages such that neither is Turing-reducible to the other, but I'm struggling to find examples.


texts: What could you learn from studying player movement and behaviour on online FPS games?

texts:
Just thinking of Counter Strike as a canonical example, if you have a coordinate representation of the map and for every player you have a complete history of everything you might need for every moment of time, say every 10 miliseconds or something and you just recorded where the players went around the map, and what they did. So maybe, for example, at each time t you had v(t) a vector function whose components are (location(t), velocity(t), rotationVector(t), rotationVelocity(t), isFiring(t), ammoCount(t), health(t), isEnemyVisible(t), isTeamMateVisible(t)) or whatever other measurements you think would be useful for the state space.

If you collected a bunch of data like this what sort of hypotheses or models would you consider testing? Would it be possible to construct a probabilistic model to classify histories and possibly predict outcomes of player-enemy encounters? Could you train AI bots on this data?


texts: Bubble sort: average number of total key comparisons

texts:
I want to know the steps for finding a Formula for Average number of total comparisons in bubble sort.
Please look at this example:

4 3 2 1 -> 3 2 1 4 ->   3 comparisons
3 2 1 4 -> 2 1 3 4 ->   2 comparisons
2 1 3 4 -> 1 2 3 4 ->   1 comparisons

For ordered and reverse ordered input we have different formula for number of total comparisons:
Min = n-1
Max = n(n-1)/2

And I want a formula with steps to get average of it - all possible inputs - / expected number of key comparisons for each of n input values selected from a uniformly random source
My try
(Sum of total comparisons)/(n-1) =>  n(n-1)/2/(n-1) => (n-1)

NOTE : (n-1) is number of steps
is it right?


texts: Finding first occurence of all possible matches?

texts:
Say you have multiple strings that you're trying to match in a text. And it's possible all these strings have a match in the text. Is there a good way to return out of all the matching strings the index of the one that comes first? Or a -1 if there are no matching strings whatsoever.
For example, say the text is
"The seven dwarves are Grumpy, Dopey, Doc, Happy, Bashful, Sneezy, and Sleepy." Then the code would find the first occurrence out of the dwarf names that do appear in the text. In this case Grumpy is the first time a dwarf name appears which is index 22.


texts: Solving Subproblem in Logic (first-order, propositional, pddl)

texts:
One sentence question

Is there any algorithm able to prove (solve) a logic problem (first-order, propositional, pddl) by finite induction?

Background

I am researching Hierarchical planning solvers and I found the following problem.
Let a problem climb a stairway. An agent is able to move up or down. For example, suppose the following "move up" action:

moveup(position):
    pre-condition: on(position)
    post-condition: ~on(position) ^ on(next(position)

Now, let a stairway be defined as:

stairway:
   next(first_step) = second_step
   next(second_step) = third_step
   ...
   next(nminusoneth_step) = nth_step

and, a start point from agent is on the first step:

on(first_step)

Now, I want to create a plan to bring the agent from the first step to last one.
Of course, I can solve that in many different ways (brute force for example), but I know how to climb an one-step stairway (just move up) so, I am able to infer that all I need to climb an n-step stairway is just moving up (it is not necessary to decide each action individually). Is there already any algorithm for that (recognize a subproblem structure and infer actions by induction)?


texts: Is there an algorithm for reducing CNFs further

texts:
I have a boolean formula in conjunctive normal form (CNF):
$(a\vee b \vee c) \wedge (a \vee b \vee \neg c) \wedge (x \vee y)$
I know that this can be simplified to:
$(a\vee b)\wedge (x \vee y)$.
a) Is there an algorithm to decide if a CNF is already in the reduced form or not?
b) Is there an algorithm that can do this reduction in an manner more efficient than comparing each pair of clauses to see if any pairing can be reduced? I wish to automate this reducing for any CNF and am looking for any algorithms that I can borrow/implement.


texts: Graph splitting via an algorithm and proof of properties

texts:
Given the following function:

function split(G)
    if (all vertices of G have even degree) then
        return (V (G), ∅)
    else
        Let a ∈ V be a vertex of odd degree;
        S ← NG(a);
        G ← G − a;
        for ((∀)u, v ∈ S, u != v) do
            if (uv ∈ E(G)) then
                E(G) ← E(G) − uv;
            else
                E(G) ← E(G) ∪ uv;
        (W1, W2) ← split(G);
        if (|W1 ∩ S| % 2 = 0) then
            V1 ← W1 ∪ {a};
            V2 ← W2;
        else
            V2 ← W2 ∪ {a};
            V1 ← W1;
return (V1, V2)

I have to show that V1∩V2 = ∅, V1∪V2 = V(G) and the subgraphs of G obtained from V1 and V2 have an even degree on all vertices.

Now, based on the function it is obvious that the properties stated above hold true, but I am stumped as to how exactly should I go about proving them and by what general rule or criteria the split function splits the graph(I have no problem following the algorithm but the "big picture" escapes me).

EDIT: NG(a) Is the set of a's neighbours.


texts: Difference between beta reduction and substitution

texts:
I can not see the difference between beta reduction and substitution.

For example:

(+ x 1) [x -> 2]

Here I can do the substitution, replace the variable x through 2(lambda expression) and result is:

(+ 2 1)

An example of beta reduction:

(λ x. + x 1) 2

the result would be

+ 2 1

For me, there are no difference between them, but there is a rule, I can not substitute the lambda expression, when the metavariable is bound

(λ x. + x 1) [x -> 2] No possible to substitute it.

Only free variables can be substitute it.

What is the difference between the diction:

(λ x. + x 1) 2

and

(λ x. + x 1) [x -> 2]


texts:
If I have a proof for a separation between two complexity classes (using no oracles) and I want to see if it relativizes, how do I go about doing so?

Especially in the case where there already exist proofs for these classes being equal with respect to one oracle and not equal with respect to another oracle. I'm wondering, if I have a proof of inequality with respect to no oracle can I simply reference the oracle to which these classes have been proven equal, call on that example, and be done--since there exists an oracle to which they have already been proven equal this is my proof that the inequality doesn't relativize?

Or do I have to apply oracles specifically to the machines in my proof of the inequality and see if it relativizes?

I'm confused about how proving relativization / non-relativization of a specific proof of some statement relates to the relativization of other proofs of the same statement.

How can I reference the fact that other proofs of a statement relativize / don't relativize to help me prove my own relativization result about my proof of that statement?

Thanks!


texts: By what criteria is the base value selected in Rabin Karp algorithm?

texts:
In the Rabin Karp algorithm the rolling hash is calculated as follows:

H1= c1*a^k-1 + c2*a^k-2+c3*a^k-3+…+ck*a^0

where a is a constant. On what basis is this a selected? In Cormen they have used a value 10 and at some other places it is 26. By observation, when the string is of digits they have taken a = 10 and when the string is of English characters then they have taken a = 26. Is it not possible to compute the hash value using a = 10 for English characters. If not what flaws does it introduce or i am assuming it wrong. I would appreciate help.


texts: Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ context free?

texts:
I was wondering if this language is context-free:

$L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$

I know that this language is not regular because it fails the pumping lemma for regular languages but that does not necessarily mean it is not context-free. I'm not sure whether to use the pumping lemma for context-free languages to show that this is not context free or to provide context-free grammar to show that it is context free.

I've tried creating a context-free grammar to generate this language but ran into trouble which makes me believe that this language is not context-free, but I am still unsure.

If someone could point me in the right direction that would be greatly appreciated.


texts: Compute cache miss rate for the given code

texts:
Problem Description:

We consider a 128-byte data cache that is 2-way associative ($E=2$) and can hold 4 doubles in every cache line. A double is assumed to require 8 bytes.

For the below code we assume a cold cache. Further, we consider an array A of 32 doubles that are cache aligned (that is, $A[0]$ is loaded into the first slot of a cache line in the first set). All other variables are held in registers. The code is parameterized by positive integers $m$ and $n$ that satisfy $m*n = 32$ (i.e., if you know one you know the other). Recall that the miss rate is defined as $\frac{\text{number of misses}}{\text{number of accesses}}.$

// Code:
float A[32], t = 0;
for(int i = 0; i < m; i++)
  for(int j = 0; j < n; j++)
      t += A[j*m + i];

Problem:
Determine the miss rate for when $m=1,2$ and $16.$

My Attempt:

When $m=1$ we access the elements,
$$A[0],A[1],A[2],\cdots,A[31]$$
and since each block in the cache can hold $2$ doubles, this means that for every miss we get one hit and so the miss rate is $1/2.$

When $m=2$ we access the elements,
$$A[0],A[2],A[4],\cdots,A[30].$$
Here we first miss $A[0]$ but then we load the block with $(A[0],A[1]).$ However, this does not help since we need to access $A[2]$ and therefore we miss every time and thus the miss rate is $1.$

When $m=16$ we access the elements,
$$A[0],A[1],A[2],\cdots,A[31].$$
And so like before this should have a miss rate of $1/2.$

However, the answers are:
$$m=1, \text{miss rate} = 1/4$$
$$m=2, \text{miss rate} = 1/2$$
$$m=16, \text{miss rate} = 1/4.$$

I am not sure how to obtain these answers and so any help will be much appreciated.


texts:
I know the answer that it will be 1024(2^10). But iam not able to understand why, I have looked the answer but still don't find it compelling
My reason, it says ten if  are there in the language and since it follows the given grammar then the program having 10 'if' should be generated by it, which can be but in my opinion they should be non recursive that leads to like this
Statement, statement, statement.... up to 10.
But look closely they are linear  and the grammar is itself non recursive so an ' if' can't be nested here
So my answer is that the control flow path should be 20 only as with each statement we get 2 paths and here there are 10 state with each of them having 2 control flow path so answer is 10*2=20
I know that iam wrong here somewhere but I don't know where any help will be admirable


texts:
I know that this may sound a bit out of the box, in fact i used to always think inside the box, but recently i've been thinking, possibly because computer science provides an high degree of freedom, about ways to devise programs other than the ones taught in university.

Consider the factorial function. Typically we define this function like

 int fact(int n)
 {
 int r = 1;
 for(int i=2;i<=n;i++)
 r = r*i;
 return r;
 }

I'd call this an algorithm and have no doubt that this is the right way to do it. Then, i wondered "can i do this in constant time?", which let to the following idea: what if i had an array of integers where array[n] houses the factorial of n? Once this array is filled i could simply define fact as:

 int fact(int n)
 {
 return array[n];
 }

Still i cant seem to cal this an algorithm, even though it provides the correct result and operates in constant time O(1). Can this be called an algorithm? Otherwise, why not? I could argue that filling the array would require an algorithm to have operated at some time, even if it was in our brain in order for us to fill the array, but could this be the criteria? How are these aspects handled formally?

Note that this concept could be extended to any function operating over integers independly of its number of arguments, i would just have to use a matrix if the function had 2 arguments, or 3 if the function had 3 arguments, and so forth. Also, aren't these solutions used simply because of memory consumption?

Also, not that functions may also encompass any program with output, since i could find a way to index every single possible output that a program could provide.

As another exemple, consider the common use of an array: i allocate an array initially of size N, then i add elements to array by storing the value at index n and increasing n by one unit. Then, if i want to look for an elemento, i cant help but to perform a linear search over the array. If instead i created an array of size, for instance, Integer.MAXVALUE, to store integers, initialized with zeroes, i could store an integer by placing 1 at its index. Then i could search for its existence in the array in O(1) time. What if i wanted to be able to place multiple units of the same number? No problema, i'd just increase the value stored at the integer's index.

Sorting would be a bit more complicated, but nonetheless lookup and addition could be performed in O(1) time.


texts: Minimisatiom using Myhill-Nerode Theorem

texts:
I have recently studied the Myhill–Nerode theorem and while applying it to minimize these FSMs, I encountered a problem. Is it always the case that the final states should be grouped together because they are indistinguishable?

In the first FSM below, if I group states (q3,q4) on 0, q3 reaches q4 and q4 reaches q4, but on 1 both behave differently as q4 has no transition on 1.

Same trouble with the second FSM.

I want to understand how to group together the states while using the theorem.


texts: Data structure for a Rete in production rule system

texts:
Example of Data

This is the data for one monkey. There are many similar but different monkeys.

X(Y,Z) means Y, Z are parent of X.

A(D,E)  If monkey see banna (D) and monkey is hungry (E), it squeaks (A).
B(E,F)  If monkey is hungry (E), and monkey see other monkey, it jumps(B).
C(D,F)  If monkey see banna (D), and it is not hungry (E), it walks away(C).
0(A,B)  If monkey squeak(A) and jumps(B), it grabs the banna
        with priority 10 and reduce priority for doing other
        things (0).

D, E, F are the source.

Notice that this is not a tree. A-C-D is a undirected cycle. Trees have no cycle (wikipedia). The priority and the words at right are not part of the data structure I am interested in (at this moment).

Question

Is there a data structure that conserves memory and allow reasonably efficient recalculation of values for the following case?

The data structure is for the rete algorithm (https://en.wikipedia.org/wiki/Rete_algorithm).

[Description of the data]

Each node (except the end points) has exactly two parents.
Any two parents have at most one child.
A node can be the parent of multiple nodes.
Each node has value, which is a boolean. (Or an array of fixed number of boolean for sharing the nodes between different monkeys.)
Value of child is logical and of values of its parents.
Want to keep all values of the nodes to save recalculation time.

[Operations on the data structure]

The structure of the graphs never changes. I don't mind taking a long time to construct the data structure.
When value of a node changes, values of its children are
recalculated. The values of the end points occasionally changes in
every cycles of calculation.
Want to know if the predefined
interesting nodes (for example we know that node 0,3,and 5 are
interesting.) change value.
Don't need to query or look up for any
particular values among the nodes. Also don't need to output values
of all the nodes (that would take too much time.)

There are lots of nodes, and lots of parent-child relationships, because there are lots and lots of rules, and lots of slightly different monkeys.

(I have never taken any computer science class... I learned everything online. Sorry if I use the wrong terms.)


texts: Can someone provide an introductory example of a certificate in complexity theory?

texts:
Just stepping into complexity theory, I am befuddled by this notion of a certificate and can't find any utility of this concept.

From my understanding, a certificate is used when you are trying to ascertain whether a problem is NP...a problem is NP if you can verify a p-time solution exist or not (co-NP). I cannot see why you would need a certificate to perform this solution finding. And how is certificate different from "verification".

For example, if I were to try to prove whether all elements in a set is divisible by some number (say 3). Say I then brute force divide all elements by 3 and sees that indeed all elements in this set is divisible by 3. Now where in this process would a certificate come into play?

Also, how would you go about to physically construct a certificate?


texts: Computing the right tangent of two convex hulls

texts:
My question deals with the algorithm of computing the convex hull in 2D by Preparata.

Let us assume we have two sets, $A$, $B$, of points in the plane. Let $CH(A)$ and $CH(B)$, denote the convex hulls of the two sets, A and B respectively. And suppose that $y(a) < y(b)$ for all $a \in A$ and $b \in B$.

Let $CH(A) = \{a_{0},...,a_{n}\}$ and $CH(B) = \{b_{0},...,b_{m}\}$ such that we have indexed both sets to be clockwise sequences.

Now there is $k$ such that $x(a_{k}) = \text{max}(x(a_{i}))$ for all $ 0\leq i \leq n$ and $j$ such that $x(b_{j}) = \text{max}(b_{l}))$ for all $0 \leq l \leq m$.

Now our first task is to find the common tangents of $CH(A)$ and $CH(B)$. My question is about finding the right tangent.

Now let $\alpha_{i, i+1}$ denote the slope of the two points $a_{i}$ and $a_{i+1}$; $\beta_{j,j+1}$ denote the slope of the two points $b_{j}$ and $b_{j+1}$; $\gamma_{i,j}$ denote the slope of the two points $a_{i}$ and $b_{j}$ (all indices are taken mod n and mod m).

Suppose $a_{i^{*}}$ and $b_{j^{*}}$ denote the two endpoints of the right tangent.
Preparata states the two endpoints of the right tangent satisfy the following:

(1) $i^{*} > 0: \alpha_{i^{*},i^{*}+1} < \gamma_{i^{*},j^{*}} \leq \alpha_{i^{*}-1,i^{*}}$

(2) $i^{*} = 0 : \alpha_{0,1} < \gamma_{1,j^{*}}$

(3) $j^{*} > 0: \beta_{j^{*},j^{*}+1} \leq \gamma_{i^{*},j^{*}} < \beta_{j^{*}-1,j^{*}}$

(4) $j^{*} = 0: \beta_{1,2} \leq \gamma_{i^{*},1}$

However I found that if we take $A = \{(0.2,0.2),(0.3,1.3),(1.2,1)\}$ and $B = \{(2,2),(2,3),(2,3)\}$ then we have the following picture:

We see that the left endpoint (i.e. the endpoint in $CH(A)$) of the right common tangent should be $(0.2,0.2)$ and the right endpoint (i.e. the endpoint in $CH(B)$) should be $(3,2)$ .

However the criterion that Preparata claims does not select $(0.2,0.2)$ as the left endpoint, since it does not satisfy $(2)$, but $(0.3,1.3)$. Why does this occur? Does Preparata's algorithm have some other claim that it needs to be correct?

Here is a link to the original paper:

http://www.cs.jhu.edu/~misha/Spring16/Preparata77.pdf

The section I'm referring to is called "Merge Algorithm for Two-Dimensional Sets."


texts: $k$-partitioning problem via brute force

texts:
Given a set of non-negative integers $A = \{a_1,a_2,\dots,a_N \}$, the $k$-partitioning problem is to partition the numbers into $k$ sets $\{A_1,A_2,\dots, A_k\} $ such that the deviation:
$$ \underset{j,k}{\text{max }} \left|\sum_{a_i \in A_j} a_i - \sum_{a_i \in A_k} a_i \right|$$
is minimized. Is there any non-trivial upper bound that can be formulated for the minimum deviation that $A$ admits (this would not be computable as the decision problem is in NP)? Possibly in terms of $\underset{a \in A}{\text{max }} a$?


texts: Checking the existence of a pattern in a given prefix

texts:
I need to design an algorithm that given a string $T$ of length $n$, performs $O(n)$ preprocessing, and can then answer queries of the sort "does a string $P$ of length $m$ appear in $T$ before position $k$" in time $O(m)$. The algorithm should use a suffix tree.
Unfortunately there are not any good bioinformatics books with fair examples and practical methodologies. Dan Gusfield's book does not offer a solution manual.


texts: Is emptiness of the intersection of the languages of two TMs decidable?

texts:
Let

$\qquad \mathrm{DISJOINT} = \{ \langle M_1,M_2 \rangle : M_1, M_2 \text{ are TMs and } L(M_1) \cap L(M_2) = \emptyset\}$.

How do I know if this language is decidable or not? And How do I prove my answer?


texts: Why does the BFR (Bradley, Fayyad and Reina) algorithm assume clusters to be normally distributed around its centroid?

texts:
I'm following a course on data mining based on the lectures from Stanford University and the book Mining of massive datasets.

On the topic of clustering, the BFR algorithm is explained with this video.
I understand how the algorithm works, but I am unclear on the reason why the algorithm makes the strong assumption that each cluster is normally distributed around a centroid in Euclidian space.

The video explains that the assumption implies that clusters look like axis-aligned ellipses, which is understandable as the dimensions must be independent.
I've watched the video a few times, and read the section in the book (freely downloadable using the first link) on pages 257-259, but I'm unable to grasp why that assumption is made, and why it has to be made.

Could someone explain this for me?


texts: Neural Networks: Simulate the working of Dynamic Fixed Point representation of the weights on hardware

texts:
I am looking to implement a neural network on hardware using Verilog. I have completed and tested with floating point representation and a 20 bit fixed point representation. I want to further reduce the memory utilisation by using dynamic fixed point. I want to identify the less important weights, and assign them a smaller bit-width, while keeping the more important weights with a higher bit-length.
How can I identify the more/less important weights?
What I can think of is, reducing bit-width for all the small weights [-0.001, 0.001]. But isn't that like pruning?
Thanks!


texts:
I am trying to implement a BTree in a pointer-free language as a proof-of-concept. However, a question came to my mind: every time I need to split a node, I need to do a deep copy of all the nodes in the (new) left sub-tree and right sub-trees, thus (I think) destroying the advantages of using a BTree. If I had pointers, I would just point the new root to each of the new half nodes. Is that correct?

Also, I thought about trying to replicate the pointer behavior by having keys to be integers which are a list index, and that list would contain all nodes, representing a disk, for example. Although that would also destroy the advantages of a BTree, I could implement some data type that is equivalent to a list, but is written on the disk, and then everything would be ok. Is that right?


texts: Genetic Algorithm - Fit max circles inside box

texts:
I am using a genetic algorithm to find the best way to pack circles inside a box without each touching the others and filling as much space as possible. My doubt is if an individual from a generation must be a circle or all the circles.

Can anyone help me on how would I go from here? Thank you


texts: How does AlphaGo perform when increasing the size of the board?

texts:
I recently watched AlphaGo, a documentary on the recent defeat  by the best human player of Go by a computer, AlphaGo.
The commentary  the beginning points out this was ten years ahead of schedule (which of course doesn't take any account of the actual history of predictions by computer science about when computers would begin to beat human players. The first prediction being on the order of a decade perhaps sixty years ago now).
Another commentator noted that after human players had a chance to study AlphaGo's playing style they expected human performance to improve against AlphaGo. This will take some time.
After AlphaGos win, a few years ago, I glanced over a paper by the programming team behind AlphaGo where they had a graph displaying its performance by Dan playing strength. Notably, and one would expect, it began to level off eventually. Of course another standard method of gauging AlphaGo's true strength is by the standard method of handicapping by allowing its opponent to freely place n stones on the board. Typically, the difference between dan levels is around 1/3 to 1/4 of a handicap stone.
Another way of gauging AlphaGo's performance, which simply isn't suitable, for humans, is to look at how it performs once the board is expanded say from 19 x 19 to 31 x 31 and then higher, 51 x 51 and even 101 x 101 to see whether it's performance stays steady - or degrades.
A further way is by expanding the dimension of the game, from a 2d board game; to a 3D board game and higher. This most likely will require changing the go rules for an eye - again something that AlphaGo is not capable of suggesting on its own - without human input.
Q. Have these experiments been carried out? If not, can they carried out?
A notable feature of Go is that it's very game is such that these changes are easily imaginable - and perhaps not imaginable by AlphaGo.


texts: How to use Clarke and Wright saving algorithm to afford heterogeneous fleet?

texts:
I want to solve Heterogeneous fleet in vehicle routing  problem using the Clarke and Wright saving algorithm. After reading many literature I found two options:

Explicit and early assignment for the route.
Using saving algorithm sequentially, and iterating over all generated routes to fulfill capacity constraints.

But I'm unsure about these two options. Is there any other solution?


texts: What is an example of a (simple) tail recursive algorithm that doesn't use a helper function?

texts:
I know one can compute things using tail recursion with helper functions like:

let sum_helper n accumulator =
match n with
| 0 -> accumulator
| _ -> sum_helper (n-1) (accumulator+n-1);;

let sum_tail n = sum_helper n accumulator 0;;

sum_tail 3;;

which gives:

# sum_tail 3;;
- : int = 3

but I wanted an example of something that didn't use a helper function (idk if the above can be made without a helper function).

Ideally something simple so to understand the concept better since I'm trapped into thinking all tail recursions look like that.


texts: Best improvements to do to the DPLL SAT algorithm

texts:
As part of a college class, I'm asked to improve the performance of a basic DPLL sat solver. I'm already provided a basic, slow working version (essentially the DPLL algorithm; furthermore, to select the next variable, it just loops an array and gets the next unused  one). I have been reading papers on ways to improve it, but I'm a bit overwhelmed by the amount of optimizations one can do. I'm not looking to make an extremely efficient solver; just something that works better than a plain basic DPLL one. I have read about 2WL, VSIDS, and a handful more. Which optimizations will give me the most performance without overcomplicating things? The input with the most variables that I have to solve is of the order of 300, with 1500 clauses, if that is of any interest.

I apologize if something similar has been asked before, but I haven't found anything. I would appreciate any other tips if you guys have. Thank you.


texts: Does the following operation makes the language regular?

texts:
I came across a question stated as $L = \{wxwy \mid w \in \{0,1\}^* , x,y \in\{ 0,1\}^* \}$ is regular and I have no problem understanding it.

However I thought what could happen if the language is modified to $L = \{wxw \mid w \in \{0,1\}^+ , x \in\{ 0,1\}^* \}$.

In my opinion the above language is regular and it represent not what is seen by naked eyes, by that I mean the above language could be written as $L=(0+1)^*$. Please correct me if I am wrong.


texts: I want to design a context free grammar for the following

texts:
This below language

$$L = \{ w \in \{a, b\}^n : \lvert w\rvert \text{ mod } 3 = 0 \}$$
where $n \geq0$.


texts: route and/or packing optimization algorithm

texts:
What type of problem would this question fall under, are there known algorithms/heuristics for it, what would be good resources to learn more about solving it?

Given:

a list of items each with a destination location: the number of items per destination is unbounded (and can be zero for some locations). All items are at a central location.
a number of destination locations, each awaiting a set number of the items: the number of locations is finite, and small [under a thousand]
a number of couriers, all at the same point initially (the same initial location as the items); each courier has a maximum number of items they can carry: the number of couriers is very small [a dozen]
the duration of travel between all locations [all couriers travel at the same speed]

Problem:
minimize the maximum wait time of each location [the time it takes for all the items due at that location to be delivered]
by allocating items to couriers.


texts: Curry Howard correspondence and Church-Turing thesis

texts:
Curry-Howard correspondence states the equivalence between logic/deduction and types/programs.

The Church-Turing thesis states the equivalence of some models of computation. Specifically, all computable functions can be written both on a Turing Machine and in Lambda Calculus.

Not all logics are equivalent however. 2nd order logic can quantify over sets whilst 1st order can't.

Can someone explain the dissonance? Can some computable functions be
expressed at a "higher-level" but not at a "simpler-level"?

[CLARIFICATION]

If I define a model for computation off say 2nd order logic whilst the Turing Machine is a model for 1st order logic, then does that mean my hypothetical language can compute "uncomputable" functions? It appears so to me because 2nd order logic is more powerful than 1st order logic. This is clearly nonsense because Haskell is based off a flavor of 2 order logic (system F with extensions) but isn't more powerful than say C: any program achievable in Haskell is achievable in C. The mapping (or equivalence) between logic and computation does not appear to preserve the notion of strength: 2nd order logic is stronger than 1st order logic but programming languages off 2nd and 1st order logic have the same strength. Does that make sense?

The only conclusion I can come to is that the relationship between logic and types is not a straightforward mapping. The Turing Machine is not based off any specific logic and that any logic/deductive system can be mapped to the Turing Machine. Can you confirm?

[CLOSING WORDS]

I think that my mistake is in not realizing that there is a large divide between the colloquial "program" and programs in the context of types.

Haskell which is based on a stronger, more expressive type system does indeed provide stronger, more expressive programs. These programs are stronger in the sense that more can be guaranteed about them (in the same sense as "type safe"). This does not mean that Haskell can "compute" more; it is still merely Turing complete.


texts: Implementing a symbol table with a hash table and a stack

texts:
I was in class today, in a Language Translations course, thinking about the best way to write a symbol table for a compiler. My professor showed us a hash-table with linked-lists connecting different levels of "blocks", which are usually { } curly brackets in languages such as C.

My thought was, what's wrong with using stacks instead?

For example, here's some code:

int x = 5;
float y = 3;
{
    // stuff
    int x = 100;
}

Would I not be able to start off, hashing x, pushing it onto a stack struct as

struct symbol_def{
    char * type;
    val_type value;
}

I don't know how to do a dynamic type for the value (if the value is even needed in there).

When the second x comes in:

int x = 100;

Then we just again hash x, push onto the stack.

At any given moment, the top of the stacks are the current scope's visibility.

The issue might come with popping however. How do we pop off the right things? That one I'm not entirely sure about, and could be a fatal flaw of this design.

In theory, this would be a lot of O(1) jobs (hash table lookup, pushing, popping, peeking).

Let me know your thoughts. Maybe I'm missing something here, or maybe this is how it's really done already.


texts: Understanding the rules of parsing table construction

texts:
I'm studying top-down parsing, especially LL(1) parsing. However, I cannot understand what is the meaning of rules.

Example grammer is like this

S → ( S ) S | $\epsilon$

How can I derive like below table?

I read all explanations of textbook, but I cannot totally understand the process of table construction. Are there anyone who can explain more easily about this process?


texts: Given a random number generator rand5() generate gen7()

texts:
Given a pseudo random number generator rand5() that generates a random integer in the set [0,1,2,3,4], how would someone use this to generate a function rand7() that outputs [0,1,2,3,4,5,6] with equal probability.

I was thinking of approaching it this way: reduce the problem to generate number from 0 to 6 using a coin.

We can represent [0,1,2,3,4,5,6] using bit-wise from 000 to 111.
Selecting each bit from LSB to MSB can be done using tossing a coin.
However, if we continue in this fashion from LSB to MSB then we
can get all bits as 111 which is decimal 7. So, in the case of MSB
if we get 1 then discarding it and starting again should give
the result? Right?

Reducing the problem from rand5() to coin can be done in this way: if the number is 0,2 then we can consider it as head and getting 1,3 can be considered as tail.

Is my solution right?


texts: Is the union of a non-regular and a regular language regular?

texts:
I am studying Automata and stuck in a question that says:
Is the following a regular set {a^p, where p is prime} U {even-length strings}?

As we see here this language consists of two sub-languages. The left side one is infinite, and by using prove by pumping lemma, we will wind up that it is not regular.
However, the  right side one is also infinite but we can build the fsa for it and the regular expression is ((0+1)(0+1))*. So, it regular language.

What I stuck in is that When we Union regular language with non-regular language what is the the final result will be????

From the OR truth table it says to return TRUE value, either of them TRUE or both.


texts:
My Problem is like this:

I have a physical layout represented as a graph. The Nodes represents hooks/ducts where a wire can anchor and Edges are the possible connection between 2 nodes from where wire can go.
There are some special Nodes, called splitters, from where a single wire can be splitted to  2 or more up to k. The k can be taken constant for now but it varies from node to node. Not all nodes are splitters.
There is one source of power from where a wire will emerge. It is the source. The wire has to be taken to n sinks.
An edge can take any number of wires traversing through it in either direction.
The the total wire length has to be minimized.
The nature of graph, planar or euclidean is not known.

Example: Below is a sample network. Nodes are named as numbers and edges are provided with equal weights of 1. Source is Node1 and Sinks are Node5, Node9 and Node13. In case 1 Node6 is Splitter node. In case 2 Node6 and Node4 are splitter nodes. The splitter node's k=3, i.e., it can take in one wire and split it out to 3 wires.

Case 1. Only one splitter Node. It makes sense to split at Node6.

Case 2. Two splitter Node. It makes sense to split at Node4 instead of Node6.

I am looking for different strategies to find out a generic solution for this problem. The graph presented here is of a smaller scale as compared to the problem in hand. The graph is static and can not be changed (i mean the solution should not suggest any new edge or propose new splitter location ).
Any reference to research paper published on this kind of problem is also welcomed.

Case 3. Two splitter Node. It makes sense to split at Node4 and Node14. Note that this case has edge weights changed for Edge 8-12, 6-10 and 10-11. The important thing in this case is retracing of a wire after getting splitted from Node14.


texts: Dynamic programming: Knapsack with repetition, Find the number of redundant machines

texts:
I have just started to learn Dynamic Programming, and so far I have studied the few basic concepts; longest common subsequent problem, edit distance problem and the knapsack problem. I have attempted to solve the following exercise that is related with this topic, and so far I think I have a way how to approach it , but I am stuck at one point. Please, if you can, read my solution and tell me whether I am doing something wrong. I absolutely do not want you to solve it for me, just give me some help/hints.

A mission-critical production system has n stages that have to be performed sequentially; stage i is performed by machine M_i. Each machine M_i has a probability r_i of functioning reliably and a probability 1-r_i of failing (and the failures are independent). Therefore, if we implement each stage with a single machine, the probability that the whole system works is r_1,r_2,...,r_n. To improve this probability we add redundancy, by having m_i
copies of the machine M_i that performs stage i. The probability that all m_i copies fail simultaneously is only (1-r_i)^(m_i), so the probability that stage i is completed correctly is 1-(1-r_i)^(mi) and the probability that the whole system works is prod(i=1,n){1-(1-r_i)^(m_i)}. Each machine M_i has a cost c_i, and there is a total budget B to buy machines. (Assume that B and c_i are positive integers.) Given the probabilities r_1,...,r_n, the costs c_1,...,c_n, and the budget B, find the redundancies m_1,...,m_n that are within the available budget and that maximize the probability that the system works correctly .

________________________ MY PROPOSED SOLUTION

We need to make sure that all the given probabilities are different from 0, meaning for all r_1 !=0 (if we had a probability 0 the system would not work)
We must make sure that we have at least one machine of each type, meaning we have one copy of each machine (if we do not have a certain machine, like in point 1 the system would not work). In addition, by having already a copy of machines from m_1,...,m_n, the total cost of this machines would be sum(i=1,n)=c_i. This means that from the total budget B we need to subtract this cost, and get the extra budget for the redundant machines. B_extra= B-sum(i=1,n)=c_i
To find the redundant number of machines we just need to model the problem as knapsack. Subproblem: K(c) ->maximum probability that a system works correctly. Recursive relationship:

for c=1 to B_extra
 K(c) = max{K(c-c_i)*(1-(1-r_i)^(m_i)):c_i<=c}

Now, the points where I am stuck and need help are:

The way I am defining the problem, is it correct or am I missing any special case? I think that the recursive relationship should work fine; any reason why it shouldn't?
How should I keep track of the number of m_i machines. I know that the initial value for each m_i is one (from point 2 we need at least one copy of each machine). Should I just keep track of another variable in the problem K(c, m) and every time increase m_i++?


texts:
I read on the internet that it's possible to reduce clique to vertex cover. Almost everyone use this theorem:

  if a graph $G$ has a clique of size $k$ then the complement of $G$ has a vertex cover of size $n-k$, where $n$ is the number of vertices.

Consider the graph on five vertices and the following edges: a clique on $\{1,2,3,4\}$ and $(1,5),(2,5),(3,5)$. The complement of this graph has only one edge, and it does not cover the set of vertices.

Is the statement I quoted correct?


texts: Finding the lightest simple path in trees with integer weights

texts:
A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest paths where the length of the path is equal to sum of all edges weights.

I know that in a tree there is only one simple path between every pair of nodes.
So, even if you try every pair of nodes finding the path between then, you would have an $O(n^3)$ algorithm.

A better way is to find for every node the cost to every other node in a single visit. This lowers the algorithm to $O(n^2)$.

Is there any algorithm that runs in linear time?


texts: what is the best practice for turing test

texts:
I'm working on a AI project which generates poems in Turkish language like this project: https://github.com/schollz/poetry-generator

It's a successful project but it's a template based poem generator. You can't select a topic for poem generation. It generates poems randomly with hardcoded templates and words.

In my project I also have some templates and huge lexicon but there is a difference. User can select a topic or give a sentence to identify poem's theme. Program does word similarity analyse and select word according to these results.

I'm not finished this project yet. But I believe I will soon. At the end, I want to do an experiment/turing test in order to calculate it's success ratio. But I'm not sure which way should I follow.

My idea: I will publish an experiment announcement in my university. I won't say it's about AI or computer science. It will be like poem contest or something. I will show the human generated and ai generated poems to human subjects. They will score the poems according to their taste of art. After the first phase is finished, I will tell them some of the poems were generated by an AI. After then they will try to identify AI generated poems.
I'm not sure it's a suitable turing test. What is the best practice for this one?


texts:
I have a problem with following task: $4COL \in PTIME \Rightarrow 3COL \in PTIME$.

Is there any elementary proof to do it?


texts: What does a solution to the Rectangle-Fit problem look like?

texts:
I've been learning about NP-Complete problems, and came across the rectangle fit problem. Basically, the rectangle-fit problem is the problem of whether or not a set of 2d rectangles can fit in a larger 2d rectangle. What I have not been able to find, or solve myself, is what a possible solution looks like.

Say there is a set of rectangles $R$ and a large rectangle $T$, how do I indicate a possible placement of all rectangles in $R$ into $T$? I was thinking coordinates, but there is no assumption $T$ is defined as a graph. At a high level, how would I denote where/how each rectangle should be placed?

I am not asking for how to solve this NP-Complete problem. I am asking how do I define the placement of rectangles in $R$ for a candidate solution. I saw an academic paper saying that it is obvious there is a polynomial time verifier for the problem, but there was no explanation of what the certificate the verifier is using looks like.

Particularly, I was looking at: http://ranger.uta.edu/~weems/NOTES5311/hw3ansold.pdf for the verifier.


texts: Blind sorting an array with a singular sort function?

texts:
I am doing some interview prep, and I came across a question that really stumped me, and it didn't provide an answer.

The premise of the question was as follows:

You are given some unsorted array A of size n. You are not allowed to access the array, read values, or compare the values.

The only manner in which you may interact with said array is with a BlockSort() functions, such that calling BlockSort(index) will automatically sort the elements within the inclusive bounds of [i,i+u] for some arbitrary but fixed u, such that u≥1.

Sort A with O((n/u)^2) calls to BlockSort.

My initial approach to this question was to mimic Bubble Sort, except stagger the calls to BlockSort, such that each successive call overlaps with one element of the previous call, (i.e. BlockSort(0,u), BlockSort(u,2u)...etc.) and then after iterating like that through the array once, you are left with the global maximum at the end of the array, and an unsorted array of size n-1, and then you can recursively solve the problem.

This has a time complexity of O((n^2)/u) though.

I have thrown an hour or 2 at the problem, and I can't quite see how they achieved O((n/u)^2).

Is there anything I could think about to get to the answer?


texts: Computing optimal assignments using little memory

texts:
I have two lists where each item in the first list has a rating for each item in the second.  I need to determine an optimal matching (or the best x scenarios) where items are matched, but each item can only be matched once.

For example, there are 150 movies available, 100 people, and each person has rated each movie between 0 and 100.  Once a movie is given to a person, it is no longer available for another person.

In this example, I'd like to find the scenario where the person/movie with the lowest rating is the best rating possible.  Then, the average of all ratings is the best possible. Ideally, no one person would be unhappy with their movie (data permitting).  There might be multiple optimal solutions, so I'd like to determine and rank the top 5 scenarios.

I plan to implement this in node.js and Javascript, so the memory footprint of data structure(s) is a factor.

What would be the optimal data structure and approach to solve something like this?


texts: Design a 1-bit ALU using the smallest MUX possible

texts:
Implement a one-bit ALU which takes two one-bit operands $a_0$, $b_0$, and produces a one-bit output $z_0$.  The ALU has a two-bit control input $cont_0$,   $cont_1$, with codes as shown below.

|$cont_0$|$cont_1$ |selects
|--- 0 ---|--- 0 ---| AND
|--- 0 ---|--- 1 ---| NOR
|--- 1 ---|--- 0 ---| OR
|--- 1 ---|--- 1 ---| XOR
(Sorry I didn't know how to make a properly formatted table)

The questions is:
Design the ALU using the smallest MUX possible.

I made a truth table as a start, then I came up with an ALU model, but I am not too confident with it. Any input on how to tackle this problem is appreciated.

Here's the truth table I made:

And here's the ALU that I'm doubtful about because it seems too easy of an approach.


texts: Why is deciding regularity of a context-free language undecidable?

texts:
As I have studied, deciding regularity of context-free languages is undecidable.

However, we can test for regularity using the Myhill–Nerode theorem which provides a necessary and sufficient condition. So the problem should be decidable.

Where is my mistake?


texts: Is there a complexity class “BQP without error”?

texts:
I was wondering if there is a complexity class for problems that can be solved efficiently by a quantum computer such that it always gives the right answer? For example the Deutsch-Josza algorithm never fails. Another way of asking would be: is there a class (call it Q) such that Q is to P what BQP is to BPP?

I guess classically the question also makes sense: is there a class for problems that can be solved efficiently by a computer with access to randomness and never making an error? (I suspect this is simply equal to P?)


texts: Testing graph property on enumerated graphs

texts:
I wanted to verify some graph properties on all possible graph enumerations (or graphs satisfying certain properties). There is a list of all the graphs upto 10 vertices here, but that is not sufficient for my use.

So I had two questions:

Which would be the most user friendly and RAM efficient program/library to work with graphs, if I already have the graph with me.
What would be an easy and efficient way to generate graphs satisfying certian conditions. I tried to search about Nauty over net but it is difficult to find a tutorial.


texts: Algorithm to separate circles to reduce collision the maximum between them

texts:
I'll try to do my best to explain this.

I have X circles (from 2 to 4) which can move around smaller pivot circles. The pivot circles are fixed and cannot be moved once they are in the "field". Pivot circles are never created colliding with other pivot circles. Something like this:

Red are pivot circles (fixed) and orange are the normal circles (displace without exiting the pivot circles).

Now if I put two pivot circles near, the algorithm should do something like this:

This is pretty easy to achieve. Detect colliding circles and displace them the needed amount. Because red circles never collide, the orange circles are never going to break the "do not exit the pivot circle" rule.

The problem comes when 3 or more circles come into play. Because they cannot exit the pivot circle zone, so there should be some vertical/horizontal movement, like this:

I think this is the least colliding I can achieve when 4 pivots are next to the other. I created this manually but I'd like to know if there's already an algorithm to detect this efficiently without making a lot of detections/passes to achieve the least colliding factor, as I don't like everything that I'm thinking on.

The best I can think of is to simply do a loop where I detect all circle collisions, then displace the circles the amount needed for them to avoid the collisions the maximum possible, then repeat the loop, and repeat until I find that the "collision factor" is not reduced anymore for the next X steps. To make the circles go "up" and "down" I can try to create a bit of noise each time, and the algorithm will do the rest to move the circles up and down. Also, instead of noise I can try to detect if they are colliding "horizontally" or "vertically" and add a bit of horizontal/vertical movement when a circle with 2 or more collisions has a perfect horizontal/vertical collision.

I don't like this much actually, so well, here I am hehe.

I can't think of something, but I'm pretty sure that there's something that can be calculated with one step, instead of looping the same step multiple times, but I'm really stuck and nothing comes out of my head.


texts: Is order of matrix multiplication affecting numerical accuracy of the result?

texts:
I have to multiply three matrices of floats: A (100x8000), B (8000x27) and C (27x1).

Is there any difference in accuracy between A(BC) and (AB)C?
If yes - how may I determine the more accurate multiplication order?
Speed is not a factor here.

Matrices A and B contain 8000 samples of (respectively) 100 and 27 features.


texts: Is $\{u u^R u : u \in \Sigma^*\}$ context-free?

texts:
Given a finite alphabet $\Sigma$ with more than one symbol, is $L = \{u u^R u : u \in \Sigma^*\}$ context-free? ($u^R$ is the reverse word of $u$)

I tried to show it wasn't context-free by using the pumping lemma but I'm out of ideas.


texts: Data structure and algorithms for a medical diagnosis software

texts: For an academic question, I plan to design a medical diagnosis system. Given a description of symptoms, produce a list of probable diseases (with closeness matching). I'm having some trouble finding papers for getting started. Which algorithms and data structure should I consider?


texts: Is a single starved process considered deadlocked?

texts:
In regard to the critical section problem, an algorithm that switches between allowing one of two processes, P1 or P2, to complete their critical section would cause starvation for P1 if P2 stayed in its non-critical section forever.

However, if P2 exited, descriptions of this algorithm also classified it as
only starvation. Since no processes in the remaining set {P1} are allowed to run their critical section, could you not say that the system is also deadlocked? Is deadlock only in context of resource allocation?

I know the standard conditions for deadlock include circular wait with more than one process, however in my search I have seen people describe deadlock in situations where a semaphore is never released before a crash of the second process etc. so I wanted to clear-up this specific case.


texts: Can I construct a Turing machine that accepts only its own encoding?

texts:
Is the set $S$ = $\lbrace M \mid M \text{ is a Turing machine and }L(M)=\lbrace \langle M\rangle\rbrace\rbrace$ empty?

In other words is there a Turing machine $M$ that only accepts its own encoding? What about a Turing machine that rejects only its own encoding?


texts: When using resolution variable elimination to simplify a cnf, does that change the truth values of the other variables?

texts:
When you use resolution variable elimination to preprocess/simplify a formula in cnf form the resulting formula is equisatisfiable.

What I wonder about is if I can use this technique to remove variables i don't care about while leaving the truth values of the variables I care about untouched in the final model I get from the sat solver.


texts: Terminology needed for the computational solution to the Rubik's Cube

texts:
I apologize if this question is out of the guidelines of this forum. If it is please let me know and I will abstain from requesting definitions and terminology.

Hello!  I am currently writing a program to find the shortest path solution in a randomised Rubik's Cube. There is a certain language/search based methodology that has caught my attention, and which I would like to apply to the solution, but I am unaware of what kind of terminology I should be looking up.

THE METHODOLOGY:

The methodology is one where different languages are developed to satisfy different aspects of the cubes solution. For instance, we might find a language/grammar which appropriately describes/generates all transformations which move one block of the cube to some position we want it to be. We may then find another language which satisfies the movement of another block to some position we want it to be. The language which satisfies both of these languages is the one which generates transformations which will move BOTH blocks to where they are supposed to be.

WHAT I WOULD LIKE TO LEARN MORE ABOUT:

It is in this sense that I am interested in learning more about how languages can be tested against each other in order to CONSTRAIN the otherwise unweildly "search tree" that would be required to be derived and searched in order to find the solution.

At the same time I would like to build a symbolic vocabulary which would allow me to compare the different pertinent variables (runtime, memory size, etc.) of different tree search constraint methodologies, particularly language based methods (as I have poorly defined them).

I am also particularly interested in the methodologies that can be used to detect patterns in the strings which are satisfying two seperate languages so that a third language which satisfies both can be developed.

Also, I would like to learn more about how we can show that one language is mutually exclusive to another language.

I am particularly interested in terminology so that I might do research on the Internet, however I would also greatly appreciate any book recommendations. Thank You!


texts:
I have $m$ machines and $n$ jobs. Each machine has a load capacity. Each job can be only handled by either one or two machine, and each job takes some time to finish. After it finished, new jobs can be assigned to that machine.

I am trying to find an optimal way to assign each job to each machine by sorting all the jobs by load capacity, after that filling jobs into each available machine. After all machine is assign, I will looking for the min of all the times to complete jobs. Then subtract it from all waiting time to find the next available machine.

So by this layout machine m1 will be assigned job a1,
m2:a2,
m3:b1,
m4:a3,
m5:empty,
and m6:a4,b2,b3.

Is the a way to mathematically proof the optimal with respect to time?
It's similar to job shop problem but instead of only there is only 1 machine of each kind, mine has many
developers.google.com/optimization/scheduling/job_shop


texts:
I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word.
What does "lookahead" refer to? How does this relate to LL, LR, LALR? Basic examples would be great, as I'm not well versed in this subject.


texts:
If i have a propositional logic formula, every time i add a variable the number of interpretation grow up by 2.

So if i have a propositional formula with 3 variables i have 8 interpretations.

So, is the time complexity of the SAT problem of propositional logic a $O(2^{x})$ ?


texts:
I'm currently working on a data processing algorithm which involve (for now) grabing values from bidimentional graphs (x;y values) by hand. It is used to do polynomial fitting.
I speak about this kind of graph:

Because the amount of data to extract from these graphics can be very huge (multiple lines with different parameters) I realised that it could be really time consuming for the user. All the graphs we have are pictures.
I would like to know if in the huge world of image processing something exist for extracting a finite number of points with their coordinates from a graph.
Thank you.


texts:
Suppose I have a set of n ordered tuples, all of the same, fixed dimension.  The tuples' values are integers, with #s indicating an integer I don't care about.  For example:

  { (1,2,5), (4,2,3), (1,2,#), (#,2,3) }

Tuples can be combined so long as they don't disagree about anything.  For example, (1,2,#) and (#,2,3) can be combined into (1,2,3).  Therefore, we can simplify the above set by combining the last two elements:

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

The goal is to simplify the set as much as possible.  We can't simplify from here any more, but by simplifying in a different way, we could have done better by combining the 1st with the 3rd and the 2nd with the 4th (hence, this problem is not convex):

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

My question:

Is this a well-known problem by a different name?  (E.g., give a reduction from some NP-complete problem, perhaps?)  It's related to the set-cover problem, but somewhat different since elements can be combined and not everything need be chosen.
What algorithms can I use to solve this, even approximately?  Speed is important; I solved a similar, simpler problem in expected O(n); equivalent performance would be ideal.

Call tuples containing at least one # "free tuples" (vs. "complete tuples").  Observation: WLOG every tuple is free: combining a free tuple with a complete tuple or a complete tuple with a complete tuple is never suboptimal, so we can preprocess all such combinations first, then remove all complete tuples--since by construction, nothing can combine with them.


texts: Does the specific size of matrices affect the performance of matrix operations?

texts:
I was reading DeepMind's paper on I2A's and realized that the sizes of the hidden layers in their model were all like 32, 64, 256, and so on: all powers of 2. I have found the same thing in other papers.

Is there any performance reason for it? Maybe related to data structure alignment?

More concretely, I would like to know if I should use this "special" sizes when training my own models.


texts: Find if there is matrix that satisfying the following conditions

texts:
Given a matrix $A_{n\times n} = \{a_{ij}\}$ such that $a_{ij}$ is a non-negative number and given 2 vectors $(r_1,r_2,...,r_n)$ , $(c_1,c_2,...,c_n)$ such that $r_i,c_i\in \mathbb{Z}$ define an efficient algorithm that will determine if there's a matrix $B_{n\times n} = \{b_{ij}\}$ , $b_{ij} \in \mathbb{Z}$ and

for every $1\leq i \leq n \sum b_{ij} = r_i$

for every $1\leq j \leq n \sum b_{ij} = c_j$

and

$0 \leq b_{ij} \leq a_{ij}$

Thought something with dynamic programming but didn't manage to solve it.


texts: course suggestions to learn background for sensor fusion

texts:
Specifically what topics in probability would give me the background I need to understand sensor fusion?
I'm looking for a college class that would include these topics, so I'm wondering what the class might be called or what might be in the description.
By any chance do you know of a community college that offers a good class that would cover these topics?
To explain a bit more, I'm a rising sophomore computer science major, but I'm on leave from my university because of the pandemic. I want to take a class in the meantime, and since many community colleges are online at this point, I have many options, but I'm not sure exactly what I should be looking for.
Thanks for your help!


texts:
I am looking for a good heuristic function for solving a 2D $n\times n$ Rubik's cube using A* search. There is a game already in the play store.

The rules of the game:

Swiping LEFT means the leftmost cube of that row will come to the rightmost position in that row. All other cubes will be moved one position to the left. So it's like a circular shift. The same type of rules apply for UP, DOWN and RIGHT swipe.

The above pictures are for a $3 \times 3$ Rubik's cube, but I'm interested in algorithms that work for the general $n \times n$ case, so the state space might be fairly large.

2 possible heuristic functions that come to my mind:

(Total number of mismatches with the goal state) / (number of rows or columns or colors)
Average Manhattan distance of each cube with the goal state

Which will work better? And why? Is there any better heuristic function for this problem?


texts: Find an optimal matching in a complete graph

texts:
I have a complete edge-weighted graph with $n$ vertices (and therefore $n\cdot(n-1)/2$ edges). I want to find a complete matching (i.e., perfect matching) in which the quotient $sum_G/A_G$ is maximal, where $sum_G$ is the sum of all the edges-weights in the matching and $A$ is the amplitude of the edges-weights in the matching. That is: If the weights of the matching's edges are $G = \{g_1, g_2,…,g_{n/2}\}$, then $sum_G = \sum_{i=1}^{n/2} g_i$ and $A = max(G)-min(G)$.
I have an algorithm that solves it using $O(n^4)$ "find a matching with maximal weight" operations:

For each pair of two edges (A, B) in the original graph, presume that the amplitude is in this pair, i.e. $A = weight_A – weight_B$.
Leave only the edges whose weights are between $weight_A$ and $weight_B$.
Find a complete matching with maximal weight for this sub-graph.
We got $O(n^4)$ matchings, we pick the best one.

The question: Is there a better way (in asymptotic notation) to find a solution?


texts: How does one make an unambiguous context-free grammar for arithmetic expressions?

texts:
Say I have a context-free grammar defined by the following rule.

$$
\langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle EXPR\rangle \times \langle EXPR\rangle~|~(\langle EXPR \rangle)~|~x
$$

This grammar is ambiguous since, for instance, I can generate the string $x + x \times x$ via more than 1 leftmost derivation.

How could I make this grammar unambiguous? Should I make sure that no $\langle EXPR\rangle + \langle EXPR\rangle$ is evaluated after a $\langle EXPR\rangle \times \langle EXPR\rangle$ as such:

$$
\langle EXPR\rangle \rightarrow \langle EXPR\rangle + \langle EXPR\rangle~|~\langle MUL\_EXPR\rangle \times \langle MUL\_EXPR\rangle~|~(\langle EXPR \rangle)~|~x \\
\langle MUL\_EXPR \rangle \rightarrow \langle EXPR\rangle \times \langle EXPR\rangle~|~(\langle EXPR \rangle)~|~x \\
$$


texts: Simultaneous regression of multiple curves in the same dataset or image?

texts:
I am getting the pattern shown in the picture from an experiment. To my human brain it is evident that it consists of some 20 straight lines. I need to find position and slope of all these lines (perform a regression). But I need to do it completely automatically. If this were a a single sequence I would have used RLS(Recursive Least Squares) or Kalman filter. But how can I go about if I want to make 20 simultaneous regressions that do not conflict with each other?

What would be the most generic way to solve these kind of problems (say if I have an image of 20 overlapping boxes and need to find size, position and angle of all of them, at once)? I suppose the solution is more than well-known since this would be fundamental for any image recognition, but I cannot find a generic description of the method.


texts:
I'm trying to pack hexagons, within bigger hexagons, as shown here:

For this example, I have 5 "children" to put in my "father" hexagon.

Each time I've got too many children, I would like to reduce the size (divide by 3?) of the children, to store more of them, as shown on this image (ignore the bad position quality):

Have you ever worked on this kind of problem? Is there any algorithm I could use to determine for a given hexagon size, the position for each new hexagon?

I've seen a lot of these algorithms for circle packing, but nothing for hexagon packing.

Thanks for your help


texts: Why is there no deterministic algorithm for determining the majority vote of a recursive 3 branch tree without inspecting all the leafs?

texts:
Say that we have nodes in a tree and it has a branching factor of 3. At the leaves we have a binary value 1 or 0 (which can be viewed as "votes"). Each parent computes the majority of its children and assigns itself that value ("vote").

What I want to show is that in the worst case, a deterministic algorithm will have to query the value of all of the $n = 3^h$ leaves in order to determine the value assigned to the root.

I do have the following solution which I am having a hard time understanding:

But that algorithm doesn't seem to work in some trivial cases (unless I misunderstood the algorithm).

Say that A just started querying the leaves. So it queries the first leaf and since nothing has been assigned, when it goes to its first ancestor such that at most 1 is determined, since none of his siblings (which in this case are the siblings of the parent of the leaf, the uncles) have been determine, then that leaf is arbitrarily assigned true. When it goes to the next leaf, one should assign it false so that one has to inspect the other leaf, but when if you follow what the adversarial algorithm does it doesn't work. It says to go to the parent of the currently queried leaf and in this case, since still, none of the siblings of the parent have been assigned anything, then one would arbitrarily choose true, which is bad, because it determines the parent to be true without looking at the last leaf node of that subsection!

I am wrong or am I misunderstanding what $B$ is suppose to do?

Why isn't it just optimal to always choose 1 0 1 or 0 1 0 or 1 1 0 or however A queries leaves, to make sure that it always sees two leaf, such that it has to see the other leaf no matter what (i.e. if A sees a 1 to make sure the next thing it sees in that sub section of the leafs to see a 0 etc). I don't understand why we need to consider ancestors. Why does that matter?

For completeness I will provide the full text:


texts: Reduce the running by using doubly logarithmic tree

texts: I have two algorithms $A$ and $B$ to solve a problem $P$ of size $n$. Algorithm $A$ takes $O(\log n)$ time on the PRAM using $O(n \log n)$ operations (done in parallel). Algorithm $B$ reduces the size of $P$ by a constant factor in $O(\log n/ \log \log n)$ time using $O(n)$ operations (also done in parallel). Can I solve problem $P$ using $O(n)$ operations in $O(log n)$ time? I feel it can be done using a doubly logarithmic tree (not sure).


texts: Does the language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$?

texts: Does the Context Free Language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$? Does $t$ fix $n$? I think the string belongs to this language.


texts: Is there a philosophical counterpart question to P != NP?

texts: Gödels motivation to prove his incompleteness theorems was the philosophical statement "This sentence is wrong.". Is there a philosophical counterpart to the statement P != NP? For example such statement might be "This Theorem is practically unprovable". The consequences of an existence of such theorem would be: If the sentence is true, than there is no practical way to prove it. If it is not true, then there is a practical way to prove it, hence it must be true, which is a contradiction. Since P!=NP is such a deep question, I wonder if philosophist have a counterpart question in the sense given above.


texts: The importance of the language semantics for code generation and frameworks for code generation in model-driven development

texts:
I am implementing worflow where the code in industrial programming languages (JavaScript and Java) should be generated from the formal (formally verified) expressions (from ontologies as objects and rule formulas as behaviors). What is the best pratice for such code generation? Are some frameworks available for this?

In my opinion the semantics of the programming language is required. And I should be able to do the code generation in two steps: 1) translate my formal epxressions into semantic expressions of the target language; 2) translate semantic expressions into executable code. In reality I can not find any work that connects semantics of programming language with the code generation.

Is there special kind of semantics of programming languages that is usable not only for the analysis of the programs but also for the generation of the programs?

My guess is that it should be really useful approach for generating formally verified code but I can not find research work about this. Are there trends of better keywords avilable for this?

Maybe - more relevant question is - what kind of compilers/translators the Model Driven Development tools use for the generation of source code (platform dependent code) and how semantics of programming language can be used for the construction of such compilers?

Note added. There already is complete unifying (denotational and operational) semantics of Java, JavaScript and other industrial programmin languages in the K framework. So - this is more question about application of K framework for code generation is that is possible at all?


texts: Is Unification "an Implementation of Existential Quantification"?

texts:
I read a comment (I've forgotten the source), "Unification is an implementation of existential quantification." (Emphasis mine.)

If true, this point of view clears up many things.

For instance why omitting the "occurs check" in unification can lead to unsound inference:  it would be the same as using the assumption of the existence of a thing in your proof(-term) of the existence of that thing.

It would also explain why the algorithms for unification in logic programming language engines I've looked at seem (to me) more arbitrary than other operators such as conjunction and disjunction.

But - is the statement true?  Is it an over-simplification?


texts:
I know some examples of "pattern matching". E.g. in the context of functional programming, and regular expressions.

But is there a precise definition?

In particular, it seems that it has to do with whether a finite automaton can recognize it.