Infer number of comets, based upon observations of their periodic visits to Earth Can we algorithmically infer the number of comets that orbit the Earth, based upon periodic observations of them, if we cannot tell the comets apart?  In more detail:
The problem

There is an unknown, fixed number of comets, numComets that pass by
Earth and are visible from the ground.

Each comet takes a fixed number of years to orbit Earth.

Based only on this knowledge and the dates recorded that a comet was
sighted in the night sky, determine numComets, AND determine
the orbital period of each comet. You can use an unlimited amount of
observation data (time), but the solution in the shortest amount of
time is preferable.

Assumptions you can make

All comets look identical from the ground; there is no way to
visually identify them.

No other object will be mistaken for a comet, and all comets will be
seen.

No comet takes more than 100 years to orbit Earth, and no new comets
will be introduced.

As current answers have pointed out, the problem as it lay now is unsolvable. Would a solution be possible if numComets is known? (Even roughly get the right answer?) What modifications to the problem would have to be made otherwise, to still encasulate the spirit of the problem, and make it solvable? (or is it dead with no hope of solving accurately?)
Further assumption
All comets start at a different point in their orbit. I.e. They do not all start their orbit at the same place like racehorses coming out of a gate.
Clarification
Comets are only recorded once per year. So there is no difference between a comet that passes at the beginning of a year and at the end. The problem could just as easily have been worded as days.

Based on the restriction you gave, that you cannot identify one comet from another, there is no difinative method of calculation. Here is a proposed situation, There are 2 comets following the same trajectory, they each orbit at exactly ten year orbit durations, so each one is seen every ten years, they are however exactly 5 years apart in their orbits. From the ground if we cannot differentiate between these two comets we only see a comet appear overhead regularly every 5 years, there is no way to tell if this is one comet appearing ever 5 years, or two comets appearing every ten years, but 5 years apart. From this it is impossible to deterministically say how many comets there are, so no algorithm can give you numComets with the assumptions that you have specified.

there are many ways to interpret this problem eg as a machine learning problem. however there is some key theory that is relevant & deserves citing, that of the "N-body" problem in physics. this is the problem of predicting motions of objects based on relative gravitational attraction and its an old problem, long studied, and there is a large amount of theory on the subject. the theory originally developed in working to determine trajectories of planets in the solar system and dates at least to Newton. there are surprising new findings also such that there are instabilities and inherent chaotic dynamics to these types of equations. in other words predictability may be somewhat like the weather, namely that weather over the short term is moderately predictable but over the long term is not deterministically predictable (because of the so-called butterfly effect etc).

N-body problem
N-body simulation


Regular expression for the strings without a particular substring How can we design a regular expressions without particular substrings.
The goal of this is to create language L which won't contain a particular substring (i.e. 110)

for the case of a regular expression without substring $110$, I Was thinking of: $\require{cancel}\cancel{(101)^*+}(010)^*+(10)^*+(\cancel{1}1)^*+(\cancel{0}0)^*+(01)^*$ but is that over excessive?

Then for example, I crossed out (101)* because obviously if you have two of those 101101, a subset of that will be 110, which we don't want.

Notes:

Question has been edited since it gained attention in the past few days. Also see comment for justification.

I did the following multistep technique.

Step 1: make a DFA that accepts all strings with "110".  I am able to construct a DFA that accepts all strings with substring "110" and has just 4 states.

Step 2: Flip all the accepting states to non-accepting and all the non-accepting states to accepting.  This page at Old Dominion describes the technique quite succinctly.  This creates a DFA that accepts the language you want.

Step 3: Now you need to convert the DFA back to a regular expression.  As @Alejandro Sazo mentioned there is a proof that this is possible.  But you need an algorithm.  This paper by Christoph Neumann describes three different techniques.  The easiest one is the "state removal technique."   You remove a state and replace all the edges between states that were connected to the removed state with edges labeled with regular expressions.  As you reduce in this way you eventually get to a regular expression for the whole DFA.  (Note that Figure 4 in the paper I linked is not quite right.  The self-loop on state $q_j$ should have the regular expression "c e* b", not "c e* d".)

By going through this process it became clear that: the language you are going to need to solve for this particular problem has the property that once you have seen the sub-string "11" then you can never see another "0".

I don't know the real logic but as per my understanding... It is clearly work on the logic of don't accept the 110 .. so it means whenever you got the substring like 110 ... At that time you must be not at a " Final state" so as per the above fig mentioned by my friend it is clear that after accepting the 0 in q2 state we not reach at final state it means ..We not get the final state so system generate error or ignore this type of no to accept ...And our aim to remove or not generate the string which contain 110 is clearly satisfy..


Algorithm for finding two smallest numbers in an array I was just thinking today that the best approach to find two smallest numbers in any array would be to first sort(ascending order) it with some efficient algorithm like Quicksort(Average case complexity: nlogn) and then access the first two members of the array in O(1).

Is my approach optimal or there are some alternative better approaches?

If you keep track of the 2 smallest elements you have seen so far as you traverse the array, then you only need to go through the array once, and for each element you compare to the larger of the 2 current smallest and if the new element is smaller, then you replace the larger of the 2 current smallest with the new element. This requires only a few operations per element in the array as you traverse the array, so it's $O(n)$ with a very small constant. It's probably impossible to come up with a sort-based approach that ever runs faster, except maybe for an array of size 4 or 5 or less.

Sorting would consume extra time if it was an array with small size.! It would be better if you would just traverse through the array once and keep track of the first smallest and use the first smallest for comparison so that you get 2nd largest. But for an array of large size.. It would be better to sort using some algorithms like heap sort, merge sort or heap sort.. Because, if the smallest element in the array would be at the end of the array, it will take you O(n) time.


Is it possible to do Dependent Types in Typed Racket? Is it possible to use Dependent Types in the existing Typed Racket implementation? (ie do they exist in it?)

Is it reasonably possible to implement a Dependent Types System using Typed Racket?

Dependent Types in Racket are being worked on by Andrew Kent at Indiana University.

There is a set of slides. There is a talk.

Of interest, this potentially also impacts Typed Clojure, which is strongly modeled on Typed Racket.

I think to "do dependent types" using contracts is already possible. Check https://docs.racket-lang.org/guide/contracts-struct.html and look for "Checking Properties of Data Structures".

You could argue, that this is rather simulating the effect, than having it as part of the language. However, somewhere you'll need to write the code, which tells the interpreter/compiler what those dependencies are and in Racket you can do that with contracts.


Theoretical worst case running time of finding a path through a maze? Given a randomly generated maze of dimensions n x n, with the entrance point always being the top left corner (0,0) and the exit point always being the bottom right corner (n,n) what is the theoretical worst-case running time of finding a path through this maze?

The maze has a density of d (for example, if d = 0.5, then half of the maze is filled with obstacle/wall cells)
The path finding algorithm uses a stack to keep track of the path and for back tracking when necessary
The algorithm uses a search order of down, right, up, left

If you are only interested by the worst-case scenario, you need to consider an algorithm always picking the worst possible move at any point in time. The answer is intrinsic to both the method used to find the path through the maze and the maze topology. In fact, two randomly generated mazes might be very different from each other, one could have a path from start to end with no dead end while the other might have a lot of path intersection and dead ends. In the latter, a naive algorithm might perform worse if hitting a dead end mean searching backward to the last intersection before to attempt another path. Again, the answer is intrinsic to the algorithm used to traverse the maze and the maze topology.


Data Science vs Operations Research The general question, as the title suggests, is:

What is the difference between DS and OR/optimization.

On a conceptual level I understand that DS tries to extract knowledge from the available data and uses mostly Statistical, Machine Learning techniques. On the other hand, OR uses the data in order to make decisions based on the data, for example by optimizing some objective function (criterion) over the data (input).

I wonder, how these two paradigms compare.

Is one subset of the other?
Are they consider complementary fields?
Are there examples that one field complements the other or they are used in conjuction?

In particular, I am interested in the following:

  Is there any example where OR techniques are used to solve a Data Science question/problem?

While both Operations Research and Data Science both cover a large amount of topics and areas, I'll try to give my perspective on what I see as the most representative and mainstream parts of each.

As others have pointed out, the bulk of Operations Research is primarily concerned with making decisions. While there are many different ways to determine how to make decisions, the most mainstream parts of OR (in my opinion) are focused on modelling decision problems in a mathematical programming framework. In these kinds of frameworks, you typically have a set of decision variables, constraints over these variables, and an objective function dependent on your decision variables that you are trying to minimize or maximize. When the decision variables can take values in $\mathbb{R}$, the constraints are linear inequalities over your decisions variables, and the objective function is a linear function of the decision variables, then you have a linear program -- the main workhorse of OR for the past sixty years. If you have other kinds of objective functions or constraints, you find yourself in the realm of integer programming, quadratic programming, semi-definite programming, etc...

Data Science, on the other hand, is mostly concerned with making inferences. Here, you're typically starting with a big pile of data and you'd like to infer something about data you haven't seen yet in your big pile. The typical sorts of things you see here are: 1) the big pile of data represents the past results of two different options and you'd like to know which option will yield the best results, 2) the big pile of data represents a time series and you'd like to know how that time series will extend into the future, 3) the big pile of data represents a labelled set of observations and you'd like infer labels for new, unlabelled observations. The first two examples fall squarely into classical statistical areas (hypothesis testing and time-series forecasting, respectively) while the third example I think is more closely associated with modern machine learning topics (classification). Fun trivia: I believe that for a long time, the job title at Google for people doing what we now call Data Science was (is?) "Statistician".

So, in my opinion, Operations Research and Data Science are mostly orthogonal disciplines, although there is some overlap. In particular, I think that time-series forecasting appears in a non-trivial amount in OR; it's one of the more significant, non-math programming-based parts of OR. Operations Research is where you turn if you have a known relationship between inputs and outputs; Data Science is where you turn if you're trying to determine that relationship (for some definition of input and output).

If you count ML and AI driven by ML as a part of Data Science(which some people do and some dont according to my experience, for instance Microsoft professional program in AI contains key aspects of Data Science+Machine learning(with both DL and RL) while Higher School of Economics presents practically same advanced parts of Microsoft cuuriculum as Advanced Machine Learning) then there are many similarities in mathematics that is used in both fields. For instance: Nonlinear Programming(Lagrange multipliers, KKT conditions...)-->used for derivation of Support Vector Machines...Econometrics which is mostly based on Regressions---> Regressions are key part of both Data Scinece in general and more specifically Supervised Learning...Statistics(normally found in OR Curriculum)--->key for Data Science and Machine Learning as well...Stochastic Processes--->very important in Reinforcement Learning...Dynamic Programming--->again found in Reinforcement Learning...So,I would say there are some similarities with Data Science in general and pretty much similarities with ML. Of course, goals of these disciplines are different but there is a lot of similarities in mathematics that is being used in these disciplines.


