Why is not known whether integer factorization can be done in polynomial time knowing how to do primality tests efficiently? First of all, I have just started studying computer science by myself and maybe I just need some clarification of what "polynomial time" means regarding the time complexity of an algorithm and references to study it well.

As I have understood it, whether integer factorization can be done in polynomial time is still an open question and, as this article in wikipedia (https://en.wikipedia.org/wiki/Integer_factorization) puts it,

  When the numbers are very large, no efficient, non-quantum integer
  factorization algorithm is known; an effort by several researchers
  concluded in 2009, factoring a 232-digit number (RSA-768), utilizing
  hundreds of machines took two years and the researchers estimated that
  a 1024-bit RSA modulus would take about a thousand times as long.

So, trying to see that for myself, I have written a very naive code in MATLAB checking it with prime numbers up to 15 digits; the reasoning being that if I can check if a number is prime fast, I can easily modify the code to give me the factorization fast.

The time it takes the code to check if a number is prime doesn't grow exponentially with the input.

function[]=prime(n)
tic
f=floor(sqrt(n));
for i=2:f
    if rem(n,i)~=0
        b=0;
    else
        b=1;
        disp(i)
        break
    end
end
if b==0
    disp('prime')
else
    disp('not prime')
end
toc
end

And so I go back to the question in the title. What is wrong with my reasoning?

Since your algorithm is "fast", why did you only try it with a 15-digit number and not with a 232-digit one? There's serious money to be made if you indeed have a "fast" algorithm.

Your algorithm takes time (if we count "div" as taking constant time) proportional to $\sqrt{n}$. A $d$-digit number can be as large as $10^d$, so your algorithm takes time proportional to $\sqrt{10^d} \approx 3.16^d$, i.e. exponential in $d$, the number of digits. That is by no means "fast" and grows very quickly as the numbers get larger.

It is polynomial with respect to the value of $n$, but not with respect to the size of $n$. This behavior is called pseudopolynomiality.

The "fast" prime testing algorithms use much more sophisticated approaches which can not be modified (easily) to also give a factorization. They just report yes/no whether the number is prime. The AKS primality test uses time proportional to $d^6$.

If one uses N%D to denote the remainder after dividing N by D, and B^E to denote B raised to the power E, then for any integer N and X with no common factors greater than 1, there will exist some integer Y less than N-1 such that (X^Y)%N equals 1.  If N is prime, the smallest such integer will be Y=N-2.  For most non-prime values of N, however, most values of X will cause (X^(N-2))%N to yield something else.

If one could identify the Y values for which (X^Y)%N equals 1, that information could be used to factor N fairly easily (and likewise knowing the factors one could compute Y values), but there's no known generally-useful way to find such values without knowing or guessing at the factorization of N.


Finding number of numbers <= N, containing atleast one of the digits 2,4,6,8 Given an integer $N$, I want to find the number of numbers $\le N$, that contain at least one of the digits from the set $\{2, 4, 6, 8\}$. How do I go about solving this problem?
I was thinking of constructing all possible numbers that fit into the integer size of the language that I am using, through a recursive procedure, but I am not sure how to do that. It seems complicated. Is there an alternative solution apart from taking some of the digits from the given set and constructing numbers?

This is much easier than inclusion–exclusion.  Compute the number of natural numbers smaller than $N$ that contain none of the digits 2, 4, 6, 8 and subtract that from $N$ (or $N+1$ if you're including zero).  To compute the number of naturals that contain none of 2, 4, 6, 8, observe that, if $M\leq N$ (padded with zeroes so $M$ also has $d$ digits) then $M$ and $N$ must agree on their first $i$ digits (for some $0\leq i\leq d$), then the $(i+1)$st digit of $M$ must be less than the $(i+1)$st digit of $N$ and the $(i+2)$nd, ..., $d$th digits of $M$ can be any of 0, 1, 3, 5, 7, 9.

This is really a math question. The idea is to use the inclusion-exclusion principle. For every given position, it is possible (with some effort) to count the number of integers at most $n$ which contain one of 2,4,6,8 in that position. With more effort, you can do this for several positions at once. Now you can use the inclusion-exclusion formula to determine the quantity you are after.


Is it possible to do face recognition with just the eyes? Assuming the input photo is focused on a person's face, if the person is wearing a surgical mask, most face recognition software fail to identify the subject's face.
Most facial landmark models are trained to identify at least the eyes and the tip of the nose (for example, dlib's 5 point landmark).
Is it possible to construct a model that is trained to identify a face based on only the eyes?

Recognising the right face is not the problem. Reliably rejecting the wrong face is.


The nearest points in a set I have $N$ points and I have a distance between every pair of points stored in a 2D matrix. The goal is to find the nearest $K$ points among these $N$ points. "Nearest" means the sum of all distances between the $K$ points is smallest. A brute-force way is to search all combinations of $K$ points from the $N$ points. However, $K \ll N$. For example, $K$ is 5 and $N$ is 100. It is infeasible to search all ${100 \choose 5}$ combinations.

Actually, the distance between points is a metric to measure the difference between elements in the set, so it is better to describe the problem using graph rather than computational geometry.

I have read Clique problem on wiki, but I think the setting is different from my context here.

More info: The elements are probability discrete distributions. The metric here is Hellinger distance en.wikipedia.org/wiki/Hellinger_distance, which is to measure the difference between two probability distributions. I like to find the most similar probability distribution subset from a set.

This problem does generalize the clique problem.

One example of a metric is the shortest path distance in a connected, unweighted graph $G$, where the distance between vertices $u$ and $v$, $d(u,v)$, is the length of the shortest path between them. There exists a clique of size $K$ in this graph if and only if we can find $K$ points whose distances sum to ${K \choose 2}$.

For finding cliques of size $5$ you can do slightly better than brute force: see this answer. However without more structure on the metric you are interested in it is an open problem to do significantly better.

If the distances are a metric that would mean if A is close to B, C, D and E, then B, C, D and E should be close to each other. . Unless someone constructed the data to make it hard, the solution ought to be one data point and four of the data points closest to it.

For every point, create a list of all the other points, sorted by distance in ascending order. For each list calculate the sum of distances between the first point and the four nearest; the smallest sum would be your benchmark. Sort the points by this sum in ascending order. You now have everything arranged in an order that would tend to give you small sums of distances.

Now you can do an exhaustive search with shortcuts: You iterate through the first points with the smallest sum first, the second points in order of distance to the first points, etc. Most important that you ignore anything that cannot be optimal. Say your smallest sum of distances so far is 40, and you picked four points with a sum of distances of 26.9, then the fifth point cannot be further than 13.1 away from the first point. If the distances obey the triangular equation then you can take further shortcuts.

Say you have three points with a sum of distances of 7, the second and third points are at distance 2 and 3 from the first point, and the fourth point is at a distance d from the first point (and therefore the fifth at a distance at least d), then the last two points are at least d, d-2, and d-4 away from the first three points, so the sum of distances is at least 7 + 2 (3d - 6) = 6d - 5. So if the sum to beat is 40, we must have 6d - 5 ≤ 40 or d ≤ 7.5. That should seriously restrict the choice of the fourth point.

I'm sure it's possible to construct examples where this doesn't work well, but if you take say the locations of the largest 1000 cities in the world and you want the five closest to each other this would work quite well.

About proof that it gives the correct answer: Well, obviously yes. It does in principle an exhaustive search, except that it orders items in a way that small sums tend to be examined at the start of the search, and we can prune off search branches when it can be proven that they cannot lead to an optimal result. Sorting first means we get good (not optimal) results quickly which make the pruning more effective.

The counter example isn't a counter example. Yes, we will start with sorted lists that start with a point A on the inner n-gon, a few of the neighbouring points on the same n-gon, and some on the outer n-gon which isn't optimal. But that's just the starting point of the search. There was the assumption k << n, which is violated (k = n/2), so it will be harder to prune the search tree effectively. But that's because we don't have k << n.


Will irrational parameters make a problem not well-defined on complexity Given a set $=\{_1,⋯,_\}$ where all $_$s are rational positive numbers and $\sum_{i\in N}a_i=1$, find a subset ⊆ such that $(\sqrt{2\sum_{i\in S}a_i}-1)^2$ is minimized. Does the appearance of √ make the problem ill-defined with regrading to complexity?

The appearance of square roots does not make this an ill-defined problem.

Note that $(\sqrt{2\sum_{i\in S}a_i}-1)^2=0$ if $\sum_{i\in S}a_i = 1/2$ and $(\sqrt{2\sum_{i\in S}a_i}-1)^2>0$ otherwise. Therefore, the problem is easily seen to be NP-hard by reduction from subset sum.

In this case, minimizing your expression (given that the sum is positive!) is just to minimize the sum, the square root and square are red herings ($(\sqrt{x} - 1)^2$ is monotone).


If I have a large random array of 0s and 1s that I want to sort what kind of an algorithm and data structures should I consider? What are the types of things that need to be considered if I need to sort a large random array of 0s and 1s?

You can assume large array is in the order of million or billions.

I understand there are tons of sorting algorithms out there (quick, merge, radix,.etc.) and there are so many different data structures out there (trees, skip lists, linked lists, etc.)

If somebody asks me to sort this large array, do I simply jump to Quick Sort and say that's the best solution? If not, what am I supposed to be thinking about?

I'm not even sure if I know the right answer to this question, but I would really appreciate it if somebody in the community can give some advise.

Thanks.

Use counting sort: run through the array once and count the number of 0's. Then run through the array once more and write in it the counted number of 0's, followed by 1's. In any case, this is a purely academic exercise because nobody would ever need to do such a thing in real life.

This really depends on the number of zeroes and ones your dealing with on a per element basis.

If your dealing with 64 or less, just convert it to a number, pop it into an array, and sort the array.

32 or less, make a blank array, convert the entry to a number, and keep track of the number of times the number passed.

ok  If this is a pathological case--  lets say a billion entries each a 16kilobits long..  now your into diskland...  you split your file into ~100 mb pieces  then use the unix split, sort, and >> operators to implement a merge sort. There is a temptation to just let sort do it all in one go, ignore that temptation it leads to the land of frustration (It might have been a memory limitation).  (I did an 800GB sort this way via script a few years back)

Best of luck
   --Storm


Maximum profit by two parameters Suppose we have two markets. Each market has various buy & sell orders that we can sell to or buy from respectively. Each order represents a specific number of a particular item type  that someone is selling or buying for a specific price per item and we can buy/sell any amount of items from/to any order. Each item type has its own volume per item (m3).

We have transportion that can transport a specific amount of volume and some budget amount.

Our goal is to form such transport cargo load of items that would maximize our profit by going from station A to station B assuming our limited cargo capacity and budget.

The algorithm I'm using is the following:

Sort sell orders of the source station by price_per_item in ascending order and group them by item_type.
Sort buy orders of the destination station by price_per_item in descending order and group them by item_type.
For each item type, form pairs of sell-buy orders based on the amount available in both markets (e.g. [Item, Quantity, Buy At, Sell At]: [Apple, 25, 50, 75], [Apple, 5, 50, 70], [Apple, 20, 60, 70])
Perform one of the following actions based on user input:

(A) Sort pairs by profit per m3 (sell_price - buy_price / volume_per_item) in descending order.
(B) Sort pairs by profit / buy price ratio ((sell_price - buy_price / volume_per_item) / buy_price in descending order.

Take as many items as possible from each pair of the sorted list until either budget = 0 or cargo_capacity = 0 or there are no pairs left.

When using option (A), the described algorithm doesn't take the budget into account while forming the list of most profitable pairs so it gives poor results with a limited budget. When the budget is high, due to the variety of the market the following algorithm uses a full budget amount while cargo space is usually almost empty (which I don't consider the acceptable result as I need to mitigate risks of losing cargo and having large losses due to low ROI).

When using option (B), the gives good profit compared to the amount used to buy the items but it doesn't utilize available budget efficiently.

So the task is to maximize total_profit / total_buy_price ratio while utilizing available budget_amount and cargo_capacity as much as possible.

Does this fall under some type of mathematical problem that can be solved in a mathematical way, and if so, can you suggest some sources to read up on in detail? Thanks.

If you are handling only one truck/cargo in your problem, then this is a typical  Knapsack problem. If you are handling the bigger problem of distributing all items on how many trucks, then it is a variant of Bin Packing problem. Both problems are NP-Complete, however Knapsack has approximate algorithms with guaranteed bounds from optimality.

I suggest you use a somehow mangling compromise between A and B:

Solve using A, then solve using B and take the best answer.
Do both sortings, keep 2 arrays, then at each step compare A choice to B choice and select the better choice (greedy approach)
Assign a weight to each factor then sort an array C according to your weight function. If you don't know the weights then make it equal (half for each factor). If you value price more make its weight above 0.5 if you value volume more then give it a higher weight. This is called multiplicative weight

this is an eve online question hahaha
just take the profit per item and divide it by it's size and sort descending
then fill in your cargo with as much as you can
this way you hit both in the same time


Can only information(data) be stored in ram? Basic question, but is only information/ data stored in ram? Are computer files such as a word file considered information/ data? This is one of the questions in a summer assignment for ap computer science.

RAM is just a really fast hard disk (except the contents are usually lost if powered down). It can store anything you could store on a hard disk (programs, documents, pictures, temporary data,...).

RAM (short for Random Access Memory) is computer memory that can be accessed randomly; i.e. any byte can be accessed without using the previous byte(s). So the answer to your. So yes, only information/data can be stored using RAM.


are NP Complete languages closed under any regular operations? I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. Is it also true that NPC languages are not closed under the complement, concatenation, and kleene star operations?

For all of the examples in this answer, I'm taking the alphabet to be $\{0,1\}$. Note that the languages $\emptyset$ and $\{0,1\}^*$ are definitely not NP-complete.

The class of NP-complete languages is not closed under intersection.  For any NP-complete language $L$, let $L_0 = \{0w\mid w\in L\}$ and $L_1 = \{1w\mid w\in L\}$.  $L_0$ and $L_1$ are both NP-complete but $L_0\cap L_1 = \emptyset$.
The class of NP-complete languages is not closed under union. Given the NP-complete languages $L_0$ and $L_1$ from the previous part, let $L'_0 = L_0 \cup \{1w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$ and $L'_1 = L_1\cup \{0w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$.  $L'_0$ and $L'_1$ are both NP-complete but $L'_0\cup L'_1 = \{0,1\}^*\!$.
The class of NP-complete languages is not closed under concatenation. Consider the NP-complete languages $L'_0$ and $L'_1$ from the previous part.  Since both languages contain $\varepsilon$, we have $L'_0L'_1 \supseteq L'_0\cup L'_1 = \{0,1\}^*\!$.
The class of NP-complete languages is not closed under Kleene star.  For any NP-complete language $L$, $L\cup \{0,1\}$ is NP-complete but $\big(L\cup \{0,1\}\big)^* = \{0,1\}^*\!$.
If the  class of NP-complete problems is closed under complementation, then NP = coNP. Whether this is true or not is one of the major open problems in complexity theory.

Take a look at the proofs for union, intersection, concatenation, and kleene star of NP languages, here. Its seems like a similar argument could be made for NP-Complete languages.

For notation let

$A$ be a oracle that decides a known NP-Complete problem like 3-SAT. See the definition of turing reducible
$L_1$ and $L_2$ are NP-Complete languages
$M_1$ and $M_2$ are Turing machines that decide $L_1$ and $L_2$ using $A$.
$L_3$ is $L_1 \cup L_2$
$M_3$ is a turing machine that decides $L_3$

In the case of union from 1, we can create a new machine $M_3$ that decides $L_3$ by calling $M_1$ and $M_2$ as sub routines. In turn, each time $M_1$ or $M_2$ is called, $A$ is also called. So $M_3$ decides $L_3$ using $A$. By the argument from 1, the running time of $M_3$ is in P and since it uses $A$ as a subroutine, $L_3$ is NP-Complete. In other words, $L_3$ is NP-Complete for the same reason that $L_1$ and $L_2$ are NP-Complete.

The same argument can be made intersection and it looks like similar arguments could be made for concatenation, and kleene star.

In the case of compliment, it seems likely to be difficult to prove for the same reasons is difficult to prove compliment in NP.


Extension of SQL capturing $\mathsf{P}$ According to Immerman, the complexity class associated with SQL queries is exactly the class of safe queries in $\mathsf{Q(FO(COUNT))}$ (first-order queries plus counting operator): SQL captures safe queries. (In other words, all SQL queries have a complexity in $\mathsf{Q(FO(COUNT))}$, and all problems in $\mathsf{Q(FO(COUNT))}$ can be expressed as an SQL query.)

Based on this result, from theoretical point of view, there are many interesting problems that can be solved efficiently but are not expressible in SQL. Therefore an extension of SQL which is still efficient seems interesting. So here is my question:

  Is there an extension of SQL (implemented and used in the industry) which captures $\mathsf{P}$ (i.e. can express all polynomial-time computable queries and no others)?

I want a database query language which stisfies all three conditions. It is easy to define an extension which would extend SQL and will capture $\mathsf{P}$. But my questions is if such a language makes sense from the practical perspective, so I want a language that is being used in practice. If this is not the case and there is no such language, then I would like to know if there is a reason that makes such a language uninteresting from the practical viewpoint? For example, are the queries that rise in practice usually simple enough that there is no need for such a language?

As for your main question, I recommend this short survey by Martin Grohe.

  Are the queries that are needed in practice usually simple enough that there is no need for a stronger language?

I'd say this holds most of the time, given the fair amount of extensions added to common query languages (transitive closure, arithmetic operators, counting, etc.). This comes from the point of view of somebody who has done some work as a freelance developer of relatively simple web sites and other applications, so I'm not sure about the real uses of SQL in bigger industries/larger databases.

In the rare cases a more powerful language might be needed, my guess is that software developers deal with them by using the language in which they write the application, not the queries (like C++ or java).

Your question is not clear enough if you want an extension that captures $P$ and only $P$ or if it captures $P$ and possibly things outside $P$. It looks like that you are interesting only in the exact $P$ class, since you want safe queries and if otherwise, any Turing-complete extension of SQL would do.

We don't know if $P = NP$. If $P = NP$, then a SQL extension capable of capturing $P$ and just $P$ should be capable to compute if a boolean formula is satisfiable in polynomial time or solve any other $NPC$ problem in polynomial time.

But, if $P \ne NP$, then your SQL-extended language will not be capable to compute if a given boolean formula is satisfiable.

So, we have a question: There exist and algorithm (or query, or whatever) written in such language that is capable to decide if a boolean formula is satisfiable? I can't answer this (and probably nobody here can, as answering this is answering if $P = NP$). This question makes me believe that it is very unlikely that this language exists for real purposes.

Althought it probably does not exists for real purposes, it surely exists and is constructible and implementable. You could define that language with something capable of simulating a Turing-machine up to a given unary number of steps. I.E, capable to solve a P-complete problem. However, if you construct such a thing, it is almost Turing-complete except for the "given a unary number of steps" restriction, which in an SQL-like language would be a very strange way to limit it to only safe queries. You could do this if the steps are records of some table, but this still does not looks anything valuable for practical purposes.


DFA for a language that accepts the addition of multiple of 2 and multiple of 5 I am trying to draw a DFA that accepts the following language:

$L=\{a^{2i+5j} : i , j \geq 0\}$

I started out by drawing an NFA, which I can then convert to a DFA but I am not sure if my NFA is correct.

All natural numbers are expressible in the form $2x+5y$, except for $1,3$. You can check this directly, of use the solutino of the Frobenius problem for two denominations. Therefore another way to write your language (assuming the alphabet is $\{a\}$) is
$$
\overline{\{a,a^3\}}.
$$
You can construct a DFA for this language using 5 states, that count up to 4 and then saturate.

If you want to implement the constraint $2x+5y$ directly as an NFA (which is more economical for larger values of $2,5$), then you construct the following NFA:

States: $q_0,a_1,b_1,b_2,b_3,b_4$.
Initial state: $q_0$.
Final states: $\{q_0\}$.
Transition function:
$$
\begin{array}{c|cccccc}
q & q_0 & a_1 & b_1 & b_2 & b_3 & b_4 \\\hline
\delta(q,a) & a_1,b_1 & q_0 & b_2 & b_3 & b_4 & q_0
\end{array}
$$

In words, there is a 2-cycle and a 5-cycle sharing a vertex $q_0$, which is also the initial state and the unique final state.


Recognizing a language given an automaton I'm trying to figure out which language can be recognized in this automaton

Automata http://cdn.imghack.se/images/64b81d259a1d403b810dd9744dc222f7.jpg

According to Wikipedia here "The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted by the automaton."

So using what Wikipedia states and knowing that this automaton is a finite state automaton, I would dare to say that this automaton accepts regular languages.

If I would use M to define this automaton then I could say:

The language recognized by M is the regular language given by a certain regular expression.

But I'm having a a hard time figuring out the regular expression.

I'm not sure of about this but here is what I think the regular expression looks like

$$
L = (a|b)(a|b)^*a^*
$$

I would appreciate any help in this matter

In general, there is a dynamic programming algorithm for converting finite automata into regular expressions. But this one is simple enough that we can eyball it.

From the start state, we have two choices. So we can see our expression has the form | where _ represents the parts of the expression yet to be filled in.

Let's look at the top branch. There we must read two a's, then as many a's or b's as we want. So this part will have the form aa(a|b)*

For the second half, we see we must read at least one a or b. Then we can loop on a or b as many times a we want, and then we must read two a's. So we get (a|b)(a|b)*aa

Notice the patterns here. When we have more than one transition coming out of a state, that represents the "|" operation. A transiton on "a,b" is equivalent to having one transition on a and another on b.

So, our final expression is (aa(a|b)*) | ((a|b)(a|b)*aa).

Any time we have a cycle, either on a particular state, or on a path of states, we get something corresponding to *. And every time we have to read something in sequence, we have concatenation.

Minimise the Automaton, as it is a Finite Automaton, so we can apply the method of minimising states. The RegEx will be formed that describes the language recognised by this automaton.
Edit: this answer seems to be wrong, please refer to David's comment below.


Check if language is decidable I would like to determine if the following language is decidable or not.
L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}.

I know that every finite language is decidable, but I am not sure if this has anything to do with this particular problem.

Every help is appreciated, I am a little lost.

Thank you

Define C = { $L | L$ is decidable by a turing machine with at most 42 states }

Notice that there is a finite amount of such languages, as there are a finite amount of turing machines with 42 states. for that reason, we have $C\ne\emptyset, \sum^*$

By Rice's theorem, the language $S=$ { $w | L(M_w) \in C$ } is undecidable. This language is precisely the language in question


Complexities of basic operations of searching and sorting algorithms Wiki has a good cheat sheet, but however it does not involve no. of comparisons or swaps. (though no. of swaps is usually decides its complexity). So I created the following. Is the following info is correct ? Please let me know if there is any error, I will correct it.

Insertion Sort:

Average Case / Worst Case : $\Theta(n^2)$ ; happens when input is
already sorted in descending order
Best Case : $\Theta(n)$ ; when input is already sorted
No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(n)$ in best case
No. of swaps : $\Theta(n^2)$ in worst/average case & $0$ in Best case

Selection Sort:

Average Case / Worst Case / Best Case: $\Theta(n^2)$
No. of comparisons : $\Theta(n^2)$
No. of swaps : $\Theta(n)$ in worst/average case & $0$ in best case
At most the algorithm requires N swaps, once you swap an element into place, you never touch it again.

Merge Sort :

Average Case / Worst Case / Best case : $\Theta(nlgn)$ ; doesn't matter at all whether the input is sorted or not
No. of comparisons : $\Theta(n+m)$ in worst case & $\Theta(n)$ in best case ; assuming we are merging two array of size n & m where $n<m$
No. of swaps : No swaps ! [but requires extra memory, not in-place sort]

Quick Sort:

Worst Case : $\Theta(n^2)$ ; happens input is already sorted
Best Case : $\Theta(nlogn)$ ; when pivot divides array in exactly half
No. of comparisons : $\Theta(n^2)$ in worst case & $\Theta(nlogn)$ in best case
No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

Bubble Sort:

Worst Case : $\Theta(n^2)$
Best Case : $\Theta(n)$ ; on already sorted
No. of comparisons : $\Theta(n^2)$ in worst case & best case
No. of swaps : $\Theta(n^2)$ in worst case & $0$ in best case

Linear Search:

Worst Case : $\Theta(n)$ ; search key not present or last element
Best Case : $\Theta(1)$ ; first element
No. of comparisons : $\Theta(n)$ in worst case & $1$ in best case

Binary Search:

Worst case/Average case : $\Theta(logn)$
Best Case : $\Theta(1)$ ; when key is middle element
No. of comparisons : $\Theta(logn)$ in worst/average case & $1$ in best case

I have considered only basic searching & sorting algorithms.
It is assumed above that sorting algorithms produce output in ascending order
Sources : The awesome CLRS and this Wiki

For general algorithm of bubble sort worst case comparisons are $\Theta(n^2)$ But for special case algorithm where in you add a flag to indicate that there has been a swap in previous pass. If there were no swaps then we come out of the loop since array is already sorted. In this case comparisons are $n$ not 0.

For Quick sort you have mentioned that worst case swaps are $n^2$. Well worst case scenario for quick sort is when all elements are in sorted order thus there won't be any swaps so it should be zero.


What course in CS deals with the study of RAM, CPU, Storage? I watched the Crash Course playlist of Computer Science. It was teaching about RAM, CPU, Storage etc but I felt it was way too fast and only people who have studied the course first hand understood it better.
So I wanted to ask what CS couse actually teaches the details of CPU, RAM and how it is build from the scratch with the help of Logic Gates.

The subject you're describing often goes under the names computer architecture, computer systems, computer organization and design, and the like. One example is Elements of computing systems, based on a course From Nand to Tetris originating in the Hebrew University. The Amazon page on the book links to other popular textbooks on the topic.
Generally speaking, this area is at the intersection of computer science and electrical engineering. Some aspects are much closer in spirit to electrical engineering, for example the physics behind memory and storage architectures. Other aspects, such as cache coherence algorithms and error-correcting codes, are more likely to be considered an integral part of both disciplines.

The basic concepts without gates goes under Operating Systems course, and with gates, clocks etc. goes under Digital Logic Design or (mostly) Microprocessors as I experienced.


How are binary trees represented on disk Assume I have a word document, the contents in it are stored on the disk as bits. Nothing so complex here. When the word processor reads those bits, it just knows how to display on screen.

But what about binary trees. They are just not data, they have route node, child nodes. How are they actually represented on disk?

I tried searching using this term "binary trees representation on disk". But I didn't find anything useful.

Let me know if I am not clear

Update:
I was looking for details on how actually they are stored on disk. Given this simple binary tree:

Any data is stored in bits on disk. How are these stored?

This may not be an exact answer but some information of interest related to your question

Other answers have mentioned various ways in which the binary data structure can be represented and you might want to use one of them but mostly when using databases the Adjacency List Model and Nested Set Model are used for representing Binary Trees.

Binary Trees are mostly not used for storing data on disk and some alternatives are usually preferred.If you are interested in optimized data access, search,insertion and deletion  on disk then you may want to consider these alternatives

B-Tree data structure is one of the alternatives used for storage on disk.It provides search, sequential access, insert, and delete  operations in logarithmic time and is optimized for disk storage.

B-Tree data structure was created by Rudolf Bayer and Ed McCreight in 1972 to  overcome a shortfall of Binary Tree i.e. using too many disk reads.B-Tree reduces the number of disk reads by allowing more keys in a single node ( typically making a B-tree node as large as the sector minimizes the number of access times).

SQL Server uses a further optimized extension of B-Tree data structure known as B+Tree in which only the leaf nodes hold the actual data and the rest of the nodes are pointers.

According to Wikipedia B+Trees are also used for storing directory structures by some filesystems:

  The ReiserFS, NSS, XFS, JFS, ReFS, and BFS filesystems all use this
  type of tree for metadata indexing; BFS also uses B+ trees for storing
  directories. NTFS uses B+ trees for directory and security-related
  metadata

Update
How will a tree be represented as bits on the disk?

Trees can be represented by using static data structures like arrays  in a  fashion similar to this,consider each row tag as an array

//Node A can be represented as

[row 1][node A data in bits][separator bits]
[pointer to B i.e row 2][separator bits]
[pointer to C i.e. row 3][row1end]

//Node B can be represented as

[row 2][node B data in bits] [separator bits]
[no child flag][separator bits][no child flag][row2end]

//Node C can be represented as

[row 3][node C data in bits] [separator bits]
[no child flag][separator bits][no child flag][row3end]

I'd recommend studying some file formats so that you know how to represent logical data in a file, this also might be helpful

dcs.gla.ac.uk/Keith/Chapter.4/Ch.4.html

How would you locate your word document?

By storing the location of the "word file" somewhere in an index which again gets stored somewhere, this structure itself represent a tree

For your ans,suppose you store the location of files("C:/abc/def/a.doc") in your "word document" and those files are also "word documents" which stores location of another files and so on, this is how trees are stored,however instead of file format they store memory location of other node and so on.


Intersection of two arrays As part of a project i'm doing I have been looking for a way to find common values between 2 arrays including duplicates.
For example;
A = [2, 2, 3, 5]
B = [2, 2, 5]
would return the array;
Common values = [2, 2, 5]
I have attempted using sets, and the intersection function, but neither gave duplicates
Any help appreciated

Python-specific questions are probably off-topic here, but this question can be seen as a language-agnostic algorithmic task: given two arrays $A$ and $B$, each representing a multi-set, return an array containing the elements in the multiset $C = A \cap B$.
Here an element $x$ that has multiplicity $a$ in $A$ and $b$ in $B$, has multiplicity $\min\{a,b\}$ in $C$.
To solve this problem you can preliminary sort $A$ and $B$. Then, you can keep a pointer $p_A$ to some element of $A$ and a pointer $p_B$ to some element of $B$. Initially $p_A$ (resp. $p_B$) will point to the first element of  $A$ (resp. $B$).
I will use $A[p_A]$ (resp. $B[p_B]$) to denote the element of $A$ (resp. $B$) pointed by $p_A$ (resp. $p_B$). Also, it is convenient to assume that, whenever $p_A$ (resp. $p_B$) points past the end of $A$ (resp. $B$), $A[p_A]$ (resp. $B[p_B]$) has value $+\infty$.
Proceed similarly to the merge step of Mergesort:

Initialize $C$ as an empty array.
While ($p_A$ is not past the end of $A$) or ($p_B$ is not past the end of $B$)

If $A[p_A] = B[p_B]$:

Append $A[p_A]$ to $C$.
Advance $p_A$
Advance $p_B$.

Else if $A[p_A] > B[p_B]$:

Advance $p_B$

Else (in this case $A[p_A] < B[p_B]$):

Advance $p_A$

#include <stdio.h>
int main() {
int n1,n2,n3,i,j,k,count=0;
int a[n1],b[n2],c[n3];
n1=sizeof(a)/sizeof(a[0]);
n2=sizeof(b)/sizeof(b[0]);
n3=sizeof(c)/sizeof(c[0]);
printf("Enter the size of each array\n");
scanf("%d %d %d",&n1,&n2,&n3);
printf("enter %d elements:\n",n1);
for(i = 0; i < n1; i++) {
 scanf("%d", &a[i]);

}printf("enter %d elements:\n",n2);
for(i = 0; i < n2; i++) {
 scanf("%d", &b[i]);

}printf("enter %d elements:\n",n3);
for(i = 0; i < n3; i++) {
 scanf("%d", &c[i]);

}printf("Intersection elements:\n");
for(i=0;i<n1;i++){
  for(j=0;j<n2;j++){

    if (a[i]==b[i]){

      for(k=0;k<n3;k++){

            if((a[i]==b[j])&&(b[j]==c[k]))

                    printf("%d\n",a[i]);

                    count++;

                }

          }

      }

}

printf("No.of loops %d\n",count);
return 0;
}


how to prove that every finite language is context-free? I am trying to prove that every finite language is context-free, is there any type of way that I could do it effectively?

It's not hard to show that every finite language is regular. If you know that every regular language is also context-free, you're done.

Every finite language is Regular. ( Because we can construct a finite automata for it )

Every regular language is cf. ( Because regular language is subset of cf )

Hence proved.


Edge exchange property of two Minimum Spanning Trees Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T'
Then I want to prove the following:

For every edge e in T that's not in T', there is an edge e' in T'
that's not in T such that if we replace e with e' in T (let's call
it T_new) then it's still a minimal spanning tree of G.

I think I am too close for finding the right algorithm but stuck a little:

I have proved that weight(e) must be exactly equal to weight(e').

Since T is a tree, deleting e will result in 2 separated components, then for T_new to be a tree it must use one of the edges connecting two vertices from those different components.

But, I wasn't able to know which edge e' exactly will work. Plus I wasn't able to prove that always there is such an edge (I just found some requirements for e' that is must satisfy).
Some notes: I know Kruskal algorithm, and familiar with an algorithm in which we can paint some edges in yellow and request it to generate minimal spanning trees with maximum yellow edges (In other words from all found minimal spanning trees return the one with maximum number of yellow edges)

Here is a proof. Let $V$ be the vertices of $G$. $V$ are also the vertices of $T$ and the vertices of $T'$.
If $e$ is deleted from $T$, we will get two trees. Let the vertices of these two trees be $(V_1, V_2)$, which is a cut of $V$.
Since $T'$ is a tree, if we add $e$ to it, we will obtain a cycle. Since that cycle crosses $(V_1, V_2)$ at $e$, it must cross $(V_1, V_2)$ at another edge, say, $e'\in T'$.

Since $T \setminus \{e\}\cup \{e'\}$ is a spanning tree of $G$ and $T$ is an MST,  $\text{weight}(e) \le \text{weight}(e')$.
Since $T' \setminus \{e'\}\cup \{e\}$ is a spanning tree of $G$ and $T'$ is an MST,  $\text{weight}(e') \le \text{weight}(e)$.

So, $\text{weight}(e) = \text{weight}(e')$.
$T \setminus \{e\}\cup \{e'\}$, which is a spanning tree of the same weight as $T$,  must be an MST of $G$. $\quad\checkmark$

Add an edge to a spanning tree and you have a cycle. Deleting any edge in that cycle results in a new spanning tree.


Formula for finding number of colors to color a map such that no two adjacent counties have the same color Is there a formula for determining the minimum number of colors to color a map with n counties such that no adjacent county have the same color?

No.

The famous four-colour theorem says that four colours are always enough (assuming that counties are contiguous areas of land).
It's easy to tell if one colour is enough: this is the case only if every county is an island, so has no border with any other county.
It's easy to tell if two colours is enough: this corresponds to the adjacency graph being bipartite. You can determine this by colouring an arbitrary county red, then colouring all its neighbours blue, then colouring all their neighbours red, and so on. If this process produces a legal colouring, you have your colouring; if it fails, it turns out that there is no colouring with two colours.
If two colours isn't enough, then it's NP-complete to tell whether three is enough or you have to use four.  This means that, as far as we know, there's no efficent algorithm to determine whether an arbitrary map can be coloured with three colours. This is a result due to Garey, Johnson and Stockmeyer (Some simplified NP-complete graph problems, Theoretical Computer Science, 1(3):237--267, 1976; Science Direct).

There are efficient algorithms to find four-colourings of planar graphs: the two computer-assisted proofs that four colours is enough both gave algorithms. But, as noted above, there's no known efficient algorithm to tell whether four colours is optimal for a given map.

In this case the problem is NP-complete. By the way we know that:

Given a graph $G$, let $\chi(G)$ be the number of colors of $G$ and $\Delta(G)$ the maximum degree in $G$.  we have that $\chi(G)\le \Delta(G)+1$.

However if $G$ is a planar graph (a map), then $\chi(G)\le 4$.

For more information see the "Four color theorem by Kenneth Appel and Wolfgang Haken".


How to create DFA from regular expression without using NFA? Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that?

I asked this question to our professor but he told me that we can use intuition and kindly refused to provide any explanation. So I wanted to ask you.

"Regular exp>NFA>DFA conversion" is not an option because such a conversion takes a lot of time to convert a rather complex regular expression. For example, for a certain regex "regex>NFA>DFA" takes 1 hour for a human being. I need to convert regex to DFA in less than 30 minutes.

Since you want "to convert regex to DFA in less than 30 minutes", I suppose you are working by hand on relatively small examples.

In this case you can use Brzozowski's algorithm $[1]$, which computes directly the Nerode automaton of a language (which is known to be equal to its minimal deterministic automaton). It is based on a direct computation of the derivatives and it also works for extended regular expressions allowing intersection and complementation. The drawback of this algorithm is that it requires to check the equivalence of the expressions computed along the way, an expensive process. But in practice, and for small examples, it is very efficient.

Left quotients. Let $L$ be a language of $A^*$ and let $u$ be a word. Then
$$
u^{-1}L = \{v \in A^* \mid uv \in L \}
$$
The language $u^{-1}L$ is called a left quotient (or left derivative) of $L$.

Nerode automaton. The Nerode automaton of $L$ is the deterministic automaton $\mathcal{A}(L) = (Q, A, \cdot, L, F)$ where $Q = \{u^{-1}L \mid u \in A^*\}$, $F = \{u^{-1}L \mid u \in L\}$ and the transition function is defined, for each $a \in A$, by the formula
$$
  (u^{-1}L)\cdot a = a^{-1}(u^{-1}L)=(ua)^{-1}L
$$
Beware of this rather abstract definition. Each state of $\mathcal{A}$ is a left quotient of $L$ by a word, and hence is a language of $A^*$. The initial state is the language $L$, and the set of final states is the set of all left quotients of $L$ by a word of $L$.

Brzozowski's algorithm. Let $a, b$ be letters. One can compute the left quotients using the following formulas:
\begin{align*}
a^{-1}1 &= 0  & a^{-1}b &= \begin{cases}
 1 &\text{if $a = b$}\\
    0 &\text{if $a \not= b$}\\
\end{cases}\\
a^{-1}(L_1 \cup L_2)       &= a^{-1}L_1 \cup u^{-1}L_2,&
a^{-1}(L_1 \setminus  L_2) &= a^{-1}L_1 \setminus  u^{-1}L_2,\\
a^{-1}(L_1 \cap L_2)       &= a^{-1}L_1 \cap u^{-1}L_2,  &
a^{-1}L^* &= (a^{-1}L)L^*
\end{align*}
\begin{align*}
a^{-1}(L_1L_2)             &=
\begin{cases}
  (a^{-1}L_1)L_2                 &\text{si $1 \notin L_1$,}\\
    (a^{-1}L_1)L_2 \cup a^{-1}L_2  &\text{si $1 \in L_1$}\\
\end{cases}\\
%\\v^{-1}(u^{-1}L) &= (uv)^{-1}L.
\end{align*}

Example.
For $L = (a(ab)^*)^* \cup (ba)^*$, we get successively:
\begin{align*}
1^{-1}L &= L=L_1\\
a^{-1}L_1 &=(ab)^*(a(ab)^*)^*=L_2\\
b^{-1}L_1 &= a(ba)^*=L_3\\
a^{-1}L_2 &= b(ab)^*(a(ab)^*)^* \cup (ab)^*(a(ab)^*)^*=bL_2 \cup L_2=L_4\\
b^{-1}L_2 &=\emptyset \\
a^{-1}L_3 &=(ba)^*=L_5\\
b^{-1}L_3 &=\emptyset \\
a^{-1}L_4 &= a^{-1}(bL_2 \cup L_2)=a^{-1}L_2=L_4 \\
b^{-1}L_4 &= b^{-1}(bL_2 \cup L_2)= L_2\cup b^{-1}L_2 = L_2 \\
a^{-1}L_5 &= \emptyset\\
b^{-1}L_5 &=a(ba)^*=L_3
\end{align*}
which gives the following minimal automaton.

$[1]$ J. Brzozowski, Derivatives of Regular Expressions, J.ACM 11(4), 481–494, 1964.

Edit. (April 5, 2015) I just discovered that a similar question: What algorithms exist for construction a DFA that recognizes the language described by a given regex? was asked on cstheory. The answer partly addresses complexity issues.

Though this is not the correct way but it works most of the time.

First Step : Find the smallest string that can be accepted by the Regular Expression.
Second Step : Draw necessary states with the transaction of the minimum string accepting machine.
Third Step : For all states draw the remaining alphabets transactions.

For Example : Regular Expression (0 + 1)* 1 "String ending with 1"
Step 1: Smallest String : 1
Step 2: two states Q0 and Q1. having the transaction of 1 from Q0 to Q1. and Q1 is the accepting state.
Step 3: for Q0 State
          Q0 1 transaction is to Q1. Now make 0 transaction in Q0 itself.
        For Q1 State
          Q1 1 transaction will remain in Q1. And 0 transaction will go in Q0.


Minimum spanning tree and its connected subgraph This problem is from the book [1]. In case of being closed as a duplication of that in [2], I first make a defense:

The accepted answer at [2] is still in dispute.
The proof given by @eh9 is based on Kruskal's algorithm.
I am seeking for a proof independent of any MST algorithms.

  Problem: Let $T$ be an MST of graph $G$. Given a connected subgraph $H$ of $G$, show that $T \cap H$ is contained in some MST of $H$.

My partial trial is by contradiction:

  Suppose that $T \cap H$ is not contained in any MST of $H$. That is to say, for any MST of $H$ (denoted $MST_{H}$), there exists an edge $e$ such that $e \in T \cap H$, and however, $e \notin MST_{H}$.
  Now we can add $e$ to $MST_{H}$ to get $MST_{H} + {e}$ which contains a cycle (denoted $C$).

  Because $MST_{H}$ is a minimum spanning tree of $H$ and $e$ is not in $MST_{H}$, we have that every other edge $e'$ than $e$ in the cycle $C$ has weight no greater than that of $e$ (i.e., $\forall e' \in C, e' \neq e. w(e') \le w(e)$).
  There exists at lease one edge (denoted $e''$) in $C$ other than $e$ which is not in $T$. Otherwise, $T$ contains the cycle $C$.

  Now we have $w(e'') \le w(e)$ and $e \in T \land e'' \notin T$, $\ldots$

I failed to continue...

Algorithms, Chapter 5: Greedy algorithms
"Minimum Spanning tree subgraph"@StackOverflow

Flaws in the accepted answer: When I re-read the accepted answer given by @Mahmoud A. today, I find flaws in it.

Consider the figures for an example:

In this example, $e = CE$. In figure (5), the edge $CD$ in the cycle created by adding edge $e = CE$ into $T_H$ is not in $T_G$ shown in figure (2), but we have $w(CD)<w(e=CE)$. So the claim "For every other edge $e' \notin T_G$ in the cycle we have $w(e′)=w(e)$" does not hold.

Note: In the following, I fix the flaws. I leave the answer given by @Mahmoud A. as accepted because it is original and insightful.

Correction: While where is an edge $e \in T_G \cap H$ such that $e \notin T_H$ do:

Adding $e$ to $T_H$ to create a cycle $C$.

1.1 Because $T_H$ is an MST of $H$, for every other edge $e' \in C$ we have $w(e') \le w(e)$. Otherwise, for any edge $e' \in C$ such that $w(e')>w(e)$, $T_H + \{ e \} - \{ e' \}$ has smaller weight than $T_H$.
1.2 Let $e = (u,v)$. Remove $e$ from $T_G$. Then vertices $u$ and $v$ are separated into two different connected components, denoted by $U \ni u$ and $V \ni v$, of $T_G$. Because $T_H$ is an MST of $H$ (which includes vertices $u$ and $v$) and $e \notin T_H$, there must be an edge $e'' \in C$ which connects the two components $U$ and $V$ again.
We claim that $w(e'') = w(e)$. In 1.1, we have proved that $w(e'') \le w(e)$ (replacing $e'$ there by $e''$). If $w(e'') < w(e)$, then $T_{G} - \{ e \} + \{ e'' \}$ has smaller weight than $T_G$.
1.3 According to 1.1 and 1.2 above, there are an edge $e'' \in C$ such that $e'' \neq e \land w(e'') = w(e)$. We replace $e''$ with $e$ in $T_H$ to obtain $T'_H = T_H - \{ e'' \} + \{ e \} \in MST_H$.
Since $e'' \notin T_{G} \cap H$ and $e \in T_{G} \cap H$, $T'_H$ contains one more common edge with $T_{G} \cap H$ than $T_H$ does.

Rename $T'_H$ to $T_H$

EndWhile

After the loop we have $T_{G} \cap H \subseteq T_H$.

First assume the edge weights are distinct.  Kruskal's algorithm then implies that the MSTs $T$ of $G$ and $T'$ of $H$ are unique.  Let $S = T\cap E(H)$ and suppose that $e\in S\setminus T'$.  Because $e\notin T'$, the weight $w(e) > w(e')$ for each $e'$ on the fundamental cycle $C$ of $e$ in $T'$.  This then implies that, at the moment $e$ was added to $T$ in the Kruskal algorithm, each such $e'$ already was spanned by some connected component of a sub-forest $F$ of $T$.

In fact, $F$ has to be a sub-tree of $T$, since $C\setminus e$ is connected, and the trees of $F$ covering the endpoints of pairs of edges incident on a common vertex must be the same.

Now we are at a contradiction: both endpoints of $e$ are in a subtree of $T$ not containing $e$.  This is impossible if $T$ is actually a tree.

For the non-unique weights case, just pick an order of the edges consistent with the weights and then perturb them to reduce to the distinct case.


Fixed point, what does it mean in the world of computer science I keep coming across references to fixed point in questions and answers at stackexchange and I look up the meaning on the web obviously finding reference at sites such as Wikipedia. However none of the references really answer my question of what is a fixed point and what does it mean in the world of computer science.

EDIT

After 8 years this finally popped into my head.

How would you explain fixed point to a kindergartner?

A fix point is when you do the same thing again and again and nothing changes. So if your room is messy and you clean it, it is now at a fixed point because if you clean it again it is still clean.

I know there is a joke or comic in there somewhere but I don't have my comedian hat on today.

In computer science, the arguably most prominent use of fixed-points is in lattice theory¹. A lattice is a partially ordered set $(S, \leq)$ with the additional property that given any two elements $x,y \in S$, the set $\{x,y\}$ has both a supremum and infimum (in $S$).

Now you often consider monotone functions $f$ on this lattice which "converge", that is for some $x \in S$ you have $f(x)=x$. Important results in this area are Kleene's fixed-point theorem and the Knaster-Tarski theorem.

A prominent example is the lattice $(2^A,\subseteq)$ for $A$ some set, and $f$ induced by an inductive definition. For example, let $A = \{a,b\}^*$ and we define a language $L \in 2^{\{a,b\}^*}$ by

$\qquad \begin{align}
  \phantom{w \in L} &\phantom{\implies} \varepsilon, a \in L \\
  aw \in L &\implies baw \in L \\
  bw \in L &\implies abw, bbw \in L
\end{align}$

This inductive definition corresponds to the monotone function

$\qquad \displaystyle f(A) = \{\varepsilon, a\} \cup A \cup \{baw \mid aw \in L\} \cup \{abw, bbw \mid bw \in L\}$

By Knaster-Tarski theorem, we know $f$ has a smallest fixpoint which is a supremum of all smaller "intermediate results" (which correspond to finitely often applying the constructors of the inductive definition), and that smallest fixpoint is indeed $L$.

By the way, the largest fixpoint also has uses; see here for an example.

In recursion theory, there is another fixed-point theorem, also due to Kleene. It says²,

  Let $\varphi$ a Gödel numbering³ and $ r :\mathbb{N} \to \mathbb{N}$ a total, computable function (intuition: a compiler). Then there is $i \in \mathbb{N}$ such that $\varphi_{r(i)}=\varphi_i$.

In fact, there are even infinitely many such $i$; if there where only finitely many, we could patch $r$ (by table-lookup) to not have fixed-points, contradicting the theorem.

Everybody uses it every day, even if you don't realise it.
I don't like that Wikipedia article; you are probably better off checking a genre book.
A special kind of function numbering. For intuition, think of it as a (Turing-complete) programming language.

game theory is a major subarea of CS and an important concept there is the Nash equilibrium which is a fixed point theorem. it gives a means of identifying optimal game strategies given that other players are aware of each others strategies. it can be proven via Kakutani fixed point theorem or the Brower fixed point theorem. Nash won the Nobel Prize in Economics in part for developing this theory.


Minimal DFA for language of all strings over $\{a,b\}$ whose penultimate symbol is $b$ Design a minimum state deterministic finite automata for accepting those strings over the alphabet $\{a, b\}$ whose last but one symbol is $b$.

Note that we have at least three states:

The second last character is $b$ so the tail 2-substring is either $ba$ or $bb$.
The last two characters are $ab$ (read at least one more character).
The last two characters are $aa$ (read at least two more characters).

which leads to the following DFA:

The above DFA contains minimal number of states if and only if it equals its minimization. Following this page in DFA Minimization using Equivalence Theorem we have

$P_0 = \{(1, 2), (3)\}\\
P_1 = \{(1), (2), (3)\}$

In $P_1$ we used the fact that one single character may lead state 2 to an accepting state, whereas 1 does not "reach that far". Since $P_1$ gives no opportunity for further refinement, we may stop and we know that the DFA is minimized.

Here second symbol from rhs is b or penultimate symbol is b


How do contemporary processors differ from a pure von Neumann architecture? So I never really understood the von Neumann architecture, and have started to revise it as I wasn't in school during the lessons of the CPU. Can't really get help through my teacher as they wont respond to their email.

I have learnt about the von Neumann architecture, and now I need to know how the architecture differs from a contemporary processor.

I know that contemporary processors sometime use a mixture of Harvard and von Neumann architecture by using Harvard for the communication between the control unit and caches though for cost effective reasons von Neumann is used between the main memory and cpu.

The specification point wants to know how it differs though, and I will be very thankful for any responses that might answer the question.

Thanks!

Well I think I may have answered my own question, the specification just wanted to know how it differs from the pure von Neumann architecture. It differs as contemporary processors use a mixture of architectures from Harvard and von Neumann for many reasons (mainly cost) and where speed advantages outweigh the complexity costs.

Contemporary processors use a mixture of both von Neumann and Harvard architecture, which differs from a pure von Neumann architecture by using von Neumann architecture for the main memory to the CPU and Harvard for the control unit and caches.


Shortest path in a known room for a Roomba I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search can do this, but I was left wondering if you could minimize the backtracking.

I looked into how it's actually done for Roomba and from what I read on Robotics stack exchange, it doesn't use a deterministic algorithm that guarantees shortest distance, because it doesn't know the room layout and obstacles ahead of time.

But what if we did know the full layout of the room at the start? Is there a way to use a map to generate a path through the room with minimum backtracking? In this example, the map is an undirected graph without weights (or every joining edge distance is 1), and it likely contains cycles.

The problem sounds similar to travelling salesman and Hamiltonian paths, but I don't think it maps to them exactly. Travelling salesman and Hamiltonian paths have the requirement that vertices are only visited once. In the Roomba example, we don't care if it vacuums the same spot twice, we just want it to thoroughly vacuum the whole room (don't miss anywhere) as fast as possible.

the classic A* algorithm was invented in 1968 and is used for the purpose of shortest path-finding by robots, and it is provably optimum in a limited sense (eg given an unchanging layout and other constraints). there are many other pathfinding algorithm variants, basically "smart graph traversal" algorithms, eg focused on the online problem with changing constraints, see eg "how do state of the art pathfinding algorithms differ", cstheory.

here is some information on the roomba algorithm which is somewhat proprietary based on an interview with one of the designers (the interview seems no longer available). it is somewhat random and apparently uses a locally optimizing algorithm aka "greedy".


Correctness proof of greedy algorithm for 0-1 knapsack problem We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an optimal solution.

Given the two orders I imagined that we could just choose the first k elements from either sequence and use them to fill knapsack until it was full. This would be similar to choosing the items with the greatest ratio of value to weight. But I don't think that is an optimal solution.

So what I need help with is whether or not this solution is optimal. And how would I prove the correctness of a greedy algorithm.

Hint: Let $x$ be the item of smallest weight (and so of highest value). Take any solution which doesn't contain $x$. If there is room for $x$, add it to the solution. Otherwise, remove some element and add $x$ (why is that possible? does it necessarily improve the solution?). Conclude that the optimal solution always contains $x$. Apply this reasoning recursively to come up with a greedy algorithm.

Let O be the optimal solution.

O = {o1, o2, o3 ..., oj}

Let G be our greedy solution.

G = {g1, g2, g3, ..., gk}

K = Initial Weight = Empty Knapsack

K = k - 0              //Initially

If g1 is in O then we are done.

But if g1 does not exist in O, then there might be another optimum solution.

O' = O - {g1}          Equation : 1
K' = K - {g1}          Equation : 2   //Which means w1(least weight)

If O' does not make an optimal solution then, our claim is wrong that g1 does not exist in O.

Therefore,

O' = K'   // Since the optimum solution should have next weight possible
O' = K - {g1}          From Equation : 2
O' = O - {g1}          From Equation : 1
O - {g1} = K - {g1}    Equating

So, O = K

which proves that, The optimal solution after removing g1 from O' is still O.

Q.E.D


Are all Integer Linear Programming problems NP-Hard? As I understand, the assignment problem is in P as the Hungarian algorithm can solve it in polynomial time - O(n3). I also understand that the assignment problem is an integer linear programming problem, but the Wikipedia page states that this is NP-Hard. To me, this implies the assignment problem is in NP-Hard.

But surely the assignment problem can't be in both P and NP-Hard, otherwise P would equal NP? Does the Wikipedia page simply mean that the general algorithm for solving all ILP problems is NP-Hard? A few other sources state that ILP is NP-Hard so this is really confusing my understanding of complexity classes in general.

If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard.
It is perfectly possible for other specific classes of instances to be solvable in polynomial time.

Consider for example the problem of finding a 3-coloration of a graph. It is a well-known NP-Hard problem. Now imagine that its instances are restricted to graphs that are, for example, trees. Clearly you can easily find a 3-coloration of a tree in polynomial time (indeed you can also find a 2-coloration).

Consider decision problems for a second.
A method of proving the hardness of a decision problem $P$ is devising a polynomial (Karp) reduction from another problem $Q$ that is known to be NP-Hard.
In this reduction you show that there exists a function $f$ that maps each instance $q$ of the problem $Q$ to an instance of the problem $P$ such that:
$q$ is a yes instance for $Q \iff f(q)$ is a yes instance for $P$.
This implies that solving $f(q)$ must be "at least as difficult" as solving $q$ itself.

Notice how it's not required for the image of $f$ to be equal to the set of the instances of $P$ . Therefore it's perfectly possibile for problem $P$ restricted to some subset of instances to not be hard.

To return to your original question:

The assignment problem can be solved in polynomial time, i.e., a solution to each instance of the assignment problem can be computed in polynomial time.
ILP is NP-Hard: in general it might be hard to compute a solution to an ILP problem, i.e. there are instances of ILP that are hard.
Some specific instances of ILP can be solved in polynomial time.

The assignment problem is not a ILP, but an LP problem and therefore not NP-hard.


Finding a O(n) solution to: max difference of pairs array question I don't know an O(n) solution to the following:

Given an array of n integers, find the largest difference between any two pairs in the array: however, the larger integer must have a higher index in the array than the other.

Ex: alg({9, 2, 6, 7}) = 5

It seems straightforward, yet it eludes me.

Create an array considering the minimum value seen so far in the array (in O(n)).

Ex. (9, 2, 2, 2)

Create an array containing the differences between the previous array and the original array (again, in O(n)).

Ex. (0, 0, 4, 5)

Find the maximum value in the array (O(n)). In this case, the answer is 5 as required.

This can be done in O(1) memory and only one pass if a few optimizations are made.

It is rather tempting to think that the problem asks for the largest and smallest integers in the array such that the larger integer has a higher index, and therefore forget about "largest difference". It is rather straightforward if you don't get trapped in thoughts like that! The code below solves the problem:

larger = array[1];
smaller = array[0];
smallest = array[0];
largest_difference = array[1]-array[0];

for(i=1; i<n-1; i++)
{
    if(array[i] < smallest)
        smallest = array[i];

    if( array[i+1] - smallest > largest_difference )
    {
        largest_difference = array[i+1] - smallest;
        smaller = smallest;
        larger = array[i+1];
    }
}

Proof: In short, for every integer X in the array starting from X=array[1], we know the smallest integer S before it. We compute its difference with this smallest integer (X-S), and so we know the largest difference as far as 'X' is concerned. As we do this for all X, we keep track of the largest of these 'largest differences'.


Why would anyone want CISC? In our computer systems lecture we were introduced to the MIPS processor. It was (re)developed over the course of the term and has in fact been quite easy to understand. It uses a RISC design, that is its elementary commands are regularly encoded and there are only few of them in order to keep the wires simple.

It was mentioned that CISC follows a different philosophy. I looked briefly at the x86 instruction set and was shocked. I can not image how anyone would want to build a processor that uses so complex a command set!

So I figure there have to be good arguments why large portions of the processor market use CISC architectures. What are they?

There is a general historical trend.

In the olden days, memories were small, and so programs were perforce small. Also, compilers were not very smart, and many programs were written in assembler, so it was considered a good thing to be able to write a program using few instructions. Instruction pipelines were simple, and processors grabbed one instruction at a time to execute it. The machinery inside the processor was quite complex anyway; decoding instructions was not felt to be much of a burden.

In the 1970s, CPU and compiler designers realized that having such complex instructions was not so helpful after all. It was difficult to design processors in which those instructions were really efficient, and it was difficult to design compilers that really took advantage of these instructions. Chip area and compiler complexity was better spent on more generic pursuits such as more general-purpose registers. The Wikipedia article on RISC explains this in more detail.

MIPS is the ultimate RISC architecture, which is why it's taught so often.

The x86 family is a bit different. It was originally a CISC architecture meant for systems with very small memory (no room for large instructions), and has undergone many successive versions. Today's x86 instruction set is not only complicated because it's CISC, but because it's really a 8088 with a 80386 with a Pentium possibly with an x86_64 processor.

In today's world, RISC and CISC are no longer the black-and-white distinction they might have been once. Most CPU architectures have evolved to different shades of grey.

On the RISC side, some modern MIPS variants have added multiplication and division instructions, with a non-uniform encoding. ARM processors have become more complex: many of them have a 16-bit instruction set called Thumb in addition to the “original” 32-bit instructions, not to mention Jazelle to execute JVM instructions on the CPU. Modern ARM processors also have SIMD instructions for multimedia applications: some complex instructions do pay after all.

On the CISC side, all recent processors are to some extent RISC inside. They have microcode to define all these complex macro instructions. The sheer complexity of the processor makes the design of each model take several years, even with a RISC design, what with the large number of components, with pipelining and predictive execution and whatnot.

So why do the fastest processors remain CISC outside? Part of it, in the case of the x86 (32-bit and 64-bit) family, is historical compatibility. But that's not the whole of it. In the early 2000s, Intel tried pushing the Itanium architecture. Itanium is an extreme case of complex instructions (not really CISC, though: its design has been dubbed EPIC). It even does away with the old-fashioned idea of executing instructions in sequence: all instructions are executed in parallel until the next barrier. One of the reasons Itanium didn't take is that nobody, whether at Intel or elsewhere, could write a decent compiler for it. Now a good old mostly-sequential processor like x86_64, that's something we understand.

CISC cpu has more advantages than RISC. Because CISC use less hardware register and XNOR/XOR gates than RISC many times!!!! Imagine the instruction bytes in CISC will be executed-sequence, there is only one logic gate and register is used. If 1 bilion transistors can produce about 300 million logic gates, so you can process 300 milion operators or processes (IF, equal, mathematic, variable, addressing... etc) and more program can run in CISC. But in RISC, it takes dozen times of logic gates for running a program in pipelined design. So 300 milion x 50 times (50 instructions) + 15000000000 bit counters!!! in so-called RISC. CISC use more hardware to reduce software algothrim which slow down the cpu.


Construct a grammar for the language How can I achieve this. Write a grammar for the language consisting of strings built only of the letters a and b. The strings may have any number of these letters, but the letter combinations bab must be in each string somewhere, and each string must start with a bb. For example, the strings bbababbbaa, bbbaaaababaa, and bbbab are in the language, while a, aabb, baaa, and bbba are not.

The string much start with $ bb $ .
There should at least one occurrence of the sub-string $ bab $

Hence, the structure of the regular expression must be something like this:
$$ bb[some \: string]bab[some \: string] $$

and, we can define $ [some \: string] $ something like this:

$$ (a + b)^* $$

which means, there can be any number (including 0) of either a's or b's.
Therefore, the final regex for the word is,
$$ bb(a+b)^*bab(a+b)^* $$


A recursively enumerable language and a recursively enumerable set I am confused between these two terminologies: recursively enumerable language, recursively enumerable set.

Do they have the exactly same meaning?

No they do not have exactly the same meaning. A language is a set of strings, whereas a set can be virtually anything. Usually such a set is a set of (natural) numbers, but we also can consider sets of graphs.

However, when the sets are accepted or generated by Turing machines, then they have to be represented on a tape (for input or output). This means they have to be represented as strings anyhow. Hence for the Turing machine itself there is no difference. Only for the human beholder there is an interpretation of the string as number or graph.

The language describes the set, it defines how to decide if a given element is part of the set or not.

The complexity in your given case for that decision is recursively enumberable.
You could create a Turing Machine to make this decision, or an computer program in any other prorgamming language like e.g. Java.

Example:
The Java compiler tells you if the given input is part of Java or not.
Language: Java
Set: All possible programs accepted by the Java Compiler
Complexity: Time a Turing Machine will take to decide if input is part of the set defined by the language.

Personally I would say the terms can be regarded as the same thing at least in spoken language.


Steiner tree problem with the known optimal subset of Steiner vertices in approximation algorithms I want to prove that the hardness of the Steiner tree problem lies in determining the optimal subset of Steiner vertices that need to be included in the tree and I need to show this by proving that if this set is provided, then the optimal Steiner tree can be computed in polynomial time.

It is clear that we can find an MST on the union of this set and the set of required vertices with Kruskal algorithm, and by contradiction proof, can be said that if this union of sets didn't give the MST so the subset of Steiner vertices is not the optimal subset.  Any hints or tips would be appreciated.

It can be proved as I mentioned with  contradiction, assume that $S1$ is the optimal subset of steiner nodes and $R$ is the required nodes, so we give the subgraph of main graph including $S1$ and $R$ nodes and the edges between them to Kroskal algorithm then we have a MST for them, we assume that it is not equal to OPT (solution for steiner tree problem), so the given subset (S1) was not optimal I mean at least one steiner node was not given or was given falsly.


Can the algorithm be optimized? I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach with mermoization and a bottom up using dynamic programming. Even the brute force apporach always starts using a top down approach breaking the problem down into smaller sub problems and then caching.

However, I have written the following algorithm that is not optimized to do the same but cannot figure out how to apply memoization. Is it even possible?

My basic algorithm is I start from sum = 0 and keep count of how many coins I have used by adding coin values and then returning the minimum count.

//function is called with sum = 0, coins = 0 and minCoins = Integer.MAX_VALUE
//coins[] contains the different coin denominations and target is the desired amount
// count is the number of coins that have been used

public static int makeChangeBacktracking(int sum, int[] coins, int target, int count, int minCoins) {

        if(sum == target) {
            return count;
        }

        for(int coin : coins) {
            //choose
            sum+= coin;
            //explore
            if(sum <= target) { //if it is greater than the target then why recurse???
                int c = makeChangeBacktracking(sum, coins, target, count + 1, minCoins);
                if(minCoins > c) {
                    minCoins = c;
                }
                //undo
                sum-= coin;
            }
        }
        return minCoins;
    }

I would like to apply any technique to improve the run time of the above algorithm. A clear explanation of whether or not memoization or other optimization techniques can be applied to this to speed up would be helpful.

A simple and efficient algorithm would be (correct me if I'm wrong):

1) Find the biggest valued coin just below that particular amount
2) Do the same thing with amount - coin_chosen
3) Repeat until convergence

Does this solve your problem?

e.g   Available coins: 1p,2p,5p,10p,20p,50p,£1 ...
47p -> -20p -> 27p -> -20p -> 17p -> -10p -> 7p -> -5p -> 2p -> -2p -> 0p

There are other less efficient ways to do this like maybe using genetic algorithms but I guess this would be the quickest ...


What is the exact relation between programming languages and Turing machines? I don't know much about yacc, bison, flex or lex and please correct me if I'm wrong but a programming language is also a Turing machine and a Turing machine is defined as the tuple $(Q, \Gamma, b, \Sigma, \delta, q_0, F)$ where $Q$, $\Gamma$, $b \in \Gamma$, $\Sigma \subseteq \Gamma \smallsetminus \{ b \}$ as input, $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{ L, R, N \}$ as transition function where $L$ = number of steps to the left, $R$ = number of steps to the right, $N$ = "standby", $q_0 \in Q$ is the initial state and $F \subseteq Q$ is the set of end states.

How similar is implementing a programming language to implementing a Turing machine? Can it be said that what is done when a programming language is implemented is that a Turing machine like the above is defined? If yes, how come we can't just use a model that looks like the definition of a Turing machine when a programming language is defined? Instead something else like BNF seems to be the standard.

Maybe I'm misreading the question, but it sounds like there's some confusion in the comparison between Turing machines and programming languages.

The definition and method of defining a Turing machine constitute a programming language. Turing machines represent programs in that language.

Language syntax and semantics (e.g., in BNF) can constitute a programming language, and artifacts which satisfy those syntactic and semantic constraints are programs in that language.

So it's not really precise (IMHO; of course we can think about what TMs do in different ways, and in some of these ways of looking at TMs, you could think of individual TMs as defining programming languages. Indeed, a classically constructed universal Turing machine defines a very clear programming language, i.e., representations of Turing machines as strings) to compare implementing a programming language to implementing a Turing machine. Implementing a programming language involves defining the rules of the game, much like Turing defined the rules of the game (or whoever it was, whatever) when he defined what it meant for something to be Turing machine.

"Implementing" a programming language, and defining Turing machines, is a very difficult activity. Writing programs in a language, and defining specific Turing machines, is also a difficult activity. But they are quite different activities (except in those exceptional cases where you're writing a Turing machine to act as an interpreter, in which case maybe it makes sense to talk about designing a programming language via writing a TM... but I'm not sure this is what you were after).

nice question, but you're overthinking this. getting lost in the symbols. lets look at it all in a simple, basic way. a programming language is in ASCII or say just 0/1 bits for characters. now imagine the TM has 0/1 bits to simplify it, or say ASCII as input characters.

the key realization, and analogy, is that TM state table doubles as reading the input character set, and containing the programming language/program encoding.

this can be realized by building or examining simple TMs & their state tables to compute basic calculations eg sums or whatever. another very useful approach is to play with TM simulators.[3]

all this would be much more obvious if in some classes they taught CS using real TM compilers that would take an arbitrary program (source code) and compile it into a TM state table (similar to object code). unfortunately, nobody believes that is useful right now.[1] (plz vote to reopen if you disagree! =)

but if you play with TM simulators, it will help you build this basic intuition. [2] is possibly the most sophisticated available in the world right now.

[1]  https://cs.stackexchange.com/questions/2916/is-there-a-compiler-from-high-level-language-to-turing-machine

[2] TM compiler in ruby with example source/object code & output (for a nonhalting $a+b=b+a$ commutative addition law verifier)

[3] https://cs.stackexchange.com/questions/10379/top-turing-machine-simulators-on-the-web


why don't we use machines with random access memory as our basic model of computation? Turing machines are perhaps the most popular model of computation for theoretical computer science. Turing machines don't have random access memory, since we can only do a read where the slider is currently located.

This seem unwieldy to me. Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?

Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?

The short answer is that this model is actually more complicated to describe and prove things about. "Jumping" from one place in memory to another is a more complex operation. Note that it requires:

Reading an address (requires that we define how the address is written on the tape)
Jumping to where that address says on the tape

Alternatively I'm not sure what you have in mind by "register machine", but this also requires care. How large can the registers be? And the machine then has separate mechanisms for how it accesses/modifies the registers, and how it accesses/modifies main memory.

In sum, it's a more complicated model and Turing machines are easier to deal with.

However, the long answer is that theoretical computer scientists do use a model with random access memory, in real practice: it's called the RAM (Random Access Machine) model. The Turing machine is not considered to be a good model for so-called "fine-grained complexity" (e.g. whether a problem can be solved in $O(n^2)$ or $O(n)$ time), and so this requires more careful models. The RAM model is standard and perhaps, arguably, more accepted than the Turing machine as a model of how real computers work, despite being more complicated.

For example, we can show that for a Turing machine to decide if two strings are equal requires $O(n^2)$ time. But this of course does not hold in more accurate models of computation like the RAM model, where it will take $O(n)$. Therefore:

If you just care about whether a problem can be solved at all (or whether it can be solved in polynomial time), Turing machines are considered sufficient.
But if you care about exactly how difficult it is to solve, then you have to resort to a more complex model, such as RAMs.

Turing invented the 'machine' purely to show, in the simplest possible way,

1)that mechanical computing was possible, and
2) that if a problem could not be solved by it, then it could not be solved.

Performance is irrelevant - no-one has ever built one, or ever will.  But we can emulate it, and reason about it.


What does "non-pathological data" mean? I took an algorithms class on Coursera. The professor in the video about hash tables said that

  What's true is that for non-pathological data, you will get constant time operations in a properly implemented hash table.

What does "non-pathological data" mean? Can you give some examples?

Pathological data is supposed to be data that makes things go wrong in
some way for your intended computation. It can be called
pathological when it is rare enough in actual uses, so that things
work OK most of the time. This can sometimes be made mathematically
more precise (for example with probabilities), but the use of the
word pathological in often informal.

For example, tomato salad and ketchup are excellent food, except for
pathological people, meaning those people who are allergic to
tomatoes. It can actually kill in some cases.  But people allergic to
tomatoes are very rare so that tomato dishes are considered excellent,
except in pathological cases.

There are many algorithms that, while having a worst case complexity
above the optimal one, are on the average as good or better than worst
case optimal algorithm. If you compare quicksort and merge sort,
quicksort is time $O(n^2)$ while merge sort is $O(n \lg n)$ in the worst
case. But people will often use quicksort, because they both are time
$O(n \lg n)$ on average, and the space complexity is $O(\lg n)$ for
quicksort and $O(n)$ for merge sort.

The fact that quicksort is as good on average may be attributed to the
fact that the $O(n^2)$ time complexity actually occurs only on
pathological (implying bad but rare) cases.