Determining number of elements divisible by at least one prime of set I have an array ($|A|\leq 10^6$) of numbers ($A_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the given set.

For example:

  Array: {3,5,7,15,21,143}

  Set: {3,5,7}

  Output : 5

The numbers are 3(3), 5(5), 7(7), 15(3,5), 21(3,7).

If the array size is $10^6$, an $n^2$ algorithm would time out.

Possible approach: I can preprocess all numbers in the array and store the count of elements each prime factors appear in.

For the example given above : The prime factors are 3,5,7,11,13 and values of the count array will be count[3]=3, count[5]=2, count[7]=2, count[11]=1, count[13]=1.

Can the principle of inclusion and exclusion be applied in this case or is there any other approach to the problem?

One possible approach is to use the GCD algorithm: calculate the GCD of each number in your array with the product of the given primes.

I think this process might give you the results
Step1. know the no of elements
Step2. Load the first prime number and check for divisibility.
Step3. If the number in the array is divisible replace it with the prime you are dividing else Skip it.
Step4. Load the next prime & repeat the process up to last prime in the set.
Step5. Output={no of elements that are grater than largest prime number in the set}.
I think the program goes like this

#include <stdio.h>#include < math.h>
Int main()
{
Int x[100],y[20],z[100],I,j;
Scanf/give x&y;
For (i=1;i<=100;i++){
z[i]=x[i];
}
For (j=1;j<=20,j++)
{
For(i=1;i<=100;i++)
{
z[i]=x[i]%y[j];
If(z[i]==0)
{
z[i]=y[j];
}
else
{
z[i]=x[i];
}
}
}
j=0;
for (i=1;i<=100;i++)
{
If(z[i]>y[20])
{
j++;
}
}
Printf j;
return 0;
}

Ps:I skipped some syntax & I forgotten some syntax.


Can $\{a^mb^nc^n\mid m,n \ge 1\}$ be proved non-regular using the pumping lemma? $\{a^mb^nc^n\mid m,n \ge 1\}$ intuitively seems like a non-regular language. It looks like the machine needs to remember the number of $b$s (which isn't limited). The pumping lemma can be used to prove a language is non-regular. In reference to the Wikipedia article linked (see "Use of Lemma"), every string I have tried doesn't give a contradiction. For example, a string like $a^1b^pc^p$ (where $p$ is the pumping length) seems to nicely split into $x = \varepsilon$, $y = a^1$, $z = b^pc^p$. What am I missing here?

You've forgotten that $y$ can be pumped any number of times, including zero. The string $xy^0z = b^pc^p$ is not in the language.

$S = a^Pb^{PM}c^{PM}$. It can be divided in $S = xyz$ where $x = \epsilon, y = a^P, z = b^{PM}c^{PM}$ which satisfies the following conditions:
$$ |xy| \le P $$
$$ xy^iz \in L $$
$$ |y| >= 1 $$
The middle condition is satisfied because the length of a is irrelevant to the length of b and c.
But, this doesn’t mean that a language is regular. The pumping lemma in simple words only says that: each regular language that can be represented with an automaton that has |finiteStates| = $x$, and the sequence it accepts is of length > $x$ then according to the pigeon-hole theorem,  at least one state is looping.
The pumping lemma does not work both ways. Therefore a language that satisfies it is not necessarily regular. It only means that the ones with variable length that don't satisfy it are irregular.


Shortest paths candidate Let $G = (V,E)$ be a directed graph  with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. Let $f : V \to \mathbb R$ be a given function. Describe an algorithm that runs in $O(|V| + |E|)$ time that answers yes/no to the question: is it true that for all $u \in V, f(u) = \delta(v,u)$, where $\delta(v,u)$ is the weight of the shortest path from $v$ to $u$?

Obviously what comes to mind is Bellman-Ford algorithm, but it doesn't satisfy the time requirement. I don't really see how having the candidate $f$ function helps us in this regard.

The idea is to build a graph with only the edges that are candidates for the shortest path from $v$ to $u$ assuming that $f$ is the required solution.

If during the process we find an edge that lead to a shorter path then we return false.

Otherwise, at the end, we check that all the nodes are still connected (with a DFS) hence that there exists a path with the required weight.

  if $f(v)\neq 0$ then return false

  $\forall e=(v_1,v_2)\in E $ do

  if $f(v_2) > f(v_1)+w(e)$ then return false

  if $f(v_2) < f(v_1)+w(e)$ then remove $e$ from $E$

  done

  build $cV$ the set of reachable vertices in the new graph (with a DFS)

  return $V=cV$

Correction:
- if there exists $u\in V$ such that $f(u)>\delta(v,u)$ then there exists $e=(v_1,v_2)\in E$ such that $f(v_2) > f(v_1)+w(e)$. Let $e_1,...,e_n$ be the shortest path from $v$ to $u$ if $f(v_{i+1}) \leq f(v_i)+w(e_i)$ then $f(u)\leq \delta(v,u)$ contradiction.

Hence the algorithm return false.

otherwise if there exists $u\in V$ such that $f(u)<\delta(v,u)$ then $u$ is disconnected from $v$ in the resulting graph.
Hence the algorithm return false. $u$ is connected, hence there exist a path $e_1,...,e_n$ from $v$ to $u$ such that $f(v_{i+1}) = f(v_i)+w(e_i)$ hence $f(u)\geq \delta(v,u)$ contradiction.
otherwise if for all $u\in V$ $f(u)=\delta(v,u)$ then all the edges belonging to the shortest path verify $f(v_{i+1}) = f(v_i)+w(e_i)$ hence are still in the graph at the end hence all the vertices are still connected. Also there are no edges such that $f(v_2) > f(v_1)+w(e)$ otherwise $f(v_2)>\delta(v,v_2)$.

Complexity:

$O(|E|)$ to build the new graph plus $O(|E|)$ for the DFS plus $O(|V|)$ for set equality hence $O(|V|+|E|)$.


Is a computer without RAM, but with a disk, equivalent to one with RAM? Memory is used for many things, as I understand. It serves as a disk-cache, and contains the programs' instructions, and their stack & heap. Here's a thought experiment. If one doesn't care about the speed or time it takes for a computer to do the crunching, what is the bare minimum amount of memory one can have, assuming one has a very large disk? Is it possible to do away with memory, and just have a disk?

Disk-caching is obviously not required. If we set up swap space on the disk, program stack and heap also don't require memory. Is there anything that does require memory to be present?

Sure.  In principle, given appropriate hardware, you could have just a disk, with everything stored on disk.  Any time the CPU did a load or store instruction, there could be some hardware that turns that into a disk read or write.  It'd be extremely slow: on a magnetic disk, each seek takes about 10ms, so you could do about 100 random-access reads and writes per second.

Some systems have flash memory-mapped into their address space.  Flash memory provides non-volatile (persistent) storage.  So, in some ways this resembles what you mention -- though those systems usually also have RAM as well.

Technically, RAM is a primary volatile memory that is used to improve the processing speed. Once the power is gone, the data in primary memory is lost. If we use a disk, ie as you say, only disk and not RAM, we could still run our computer but there would be more read write overhead thereby considerably slowing down the system . Hence, we use RAM.


Is Python a context-free language? From Wikipedia: Off-side_rule#Implementation, there is a statement:

  ...This requires that the lexer hold state, namely the current
  indentation level, and thus can detect changes in indentation when
  this changes, and thus the lexical grammar is not context-free –
  INDENT/DEDENT depend on the contextual information of previous
  indentation level.

I'm a bit confused. Some lexical grammars of Python is not context-free but INDENT/DEDENT themselves can be expressed in CFG. So lastly, Python is a context-free language or not?

Context-free grammars cannot express the rules of INDENT/DEDENT and so Python (which we use today in practice with INDENTs/DEDENTs)is not pure CF. Parsers (or lexical analyzers or lexers) for these languages use additional techniques to handle those structures. For example keep track of indentation levels, or tokenizer (scanners) may count number whitespaces and store that info in a table for later use. This is similar to something like trying to write a parser for the language $a^nb^{2n}c^n$, where you must keep track of value of $n$.

A simple example of adding additional power to a lexer is removing redundant whitespace symbols (space/tabs/newlines) or removing comments which has no meaning for the parser (parsing a CFL).

As another example, roughly it can be described as following. Assume a grammar $a^nb^mc^k$ which is clearly CFG.  You use BISON/YACC like tools to generate a parser for this grammar. Then you can introduce an additional rule like number of $a$s must be equal to the number of $c$ which makes the language non CF. So you just add extra logic (manually coding) to your parser to handle that rule by means of, say, annotated trees. Your original language is still context free but extra piece of code you added manually allows it to accept non CF subset of the original language.

I don't think that such parsers are generated automatically by compiler tools (at least I don't know) and so that ("non context free") part must be coded manually.

Python is not a context free language. We can check any language context free or not using Odgens's lemma (In the theory of Formal languages).


Counting permutations whose elements are not exactly their index ± 1 This is a special case of the question:
Counting permutations whose elements are not exactly their index ± M

The $M=0$ case has already been solved, but no one was sure how to work out the non-zero cases.

So I decided to try to just brute force some values and search the results for a recursion relation.  As a test I first tried $M=0$ and searched for recursion relations that looked like:
$$ a_n = \sum_{1\le i \le k} (A_i n + B_i) a_{n-i} $$
where $k$ is some cutoff of how far back to search, $A_i \in \{-1,0,1\}$ and $B_i$ some small integers.  It was correctly able to find:
$$a_n= (n-1)a_{n-1} +(n-1)a_{n-2}$$

So I then tried for $M=1$ and found:
$$ a_n= (n) a_{n-1} +(-n+2) a_{n-3} + (-1)a_{n-4} $$

It's possible it's just a coincidence, but I ran a brute force approach to calculating the $M=1$ cases overnight to get a couple more values and it still holds. But even with this potential answer in hand, I cannot figure out a reason this recursion would hold.

Is there a simple combinatoric argument I'm missing here?

Checkout Derangements

"Suppose that there are n people who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as their number."

In applying this to your problem, there would be two hats: the element's index +1, the elements index -1.

I'm not certain this solves the problem, but it seems like a step in the right direction.


What are the implications of P=NP? Is there a list of implications of $P=NP$?

Presumably, a proof of $P \ne NP$ will be by contradiction, for which a list of consequences of $P=NP$ would be useful.

If P=NP, then all of the NP problems can be solved deterministically in Polynomial time.

This is because the NP problems are all essentially the same problem, just stated in different terms.

As far as lists go -- many of the NP-Complete problems are enumerated here:
https://en.wikipedia.org/wiki/List_of_NP-complete_problems

Further implications? Our cryptosystems break down, armchair philosophers argue about what it means, the world changes, and somebody gets a Fields medal or Turing award + a big hunk of cash, etc... but that's a tangent.

For example, one of the classic NP problems is clique. If you could solve clique with a polynomial time algorithm, this would prove that P=NP, and then you could also use your method for solving clique to solve all of the other problems on that wiki-list, as an implication.

It also implies that some unsolvable problems may just be very hard.
One of which being "which specific genes cause the phenomenon of consciousness" which could yet be solvable.


Difference between DPDA and NPDA? What are the major differences between Deterministic Push Down Automata and Non-deterministic Push Down Automata? Which one is faster and how? Also what are the drawbacks of DPDA with respect to NPDA.
Can anyone quote an example and explain these concepts.

The main (and only) difference between DPDA and NPDA is that DPDAs are deterministic, whereas NPDAs are non-deterministic. With some abuse of notation, we can say that NPDAs are a generalization of DPDAs: every DPDA can be simulated by an NPDA, but the converse doesn't hold (there are context-free languages which cannot be accepted by a DPDA).

The main advantage of DPDAs is that we can simulate them much more easily with our deterministic computers (real hardware is always deterministic). In fact, simulating general DPDAs is not fast enough for most purposes, and so when parsing code we usually use LALR grammars which are weaker than DPDAs.

The transition function delta is almost single-valued for DPDA , multi-valued for an NPDA.


Time Complexity: Why does $n^n$ grow faster than $n!$? Seeing the title, you will probably like to give your explanation as

$n!=n\times (n-1)\times (n-2)\times (n-3)\times\cdots\times 1$

where as

$n^n$ = $n\times n \times n\times n \times\cdots\times n$ $\text{($n$-times)}$

but consider one thing: if we do $\log(n!)$ then it comes out to be $O(n\log n)$.

On the other hand, if we do $\log(n^n)$ it also comes out to be $O(n\log n)$. So, aren't they equal asymptotically?

The core source of your confusion is that you have assumed that the asymptotic behavior of functions is closed under taking $\log$, which is false. There are countless examples, take:
$$f(n)=n^{100}, \quad g(n)=n$$
If you take their logarithm they become:
$$\log f(n) = 100 \log n,\quad \log g(n) = \log n $$
So their logarithms are both linear in $\log n$, while it's obvious they do not have a similar growth rate.  Another example can be:
$$f(n)=\exp(2 n), \quad g(n)=\exp(n)$$
and their logarithms are:
$$\log f(n) = 2n, \log g(n) = n$$
You can see that $f(n) = g(n)^2$ and it has faster growth rate, but both their logarithms are linear in $n$.
The intuitive reason is that, when you compare $\log f(n)$ and $\log g(n)$, you are basically comparing their exponents. Showing that the exponents of two functions have a similar growth rate is not the same as showing that the functions have the same growth rate.

In case you are wondering, the reversed direction would actually hold most of the time: If $\log f(n)$ grows faster than $\log g(n)$, and $g(n)=\Omega(1)$, then $f(n)$ grows faster than $g(n)$, and the condition $g(n)=\Omega(1)$ prevents cases like $f(n) = \exp(1/n), g(n) = \exp(1/n^2)$.

The first part is right. But you have a wrong conclusion! If $g(n) = \Theta(f(n))$, you cannot say for $every$ function $h(n)$, $h(g(n)) = \Theta(h(f(n))$.

For the case, we know that $\log(n!) = \Theta(n\log(n))$, but you can not conclude that it is also true if we apply $h(n) = e^n$ over the functions. In your case, intuitively, the main difference in $\log$ cases and exponential cases is we sum limits in $\log$ cases and multiply limits in the exponential case!


For what kind of data are hash table operations O(1)? From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there are techniques to help make these conditions broad.

However, from a programmer's perspective, I don't know in advance what my data will be: it often comes from some external source. And I rarely have all the data at once: often insertions and deletions happen at a rate that's not far below the rate of lookups, so preprocessing the data to fine-tune the hash function is out.

So, taking a step out: given some knowledge about data source, how can I determine whether a hash table has a chance of having $O(1)$ operations, and possibly which techniques to use on my hash function?

Hash table lookup can always be $O(1)$ for static sets, see the 2002 paper by Arne Andersson and Mikkel Thorup: Dynamic ordered sets with exponential search trees

  Firstly, we give the ﬁrst deterministic polynomial-time (in n)
  algorithm for constructing a linear space static dictionary with $O(1)$
  worst-case access cost (cf. perfect hashing). As mentioned earlier, a
  linear space data structure that supports member queries (neighbor
  queries are not supported) in constant time can be constructed at a
  worst-case cost $O (n^2 W)$ without division [30]. We show that the
  dependency of word size can be removed.

In the general case, Andersson et al provide an algorithm for hash-indexed data structures that support lookups and updates in $O(\sqrt{\log n / \log \log n})$. Furthermore, they prove that this bound is optimal. So we know exactly how close we can get to $O(1)$ in the general case.

Permutations (of a fixed length), as a specific case of finite known sets: it is relatively easy to assign unique numbers to permutations, as in this paper. I have used this (in a somewhat less ghastly implementation) to map permutations of length $n$ into an array of size $n!$. But I could do this because I was eventually going to need every permutation; if you are only using a subset, you would need a function tailored to that subset or an efficient sparse array.


Which architecture do modern computers use? Is it one of:

Harvard
Modified Harvard
von Neumann

Or are they antiquated models that modern computers are only loosely based on?

If you asked Intel or AMD what would they say?

Modern general-purpose high-performance processors use separate instruction and data caches, and so could be classified as modified Harvard even though they use a unified address space. (Some microcontrollers—usually to provide extra memory or protection without a memory protection unit—use a Harvard architecture in which data and code use separate address spaces.)

x86 might be considered a little more nearly "pure" von Neumann than some other ISAs in that self-modified code is guaranteed to be handled properly if a jump is used. Many other ISAs require an instruction synchronization instruction and may require explicit invalidation of any modified memory from the instruction cache (i.e., the instruction cache is not necessarily coherent).

Cross-modified code is somewhat more complex; even x86 requires a synchronizing instruction.

I think Von Neumann is appealing answer but most processors implement a modified harvard architecture so they can load programs for disk storage as data and then execute it!..


Algorithm to find "truncatable words"? My son who is just learning to read loves the concept of hiding one letter of a word with his finger and asking what the rest of the word spells. His favorite is turning "her" into "he" and "then" into "the."

As he's starting to learn bigger words I want to find some words for him that are "truncatable," similar to the concept of a truncatable prime. These would be dictionary words that are also dictionary words when a character is removed from either the left or the right side. A properly "truncatable" word would continue to be a word down to 1 character, but I would be really only looking for those that are truncatable down to three letters:

 Browser
 Browse
 Brows
 Rows
 Row

What is the best algorithm to do this? My initial naive approaches are proving quite horribly inefficient for the dictionary file that I am using. I am currently literally testing every word in the dictionary, recursively, and the running time and space are intractable and the methodology ends up testing each word many times.

Is there an efficient memoized or otherwise optimized way of finding truncatable words?

Edit: Thank you to https://cs.stackexchange.com/users/755/d-w who provided guidance, this is the code I ended up coming up with which works:

# find list of truncatable words in English
# truncatable words are those where a word
# can be dropped from the beginning or end
# to form a new valid word, all the way down
# to three letters or fewer!

def main():
    # Find the truncatable words

    # read dictionary into a list
    f = open("english3.txt","r")
    wordlist = []
    for line in f:
        wordlist.append(line.strip().lower())

    # sort by length

    wordlist2=sorted(wordlist,key=len)
    max_word_length = len(wordlist2[-1])

    # set up list of dictionaries for truncatable words
    Truncatables = []
    for filler in range (max_word_length+1):
        Truncatables.append({})

    # iterate through dictionary and test for truncatability
    for word in wordlist2:
        if len(word)<=3:
            Truncatables[len(word)][word]='default'
        else:
            front = word[1:] in Truncatables[len(word)-1]
            back = word[:-1] in Truncatables[len(word)-1]
            if front and back:
                Truncatables[len(word)][word]='both'
            elif front:
                Truncatables[len(word)][word]='front'
            elif back:
                Truncatables[len(word)][word]='back'
            else:
                pass
    print(Truncatables)

    # Define a function that recursively prints out a truncatable chain

    def printTruncatable(word):
        if word in Truncatables[len(word)] and word in wordlist2:
            print(word," ",end="")
        TruncType = Truncatables[len(word)][word]
        if TruncType == "back" or TruncType == "both":
            printTruncatable(word[:-1])
        elif TruncType == "front":
            printTruncatable(word[1:])
        elif TruncType == "default":
            print("\n")
        else:
            print("ERROR")

    # print the top truncatables
    for wordlength in range(max_word_length,7,-1):
        for key in Truncatables[wordlength]:
            print(wordlength,": ", end="")
            printTruncatable(key)

if __name__ == "__main__" :
    main()

Here is a simple implementation strategy.

Find all three-letter truncatable words.  Every three-letter word is truncatable, so this is a linear scan through the dictionary to find the three-letter words.  Store them in a hashtable.

Find all four-letter truncatable words.  You can check whether a four-letter word wxyz is truncatable by checking whether wxy is a truncatable word; the latter can be checked by looking it up in the previous hashtable.  So, this can be done with a linear scan through the dictionary.  Store all four-letter truncatable words in a hashtable.

Find all five-letter truncatable words, by a linear scan plus a lookup in the hashtable for four-letter truncatable words.  Note that given a word vwxyz, it suffices to check whether vwxy is truncatable (you don't need to check vwx).

Find all six-letter truncatable words.

And so on.  Finish when you've exhausted the length of words in the dictionary.

Never done it, but this might work for you. I'm using 2 characters as my threshold to generate my example because its easier cognitively, but maybe something along the lines?

Run through the dictionary and discard any word less than 3 characters as 2 letter-strings are non-truncatable; then organize by size from largest to smallest by length and alphabetize each subset; this subset of the dictionary is D'.

  {a, aa, aardvark, ..., an, ant, anteater, ...} ->
  {aardvark, ..., ant, anteater, ...} ->
  {aardvark, ..., anteater, ..., ant, ...}

Use recursion and a binary tree to move through D' to generate a candidate list L from word W. Your base case would be a two-letter string. You can discard two-letter results. For example:

  "that" ->
  (that (hat,tha)) ->
  (that (hat (at, ha)),(tha (ha, th))) ->
  {(that, hat, at), (that, hat, ha), (that, tha, ha), (that, tha, th)}

Note that this would generate combinations that have non-words, so at each level of recursion, you can check D with a regex for membership. In python, this is easier with an is-in call.

  with is-in check : {(that, hat, at), (that, hat, ha)}

Concatenate your tuples into new dictionary of results R.
Remove all entries in tuples of R from D' so you don't duplicate your work. For instance, this algorithm checks "that" before "at", "ha", and "hat", so eliminate "hat" AND "that" from D'. (D' has already been stripped of "at" and "ha".)
Reiterate steps through revised D' until D' is exhausted.

R should now contain tuples of various lengths without redundancy. I'd alphabetize R because that's my nature.


What does the leading turnstile operator mean? I know that different authors use different notation to represent programming language semantics.  As a matter of fact Guy Steele addresses this problem in an interesting video.

I'd like to know if anyone knows whether the leading turnstile operator has a well recognized meaning.  For example I don't understand the leading $\vdash$ operator at the beginning of the denominator of the following:

$$\frac{x:T_1 \vdash t_2:T_2}{\vdash \lambda x:T_1 . t_2 ~:~ T_1 \to T_2}$$

Can someone help me understand?
Thanks.

On the left of the turnstile, you can find the local context, a finite list of assumptions on the types of the variables at hand.

$$
x_1:T_1, \ldots, x_n:T_n \vdash e:T
$$

Above, $n$ can be zero, resulting in $\vdash e:T$. This means that no assumptions on variables are made. Usually, this means that $e$ is a closed term (without any free variables) having type $T$.

Often, the rule you mention is written in a more general form, where there can be more hypotheses than the one mentioned in the question.

$$
\dfrac{
  \Gamma, x:T_1 \vdash t : T_2
}{
  \Gamma\vdash (\lambda x:T_1. t) : T_1\to T_2
}
$$

Here, $\Gamma$ represents any context, and $\Gamma, x:T_1$ represents its extension obtained by appending the additional hypothesis $x:T_1$ to the list $\Gamma$. It is common to require that $x$ did not appear in $\Gamma$, so that the extension does not "conflict" with a previous assumption.

In every situation that I've seen, $X\vdash Y$ means that there is a proof of $Y$ assuming that $X$ holds. If $X$ is empty, that means that $Y$ is a tautology: it has a proof without needing any assumptions.


Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$ I'm reading a book at the moment about logic gates and Boolean simplification. There is a part which I can't seem to follow.

I can easily work out that $A \vee (\neg A \wedge B) \equiv A \vee B$ using a truth table as it's easy to see.

However, I can't seem to turn $A \vee (\neg A \wedge B)$ into $A \vee B$ using steps such as distributive / absorption etc.

Can someone talk me through the steps that you would take to simplify this?

Note that

$\qquad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$;

you can "multiply out". Add in

$\qquad (A \lor \lnot A) \land B \equiv B$

and you are done.

absorption rule: (if P then Q) iff (if P then (P and Q))
identity: (if P then Q) iff ((not P) or Q)
so: (A or B) iff (if(not A) then B) (by identity)
hence: (A or B) iff (if(not A) then ((not A) and B)) (by absorption)
hence: (A or B) iff (A or ((not A) and B)) (by identity)

Basically, (A or B) iff (A or ((not A) and B)) is the absorption rule


Traverse Matrix in Reverse Diagonal strips I thought this problem had a trivial solution, couple of for loops and some fancy counters, but apparently it is rather more complicated.

So my question is, how would you write (in C) a function traversal of a square matrix in diagonal strips.

Example:

1 2 3
4 5 6
7 8 9

Would have to be traversed in the following order:

[3],[2,6],[1,5,9],[4,8],[7]

Straight lines are defined by linear equations. Assuming arrays indexed from zero, as in C, you want the lines $x-y=c$ for $c=2,\,1,\,0,\,-1,\,-2$. This gives something like

for c := 2 to -2 step -1
    for x := 0 to 2
        y := x-c
        if 0<=y<=2
            print A[x,y]

Here's the Python version:

def reverse_diagonal_traversal(matrix):
    side = len(matrix) + 1
    iterations = side - 1
    for i in range(1, side):
        for j in range(i):
            yield matrix[j][iterations + j - i]
    for i in range(side - 2, 0, -1):
        for j in range(i):
            yield matrix[iterations + j - i][j]

def test(side):
    matrix = [range(i * side, side + i * side) for i in range(side)]
    print matrix
    for i in reverse_diagonal_traversal(matrix):
        print i

Writing this in C would require too much code dealing with memory (de)allocation / printing, which isn't really part of this problem.  I'd imagine that porting the above to C won't be a problem.

The idea behind the code is that you need to produce iterations of 1..N length until you reach the main diagonal, and then N-1..1.  In the first half, you'd have to select the row at N at the first step of the iteration, and then N-i for each value of i in the iteration. You'd select the column starting at nth iteration - length of iteration, and then for each iteration step you'd increment that by one.

Finally, I'm not sure this is the most "elegant" solution (maybe you can do it in just half the code), but I couldn't find a good way to do that.


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

You can't.  There isn't enough information in a single elimination tournament to know who the $n$ best players are.  All you can infer is who the best player is.  You can't even tell who is second best; the second-best player could be any of the people who lost to the best player.

If you're not limited to a single-elimination tournament, I recommend you use a selection algorithm to find the top $n$ players, then use a sorting algorithm to rank-order those $n$ players.  Asymptotically, this needs only $O(N + n \log n)$ matches if you start out with $N$ players and want to rank-order the top $n$ of them.  If you only want to find the top $n$ players without rank-ordering them, a selection algorithm suffices, and then you'll only need $O(N)$ matches.  You can study the literature on selection algorithms and sorting algorithms to figure out how to reduce the constant factor hidden in the big-O notation.

In practice if you want to hold some matches simultaneously, you might want parallelizable selection algorithms and sorting algorithms.  Figuring out how to parallelize selection algorithms might be worth a question of its own.

One easy way I can think of is

Step1 : Sort the players wrt No.of matches won
Step2 : Sort the players who have an equal No.of matches won wrt Best opponent faced

In the case given by you , if you sort wrt to "No. of matches won" you get a list in the following order

10,7,[6,9],[5,0,8,1]                    // After applying Step 1 to the list

Now you can see that the players in brackets have an equal "No. of matches won".So you need to sort the lists
[6,9] and [5,0,8,1] wrt to the "Best opponent faced"

Start from the first list that appears from left

[6,9] becomes  [9,6] because

9 faced 10 which comes first in the list obtained after Step 1.
And 6 faced 7 which is second in the list obtained after Step 1

So

10,7,[6,9],[5,0,8,1]  becomes

10,7,9,6,[5,0,8,1]                      //After applying Step 2 on [6,9]

Now if we sort [5,0,8,1] wrt to the "Best opponent faced" then we get
[1,0,8,5] because

1 faced 10 which is first in the list
0 faced 7 which is second in the list
8 faced 9 which is third in the list
and lastly 5 faced 6 which is fourth in the list

So 10,7,9,6,[5,0,8,1] becomes

10,7,9,6,1,0,8,5                       //After applying Step 2 on [5,0,8,1].

You can repeatedly perform Step 2 unless you get the desired number of top players.Your top 5 players for the case in order are

10,7,9,6,1

Usually another performance criteria(like points scored) for sorting in Step 2 is available but I think this one suits if you don't have one.


set cover where only certain special subsets are allowed I am trying to solve a problem which turns out to be a form of the set cover problem. I've implemented the greedy Set cover approximation algorithm for set cover, but it turns out to not be accurate enough for my needs.

Specifically I have a fixed, finite, list of special sets and I am trying to create a function which when given a set returns the smallest list of special sets which cover that given set, and that list should contain no sets which contain elements not in that given set. The fixed list seems like it should make the problem easier to solve than set cover, but I'm not sure how the additional requirement of no extra elements affects the difficulty. My sets also have a known maximum size which should also make this easier to solve.

A toy version of the problem is as follows:

  Let $U$ be the set $\{a,b,c,d,e,f,g,h\}$. All the sets we mention from
  here on will be subsets of this set.

  Let $S$ be a list of special sets. For this version of the problem we
  can use the following list:

  $$ S = [\{a,b,c,d,e,f,g,h\}, \{a,b,c,d\}, \{e,f,g,h\}, \{a,e\}, \{b,f\}, \{c,g\}, \{d,h\}, \{a,b\}, \{b,c\}, \{c,d\}, \{d,e\}, \{e,f\}, \{f,g\},\{g,h\}, \{a\}, \{b\}, \{c\}, \{d\}, \{e\}, \{f\}, \{g\}, \{h\}]$$

  For a given set $G$ what is the smallest list of sets which are part
  of $S$ which cover $G$, (that is where the union of the sets in the
  list is $G$).

For the above toy problem, the greedy approximation I've implemented, if presented with a set like $\{b, c, g, h\}$, produces $[\{c, g\}, \{b\}, \{h\}]$ instead of the smaller list $[\{b, c\}, \{g, h\}]$.

Has this sort of problem been well studied? Is there a known non-approximate algorithm given the additional constraints, that would be better than naive dynamic programming? A well-known name for the version of set cover where extra elements are not allowed would also be useful.

Your problem is hardly easier than the general set cover problem.

Given a set $G=\{b, c, g, h\}$, we remove all elements in $S$ that are not contained in $G$, obtaining a collection of set $C=[\{c,g\}, \{b,c\}, \{g,h\}, \{b\}, \{c\}, \{g\}, \{h\}]$. Now the problem becomes the standard set cover problem with $G$ being the universe and a collection of 7 subsets. Since this reduction process takes $O(n^2)$ time where $n$ is the total number of elements in $U$, your problem cannot not significant easier than the general set cover problem unless there are further conditions to be exploited.

Unfortunately, the general set cover problem is NP-hard. It is one of Karp's 21 NP-complete problems. Even more unfortunately, the simple greedy algorithm achieves about the best approximation ratio, $H(s')$, where $S'$ is the maximum cardinality of the sets. Here $H(n)$ is the $n$-th harmonic number.

If you have to obtain the exact minimum set cover, you will have to resort to exponential algorithms. One simple simplification that can be done is to remove all elements in $C$ that are subsets of another element of $C$. That is, we can replace $C$ by $[\{c,g\}, \{b,c\}, \{g,h\}]$. A simple brute force algorithm is just to test all subsets of $C$ of size 1, those of size 2, those of size 3, etc. A common way to attack the problem is by integer linear programming.

Just in case, you might want to take a look at some literature on the set cover problems. For example, An Exact Algorithm for Unicost Set Covering and LP techniques for set cover.

I am trying to solve a problem that is some how similar to the set cover problem and would like to share my thoughts. What about trying an SMT solver or CSP solver?. However, I don't know yet if one of them would give better results


Coin Change Problem(Greedy Algorithm) In Coin Change Problem, if the ratio of Coin Value ($\frac{Coin_(i+1)}{coin(i)}$) is always increasing then we can use Greedy Algorithm?

Example- $(1,3,4)$ are denominations of coin.
If I want to pay $Rs.6$ then the smallest coin set would be $(3,3)$.
This solution set cannot be found by greedy Algorithm because it does not satisfy $(\frac{4}{3} > \frac{3}{1})$.

For the set of coins (2,3,11). $\frac{3}{2}<\frac{11}{3}$ so by your assumption we can be greedy here. Consider the value of 23. The greedy strategy would involve first taking 2 11 cent coins to give us 22 cents. Then there is nowhere left to go, we cant possibly get to 23 from here. We do have a solution though with $(0,4,1)$

Say, set of coin = {1, 10, 25}

It doesn't satisfy 25/10 > 10/1 But still can be solved by greedy algorithm.

Now, say X is any set of coins in increasing order. Then, for all a and b in X where a < b, if 2*a <= b satisfies, It will be solvable with greedy algorithm.


Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity.

In practice, what is needed is an algorithm that would work fast on a finite (although possibly very large) number of instances.

An algorithm which works well in practice on the finite number of instances that we are interested in doesn't need to have good asymptotic complexity (good performance on a finite number of instances doesn't imply anything regarding the asymptotic complexity). Similarly, an algorithm with good asymptotic complexity may not work well in practice on the finite number of instances that we are interested in (e.g. because of large constants).