another way to think about this: hash keys are like separate "bins" that contain the data. one would expect/hope that the data is evenly distributed between all the bins, "balanced". for nonpathological data each bin has/contains roughly the same amount of data. if the data is pathological (wrt key hashing algorithm), it all "piles up" in fewer bins, and some bins have far less. this is inefficient because the lookup time increases (and efficiency decreases/converges to that of looking up an unsorted list) when the bins are filled larger. note that merely changing the key hashing algorithm could turn the data from "pathological" to "non pathological" or vice versa, hence the importance of the hashing algorithm.

also there are many other algorithms for which the distinction of "pathlogical vs nonpathological" might be applied, with basically the "pathological" data making the algorithm perform in worse case (eg the concept is also used with sorting algorithms). as you can see its a statistical concept. also for the same problem, data that is "pathological" for one algorithm might not be "pathlogical" for another. etc.


Checking if sequence is almost strictly in ascending order This was part of my interview questions.

Given a sequence of integers as an array, I have to determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
For instance,
For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false
There is no one element in this array that can be removed in order to get a >strictly increasing sequence.
For sequence = [1, 3, 2] the output should be
almostIncreasingSequence(sequence) = true
We can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, we can remove 2 to get the strictly increasing sequence [1, 3].
The function must return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

The conceptual algorithm that the interviewer wanted was below with Java:
boolean almostIncreasingSequence(int[] sequence) {
    int seq1 = 0;
    int seq2 = 0;

    for(int i = 0; i < sequence.length - 1; i++){
        if(sequence[i] >= sequence[i + 1]) seq1++;
    }

    for(int k = 0; k < sequence.length - 2; k++){
        if(sequence[k] >= sequence[k + 2]) seq2++;
    }

    return !(seq1 + seq2 > 2);
}

but I didn't get the part comparing sequence[i] with sequence[i+1] andsequence[i+2] to increment the counter which are seq1 and seq2. How does this cover all the cases?

It does not cover all cases! Consider the sequence [2, 6, 4, 8, 7].
Before the return statement, the values of seq1 and seq2 are: $seq_1 = 2$, $seq_2 = 0$. So the function would return $True$. However, the sequence is not almost strictly increasing, because you need to remove at least two elements from it to obtain an increasing sequence.

So, either the Java implementation is not faithful to the conceptual algorithm, or the conceptual algorithm is wrong.

The problem can be solved by finding the length of the longest increasing subsequence (LIS) of the given sequence. Call $n$ the length of the original sequence. If the LIS has length $\ge n-1$, the sequence is almost increasing according to your definition. If the LIS has length $\le n-2$, the sequence is not almost increasing.

Strictly ascending requires not to have repeated values after removing one element from the array. Hence there should never be more than one repeated element.

In Python3,

def almostIncreasingSequence(sequence):
   # To check if there are more than one repeated numbers, set() can be used to eliminate repetitions
   # len(x) to find the count of array x
   # len(set(x)) - remove repetition and find count
   if len(sequence) - len(set(sequence)) > 1:
        return False
   # popping each element and checking whether the remaining array is same
   # as the original after sorting one of the copy
   for i, n in enumerate(sequence):
        # list.copy() to make a copy of the array
        temp = sequence.copy()
        temp2 = sequence.copy()
        #list.pop(i) to delete the element at index i
        temp.pop(i)
        temp2.pop(i)
        # list.sort() to sort array in ascending order
        temp.sort()
        if temp == temp2 and (len(temp) - len(set(temp))) == 0:
            return True
   return False