Why do we use asymptotic complexity? How do these asymptotic analysis related to design of algorithms in practice?

The interesting question is: what is the alternative? The only other method I know is testing/benchmarking. We program the algorithms, let them run on (a representative sample of) the finite input set and compare the results. There are a couple of problems with that.

The results are not general in terms of machines. Run your benchmark on another computer and you get different results for sure, quantitatively, and maybe even qualitatively.
The results are not general in terms of programming languages. Different languages may cause very different results.
The results are not general in terms of implementation details. You literally compare programs, not algorithms; small changes in the implementation can cause huge differences in performance.
If the worst-case is rare, a random input sample may not contain a bad instance. That is fair if you are concerned with average case performance, but some environments require worst-case guarantees.
In practice, input sets change. Typically, inputs become larger over time. If you don't to repeat your benchmark every six months (yes, some data grow that fast), your results are worthless soon¹.

That said, ignoring all kinds of effects and constants in the analysis is typical, but can be called lazy (with respect to practice). It serves to compare algorithmic ideas more than to pinpoint the performance of a given (even pseudocode) implementation. It is well known to the community that this is coarse and that a closer look is often necessary; for example, Quicksort is less efficient than Insertion sort for (very) small inputs. To be fair, more precise analysis is usually hard².

Another, a posteriori justification for the formal, abstract viewpoint is that on this level, things are often clearer. Thus, decades of theoretic study have brought forth a host of algorithmic ideas and data structures which are of use in practice. The theoretically optimal algorithm is not always the one you want to use in practice -- there are other considerations but performance to make; think Fibonacci heaps -- and this label may not even be unique. It is hard for a typical programmer concerned with optimising arithmetic expressions would come up with a new idea on this level (not to say it does not happen); she can (and should) perform those optimisations on the assimilated idea, though.