Minimum difference between two subsets of an array of integers The Problem

Suppose we have an array A[1...n] of integers, with values ranging from 0 to K (so 0<=A[i]<=K for each i). We need to describe an algorithm to find an (X,Y) partition from the set {1,2,...,n} such that |Sx-Sy| is minimum, where Sx and Sy are the sums of the elements in X and Y. i.e., if A=[1,3,1,1], then X={1,3,4} and Y={2} and the solution is optimal with Sx=3, Sy=3, |Sx-Sy|=0.

My Solution (In pseudocode)

For i=0 to n
    if A[i]==K //If this element is the highest element in the array, put it in Sy
        Sy.add(A[i])
Else if A[i]=/=0 //We don't care about zeroes, the rest goes in Sx
    Sx.add(A[i])
min = |Sx-Sy| //Calculate our min as it is
DO
    go=false
    //Move the smallest element from the biggest group to the other one
    if Sx>Sy
        SyTemp = Sy + min(Sx)
        SxTemp = Sx - min(Sx)
    else if Sy>Sx
        SxTemp = Sx + min(Sy)
        SyTemp = Sy - min(Sy)
    //if this improves on our min, save it and check for another iteration
    if |SxTemp-SyTemp|<min
        Sx=SxTemp
        Sy=SyTemp
        min = |Sx-Sy|
        go=true
    else
        Return Sx,Sy //if the new sets are worse than the ones before, return the old ones