There are formal, theoretic tools to close the gap to practice to some extent. Examples are

considering memory hierarchy (and other I/O),
analysing the average case (where appropriate),
analysing numbers of individual statements (instead of abstract cost measures) and
determining constant factors.

For example, Knuth is known for literally counting the numbers of different statements (for a given implementation in a given model), allowing for precise comparison of algorithms. That approach is impossible on an abstract level, and hard to do in more complex models (think Java). See [4] for a modern example.

There will always be a gap between theory and practice. We are currently working on a tool³ with the goal to combine the best of both worlds to make sound predictions for both algorithmic costs and runtime (on average), but so far we have not been able to do away with scenarios where one algorithm has higher costs but smaller runtime (on some machines) than an equivalent one (although we can detect that, and support finding the reason).

I recommend for practictioners to use theory to filter the space of algorithms before running benchmarks:

if ( input size forever bounded? ) {
  benchmark available implementations, choose best
  schedule new benchmarks for when machine changes
}
else {
  benchmark implementations of all asymptotically good algorithms
  choose the best
  schedule new benchmarks for when machine changes or inputs grow significantly
}

There can be crazy changes in absolute and relative performance once the number of cache misses increases, which typically happens when inputs grow but the machine stays the same.
As in, leading researchers in the field are not able to do it.
Find the tool here. An example use has been published in Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn by S. Wild et al. (2012) [preprint]
Average Case Analysis of Java 7’s Dual Pivot Quicksort by S. Wild and M. Nebel (2012) -- [preprint]

how about a simple near-visceral illustrative example using one of the most ubiquitous algorithms/applications in CS, namely sorting? Bubblesort takes $O(n^2)$ both average and worst case time and quicksort about $O(n \log n)$ on average and only $O(n^2)$ "rarely" in worst case. a nice way to see the difference is to look at the side-by-side, synchronized animations of sorting random arrays & their performance. almost always the bubblesort will take "longer" and one will be left waiting for it to finish in comparison to quicksort.

now imagine that wait repeated in the code as many times as the code is called. how does one mathematically quantify/justify this apparent superiority of the quicksort algorithm? (ie is its name really justified or is it just a marketing slogan?) via asymptotic complexity measurements. one is left looking at the animations subjectively feeling that bubblesort is somehow a weaker algorithm and asymptotic complexity analysis can prove this quantitatively. but note that asymptotic complexity analysis is just one tool in the bag of tools to analyze algorithms and its not always the ultimate one.

and its worth looking at the side-by-side code also. bubblesort seems to be conceptually simpler and doesnt use recursion. quicksort is not as immediately comprehended esp the "median of 3" pivot principle. bubblesort might be implemented just in loops without a subroutine, whereas quicksort might typically have at least one subroutine. this shows the pattern that more code sophistication can sometimes improve the asymptotic complexity at the expense of code simplicity. sometimes there is an extreme tradoff similar to the concept of diminishing marginal returns (orig from economics) where very large amts of code complexity [requiring entire papers full of thms and proofs to justify] only buys very small improvements in asymptotic complexity. this shows up as an example esp with matrix multiplication and can even be graphed.


What's the problem of using the clock to generate random numbers? If the clock shows 14:15:36.909302, why not just use the fractions of a second part (09302) as a kind of random number?

What is wrong with this form of generating random numbers?

I am aware that obtaining truly random numbers is a difficult task, so I am assuming that there is something wrong with this method.

Quick answer:

If the run time of your algorithm to pick a random number is not random you could get a pattern of times which is not random.

As an example. Suppose the function to read the time is triggered by an event, and the event is timed to the clock, now your functions based on the clock.
If the run time of your algorithm is faster than the precision of the clock, then you will get duplicate times and thus duplicate numbers which are not random.

As an example. You write a function for use by others, and someone decides to generate 10,000 random numbers and store them. The loop is so tight for reading the clock and saving the values that you get 10,000 numbers all identical.

These are just cases that can make the data non-random. In reality if it is not security related I run a large sample through a test for randomness and if it were reasonable I would use it, but if it is security related I would ask at Security or Crypto

If you use a clock to generate a number for a roulette machine then every hour you will have 3600 seconds to use as your seed number,multiply this seed number by the same fixed number every second and you will produce a different number every second. If you make the fixed number the date then every day you will get a different sequence of numbers,even better,if you started with pi at the very beginning then the very last 4 digits could be your fixed number as pi never repeats a sequence? The number generated would be the last digit of the equation,as long as it is between Zero and 37,if it outside this range it gets disguarded and the next number used,if there are a few numbers in succession that fall outside our scale then this is when you get repeat numbers or zero!!! Any thoughts?


How to speed up finding a subset of a given set? Is there a data indexing technique that speeds up finding subsets of a given set in a collection, or do I always have to scan all of the data?

For example, let's say that I have a collection of sets:
(a, b)
(b, c)
(a, b, c, d)
(a, b, c)
(b, c, d)
(b, e)
(d, e, f)
(d, f, g)
(d, e, f, g)

I want to find subsets of (a, b, c, d), so the output should be:
(a, b)
(b, c)
(a, b, c, d)
(a, b, c)
(b, c, d)

Is there a method to index/hash data in a way that will limit the number of collection elements that I have to scan in order to find all matches?

if you map every element in set in S into a bit in a binary number. For set with n elements, we have n bit binary number. the $i$-th number takes 1 if the subset has that element. Then we can use a binary number from $00,...,00$ to $11,...,11$  to represent all the subset.

If you map all your subset into binary numbers, then you are searching in the number space.


What exactly is a "binary file"? I suspect this may be more of a concept / theory question, but, I haven't been able to wrap my brain around what exactly a binary file is.

I've read links such as the below:

https://en.wikipedia.org/wiki/Binary_file

https://betterexplained.com/articles/a-little-diddy-about-binary-file-formats/

But, the piece of the puzzle that's confusing me, is that ALL files are stored as 1's and 0's on a hard-disk, or, in RAM, etc.
(i.e. there's no physical engraving of the hex characters "6F" onto a disk platter for example; it's still a binary format that the data is stored in).

So, if all files are stored as binary, then, presumably it's an operating-system, (& filesystem) concept to refer to something as "binary" file?

A binary file is a file that is simply not a text file. It means that a bin file has a specific format (mp3, exe, jpg...) and can not be interpreted only as a character sequence. There are many ways data can be formatted and read.


Why complement of most negative number in octal does not turn out to be itself I know the range of the $n$ digit numbers in $r$'s complement system is given as

  $r^{n-1}-1$ to 0 to $-r^{n-1}$.