While(go)

My question

Apparently, this problem is NP complete (At least that is what my professor told me), and my question comes from the way he scored my solution. I got 3 points out of 9 because a dynamic programming solution is what was requested - while this is a greedy approach - and my solution has edge cases in which it won't work.

the example he gave me to prove that these edge cases exist was [1,2,5,5] and he said that in this case the algorithm would return {1,2,5},{5} instead of {1,5},{2,5}. Now, to me it seems like my solution would actually return what he wants, and I can't really think of an example this algorithm couldn't deal with, so I'm here to ask the community if you see any errors in my solution, if you think my professor is right in saying that his example wouldn't be solved optimally (or that there are edge cases in which this approach won't work), and if you think this will perform better than O(K(n^2)), where K is the sum of all values of the array (which apparently is the time complexity of his DP solution).

My algorithm got proven wrong by Ricky Demer in a comment to the OP, with the example [2,2,3,3], for which we have a suboptimal output ({2,2} and {3,3} instead of {2,3} and {2,3}, for those wondering). Altough this flaw could be fixed in my code, it would then perform suboptimally in the example my professore had given me (And that I wrote in the OP).

A good greedy version of the algorithm is given on Wikipedia and is as follows:

def find_partition(int_list):
"returns: An attempt at a partition of `int_list` into two sets of equal sum"
A = set()
B = set()
for n in sorted(int_list, reverse=True):
    if sum(A) < sum(B):
       A.add(n)
    else:
       B.add(n)
return (A, B)

This approach gives a 7⁄6-approximation of the optimal solution, thus the only viable technique to use in case you need an optimal algorithm is dynamic programming. An implementation can be found, again, on Wikipedia and will run in pseudo-polynomial time.

This will help to get the subset

numbers=[5,6,1,11]
numbers.sort(reverse = True)
total=sum(numbers)/2
S1=[]
S2=[]
for i in numbers:
    if(i+sum(S1)-total)<0:
        S1.append(i)
    else:
        S2.append(i)
print ('S1' ,S1)
print ('S2',S2)

Source :https://www.youtube.com/watch?v=XafGZHCxdc0


Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language? I'm looking for intuition about when a language is regular and when it is not. For example, consider:

$$ L = \{ 0^n 1^n \mid n \geq 1 \} = \{ 01, 0011, 000111, \ldots \}$$

which is not a regular language. Intuitively it seems a very simple language, there doesn't seem to be anything complicated going on. What is the difference between $L$ and a regular language like:

$$L' = \{ w \mid w \text{ does not contain } 11 \} = \{0,10\}^*\cdot (1 \mid \varepsilon).$$

I know how to prove that $L$ is not regular, using the Pumping Lemma. Here I am looking for intuition about what makes a language regular.

To expand on Artem's comment, note that if we have an $m$ state automaton, at each point we can remember at most $\lg m$ bits of information about the part of input we have read so far. Based on this finite amount of information about the the previous bits of the input, you should be able to end up in the right accepting/rejecting state for all possible ways that the input can continue. If this amount of information is not sufficient to answer correctly then the language is not regular.

For this language we may need $m$ bits of information to be able to correctly answer where $m$ is an arbitrary large number (and therefore can be taken to be larger than $n$ which is fixed since the same atuomaton should work for all inputs).

One way to formally show this is pumping lemma. A more general way that is harder to use is to directly show that the number of equivalence classes of strings w.r.t. the language is not finite (we say strings $x$ and $y$ belong to the same class and write $x\sim y$ if for all strings $w$, $xw \in L$ iff $yw \in L$) which is the same as saying the amount of information that the machine needs to remember is not finite (constant w.r.t. to inputs).

You can not pump $0^n1^n$, the pumping lemma defines a regular language as those where given a word in the language of the form $xyz$, all expressions $xy^iz$ are also in the language.

You can't do this with any $0^n1^n$.

Since it fails the pumping lemma it's not regular.


How can I teach computer science without using computers? In some places in the world, people don't usually have access to (and hence little knowledge of) computers, and even if they have, hard- and software are outdated and usage plagued by power outages and such. Access to (good) books also tends to be lacking. How can I teach computer science under such circumstances?

I'm worried that without being able to do experiments and apply what they learn, they won't learn (well) at all even though they are incredibly motivated and devote most of their time to this hobby. Is it possible to teach CS only theoretically?

Asking how you can study computer science without computers is a bit like asking how you can study cosmology without telescopes. Sure, it's nice to be able to look at the things you're studying and it's often very helpful to be able to play around with things. But there's a whole lot you can do without access to a computer: in extremis, you could probably do almost all of a undergrad course with no computers.

In practical terms, access to computers helps reinforce a lot of what you learn in a computer science course. Programming courses are, obviously, much more natural with access to a computer. On the other hand, being forced to write code on paper does encourage people to think about their code and make sure it really works, rather than just running it through a compiler again and again until it compiles and then running trivial test cases again and again until the obvious bugs go away.

Topics that would be most natural without computers would be the more mathematical ones. All the background mathematics, such as combinatorics and probability. Computability, formal languages, logic, complexity theory, algorithm design and analysis, information and coding theory. Anything to do with quantum computation!

am going to try wiggle on this one a little & "think outside the box". full blown computers are indeed expensive, sometimes resource-demanding and tricky to maintain. but there are many inexpensive electronic systems that mimic full-blown computers eg with LCD screens etc and which many basic programming principles can be applied, many battery powered. there is also a close connection of EE principles with computing such as building binary logic circuits etc.; also nowadays some toys have programmability capabilities.

programmable calculators. some have entire programming languages (not so high level but more like assembly languages) built into them. some would support advanced programs.
Raspberry pi minicomputer/microcontroller was developed for this purpose & runs linux. less than $40 in many cases.
parallax STAMP kit microcontroller requires a USB connection but maybe a Raspberry pi would be sufficient. see also PIC microcontroller
robotics systems. there are many inexpensive ones that have some programmable logic. Lego robotics mindstorms/nxt is one of the best & there are less expensive models.
some console games have programming principles built into them. eg Little Big Planet has amazing programming features built into it. there are some handheld versions of programmable games. there are many youtube videos of complex constructions for inspiration.
smartphones are the new programming world. they have browsers that run javascript, and there are many programming related apps, and one could even surf programming sites with an internet connection (incl wifi).

also suggest as in comments building TM programs eg for addition etc and attempting to follow them by hand.


Undecidability of telling if a program returns true or false Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are allowed to give any answer (but you have to halt and give some answer on all inputs).

Is this problem undecidable? My gut says that it should be, but I can't find a reduction to the halting problem. Given a Turing machine that may or may not halt, we can set up the machine to finish with a $0$ in the case that it halts, but can't finish with anything in the non-halting case, so the oracle could just say $0$ in this case without having to figure out whether in fact the machine halts.

Note that a reduction in the other direction is simple; if you can solve the halting problem, then given a TM that either finishes with $0$ or $1$, we replace the $1$-writing step with an infinite loop to create a new TM. If the new TM halts, we say "it writes a $0$" and if it does not halt we say "it writes a $1$". This answer is guaranteed to be correct as long as the TM in fact halts with a $0$ or $1$, so we can solve the original problem.

Assume you have a function like the one you described:

def haltify(f):
    # Never fails to halt.
    # If 'f' halts, returns f().
    # If 'f' doesn't halt, anything could be returned.
    ... magic ...

But then someone comes along and does this:

def evil():
    return not haltify(evil)

See the problem?

If haltify(f) is guaranteed to halt for all f, then evil is also guaranteed to halt because it just calls haltify on a specific f and inverts the output.
Since evil halts, haltify(evil) must evaluate to the same thing as evil().
So not haltify(evil) simplifies to not evil() and that's what evil() returns.
That's a problem, because there's no x satisfying x == not x. Evil's result is contradictory.
Therefore one of the assumptions we used is wrong: either haltify isn't guaranteed to halt, or it isn't guaranteed to return f() when passed a halting f.

Bonus exercise: why doesn't the function def good(): return haltify(good) cause problems for haltify, despite apparently simplifying to the infinite loop def good(): return good()?

Your reduction to the halting problem is streightforward logically. If your machine halts, it must halt in some time T based on a primitive construction of its input. If the halting problem is unsolvable, the construction must be lossy; therefore there exists a machine for which it guesses wrongly and does halt without being fully evaluated, and a long chain of XOR forces full evaluation to reach the right answer. Therefore there exists a machine for which it yields the wrong answer.

In fact any nontrivial problem that does not exclude non-halting machines as input reduces to the halting problem in this manner. Ref:
https://en.wikipedia.org/wiki/Rice's_theorem