So for 3 bit 2's complement, its:

  $(2^2-1)$ to $0$ to $-(2^2)$
  that is
  $3$ to $0$ to $-4$
  that is
  $(011)_{\text{2's comp}}$ to $(0)_{\text{2's comp}}$ to $(100)_{\text{2's comp}}$

And for 3 digit 8's complement, its

  $(8^2-1)$ to $0$ to $-(8^2)$
  that is
  $63$ to $0$ to $-64$
  that is
  $(077)_{\text{8's comp}}$ to $(0)_{\text{8's comp}}$ to $(700)_{\text{8's comp}}$

Now I came to know that

  the $r$'s complement of the smallest / most $-$ve number in the range will be the same number.

For example, taking 2's complement of most $-$ve / smallest number possible with 3 bit 2's complement system, $(100)_{\text{2's comp}}$ is itself:

1 0 0
0 1 1 (1's complement)
1 0 0 (add 1 to get 2's complement)

But taking 8's complement of most $-$ve / smallest number possible with 3 digit 8's complement system, $(700)_{\text{8's comp}}$ does not seem to be itself:

7 0 0
0 7 7 (7's complement)
1 0 0 (add 1 to get 8's complement)

So 8's complement of 700 does not seem to be 700 itself but is in fact 100. So what I am missing? Or I am doing it all wrong?

First of all, if you are considering the $n$th digit of the number as being a sign digit, you can think of it as being either 0 or 1, no matter the value of $r$. In other words, it is always a bit (a  binary digit), and that's how you would represent it in hardware, should that be the case.

  $[1]73_{\text{8's comp}} = -5$

  $[1]73_{\text{8's comp}} + [0]06_{\text{8's comp}} = [0]01_{\text{8's comp}}$

The complement of a negative number represented in $r$'s complement will obviously produce the positive version of that same number. The most negative number doesn't have a positive of the same magnitude that fits into the given number of digits (a weakness of this form of representation).

The number is still there, though, only unsigned:

  $[1]00_{\text{8's comp}} = -64_{10}$

  $100_8 = 64_{10}$

The smallest 3-digit 8's complement number is not 700, but 400.

Indeed, the assertion at the start of the question is already wrong: as long as $r$ is even, the actual range is from $-\tfrac r2r^{n-1}$ to $\tfrac r2r^{n-1}-1$.


Is this special case of a scheduling problem solvable in linear time? Alice, a student, has a lot of homework over the next weeks.  Each item of homework takes her exactly one day.  Each item also has a deadline, and a negative impact on her grades (assume a real number, bonus points for only assuming comparability), if she misses the deadline.
Write a function that given a list of (deadline, grade impact) figures out a schedule for which homework to do on which day that minimizes the sum of bad impact on her grades.
All homework has to be done eventually, but if she misses a deadline for an item, it doesn't matter how late she turns it in.

In an alternative formulation:

ACME corp wants to supply water to customers.  They all live along one uphill street.  ACME has several wells distributed along the street.  Each well bears enough water for one customer.  Customers bid different amounts of money to be supplied.  The water only flows downhill.  Maximize the revenue by choosing which customers to supply.

We can sort the deadlines using bucket sort (or just assume we have already sorted by deadline).
We can solve the problem easily with a greedy algorithm, if we sort by descending grade impact first.  That solution will be no better than O(n log n).
Inspired by the Median of Medians and randomized linear minimum spanning tree algorithms, I suspect that we can solve my simple scheduling / flow problem in (randomized?) linear time as well.
I am looking for:

a (potentially randomized) linear time algorithm
or alternatively an argument that linear time is not possible

As a stepping stone:

I have already proven that just knowing which items can be done before their deadline, is enough to reconstruct the complete schedule in linear time.  (That insight is underlying the second formulation where I am only asking about certificate.)
A simple (integral!) linear program can model this problem.
Using duality of this program, one can check a candidate proposed solution in linear time for optimality, if one is also given the solution to the dual program.  (Both solutions can be represented in a linear number of bits.)

Ideally, I want to solve this problem in a model that only uses comparison between grade impacts, and does not assume numbers there.
I have two approaches to this problem---one based on treaps using deadline and impact, the other QuickSelect-like based on choosing random pivot elements and partitioning the items by impact.  Both have worst cases that force O(n log n) or worse performance, but I haven't been able to construct a simple special case that degrades the performance of both.

A few things I found out so far.

We can reduce ourselves to solving the following related problem:

newtype Slot = Slot Int
newtype Schedule a = Schedule [(Slot, [a])]

findSchedule :: Ord a => Schedule a -> Schedule (a, Bool)

I.e. give the input data already sorted by deadline, but allow an arbitrary non-negative number of tasks to be done on each day.  Give the output by just marking the elements on whether they can be scheduled in time, or not.

The following function can check whether a schedule given in this format is feasible, ie whether all items still in the schedule can be scheduled before their deadlines:

leftOverItems :: Schedule a -> [Int]
leftOverItems (Schedule sch) = scanr op 0 sch where
  op (Slot s, items) itemsCarried = max 0 (length items - s + itemsCarried)

feasible schedule = head (leftOverItems schedule) == 0

If we have a proposed candidate solution, and all items left out, we can check in linear time whether the candidate is optimal, or whether there are any items in the left-out set that would improve the solution.  We call these light items, in analogy to the terminology in Minimum Spanning Tree algorithm

carry1 :: Ord a => Schedule a -> [Bound a]
carry1 (Schedule sch) = map (maybe Top Val . listToMaybe) . scanr op [] $ sch where
  op (Slot s, items) acc = remNonMinN s (foldr insertMin acc items)

-- We only care about the number of items, and the minimum item.
-- insertMin inserts an item into a list, keeping the smallest item at the front.
insertMin :: Ord a => a -> [a] -> [a]
insertMin a [] = [a]
insertMin a (b:bs) = min a b : max a b : bs

-- remNonMin removes an item from the list,
-- only picking the minimum at the front, if it's the only element.
remNonMin :: [a] -> [a]
remNonMin [] = []
remNonMin [x] = []
remNonMin (x:y:xs) = x : xs

remNonMinN :: Int -> [a] -> [a]
remNonMinN n l = iterate remNonMin l !! n

data Bound a = Bot | Val a | Top
  deriving (Eq, Ord, Show, Functor)

-- The curve of minimum reward needed for each deadline to make the cut:
curve :: Ord a => Schedule a -> [Bound a]
curve = zipWith min <$> runMin <*> carry1

-- Same curve extended to infinity (in case the Schedules have a different length)
curve' :: Ord a => Schedule a -> [Bound a]
curve' = ((++) <*> repeat . last) . curve

-- running minimum of items on left:
runMin :: Ord a => Schedule a -> [Bound a]
runMin = scanl1 min . map minWithBound . items . fmap Val

minWithBound :: Ord a => [Bound a] -> Bound a
minWithBound = minimum . (Top:)

-- The pay-off for our efforts, this function uses
-- the candidate solution to classify the left-out items
-- into whether they are definitely _not_ in
-- the optimal schedule (heavy items), or might be in it (light items).
heavyLight :: Ord a => Schedule a -> Schedule a -> ([[a]],[[a]])
heavyLight candidate leftOut =
    unzip . zipWith light1 (curve' candidate) . items $ leftOut
  where
    light1 pivot = partition (\item -> pivot < Val item)

heavyLight not only checks a proposed schedules for optimality, it also gives you a list of items that can improve a non-optimal schedule.

No. This is not a special case of a flow problem solvable in linear time.
Because complexity is given by $O(n^2)$ and while sorting itself we get complexity as $O(n\log n)$ and in order to execute all the other n processes complexity definitely wouldnt remain linear.


Algorithm to distribute items "evenly" I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways to describe it... later I'll provide a way to measure if a result is better than other).

So, for the list:

[1, 1, 2, 2, 3, 3]

One of the best results, after re-distributing the values, is:

[1, 2, 3, 1, 2, 3]

There may be other results as good as this one, and of course this gets more complicated with a less uniform set of values.

This is how to measure if a result is better than other:

Count the distances between each item and the next item with the same value.
Calculate the standard deviation for that set of distances. A lower dispersion means a better result.

Observations:

When calculating a distance and the end of the list is reached without finding an item with the same value, we go back to the beginning of the list. So, at most, the same item will be found and the distance for that item will be the length of the list. This means that the list is cyclic;
A typical list has ~50 items with ~15 different values in varied quantities.

So:

For the result [1, 2, 3, 1, 2, 3], the distances are [3, 3, 3, 3, 3, 3], and the standard deviation is 0;
For the result [1, 1, 2, 2, 3, 3], the distances are [1, 5, 1, 5, 1, 5], and the standard deviation is 2;
Which makes the first result better than the second (lower deviation is better).

Given these definitions, I ask for a clue of which algorithms or strategies should I search for.

I ran across this question while researching a similar problem: optimum additions of liquids to reduce stratification. It seems like my solution would be applicable to your situation, as well.

If you want to mix liquids A, B, and C in the proportion 30,20,10 (that is, 30 units of A, 20 units of B, and 10 units of C), you end up with stratification if you add all the A, then all the B, and then all the C. You're better off mixing smaller units. For example, do single-unit additions in the sequence [A,B,A,C,B,A]. That will prevent stratification altogether.

The way I found to do it is to treat it as a kind of merge, using a priority queue. If I create a structure to describe the additions:

MergeItem
    Item, Count, Frequency, Priority

The Frequency is expressed as "one every N". So A, which is added three out of six times, has a frequency of 2 (6/3).

And initialize a heap that initially contains:

(A, 3, 2, 2)
(B, 2, 3, 3)
(C, 1, 6, 6)

Now, I remove the first item from the heap and output it. Then reduce its count by 1 and increase Priority by Frequency and add it back to the heap. The resulting heap is:

(B, 2, 3, 0)
(A, 2, 2, 4)
(C, 1, 6, 6)

Next, remove B from the heap, output and update it, then add back to the heap:

(A, 2, 2, 4)
(C, 1, 6, 6)
(B, 1, 3, 6)

If I continue in that fashion, I get the desired mixture. I use a custom comparer to ensure that when equal Priority items are inserted into the heap, the one with the highest Frequency value (i.e. the least frequent) is ordered first.

I wrote a more complete description of the problem and its solution on my blog, and presented some working C# code that illustrates it. See Evenly distributing items in a list.

Update after comments

I do think my problem is similar to the OP's problem, and therefore that my solution is potentially useful. I apologize for not framing my answer more in the terms of the OP's question.

The first objection, that my solution is using A, B, and C rather than 0, 1, and 2, is easily remedied. It's simply a matter of nomenclature. I find it easier and less confusing to think about and say "two A's" rather than "two 1's". But for purposes of this discussion I have modified my outputs below to use the OP's nomenclature.

Of course my problem deals with the concept of distance. If you want to "spread things out evenly," distance is implied. But, again, it was my failing for not adequately showing how my problem is similar to the OP's problem.

I ran a few tests with the two examples that the OP provided. That is:

[1,1,2,2,3,3]  // which I converted to [0,0,1,1,2,2]
[0,0,0,0,1,1,1,2,2,3]

In my nomenclature those are expressed as [2,2,2] and [4,3,2,1], respectively. That is, in the last example, "4 items of type 0, 3 items of type 1, 2 items of type 2, and 1 item of type 3."

I ran my test program (as described immediately below), and have posted my results. Absent input from the OP, I can't say if my results are similar to, worse than, or better than his. Nor can I compare my results to anybody else's results because nobody else has posted any.

I can say, however, that the algorithm provides a good solution to my problem of eliminating stratification when mixing liquids. And it looks like it provides a reasonable solution to the OP's problem.

For the results shown below, I used the algorithm that I detailed in my blog entry, with the initial priority set to Frequency/2, and the heap comparer modified to favor the more frequent item. The modified code is shown here, with the modified lines commented.

private class HeapItem : IComparable<HeapItem>
{
    public int ItemIndex { get; private set; }
    public int Count { get; set; }
    public double Frequency { get; private set; }
    public double Priority { get; set; }

    public HeapItem(int itemIndex, int count, int totalItems)
    {
        ItemIndex = itemIndex;
        Count = count;
        Frequency = (double)totalItems / Count;
        // ** Modified the initial priority setting.
        Priority = Frequency/2;
    }

    public int CompareTo(HeapItem other)
    {
        if (other == null) return 1;
        var rslt = Priority.CompareTo(other.Priority);
        if (rslt == 0)
        {
            // ** Modified to favor the more frequent item.
            rslt = Frequency.CompareTo(other.Frequency);
        }
        return rslt;
    }
}

Running my test program with the OP's first example, I get:

Counts: 2,2,2
Sequence: 1,0,2,1,0,2
Distances for item type 0: 3,3
Stddev = 0
Distances for item type 1: 3,3
Stddev = 0
Distances for item type 2: 3,3
Stddev = 0

So my algorithm works for the trivial problem of all counts being equal.

For the second problem that the OP posted, I got:

Counts: 4,3,2,1
Sequence: 0,1,2,0,1,3,0,2,1,0
Distances for item type 0: 3,3,3,1
Stddev = 0.866025403784439
Distances for item type 1: 3,4,3
Stddev = 0.471404520791032
Distances for item type 2: 5,5
Stddev = 0
Distances for item type 3: 10
Stddev = 0
Standard dev: 0.866025403784439,0.471404520791032,0,0

I don't see an obvious way to improve on that. It could be rearranged to make the distances for item 0 [2,3,2,3] or some other arrangement of 2 and 3, but that will change the deviations for items 1 and/or 2. I really don't know what "optimum" is in this situation. Is it better to have a larger deviation on the more frequent or on the less frequent items?

Lacking other problems from the OP, I used his descriptions to make up a few of my own. He said in his post:

  A typical list has ~50 items with ~15 different values in varied quantities.

So my two tests were:

[8,7,6,5,5,4,3,3,2,2,2,1,1,1,1]  // 51 items, 15 types
[12,6,5,4,4,3,3,3,2,2,2,1,1]     // 48 items, 13 types

And my results:

Counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sequence: 0,1,2,3,4,5,7,6,0,1,2,8,9,10,4,3,0,1,5,2,0,1,3,4,6,7,14,11,13,12,0,2,5,1,0,3,4,2,8,10,9,1,0,7,6,5,3,4,2,1,0
Distances for item type 0: 8,8,4,10,4,8,8,1
Stddev = 2.82566363886433
Distances for item type 1: 8,8,4,12,8,8,3
Stddev = 2.76272565797339
Distances for item type 2: 8,9,12,6,11,5
Stddev = 2.5
Distances for item type 3: 12,7,13,11,8
Stddev = 2.31516738055804
Distances for item type 4: 10,9,13,11,8
Stddev = 1.72046505340853
Distances for item type 5: 13,14,13,11
Stddev = 1.08972473588517
Distances for item type 6: 17,20,14
Stddev = 2.44948974278318
Distances for item type 7: 19,18,14
Stddev = 2.16024689946929
Distances for item type 8: 27,24
Stddev = 1.5
Distances for item type 9: 28,23
Stddev = 2.5
Distances for item type 10: 26,25
Stddev = 0.5
Distances for item type 11: 51
Stddev = 0
Distances for item type 12: 51
Stddev = 0
Distances for item type 13: 51
Stddev = 0
Distances for item type 14: 51
Stddev = 0

And for the second example:

Counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sequence: 0,1,2,0,3,4,7,5,6,0,1,8,9,10,0,2,0,3,4,1,0,2,6,7,5,12,11,0,1,0,3,4,2,0,1,10,8,9,0,7,5,6,0,
4,3,2,1,0
Distances for item type 0: 3,6,5,2,4,7,2,4,5,4,5,1
Stddev = 1.68325082306035
Distances for item type 1: 9,9,9,6,12,3
Stddev = 2.82842712474619
Distances for item type 2: 13,6,11,13,5
Stddev = 3.44093010681705
Distances for item type 3: 13,13,14,8
Stddev = 2.34520787991171
Distances for item type 4: 13,13,12,10
Stddev = 1.22474487139159
Distances for item type 5: 17,16,15
Stddev = 0.816496580927726
Distances for item type 6: 14,19,15
Stddev = 2.16024689946929
Distances for item type 7: 17,16,15
Stddev = 0.816496580927726
Distances for item type 8: 25,23
Stddev = 1
Distances for item type 9: 25,23
Stddev = 1
Distances for item type 10: 22,26
Stddev = 2
Distances for item type 11: 48
Stddev = 0
Distances for item type 12: 48
Stddev = 0

ANSI C CODE

This code works by imagining a straight line in n dimensional space (where n is the number of categories) passing through the origin with directional vector (v1, v2, ..., vi, ... vn) where vi is the number of items in category i.  Starting from the origin the aim is to find the next nearest point to the line.  Using the example [0 0 0 0 0 1 1 1 2 2 2 3] it produces the result [0 1 2 0 3 1 0 2 0 1 2 0].  Using Lungj's example [0 0 0 0 0 0 1 1 2] we get [0 1 0 0 2 0 0 1 0], which is exactly the same as Lungj's result.

The algorithm is made more efficient by only using integer arithmetic and considering only the deltas between the distances from each point to the line.

#define MAXCATEGORIES 100

int main()
{
    int i = 0;
    int j = 0;
    int catsize = 0;
    int vector[MAXCATEGORIES];
    int point[MAXCATEGORIES];
    int categories = 0;
    int totalitems = 0;
    int best = 0;
    long d2 = 0L;
    long vp = 0L;
    long v2 = 0L;
    long delta = 0L;
    long beta = 0L;

printf("Enter the size of each category (enter 0 to finish):\r\n");
do
{
    catsize = 0;
    #ifdef _MSVC_LANG
            scanf_s("%d", &catsize);
    #else
            scanf("%d", &catsize)
    #endif
    if (catsize > 0)
    {
        vector[categories] = catsize;
        totalitems += catsize;
        categories++;
    }
} while (catsize > 0);

for (i = 0; i < categories; i++)
{
    v2 += vector[i] * vector[i];
    point[i] = 0;
}

for (i = 0; i < totalitems; i++)
{
    for (j = 0; j < categories; j++)
    {
        delta = (2 * point[j] + 1)*v2 - (2 * vp + vector[j])*vector[j];
        if (j == 0 || delta < beta)
        {
            best = j;
            beta = delta;
        }
    }
    point[best]++;
    vp += vector[best];
    printf("%c ", best + '0');  // Change '0' to 'A' if you like letters instead
}
return 0;

}


Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete I tried to solve the above NP-completeness exercise by making a bipartite graph from a general one (undirected) by inserting a vertice in the middle of every edge of the first (general) graph. This generates problems as suggested here: Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs
Anyone can give a hint on how to make a bipartite graph from a general one without using the above method and how the hamiltonian property can be passed to it?

Given $G = (V,E)$, define $\tilde{G} = (\tilde{V},\tilde{E})$ by adding vertices $i^+$ and $i^-$ to $\tilde{V}$ for each $i\in V$ and edges $i^-j^+$ and $i^+j^-$ for each edge $ij\in E$.

It's not too hard to check that if $|V|$ is odd, $G$ has a Hamiltonian cycle if and only if $\tilde{G}$ is.  If $|V|$ is even, just add one new vertex of degree 2 with neighbors that have an edge between them.

So far, we've seen that Hamiltonian Cycle in bipartite graphs is hard.  To reduce this to Hamiltonian Path, just continue in the way you normally would to reduce Hamiltonian Cycle to Hamiltonian Path.

If a bipartite graph has an odd number of vertices then it is proven that it is non-Hamiltonian thus it is not a HC. The proof is in the pdf here: http://www.cs.helsinki.fi/u/polishch/pages/teaching/solutions03.pdf

Now I think for the HC with even number of vertices, you just do the known reduction from the HP we have done in class. I'm not quite sure about this though.

Also, I found this. Maybe it helps you maybe not.
It has the proof from a directed HC to undirected HC.
http://classes.soe.ucsc.edu/cmps201/Fall09/Handouts/ho11-hc-dir.pdf

Also you can check this out: http://courses.cs.tau.ac.il/cc/02a/exercises/ex04_ans.pdf question 4

Also maybe Reza Zamani Nasab's thesis will help you.


How do you have a type typed "Type" when implementing a programming language? I am working on the base of a language model, and am wondering how to represent the base type, which is a type Type. I have heard of an "infinite chain of types", but (a) I can't seem to find it on the internet while searching anymore, and (b) I am not sure if that's what I need or what it really means in practice.
Basically, I have a system in the language like this:
type User
type String
type X
...

Internally these get compiled to something like this:
[
  {
    type: 'Type',
    name: 'User'
  },
  {
    type: 'Type',
    name: 'String'
  },
  ...
]

But actually, the type: 'Type' gets further compiled not pointing to the string 'Type', but to the actual Type object:
[
  {
    type: theTypeObject,
    name: 'User'
  },
  {
    type: theTypeObject,
    name: 'String'
  },
  ...
]

So then the problem is, I need to now define or specify the "type type" itself:
type Type

which I try represent in a similar way, so now we have:
[
  {
    type: 'Type',
    name: 'Type'
  },
  ...
]

which is:
let theTypeObject = { name: 'Type' }
typeTypeObject.type = theTypeObject

Is that correct? What is this really saying? It is a circular structure, does this even make sense conceptually?
What would be better to do in this situation? Or is this perfectly acceptable? Basically I would like to understand how to explain what this circular structure even means, because it just makes me confused.

The type "Type" is typed "Type". It is an element of itself...

That doesn't seem logically possible. So what should I do?

I think what you might have found in your previous researches might be a pure type system.
In a pure type system, to avoid having "Type" being a "Type" at the same level that "Int" is a "Type", you would define another layer of "Types" where you would define "Type" as the entire first layer (and you would define this layer in the next one, and so on)
In practice, you could define your base types as "types", and the next layer would be kinds. The type "type" would be a kind. You might also want to consider functions of types to types as another kind.

I suspect that part of the problem might be your choice of root type.
A root type typically is a type with very few properties, because (by definition) it's the union of properties of all types. Yet a Type type, which needs to handle the complexity of your type system will have quite a few properties.
Having said that, for a language model it does not really matter what that your Type has a type that is itself Type. That's just how you model it. Models are just descriptions. But you say "compile", and that means you're actually going to do things. And that means you're dealing with such practical matters as code and data.
In particular, type systems are generally used to represent object types, where objects are combinations of code and data. Sure, there's a data property type name which has itself type String and can have a value of "Type". But that data is mostly meaningless without code.
Also, code doesn't live in its self-shaped world. Your code will not execute in an environment that already understood your type system, that's the whole point why you need code in the first place. It's your code and data which will need to materialize your type system in more primitive terms. Again, unlike a model, which can live in its own world.


What is it called when f(g(x)) = x? There are a couple of function pairs which give the identity when composed, e.g.,

decrypt(encrypt(value)) == value
deserialize(serialize(data, filepath)) == data

What is this property called? Suppose one function undoes the property of the other, and it is guaranteed that this is possible for all values (within the domain of interest).

I would add to the existing answer that the composition $h = f \circ g$ is the identity, which you already pointed out. This means that $g$ is the right-inverse of $f$, and $f$ is the left-inverse of $g$. That makes each of $f$ and $g$ invertible on the given side. For the pairs you have given, I would expect $g \circ f$ to also be the identity in the naïve/straightforward case, and so the left/rightness is flipped, and you have full inversion. The domain matters, as usual.
As pointed out in the comments, this is not necessarily the case for some kinds of the functions you give—re-encrypting after retrieving the original value $(g \circ f \circ g)(x)$ may not necessarily give the same encrypted code $g(x)$; but then, it’s not nearly useful to consider $g$ a function, for the normal rules don’t apply. Notice that we still take the value passed to $f$ (here, the decryptor) to be an encrypted value; we assume the domain of $f$ to be properly encrypted values. Mathematically we are unable to apply $f$ to anything else (though I could have used a name like $y = g(x)$). Programmatically, of course, the type system may permit values outside the domain to be given, and then we either get an error or garbage. Again, I consider those irrelevant and outside the domain here.
Versioned serialization actually doesn’t have this issue—a function that deserializes or serializes a different version than $f$ or $g$ is not $f$ or $g$, respectively, and therefore not relevant! The domain matters.
We also have $\forall x$ in the domain $h(x) = x$ by definition, and that means every $x$ is a fix-point of $h$ (this is trivially true for any identity).

If for all $x$ in some set $S$, we have $f(g(x)) = x$ then $f$ is the "inverse" of $g$


How to Modify SAT Solvers to Produce Resolution Refutations for Unsatisfiable Instances? In recent SAT competitions, there is a Certified UNSAT track. The problem instances are all unsatisfiable and the solvers are asked to produce certificates for unsatisfiability. One way is to produce a resolution refutation for the set of clauses in a problem instance. How can a SAT solver, say MiniSAT, be modified to do this? Can this be done for every solver? I searched the Internet and found little information. A reference is good for me.

A clause-learning SAT solver can be described approximately as follows. There is a stash of learned clauses, which starts empty. We run a recursive procedure, which at each point in time, first checks whether the current assignment (initially empty) contradicts an axiom or something in the stash. If so, there is no need to explore this branch. Otherwise, it picks a variable, and tries both assignment recursively. When a recursive call corresponding to a partial assignment $\alpha$ returns, we learn the clause $\lnot \alpha$. At any given point in time we are allowed to forget clauses. (It's important for the proof that each clause is learned, even if we forget it later on).

We now take the transcript of the algorithm and consider the clauses in the order in which they are learned. We prove that whenever a clause $c$ is learned, it can be derived using the rules of resolution from existing clauses or from axioms; in particular, at the very end we derive contradiction.

We allow the weakening rule in the refutation we construct; we can always get rid of weakening later on without increasing the refutation length (exercise).

There are three cases to consider. If the clause $c$ was learned because the corresponding assignment contradicted an axiom $c'$ or a clause in the stash $c'$, then $c$ is a weakening of $c'$. The interesting case is when $c = \lnot \alpha$ was learned since both assignment to some variable $x$ failed to produce a satisfying assignment. These assignments correspond to the learned clauses $c \lor x$ and $c \lor \lnot x$, from which $c$ follows by resolution.

Note that if we never use clauses in the stash then the resulting refutation is tree-like (every clause is used once), assuming we state each axiom whenever it's needed (rather than once and for all). Also, in any case the size (number of lines) of the refutation is the same as the number of recursive calls.

Not every solver can be thus modified, and people are searching for new solvers that cannot produce resolution refutations. (Resolution is slow and we want fast solvers.)

But CDCL solvers can p-simulate general resolution. That means they can produce resolution refutations that are only polynomially larger than general resolution. The method is written in Pipatsrisawat and Darwiche's On the power of clause-learning SAT solvers as resolution engines.

But that is not a good answer, because we want to show SAT solvers are slow, instead of how efficient they are. One way is to show general resolution p-simulates CDCL solvers. But people are too happy proving how good SAT solvers are to consider the other direction.

I don't know how to answer my own question. That's why I seem to turn this to a discussion forum. But that's why I'm asking in the first place.

Those who know why "CDCL solvers correspond to general resolution" please stand up and explain why general resolution is as good as CDCL SAT solvers!


Oracle machine solving halting problem for other oracle machines Could someone give me a simple explanation why an oracle machine that can solve the halting problem for standard Turing machines, is however unable to solve the halting problem for other such oracle machines?

I have tried searching for the answer online but could not find any that really answered the question.

The proof that a Turing machine with an oracle for $X$ can't solve the halting problem for Turing machines with an oracle for $X$ is identical to the proof that an ordinary Turing machine can't solve the halting problem for ordinary Turing machines.

For me, the halting problem is entirely artificial. The whole point is that there is one and only infinite Turing machine that can't decide whether the same infinite Turing machine will stop on given problem.

But real computers always have limited memory. And practically speaking, we don't expect that computer with 1 MB of memory will solve the halting problem for any program using entire MB of memory. It needs some more memory to store its own data.

And the halting theorem proof doesn't say anything about using 2 MB machine to prove that 1 MB machine will stop on given program.

And that's all about it. The halting theorem proves very obvious thing about real computers - that computer can't check itself because it doesn't have enough resources. Once you differentiate between checking and checked computers, the proof don't work anymore.


Your image appears darker because standard RGB is used in transformation, with problem inherent to color - grayscale conversion as standard RGB transformation does not preserve luminance.

Simple modification is to switch RGB channels to color space using perceived luminance: $Y = 0.299*R + 0.587*G + 0.114*B$. That way, luminance and chrominance blurring will not result in darkening or artificial color bleeding.

Color spaces like Y'UV or RGB are non-linear, so make sure to use linear one, say sRGB or any perception-aware/ linear space.

If you can trade speed with accuracy, floating-point box filters are visually better. Given 5x5 blur is tempting, but does not approximate Gaussian Blur accurately enough.

Something is wrong with your code.
Images appears darker by bad color space, but not that much. I took python code found here as it is, and took your image, the result is darker in my opinion, but not visible to the point of shadow dark.

I haven't seen your picture while writing answer but, it seems to me that divisor used is bigger than the sum of cell values.

You must Normalise the values.
If the values divide by (sum of them), that will not be happend.


Computer science for programmers I'm a self-taught programmer and have been coding for 8 years. Due to this experience, I'm already very familiar with the principles of programming (such as if-statements, classes, polymorphism, etc.).

However, I never learned "computer science," only programming. What are some good resources for someone in my position to self-study computer science - that is, resources which move at a quick pace and assume basic programming knowledge?

Computer Science is a multifaceted discipline - and Algorithms and Data Structures is important part of it. You can try free video-courses, like Algorithms, Part 1, from Princeton University - it's running right now.

Another remarkable free video-course Algorithms: Design and Analysis, Part 1, from Stanford has finished recently - hopefully it will be repeated in the future. Part 2 of this course will start this Monday.

Other courses that I studied (and I think are important):

Design patterns (like Singleton, Facade, Factory .etc)
Discrete Structures

Asymptotic complexity is a very important topic in CS as well. I would recommend "Introduction to Algorithms" as a good reference book for Data structure and Algorithms.You can then practice at Project Euler. Other than that, MIT has courses MIT Open CourseWare over at YouTube. I find their data structure courses very helpful.

Another thing I can suggest is also going through any University's CS coursebook to get the topics and see which one is of interest, and study them.


Given a regular language, show another language is regular I was hoping someone could help me with this question, since I'm having trouble determining what approach to take.

Let $L \subseteq \{0,1\}^*$ be a regular language. Show the language $\{w \in \{0,1\}^* | 1w \in L\}$ is also regular.

My idea is that whenever we're at the start state to compensate for the lack of the 1, you do an additional transition as if 1 was part of the input and then carry on reading the input as normal.

Since L is regular it has a NFA that accepts it $(Q,\Sigma, \delta, q_0, F)$. Then construct a new NFA $(Q,\Sigma, \delta', q_0, F)$ such that $\delta'(q,a) = \delta(q,a)$ for $q \ne q_0$ and $\delta'(q,a) = \delta(\delta(q,a),1)$ for $q = q_0$

Is this correct?

Your idea is right.

However, in general the initial state $q_0$ of a finite state automaton may also be used in other ways than just as a starting position, so the automaton may return to the state. Those later visits do not want to loose the letter $1$.

Are you sure the order $δ(δ(q,a),1)$ is correct?

we known that L is regular.

1w is a concactenation of 1 and w and is regular.(the concatenation of 2 regular language is regular) then w is Necessarily regular.
I think.
(Wait for the other answers to see)