Data structure for range-value-sum I have to be able to perform insert, delete, range-value-sum, and range-2-max-values with a data structure.

Range-value-sum(xl,xr): with a range [xl,xr] (for a range query), it reports the sum of values of all elements whose keys are in the range of [xl,xr], where xl and xr are real numbers and xl ≤ xr

Range-2-max values reports the largest value and the second largest.

Approach: This is my take on it so far, to use a single balanced binary search tree that is sorted by its keys. The augmented fields  would be the value (of the key-value pair), subtree min and max keys, sum of the subtree, and the 1st and 2nd maximum of its subtree.
The sum and 1st and 2nd max are of the values, not keys since the values don't have to be ordered in this case.
For range-value-sum the recursion is to pretty much keep track of the 1st and 2nd max values that are within the range.
Finally, you return the top 2 in each recursive step, excluding unnecessary values.

Thoughts? Ways to make more specific? For the time analysis, I'm relying O(logn) due to it being a binary search tree and its height.

use Binary Index tree, segment tree for the range-value-sum it is the easiest way to do so and for range-2-max use a linear search to keep track of two maximums.For range-2-max you can also use min-heap(this can help you to find range-N-max).

BinaryIndexTree(fenwick tree) has many online tutorials read them and see this visualizer for understanding it.
http://visualgo.net/bit.html

Hope this clears or solve your problem.


Reason to learn propositional & predicate logic I can understand the importance that computer scientists or any software development related engineers should have understood the study of basic logics as a basis.

But is there any tasks/jobs that explicitly require the knowledge about these, other than the tasks that require any kind of knowledge representation using Knowledge Base? I want to hear the types of tasks, rather than conceptual responses.

The reason I ask this is just from my curiosity. While CS students have to spend certain amount of time on this subject, some practicality-intensive courses (e.g. AI-Class) skipped this topic entirely. And I just wonder that for example knowing predicate logic might help drawing ER diagram but might not be a requirement.

Update 5/27/2012) Thanks for answers. Now I think I totally understand & agree with the importance of logicin CS with its vast amount of application. I just picked the best answer truly from the impressiveness that I got by the solution for Windows' blue screen issue.

I tend to like Unification and anything related to it. If you don't know propositional & predicate logic, then you are skipping the basics of logic. If you have an interest in anything listed, then it would be like having an interest in math and skipping addition and multiplication. Logic is not just for AI.

As a practical answer, remember the Intel floating point problem and how you never see them anymore? Thanks to the use of theorem provers they are a thing of the past. Remember the Microsoft blue screen of death. Thanks to SAT solvers, model checking and other logic based solution, they are an endangered species.


Inferring used fields in return type A common issue in app development is avoiding over-fetching of data, such as in this naive (pseudocode) example:

get_user(id) {
  return sql_query("SELECT * FROM users WHERE id=$1", id);
}

render_some_webpage() {
  // ...
  print get_user(session.user_id).username;
  // ...
}

While this would work, it requires the database to send back a bunch of user fields when only the username is used (it's not a big deal in this trivial example, but gets much worse when associations/joins are involved). This problem is normally solved via adding an additional argument to get_user with a list of required fields, but that's far from a perfect solution. It seems the language could infer which fields of the user were actually used and allow get_user to act on this information (by only fetching the username).

Is this a known concept? Are there languages that implement this idea?

Few otherwise general-purpose languages bother to deeply integrate with (relational) databases. Most languages I've seen that do do some integration (though fairly shallowly) are bolt-on abominations. Links is quite a bit more principled, and I believe can actually more or less do what you want. It's a statically typed functional language whose goal was to collapse multi-tier web applications into one coherent (source) program.

In Haskell, a general-purpose, statically typed, purely functional language with no database integration, you can use the type class system and type inference to propagate information about the used fields back to the query site. The simplest approach to this will not actually know what columns are on the table, and so will lead to queries that may access columns that don't exist. Part of the reason I think Links can do what you want is that the type systems of Haskell and Links have some relation, and Phil Wadler, one of the primary designers of Links, is also the creator of type classes. (The mechanism is different though, using row types rather than type classes. Indeed, the approach in Haskell would be more like a poor man's row types.)

That said, it's not clear how desirable this actually is, especially when given a clean, modular syntax for making queries e.g. something like C#'s Linq. Using Linq is like your solution of passing in the list of required fields except you have the full flexibility of, at least, Linq's query syntax and so you aren't just slinging strings about and thus can't typo one of the fields. You're still required to change the query to return the appropriate fields, but often you do want some awareness and control over the query. (This is especially true if the code isn't validated against the schema and so typoing a field name can lead to non-existent column names in the query.)


Solving $T(n) = 4T(n/2) + n^2log_2(n)$ My first thought was using the third case of the master theorem, but I am not sure if I can use $\epsilon \rightarrow 0$, so $f(n) \in \Omega(n^{log_2^4+\epsilon})$.

Otherwise, I tried solving the equation by iteration where I got $T(n) \in \Theta(n^2log_2^3n)$ instead of $T(n) \in \Theta(n^2log_2n)$.

Which solution is right and why? Thanks.

When you applied the master theorem, f(n) is n^2 right. This is anyways asymptotically lesser than O(n) which is the n^2log(n). Hence at each node of the recursion tree, the O(n) would dominate computation hence T(n) is O(n). The reason why this is true is because when you apply the recursion tree the number of processes at each node if you calculate would be 2O(n/2)+4O(n/4)...... whose sum turns out to be lesser than O(n).


Are there current benchmarks for algorithms solving Travelling Salesman? I'm researching the travelling salesman problem and looking for data regarding the current state of affairs regarding solutions and performance. So far the only data I've states that the current record for optimality is held by 'Concorde' which found a solution for a graph containing 85,900 cities. I've also found benchmarking data for Concorde, as well as data pertaining to the current best performance for a world map.

Is this data still accurate? It looks like a lot of this hasn't been updated since the early 2000s.

TSP has many variants under study eg Euclidean vs noneuclidean, exact vs approximations, interrelated but also at times separate threads of research. heres a recent nontechnical survey from early 2013 on TSP by an expert mathematical writer Klarreich, Computer Scientists Take Road Less Traveled that sheds some insight on recent improvements/ theoretical advances & can be mined for some refs. an old approximation algorithm by 1976 Christofides has been unrivalled for decades but some minor theoretical improvements have been made recently. as indicated in the article some theoretical TSP research that is not nec (practically) implemented veers into what is referred to as Galactic algorithm territory by expert RJ Lipton.

as a more applied resource/ angle, also a leading group/ site for benchmarking is DIMACS, NSF center for discrete math & CS, which also has a TSP page with algorithms/ benchmarks updated 2013.


Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$ I'm trying to proof that the following language is not regular using pumping lemma.
$L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$

I started by stating that:

$|w\bar{w}| = 2p = |xyz|$

Because of Pumping Lemma the following has to be true:

$1 \leq |y| \leq |xy| \leq p$

Because $|xy| \leq p$ and $|w|=|\bar{w}|$ have to be true, $\bar{w}$ has to be completly in $z$. I now tried somehow to manipulate the first half, so that it always evaluates to a contradiction, but I am stuck.

Just show that after processing $0^n$ and $0^{n’}$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $1^n$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states.

Or you just take the pumping lemma, p arbitrary large, and w = $0^p 1^p$. Which makes y = $0^k$ for some k >= 1.


Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$ I have the following two functions

$f(n) = n\sqrt n + n \log n$
$\log_{100} n$

And I need to classify them into the followings:

$O(n)$, and/or
$O(n^2)$, and/or
$O(n^3)$, and/or
$O(n^{1.5})$, and/or
$\omega(n)$, and/or
$o(n\log n)$ (small o)
$\theta(n^{1.5})$,

Regarding the $\theta(n^{1.5})$, I am grasping it's idea newly, where do these functions set in. Also, does the function $f(n) =n^{0.9999}$ belong to $\theta(n^{1.5})$.

I would appreciate your feedback, as from your answers I am building up the knowledge for these.

$\log_{100}n \in \mathcal{O}(log(n))$ since base change is a constant.

$\log n \in \mathcal{O}(n) $
$\log n \in \mathcal{O}(n^2) $
$\log n \in \mathcal{O}(n^3) $
$\log n \in \mathcal{O}(n^{3/2}) $
$\log n \not\in \mathcal{\omega}(n) $
$\log n \in \mathcal{o}(n \log n) $

This table gives the order;

First of all;

$$\lim_{n \rightarrow \infty} \frac{n \sqrt n}{n \log n} = \infty$$ by using this;

$f(n)= n\sqrt n + n\log n \in \mathcal{O}(n\sqrt n )$.

$ n\sqrt n \not\in \mathcal{O}(n)$
$n\sqrt n \in \mathcal{O}(n^2) $
$n\sqrt n \in \mathcal{O}(n^3) $
$n\sqrt n \in \mathcal{O}(n^{3/2}) $
$n\sqrt n \in \mathcal{\omega}(n) $
$n\sqrt n \not\in \mathcal{o}(n \log n) $,


Recognizing vs Deciding in defining class BPP In Sipser's text, he writes:

  When a probabilistic Turning machine recognizes a language, it must
  accept all strings in the language and reject all strings not in the
  language as usual, except that now we allow the machine a small
  probability of error.

Why is he using "recognizes" instead of "decides"? If the machine rejects all strings that are not in the language, then it always halts, so aren't we restricted to deciders in this case?

The definition goes on:

  For $0 < \epsilon < 1/2$ we say that $M$ recognizes language $A$ with
  error probability $\epsilon$ if

  1) $w \in A$ implies $P(M \text{ accepts } w) \ge 1 - \epsilon$, and

  2) $w \notin A$ implies $P(M \text{ rejects } w) \ge 1 - \epsilon$.

So it seems like the case of $M$ looping is simply not allowed for probabilistic Turning machines?

Complexity theory makes no distinction between "deciding" and "recognizing". The two words are used interchangeably. Turing machines considered in complexity theory are usually assumed to always halt. Indeed, usually only time-bounded machines are considered (such as polytime Turing machines), and these halt by definition.

In your particular case, you can interpret accept as halting in an accepting state, and reject as halting in a rejecting state. The Turing machine is thus allowed not to halt. However, the class BPP also requires the machine to run in polynomial time, that is, to halt in polynomial time. In particular, the machine must always halt.


Branch and Bound - Transform a into b I'm trying to design an algorithm which will accept two natural numbers: a and b.
Its purpose is to get b from a by making the following operations: *3 and /2.
For example, if a = 10 and b = 7, then:

10/2*3/2 = 7

I decided to use branch and bound, since I believe there's no better suitable algorithm for this.

My program works, but I'm having really trouble finding a heuristic.

What could it be?

Thank you.

I don't know of any algorithm that will work for all $a,b$, because of the possibility that you might have to use an intermediate value that is extremely large, and I'm not aware of any reasonable bound on how large of an intermediate value you need to contemplate.

However, here's one heuristic.  Suppose we only consider sequences where no intermediate value exceeds some constant $K$.  Then you can use dynamic programming to determine whether it's possible to go from $a$ to $b$, without ever exceeding $K$.  You build an array $A[1..K]$ where $A[i]=1$ means that it's possible to reach $i$ from $a$,  and fill it in via a fixed point computation, as follows:

Set $A[a]=1$ and $A[i]=0$ for all $i \ne a$.
Repeatedly do the following, until you do an entire iteration without changing the array:

For each $i := 1,2,\dots,K/3$, if $A[i]=1$, set $A[3i] := 1$.
For each $i := 3,4,\dots,K$, if $A[i]=1$, set $A[\lfloor i/2 \rfloor] := 1$.

Finally, if $A[b]=1$, you know it's possible to go from $a$ to $b$.  (If $A[b]=0$, you can conclude nothing; maybe there's a way to get from $a$ to $b$ by going through some intermediate value larger than $K$.)


The Space of an Unsatisfiable Formula I am reading the paper Measuring the hardness of SAT instances by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF). I am trying to understand the demonstration of the last part of the Lemma 3 (in bold). For this, I get an example. Let be $\Gamma = (a+b)(a+b')(a'+c)(a'+c')$ then its tree-like refutation is:

Following the demonstration of the last part of the Lemma 3, $[b\rightarrow 1]\Gamma=(1)(a)(a'+c)(a'+c')$, and adding the literal $b'$ where $[b\rightarrow 1]$ has removed it, we get $\Gamma' = (1)(a+b')(a'+c)(a'+c')$. In accordance the paper the tree-like refutation of $\Gamma'$ is a proof for $\Gamma \vdash b'$. The natural question, I think so, How it is posible that the tree-like refutation of $\Gamma'$ be a proof for $\Gamma \vdash b'$ if $\Gamma \neq \Gamma'$?.

  Lemma 3 The space satisfies the following three properties:

  $s(\Gamma \cup \{\Box\})$ = 0
  For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
  For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\{x\}\to\{0,1\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.

  The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3

  $$s(\Gamma) = \min_{x, \overline{x}\in\Gamma, b\in\{0,1\}} \big\{
\max\{s([x\mapsto b](\Gamma))+1, s([x\mapsto\overline{b}](\Gamma))\}\;\big\}$$
  when $\Box\notin\Gamma$, and $s(\Gamma\cup\{\Box\}) = 0$.

Here is the original refutation:

From $a'+c$ and $a'+c'$ deduce $a'$.
From $a$ and $a'$ deduce $\square$.

When you add $b'$ back, you get:

From $a'+c$ and $a'+c'$ deduce $a'$.
From $a+b'$ and $a'$ deduce $b'$.

More generally, since the only difference between $\Gamma$ and $\Gamma'$ is the addition of $b'$, it is not hard to prove by induction that for every line $\ell$ proved in the refutation of $\Gamma$, the corresponding line in the corresponding $\Gamma'$ proof is either $\ell$ or $\ell+b'$. Hence the $\Gamma'$ proof proves either $\square$ or $b'$. It can happen that it indeed proves $\square$, in which case we can deduce $b'$ by weakening, which is an admissible rule for resolution space (we can get rid of it without increasing the space).


How to prove that a custom iterative algorithm will determine all shortest paths to a graph node? I'm not sure what the following algorithm does but it seems that it calculates the shortest paths from a node $t$.

Initially we're given a graph $G=(V,E)$ with non-negative weights $c(e) \ge0$ for each edge $e\in E$ and we're given a node $t\in V$.

The algorithm is as follows:

  Initialize array $A$ such that $A[v] = 0$ if $v=t$ else $A[v]=\infty$.

  Outer loop which is repeated continually

  $\quad$ Inner loop: we scan all edges in lexicographical order and for every $e=(u,v)\in E$ we $\quad$ do the following:

  $\qquad$ if $A[v] >A[u]+c(e)$ then $A[v] =A[u]+c(e)$

  $\quad$ if no updates were performed in the inner loop the algorithm exits.

I need to prove by induction what the algorithm does. For example for the following graph below and if $s=b$ the initialization of $A$ will be as follows:

Then the first run of the inner loop would be:

1) $A[1]$ is not bigger than $A[0]$ so we do nothing

2) $A[2]$ is bigger than $A[1]$ so $A[2]=2$

3) $A[3]$ is bigger than $A[2]$ so $A[3]=5$

The next time the inner loop will not make any updates because all the reachable nodes were already updated.

I'm not really sure if I understood correctly what the algorithm does and how to prove this inductively.

How does the fact that the algorithm checks nodes in lexicographical order come into play?

You can prove by induction that for every iteration $i$, the array $A$ during this iteration, $A_i$, contains the weights of some paths originating at $t$. More formally, for all $v\in V$, $A_i[v]$ is either $\infty$ or the weight of some path from $t$ to $v$.

Now, it is easy to show that the values of $A_i$ are monotonically non increasing, which combined with the above statement implies that the algorithm terminates. I leave the details to you.


How a Data Compression Software Reads a File as pure Binary File and makes Output? I have an hybrid compression technique I want to implement, my implementation is (so far): I can encode a string into a encoded compressed string. These are binary strings. For example,

I read texts from a text file  ->

then convert it to a binary string ->

then convert it to an encoded binary string.

At this point, I can save the encoded binary string in a text file, but I want to know what is done in general.

For example, when we use Winrar software, it -

does not read as I said above, it compresses any file
makes .rar file as output

So, how a compressor "read" any file as a pure binary form, and how it makes output file?

In another way, what i want is to know how to read any file as a pure binary form and make a output file given that I have a encoding and decoding scheme. Please comment anything related to question, I am new to the topic.

A file is a byte stream

Although OSes provide some bells and whistles (such as metadata, or forks), most define a file as a sequence of 0 or more bytes.

Each byte in the file is a numerical value from 0 to 255 (inclusive). There's nothing more to it.

A file format is a way of giving meaning to the bytes in a file

For a simple example, you could have a file representing a black-and-white image, where each byte is either 0 (black pixel) or 1 (white pixel), one row after another. Perhaps the first two bytes encode the image width as a 16-bit number, and the second two bytes encode the height as a 16-bit number.

This example is very inefficient, since each pixel byte can never use the possible values 2-255. You may want to read about information theory.

"Text file" is a file format

In a text file, every possible value 0-255 is given a meaning, a specific letter, number, symbol, or a "special effect" character like newline. Sort of. Strictly speaking, in the ASCII encoding, only values 0-127 have a meaning.

There are many different text encodings, although only a few common ones. In Unicode, characters are not always 1 byte in length.

But let's stick with ASCII. If you store "51a3" as text, the byte values 53, 49, 97, 51 will go into the file, as they correspond to "5", "1", etc.

If you store the hexadecimal value 0x51 and 0xa3 as bytes, then there will simply be those two bytes (81, 163 in decimal.) So this is half the number of bytes. However the file is no longer a text file because 163 is not defined in ASCII.

Other file formats require purpose-built software

Text files are popular because you can open them in any editor (Notepad, nano). As you understand, they are not very space-efficient.

But it is not difficult to write your own software. Here is an example.

#!/usr/bin/env python3

# PART 1 - WRITE BYTES TO A FILE

save_hex = "60b725f10c9c85c70d97880dfe8191b3"

print("Saving:", save_hex)

# group save_hex into groups of 2
save_ints = []
i = 0
while i < len(save_hex):
    # the 16 makes int() treat the value as hex
    integer = int(save_hex[i:i+2], 16)
    save_ints.append(integer)
    i+=2

print("Integer values:", save_ints)

# create a bytes object out of an array of numbers
save_raw = bytes(save_ints)

with open('myfile.raw', 'wb') as f:
    f.write(save_raw)

# PART 2 - READ BYTES FROM A FILE

with open('myfile.raw', 'rb') as f:
    contents = f.read()

print("Loaded: ", end='')
for byte in contents:
    print('{:02x}'.format(byte), end='')
print()

After running this check the length of the file is half the length of the hex string. Also, learn to use a hexdump tool to inspect the contents of the file.

Python's bytes objects have a lot of features but if you use the basic idea above (list of ints in range 0-255 -> bytes object) and (iterate over bytes object and get an int in range 0-255) then you don't need to get too deep into the details.

All-purpose compression software usually doesn't understand the files it compresses

When you put an mp3 file into a ZIP or RAR, the compression software treats it as a sequence of bytes, the same way it would treat a JPEG or EXE or HTML file.


"Flow layouts" inside a GUI -- how do I come up with a good algorithm? I was trying to write some simple code for a "flow layout" manager and what I came up with initially was something like the following (semi-pseudocode):

int rowHeight = 0;
RECT rect = parent.getClientRect();
POINT pos = rect.position;  // Start at top-left corner, row by row

foreach (Window child in parent.children)
{
    // POINT is a tuple of: (x, y)
    // SIZE is a tuple of: (width, height)
    // RECT is a tuple of: (left, top, right, bottom)
    RECT proposed1 = RECT(rect.left + pos.x, rect.top + pos.y, rect.right, rect.bottom),
         proposed2 = RECT(rect.left, rect.top + pos.y + rowHeight, rect.right, rect.bottom);
    SIZE size1 = child.getPreferredSize(proposed1),
         size2 = child.getPreferredSize(proposed2);
    if (size1.width <= proposed1.width)
    {
        child.put(proposed1);  // same row
        pos.x += size1.width;
        rowHeight = max(rowHeight, size1.height);
    }
    else
    {
        child.put(proposed2);  // new row
        pos.x = rect.left;
        pos.y += rowHeight;
        rowHeight = size2.height;
    }
}

In other words, the algorithm is very simple:
The layout manager asks every component, "is the remaining portion of the row enough for you?" and, if the component says "no, my width is too long", it places the component on the next row instead.

There are two major problems with this approach:

This algorithm results in very long, thin components, because it is essentially greedy with the width of each component -- if a component wants the whole row, it will use the whole row (ugly), even if it could use a smaller width (but larger height).
It only works if you already know what the parent's size is -- but you might not! Instead, you might simply have a restriction, "the parent's size must be between these two dimensions", but the rest might be open-ended.

I am, however, at a loss of how to come up with a better algorithm -- how do I figure out what would be a good size to to 'propose' to the component?   And even when I figure that out, what should I try to optimize, exactly? (The area, the width, the aspect ratio, the number of components on the screen, or something else?)

Any ideas on how I should approach this problem?

I've encountered variations of this problem several times doing GUI layout work. Your question about "What should I optimize?" is key to answering your question. Until you've decided that you really can't create a better algorithm.

More than likely you'd like to consider the size-ratios. Each child will have likely a minimum size, possibly a maximum in each dimension, and a preferred ratio, or range of acceptable ratios. You can use this basic data to make a guess as to what the layout should be. Now, for the resulting layout of each child you need a way to produce the preference score.

Now you simply have an optimization problem: maximize the total score of all the children. You can also include global scoring attributes, like the parent size (to cover your second problem).  Some layouts you can also reject if they produce invalid results (parent too wide, child not acceptable).

Depending on how many children you have, and how optimal your layout needs to be, will determine how good your algorithm needs to be. For a very simple greedy approach you can simply do line-based. For example, just consider two lines at a time, the current line, and the next line. You should be able to come up with a list of items that easily have enough space on this line, and some that maybe don't. Then just try a few combinations of those trailing components (this line or next) and find a maximum score.


How to convert between bases partially? I have some large number $n$ in base $b_1$ and I want to convert it to base $b_2$. $n$ is about a million decimal digits long, therefore it's impractical to convert it as a whole. However I don't need the entire $n$, just some arbitrary slice of it when it's converted to $b_2$

For example converting from base 10 to base 3, with a slice from digits 5-10:

n(10) = 2347892347
n(3) = 2000[11212]22021210211
m(3) = 11212 <-- the number I need

note: it doesn't matter if the slice starts from the left or the right of the number

Is there a fast method to get that slice $m$?
Any help is very much appreciated.

Partial answer:

It works for some pairs $b_1$ $b_2$, but may not work for every pair.

Partial solution:

for pairs $b_1$ $b_2$ where there is an $x, p_1, p_2 \in \mathbb{Z}$ such that

$\begin{alignat*}{4}
x^{p_1} & {}={} & b_1\\
x^{p_2} & {}={} & b_2
\end{alignat*}$

you can divide $n$ of $b_1$ into sections of $p_2 $ digit sections, which you can then convert into $b_2$.

If you want to query a slice in the result $b_2$, you need to calculate the section number by dividing by $p_1 $

3 -> 10 doesn't work with this, but I will give you an example

8 -> 16:

$x = 2, p_1 = 3, p_2 = 4$

8  [....][1][2][3][4][..p2 * x blocks..]
2        001010011100
16 [....][ 2][ 9][ C][..p1 * x blocks..]

3 -> 9:

$x = 3, p_1 = 1, p_2 = 2$

3  [....][1][0][2][1][..p2 * x blocks..]
3          1  0  2  1
9  [....][   3][   7][..p1 * x blocks..]


OCR Computing Question I was asked the below question in a test at school last week and I thought the answer given was incorrect.

You had to give a file format from the options for the below statement:

A file created in software that most users will not have available

You had two options, PDF or DOCX. I answered DOCX but apparently the answer was PDF, what do you think?

This looks like an advertisement for Microsoft...

The intention was that while DOCX can be created using the rather expensive but commonly available Microsoft Word, PDF is created by Adobe Acrobat (not the free Reader!) which is not commonly available. However, there are many other ways to create PDFs, and nowadays you can print to PDF even on Windows, which is roughly as commonly available as Microsoft Word.

In conclusion, it's an oversight by the question setters, who appear to be parroting material which has been influenced by Microsoft for obvious commercial purposes.


Divide and Conquer a problem into a sub-problem to solve it efficiently Assume that problem A cannot be solved in O(n^2) time. However, we can transform problem A into a problem B in O(n^2 log n) time, and then solve B, and finally transform the solution of B into the solution of A in O(n) time.

Prove or Disprove: The above approach shows that problem B cannot be solved asymptotically less than O(n^2) time.

My Answer->

Let time complexity (TC) of B be h(n).
So overall complexity is maximum of(h(n), n²logn) which will be greater or equal
to n²logn greater than n² considering the highest polynomial term.

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0 }.

Here f(n) is O(n2logn+n) and g(n) is O(n2logn) which satisfy the above condition at c>=1 and n0 = 0

(n^2 log n) < 1*(n^2logn+n) for all n > 0

So lower bound of solution B is g(n) i.e. O(n^2logn)

So B cannot be solved asymptotically less than O(n^2 log n) time

Therefore B cannot be solved asymptotically less than O(n^2) time

The given information tells you absolutely nothing about the runtime of B.

As an example, let’s say the solution is a vector of N numbers which can be found in O(n^2 log n) but not in O(n^2), and let B be the problem “What was your input”. Solve the problem in O(n^2 log n), pass the solution to B, get it back in O(n), all consistent with the information you have.


Multiplying two bivariate polynomials using FFT Consider two bivariate polynomials of degree at most $n − 1$ in each variable:
$$
F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^iy^j \quad\text{and}\quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^iy^j
$$
Show how to compute the product polynomial in $O(n^3 \log n)$ time.

Can anybody briefly explain the solution please?

The product is
$$
F(x,y) G(x,y) = \sum_{i=0}^{2n-2} x^i \sum_{i'=0}^{n-1} \left(\sum_{j=0}^{n-1} f_{i',j} y^j \right) \left(\sum_{j=0}^{n-1} g_{i-i',j} y^j\right).
$$
You take it from here.


Complementary for $SAT$ I have tried to find a definition of complementary language to $SAT$, I mean $\overline{SAT}$.
But I still confused, in case of $L\in \overline{SAT}$ is it mean:
if $\varphi\in L$ then all interpretations are satisfy and
if $\varphi\notin L$ then exists interpretation that unsatisfy
OR vice versa
if $\varphi\notin L$ then all interpretations are satisfy and
if $\varphi\in L$ then exists interpretation that unsatisfy
please if you downvote write explanation of why

Usually, when we talk about the complement of a set we have some reference set to compare to.
In the setting of languages over some alphabet $\Sigma$, this means that the complement of some language $L$ would be $\overline L = \Sigma^\ast \setminus L$, i.e. the set of all strings over $\Sigma$ which are not in $L$.
In the particular case of
$$\mathrm{Sat} = \{\langle \psi \rangle \in \Sigma^\ast \mid \langle \psi \rangle \text{ encodes a satisfiable propositional formula } \psi \}$$
we find that
$$\overline{\mathrm{Sat}} = \{w \in \Sigma^\ast \mid w \text{ does not encode a satisfiable propositional formula } \psi \}$$
and hence, $\overline{\mathrm{Sat}}$ consists of all strings which represent unsatisfiable propositional formulas (i.e. ones that have no satisfying interpretations) and all strings which don't represent formulas at all.


Can $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ be pumped using the pumping lemma? In order to show that $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ isn't CFL, I was trying to use a pumping lemma this way: At first we assign $w= A^jB^jA^jB^j ,$ $(w^i=uv^ixy^iz), p<|vxy|, p<j.$

if $vy$ contains just $a$s we choose i=0 for $w^i$, so in this case the number of $a$s isn't equal to the $b$s.
if $vy$ contains just $b$s we choose i=0 for $w^i$, so in this case the number of $b$s isn't equal to $a$s.
if $vy$ contains both $a$s and $b$s then for any i there will be a difference in there quantity compare to the $n$ $a$s and $b$s that aren't in $vy$. Also $vy$ can't contain the whole world since the number of $a$s larger than $p$.
Isn't it CFL? Can pumping lemma help here?

I was told in class that it isn't correct to use pumping lemma here, why?

Sure you can use the pumping lemma,

String in $L$ consists of four consecutive segments: a $A$ segment followed by a $B$ segment followed by another $A$ segment followed by another $B$ segment.
Assume that $L$ is context free and let $p$ denote the pumping length of $L$. consider the string $A^pB^pA^pB^p\in L$.We can write this string as $uvxyz$ where $|uxy|\leq p$ and $|uv|>1$. We look at two cases:

case 1: Either $v$ or $y$ contains more than one type of character (i.e at least one of $v$ and $y$ contains both $A$'s $B$'s). In this case, pumping up once to $uv^2xy^2z $ inserts an extra $A^iB^j$ sequence into $s$ i.e the resulting string will contain at least $3\quad A$ segments and $3\quad B$ segments. For instance, if $v=AABB$, then pumping once would result in an additional $AA$ segment followed by an additional $BB$ segment. But string in $L$ contain only four segments
case 2: Both $v$ and $y$ contain only one type of character (i.e they are both all $A$'s or all $B$'s). Since $uxy\leq p$, $uxy$ contains letters from at most $2$ segments of $s$. Pumping once to $uv^2xy^2z$ increases the number of characters in one or two of the segments, but leaves the remainig segments untouched. Thus, the number of characters in each segment will be unbalanced.


An underestimated tradeoff between Memory and the Effectivity of Computation? Is there a theorem / single formula, that describes the often necessary tradeoff between memoiziation (for example that of a certain variable x) and effective computation as written in any common form such as runtime?

(A good purely theoretical startig point to work with could really be a number sequence...)

I'm not sure I understand your question entirely, but I'm going to assume that you're talking about the space-time tradeoff. The gist of the aforementioned tradeoff is as you put it, in the context of an algorithm, the balance you have to strike between the memory it will use (its space complexity) and the time it will take to run (its time complexity).
Obviously, the faster you want it to run, the more memory you will need to use, and vice-versa. The tradeoff is in general present in most fields of computer science besides pure algorithm design, but this provides I believe a nice abstract starting point.

Let's start with the bad news: from a rigid theoretical computer science point of view, tough luck, no such unifying formula exists and it is actually a fairly well-known open problem (for more info you may want to check this question about the space-time tradeoff, but it is fairly technical). Even worse, few general results are known about this.

Now the good news, of which there are two. First of all, I highly encourage you to think about the problem yourself and come up with your own (even incomplete theory), as it isn't very hard to qualitatively come up with some pretty interesting remarks.

For instance, let us try to develop a (very!) basic theory here. At its core, a result to be obtained through computation can be decomposed into a bunch of dependencies and operations. For instance, to compute c=a+b, you need to know a and b (the dependencies, also known as operands), and add them together (the operation). This decomposition can be applied iteratively many times until all of the dependencies are directly known (present in the problem instance/the input you receive).
There are many ways of looking at this, one of them is as a DFG (Data Flow Graph), but there are of course many more with varying degrees of complexity, which each offer accuracy for different factors. For convenience, have this nice picture of a DFG:

Abstracting the compute cost of one operation to 1 (no matter its complexity or the number of operands), we can see that the lower time bound to obtain the value of a node of the DFG is equal to the length of the longest path from the node to an input operand. Indeed, if we assume entirely parallel computation (possible if no interdependencies exist between nodes at the same depth), this bound can be attained. If we would however assume entirely serial computation, we would need to add the cost of obtaining each result one by one and I choose not complicate myself with this here.
If we add memoization, this time becomes the length of the longest path from the node to a memoized operand (but we stop when we reach the first one on a given path backwards from the target node).

This sounds suspiciously simple, right?
If we know the DFG beforehand and we assume parallelism, it indeed isn't very complicated, but a few avenues of thought would be if we consider as mentioned serial (or partly serial execution) and then memoization strategy.

I'll just point out that while it's not what you're looking for, for practical purposes it's always a good idea to benchmark on real hardware as well.

Now since I mentioned that there are two good news: there are bounds on this tradeoff which have been found and proven for specific problems and computation models. If you're interested, you can find some of these purely theoretical results in this answer.


Basic control statements for Turing equivalence? Apologies ahead of time, I don't fully understand what I'm asking...

But, is it possible to program using only 'while loops' and still be Turing equivalent?

Or more generally, can I do everything with 'while loops' that I could with 'if statements' and 'for loops'?

for(X; Y; Z) { Body; } is just syntax sugar for {X; while (Y) { Body; Z; }}.

if can be simulated easily: rewrite if (X) { Body; } as while (X) { Body; break; }.


Scheduling algorithm to minimize the number of late jobs There are $n$ (non-recurring) jobs where each job $i$ has an arrival time $a_i$ and a duration $t_i$. All the jobs share a deadline length $d$ (deadline for each job is $a_i + d$). The problem is to find a (non-preemptive) scheduling time $s_i$ for each job on a single processor/machine such that the total number of missed deadlines is minimized (or maximize the number of on-time jobs).

So, even in cases where not all deadlines can be met, we want to find out the schedule that meets the maximum number of deadlines. Does this problem even have a polynomial solution? I tried a dynamic programming approach, but I can't really identify the subproblems.

For example, given this set of jobs (where each job is described by $(a_i, t_i)$): [(0, 50), (5, 20), (25, 40)] where $d = 60$, the best we can do is to meet 2/3 deadlines with a schedule like this: [(5,20), (25, 40), (65, 50)].

For an optimal selection, one possible sequencing is always the one respecting the order of arrival time $S_0$. Another may be possible, but you can check that you always can do the switches to obtain $S_0$. This is due to the fact that all jobs have the same $d$.

Thus, your problem is equivalent to select the subset of jobs which do not overlap if they are executed as soon as possible in arrival time order.

Then you can do an approximative greedy algorithm considering jobs in increasing duration order. Counting the duration sorting, this has a $O(N \log(N))$ time complexity. It would generally give a very good result but might fail for example on $(a[i], t[i]) = [(0, 60), (30, 50), (60, 60)]$ with $d = 60$.

Or you can do a dynamic programming on $T$ array of $t(n)$, the soonest time at which $n$ jobs are achieved.

Initially, $T_0 = [0, +\infty, +\infty ..., +\infty]$, it has size $N+1$, the number of jobs (+ 0 index). The jobs are considered in increasing arrival time order. $T_k$ is the state of $T$ after considering $k^{th}$ job.

To keep track of the selection, you need an array $previous$ of size $N \times N$ and an array $lastElement$ of size $N$. All are initially filled with -1. $lastElements[i]$ tracks the index of the last added job for $T_{i+1}$. $previous[i][j]$ tracks the element added just before j for $T_{i+1}$.

Then the sub-problem is to compute $T_{k+1}$ from $T_{k}$.

This is the pseudo-code:

function next_job(T_last, a_k, t_k, d):

    T = T_last

    for i from 0 to N-1 do:
        if T_last[i] == +inf then break

        begin = max(a_k, T_last[i])
        end = begin + t_k

        if (end > a_k + d) then continue

        if (T[i+1] < end) then:

            T[i+1] = min(T[i+1], end)
            lastElement[i] = k
            if(i > 1) previous[i, k] = lastElement[i-1]
        end
    end

    return T

The final result is of course the largest $i$ such that $T[i]$ is not $+\infty$.
It has a $O(N^2)$ overall time complexity.

To obtain the selection, you pick $elem0 = lastElement[i-1]$, then $elem1 = previous[i-1, elem0]$, then $elem2 = previous[i-2, elem1]$ and so on until you have your i elements.

Let's make a small example with $(a[i], t[i]) = [(0, 60), (10, 30), (50, 20)]$, $d=60$ :

$T_0 = [0, +\infty, +\infty, +\infty]$ => initialization
$T_1 = [0, 60, +\infty, +\infty]$ => one job may be achieved at time=60
$T_2 = [0, 40, +\infty, +\infty]$ => up to now only one job may be selected, but job (10, 30) took the place of (0, 60) as it can be achieved sooner.
$T_3 = [0, 40, 70, +\infty]$ => optimal solution selects 2 jobs.

At the end, $lastElements = [1, 2, -1]$ (starting job indexing at 0)
and $previous = [[-1, -1, -1] [-1, -1, 1] [-1, -1, -1]]$. This let you track the optimal selection $\{1, 2\}$.


This is related to the Hitting-Set-Decision-Problem:

Given $U=\{1,\ldots , n\}$ and $S\subseteq 2^U $, integer $k$
Decide whether $C\subseteq S $ exists s.t. $\cup_{X \in C} X = U$ and  $|C| \leq k$

The problem is NP-COMPLETE and thus we do not know whether a polynomial algorithm exists. The optimization problem which you refer to is NP-hard.
There are approximation algorithms (see wikipedia).


Height of epsilon-balanced binary search tree In Balanced Binary Search Trees on the basis of size of left and right child subtrees, Hannes says:

  For example, one can say, a BST is balanced, if each subtree has at
  most epsilon * n nodes, where epsilon < 1 (for example epsilon = 3/4
  or even epsilon = 0.999 -- which are practically not balanced at all).
  The reason for that is that the height of such a BST is roughly
  log_{1/epsilon}

I am a bit puzzled on the last statement -- how do we know that the height is roughly 1/epsilon?

Take any path in the tree, starting at the root, and consider the number of nodes at the subtree rooted at each vertex along the path. For the root, it's $n$ nodes. For the second vertex, it's at most $\epsilon n$ nodes. For the third vertex, it's at most $\epsilon^2 n$ nodes. For the $t$'th vertex, it's at most $\epsilon^{t-1} n$ nodes. If the path has length $\ell$ (edges), then the last node contains at most $\epsilon^\ell n$ nodes, and so $\epsilon^\ell n \geq 1$, or equivalently, $\ell \leq \log_{1/\epsilon} n$.


Implement multi-fragment heuristics for the traveling salesman problem I would like to implement the multi-fragment heuristics algorithm for finding a solution to the traveling salesman problem.

The algorithm is described here as follows:

  This seriation method re-organises the $D$ matrix by iteratively placing the smallest distances in matrix $D$ in the $n-1$ cells contiguous to the diagonal.

  This is a greedy approach, with $n-1$ steps.

  At each step, rows $i$ and columns $j$ in $D$ are moved so that the smallest distance is placed in a not yet allocated cell. The smallest distance is not chosen freely. It is constrained by the necessity to keep the already allocated cells in place.

  ...

  This heuristic do not guarantee to find an optimal solution but give quickly a "reasonable good" solution. This solution could be improved by a local search heuristic.

According to the mentioned article, this algorithm was mentioned in a 1992 paper "Fast Algorithms for Geometric Traveling Salesman Problems" by "Bentley", but I couldn't find it on the internet. Moreover, there are almost no other information regarding this algorithm online, except from the usual definition like:

  The multi fragment algorithm works as follows:

  Consider a distance matrix (such as the type at the back of a road atlas of Britain), containing all the distances between all cities on the tour.
  Find the shortest distance and link these two cities together.
  Then, find the second shortest distance, and link these two cities.
  Now, find the next smallest edge whose cities conform to the following criteria:

  Both must have an edge degree ratio <=1 (i.e. neither can already be linked to more than one other city)
  Adding an edge between the cities must not result in a closed tour, which does not already include all the cities on the tour.

  Repeat until all cities end up being connected to two other cities.

I understood the algorithm according to this last article I'm linking to, but I'm not seeing the connection between this last description and the description above.

If the first description is correct, I'm actually not understanding it fully and how could I implement it in practice. For example, suppose we have this simple distance matrix $D$

$$D = \begin{pmatrix} 2& 1 &2 &3\\ 3 &2 &7 &2 \\ 3 &1 &1& 0\\6& 2& 5 &1\end{pmatrix}$$

In the first description, they mention the $n -1$ cells contiguous to the diagonal, but of course we have $2$ of this $n-1$ cells, one in the left triangular matrix (currently from the top to the bottom $3, 1, 5$) and one in the upper one ($1, 7, 0$). Is it ok to choose one arbitrarily?

Then they say:

  At each step, rows $i$ and columns $j$ in $D$ are moved so that the smallest distance is placed in a not yet allocated cell. The smallest distance is not chosen freely. It is constrained by the necessity to keep the already allocated cells in place.

Of course if we move a row or a column in the matrix $D$ and if we number the nodes from $1..N$, then we need to rename the nodes according to the moves.

But actually I'm not fully understanding how these moves could proceed in practice? Any concrete example?

Furthermore, after these moves, what should we do?

I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm.

there are almost no other information regarding this algorithm online
  [...]
  I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm.

I invite you to read my paper "An Empirical Study of the Multi-fragment Tour Construction Algorithm for the Travelling Salesman Problem" appeared in the Proceedings of the 16th International Conference on Hybrid Intelligent Systems (HIS 2016) pp 278-287. DOI: 10.1007/978-3-319-52941-7_28.

You'll find a pseudo-code of the algorithm, which is similar to the "usual definition". It's explained with some examples of a small instance.
The paper also presents briefly other tour construction methods and gives experimental results for the Multi-Fragment algorithm and a comparative study to show the effectiveness of this method.

  If the first description is correct, I'm actually not understanding it
  fully and how could I implement it in practice.

It's correct but maybe a little bit hard to explain. The main idea is to move columns and rows following the criteria such that we can read the constructed tour from the $n−1$ cells contiguous to the diagonal {D[1][0],D[2][1],... D[n][n-1]}.

  In the first description, they mention the n−1 cells contiguous to the diagonal, but of course we have 2 of this n−1 cells, one in the left triangular matrix (currently from the top to the bottom 3,1,5) and one in the upper one (1,7,0). Is it ok to choose one arbitrarily?

The distances matrix in the Traveling Salesman Problem (TSP) is symmetric $(D[i][j]=D[j][i])$, we may consider only the upper/lower triangular portion of the matrix $D$.
There is another variant of the TSP which is the Asymmetric TSP.


Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case Lets say I have a list of many (10s of thousands - millions) objects, and each of these objects has a given number of 3-D vertices (my current implementation uses 8 vertices each, but this number can be reduced if it causes a very significant increase in performance). These vertices are currently stored as floats from 0-255, but this range can also be changed if need be, assuming it will not reduce accuracy too drastically. Also, I can store these objects in any data structure that would be beneficial for this algorithm.

I am given another such object, also with the same number (8) 3-D vertices, but of which in general it must be assumed that none of the vertices are common with any vertices included in the list of stored previous objects.

With all of this in mind, I need an algorithm that will return an object from that list that is optimally close to the test case object (close being defined in the normal, euclidean distance, sense). By optimally close, I mean that it does not have to be the global optimum if this will greatly increase performance, although if there is a quick algorithm that will always return the global optimum i would love to hear it.

If your shapes are not too elongated, you could calculate their axis-aligned bounding boxes (BBs) and store these bounding boxes in an index, such as R-Tree, quadtree or one of their more modern variants.
Then:

Define a distance function that gives the closest BB to the BB of your search-object.
Find the BB in the index that is closest to the BB of you search object.
Calculate the actual distance $d$ between the search-object and the object from the index.
Search the index again, this time with a window query that is by $d$ larger than the previous search BB. This should return all objects that are potentially closer than $d$.
Brute force all returned objects to calculate their actual distance to your search object.

Worst case complexity of the worst case is $O(N)$ for $N$ objects, but average case should be closer to $O(log N)$.


Proving that a sentence in first-order logic is not valid By the completeness of FOL, one can show that a sentence $S$ in FOL is valid, i.e. that it holds true in every model, by exhibiting a proof of $S$. Such a proof string is a certificate of the validity of $S$.

To show that $S$ is not valid, one can either exhibit a counterexample model in which $S$ doesn't hold, or find a proof that such a model exists, either of which would serve as a certificate.

However, do I understand correctly that while a "certificate of validity" will always exist, that "certificates of invalidity" do not exist in the general case?

In other words, that there can exist $S$ which are not tautologies, and for which a counterexample model exists, but for which one cannot actually construct a counterexample, or a proof of its existence?

This is not a question about the ability of FOL to formalize arithmetic (which Godel proved is impossible), but simply whether or not, in a very foundational sense, it is possible to prove counterexamples exist to FOL sentences in general.

The completeness theorem states, in an equivalent form:

  If a formula $S$ is not valid, then there exists some model $\cal M$ such that $$ {\cal M}\not\models S$$
  or, equivalently
  $${\cal M}\models\neg S $$

This is simply the contraposative of the completeness theorem, as stated on e.g. wikipedia.

This shows that there is always a "certificate of invalidity" as you ask. This is still true if you ask for $\cal M$ to be countable.

However, obviously there is no procedure to compute $\cal M$, by a straightforward argument involving undecidability of Robinson's arithmetic.

Edit: To answer the question of how one might represent such a counter-model:

Unpacking the proof of the completeness theorem shows that such a certificate can be represented by a Herbrand structure, which are the syntactic terms of the language, possibly augmented with constants and function symbols, and recursively enumerable interpretations for the predicate symbols.

In general however, the interpretation of a formula cannot be decided by such a recursive enumeration (but it can be semi-decided).


Number of steps in worst Case we have to run a song on a Walkman,for that we need 2 full batteries.Let s say we have a mixed set of 30 batteries (15 are emtpy and and 15 are full)
and then only way to test if the battery full or empty is to put them in the Walkman and try it out.we can not tell which one is empty or full (one we put inside one full and one empty).

The question is to find the maxmium needed step to run the walkman (to find 2 full batteries)

I modelled the problem like that :
let s that the Walkman is a function f which take two argumments and it return 1 it the walkman works ,and 0 otherwise.
$$ f: \{b_1,b_2 \dots b_{30}\} \times \{b_1,b_2 \dots b_{30}\} \rightarrow\{0,1\}$$

The answer for the question was at most 18 steps , but somehow i could not figure it out.
Any  good suggestion how to proceed ?

You arrange your 30 batteries in pairs, where each pair consists of either:

2 empty batteries
2 full batteries
1 full and 1 empty battery

If you have a pair with 2 empty batteries it follows, that there is also a pair of 2 full batteries, thus, you have to test at most all of the pairs (15 steps) until you find a pair of two full batteries.

If your walkman isn't working after testing all 15 pairs, you know that each pair consists of a full and an empty battery.
You take the first two pairs with batteries (a,b) and (c,d). You then try the pairings: (a,c), (a,d) and (b,c).
You have now tested 18 combinations and either one of them worked or (b,d) has to be a working pair.

I don't know if this counts as 19 steps for your purposes (you have found 2 full batteries after 18 steps but the walkman is not running yet).


Bottleneck in Hoare Logic unable to arrive at my {P} from {Q} {Q} = {n>0}
C1 = i := 1;
C2 = c := 1;
C3 = p := 0;
{P} = {i<=n, p = fib(i-1), c = fib(i)}

My lack of understanding towards the rule of consequence in hoare logic is blocking me from find the solution which i hope someone can shed some light on how can i approach this with minimal abstraction of the process.

{R} = {i<=n,p=fib(i-1),c=fib(i)[i\1]} i:= 1;{i<=n, p = fib(i-1), c = fib(i)}

{R} = {1<=n,p=fib(0),c=fib(1)}

{R} = {1<=n,p=0,c=1}

{R1} = {1<=n,p=0,c=1[c\1]}c:=1;{1<=n,p=0,c=1}

{R1} = {1<=n, p=0, true }

{R2} = {1<=n,p=0[p\0]}p:=0;{1<=n,p=0}

{R2} = {1<=n,  true}{1<=n,p=0}

{R2} = {1<=n -> 0>x} :( i can't arrive at exactly n>0

*edit

From my observation the key problem is regardless of sequence i would always arrive at 1<= n as not equivalent to n>0, i am not sure how i can legally perform P->P’  P’ C  Q’  Q’->Q to prove {P}C{Q}

You are doing it in the opposite order. You are starting with the postcondition
{i<=n, p = fib(i-1), c = fib(i)} and then computing the precondition relative to the first assignment. You should instead use the last assignment, and go backwards:

{Q} = {n>0}
{P3 = P2[i\1]} = {1<=n, 0 = fib(1-1), 1 = fib(1)}
C1 = i := 1;
{P2 = P1[c\1]} = {i<=n, 0 = fib(i-1), 1 = fib(i)}
C2 = c := 1;
{P1 = P[p\0]} = {i<=n, 0 = fib(i-1), c = fib(i)}
C3 = p := 0;
{P} = {i<=n, p = fib(i-1), c = fib(i)}

The steps above were computed bottom-up: you should read it in the same way.

It is then simple to check that Q and P3 are equivalent (assuming integer variables).


Given a valid combination, how to get its index in the sequence of integer partition This question is extended from this Algorithm to generate integer sets fulfills restrictions, in the answer I learned the formal term of this problem, and the recursive algorithm described in that answer also gives me the desired sequence - as much large numbers located in the front as possible, for example, we will get the following output for $F(7,3,4)$:

4>2>1
3>3>1
3>2>2

So here is the question, given a valid combination, is it possible to get its index in the result set without generating the whole result set and searching for it?

This is called ranking combinatiorial objects, in this case combinations. Ranking and unranking algorithms exist for various simple combinatorial objects and even a general ranking algorithm exists for arbitrary combinatorial objects given that computing the number of objects matching certain criteria is feasible and there is a total ordering (eg lexicographic ordering).

For combinations, a reference is Algorithms for Unranking Combinations and Other Related Choice Functions, Zbigniew Kokosinski 1995

Assuming a lexicographic ordering among combinations of $K$ from $N$ the following algorithm can be used (which runs in $O(K)$ time assuming binomial computations are cheap):

Assuming the combination is given as an array (item) of length $K$ and where

$$item[0]<item[1]<\dots<item[K-1]$$

and each $0 \leq item[i] \leq N-1$

(If you want the combination in reverse order simply change the algorithm below to match in reverse order and skip last step. Also since your combinations take values between $1$ and $N$ you might want to subtract $1$ from below algorithms, where $item[i]$ is used)

$index = 0$

for $i=1$ to $K$:

____ $c = N-1-item[i-1]$

____ $j = K+1-i$

____ if $j \leq c$ then $index \leftarrow index+\binom{c}{j}$

Finally: $index \leftarrow \binom{N}{K}-1-index$

Note: The algorithm above can be modified to rank combinations with repeated/duplicate elements. Ie

$$item[0] \leq item[1] \leq \dots \leq item[K-1]$$

One needs to replace the counts used to represent combinations with repeated elements instead of binomials which count combinations with unique elements.

$index = 0$

$N \leftarrow N+K-1$

for $i=1$ to $K$:

____ $c = N-1-item[i-1]-i+1$

____ $j = K+1-i$

____ if $j \leq c$ then $index \leftarrow index+\binom{c}{j}$

Finally: $index \leftarrow \binom{N}{K}-1-index$

In essense ranking combinations is a bijection from $N,K$ combinations to natural numbers $0 \dots \binom{N}{K}-1$. This defines a combinatorial number system.

Algorithms above are modified to match my use case (for my combinatorics library Abacus) where combinations take values $0 \dots N-1$ and are non-decreasing. For your use case you can modify them to match wikipedia article.


Minimum number of swaps to make two arrays strictly increasing I'm trying to understand the solution of the following problem (LC 801):

Given two arrays, A and B, of the same nonzero length, find the minimum number of swaps (A[i] <--> B[i]) to make A and B strictly increasing.
The solution is guaranteed to exist for the given input data.
Example:
Input: A = [1, 2, 9, 4, 5, 6], B = [7, 8, 3, 10, 12, 13]
Output: 1 (swap 9 and 3)

The solutions posted by others consider a dp array, of size [2, A.size()], which is filled as follows:
int N = static_cast<int>(A.size());
std::vector<std::vector<int>> dp(2, std::vector<int>(N, N));

for (int ii = 1; ii < N; ++ii) {
  if (A[ii - 1] > A[ii] && B[ii - 1] > B[ii]) {
    dp[0][ii] = std::min(dp[0][ii], dp[0][ii - 1]);
    dp[1][ii] = std::min(dp[1][ii], dp[1][ii - 1] + 1);
  }
  if (A[ii] > B[ii - 1] && B[ii] > A[ii - 1]) {
    dp[0][ii] = std::min(dp[0][ii], dp[1][ii - 1]);
    dp[1][ii] = std::min(dp[1][ii], dp[0][ii - 1] + 1);
  }
}

return std::min(dp[0][N - 1], dp[1][N - 1]);

How to think / develop the idea for the solution?
It is clear that in the case the monotony is broken, i.e. A[ii] <= A[ii - 1] we need to swap, but, from trying a few test cases, this is not the optimal way to do the swaps.

$dp[b][i]$ denotes the minimum number of swaps needed to make the first $i$ elements of both arrays strictly increasing where $b$ is a boolean flag denoting whether we've swapped $A[i]$ and $B[i]$ (or $\infty$ if this minimum doesn't exist).
The key observation is that we only care about what $A[i-1]$ and $B[i-1]$ are when calculating $dp[0/1][i]$. This means that we can calculate $dp[0/1][i]$ using only $A[i-1]$, $B[i-1]$, $A[i]$, $B[i]$ and $dp[0/1][i-1]$ in $\mathcal O(1)$ time. (The recurrences are shown in the code you posted).
The answer is clearly $\min(dp[0/1][N])$, and this solution runs in $\mathcal O(N)$ time.


Image pattern detection - Finding similarities in same image The problem: Only pattern-like images are supposed to be uploaded and be used as backgrounds to a site, photos should not. How would you detect if an image looks enough like itself to be regarded as a pattern?

I'm no expert in image processing, but generally, repeating patterns can be identified relatively easily in the frequency domain. This is true for signal as well as image processing.

From what I understand of your question, you want to check that each image is composed almost completely of some repeating pattern, and reject those which are not (for example, photos).

You might want to try a Fast Fourier Transform of the image, and look for peaks in the frequency domain. Here is a similar question on SO, and this accepted answer gives good suggestions - try FFT, Wavelet analysis and auto-correlation, in that order of chance of working effectively. The other answers also give links to good references, especially this link.

A google search for "Detect repeating pattern in images" should give you good references, such as this, this, this and this.

Most of these references look for unknown repeating patterns in a given image, and locate those patterns. You would need to perform some post-processing on this that ensures that the repeating pattern (almost) completely covers your image, and not a small portion of the image. This should rule out repeating patterns in parts of the image, say the pattern on a person's shirt.


NP-hardness of an extention of 2 sat a 2  sat instance which is unsatisfiable and an integer k are given, decision problem is that: is it possible to delete k variables, also remove clauses contain them, in order to satisfy the 2-sat instance?? and optimization problem is that: find the minimum number of variables to remove to make the 2  sat instance satisfiable. I want to use reduction to show this problem is np-hard but I don't know which np-hard problem should be used. I appreciate if anyone could help me by the reduction or introduce me a reference (I searched but maybe I don't know the name of problem exactly)

please notice that this problem is different from maximum 2-sat, in this problem each clause can even contain one literal and we reduce 3-sat to show it is np-hard.

You can reduce from independent set. Given a graph, have a variable for each vertex, and for each edge, add the four clauses
$$ x \lor y, x \lor \lnot y, \lnot x \lor y, \lnot x \lor \lnot y, $$
where $x,y$ are the variables corresponding to the vertices connected by the edge. I'll let you complete the proof.


Sorting lower bounds for almost sorted array Can't find a good way to tackle the problem. Would appreciate any help.

$A$ is an $n$ items array from an ordered set, in which every item is at most
 $\log n $ indices away from its position in the sorted array.

Show that:

The array can be sorted in $O(n\log\log n)$.
There is a lower bound of $\Omega(n\log\log n)$ for sorting $A$ using comparisons.

The general idea is more important than details for both assertions.

Suppose that every element is at most $k$ elements away from its true position. In order to sort the array, you maintain a heap. At step $i$, you add $A_i$ to the heap, and pop the minimum element as $A_{i-k}$. You do no popping in the first $k$ steps, and no adding in the last $k$ steps; there are $n+k$ steps in total. Since the heap is always of size $k+1$, this runs in time $O(n\log k)$.

To see that this works, note that the first element in the sorted array must be one of the first $k+1$ elements, and in particular it must be the minimum of these elements. The second element could be any of the remaining elements or the $(k+2)$'th element, and in particular it must be the minimum of these elements. And so on.

For the lower bound, partition $n$ into blocks of length $k$, and consider the set of all permutation which fix each block. The number of such permutations is
$$
k!^{n/k} = [\Omega(k)^k]^{n/k} = \Omega(k)^n.
$$
Hence the number of comparisons is at least $\log [\Omega(k)^n] = \Omega(n\log k)$.


Heuristics for the $n$-puzzle An admissible heuristic for an n-puzzle is the Manhattan distance. Now if the cost of a transition is equal to the number of the piece that is moved, is it true that the Manhattan distance is still an admissible heuristic?

In my opinion yes, because during the search, for any node, we won't have any overestimation as a misplaced tile will have to move at least the number of spots between itself and the correct position.
Is this correct?

And also, would it be correct to say that the Manhattan distance multiplied by the mean of all tiles (eg 8-puzzle -> 4.5) is a heuristic that dominates the Manhattan distance in this case?

Thank you,

(Having troubles with my 1st AI class)

First of all, a heuristic is said to be admissible if and only if $h(n)\leq h^*(n)$ for every state $n$, where $h(n)$ is your heuristic function and $h^*(n)$ is the cost of an optimal path from $n$ to the goal.

Now, when considering the sliding-tile puzzle, the Manhattan distance can be shown to be an admissible heuristic function as it results from a constraint relaxation [1].

From here, consider your first question: if the Manhattan distance is an admissible heuristic function for the sliding-tile puzzle where the cost of each movement is 1, it is also an admissible heuristic function for the case where the cost of each movement is strictly greater or equal than 1 (because all tiles are numbered 1 onwards).

Regarding your second question, a heuristic function $h_1(n)$ is said to dominate another heuristic function $h_2(n)$ if and only if $h_1(n)\geq h_2(n)$ for all states $n$. For some restrictive models (a unique goal, constant branching factor, no duplicates, etc.) it can be shown that more informed heuristics (i.e., $h_1(n)$ in the previous definition) expand less nodes when using A$^*$. From here, if you enhance your heuristic function with the average of all tiles, then it is necessarily more informed than pure Manhattan but watch out, it should be easy for you to note that this second heuristic function is not necessarily admissible as it can very easily overestimate the effort to reach the goal. Thus, using this second heuristic it is very likely that you will expand less nodes but you cannot guarantee that the solution returned is optimal.

Hope this helps,

Bibliography

[1] Pearl, Judea. Heuristics - Intelligent Search Strategies for Computer Problem Solving. Addison Wesley, 1984.


What do the ∀ and ∃ symbols mean in the Axiom of Choice? On the Wikipedia page for the Axiom of Choice the following statement is given:

$(\forall x^\sigma)(\exists y^\tau)R(x,y)\rightarrow(\exists f^{\sigma \rightarrow \tau})(\forall x^\sigma)R(x, f(x))$

Most of it seems fairly straightforward, except for the meanings of the symbols that look like 180 degree rotated 'E' and 'A'

$\forall$ reads as "for all", and $\exists$ reads as "there exists".
So, in english we have

$$\text{"if }\underbrace{\text{for all $x$}}_{\forall x^\sigma}\text{ }\underbrace{\text{exists a $y$}}_{\exists y^\tau}\text{ with $R(x,y)$, }\underbrace{\text{then}}_\to\text{ }\underbrace{\text{there is a function $f$}}_{\exists f^{\sigma\to\tau}}\text{ so that }\underbrace{\text{for all $x$}}_{\forall x^\sigma}\text{ holds $R(x,f(x))$".}$$

I skipped over the $\sigma$ and $\tau$ superscripts, as they indicate types and are not of primary importance here.


Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar) I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer):

Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve.

I could easily construct a LBA for this language.
But since the notation/construction of LBAs weren't really explained, I would have to define it in the exam.

So I assume this task was expected to be done by constructing a context-sensitive grammar.

NOTE: In our lecture the definition of a context-sensitive grammar was in fact the definition of a noncontracting grammar.
So any rule like this x -> y is allowed if |x| <= |y|

So this is allowed:

aAb -> bXaa

My best idea goes like this:

S  -> AB
B  -> bB | b
A  -> CA | C
Cb -> abC
Ca -> aC

so to generate aaabaaabaaab I do this:

S
AB
AbB
AbbB
Abbb
CAbbb
CCAbbb
CCCbbb
(let all C-Variables run through the word and leave an 'a' before every 'b')
CCabCbb
CCababCb
CCabababC
...
aaabaaabaaabCCC

But I can't make all the 'C'-Variables disappear.

Sems to be a decent approach.

The trick you need is to leave the last B  marked, say you generate bbX rather than bbb. Now the final X can absorb the C's using the production CX -> aX.

In the end you are left with the final X which can change into b again.

Of course the final production X -> b might be applied too soon, when there are still C's around. This is harmless. Now the C's cannot disappear and the derivation will not succesfully end.

In ordinary context-sensitive grammars one is usually not very interested in unsuccesful derivations, but it might be hard to consider all cases when writing formal proofs. It is some times possible to write more deterministic grammars by simulating linear bounded automata. In state p read a then write b move left to state q one would have the rewrite rule xpa -> qxb (for every letter x). Then the only problem is to make the final state disappear.


What other instructions are stored in the ROM? Apart from the start-up instructions, what other programs are stored in the ROM?

You store software in ROM for security, because it cannot be modified. Especially when your device’s operating system is updated, you want that to be controlled by software in ROM so you can detect fake or hacked software updates in a way that cannot be hacked.


Independent set on cubic triangle-free graphs I know that maximum independent set on cubic triangle-free graphs is NP-complete.

Is it still NP-complete in case we require the independent set to be of size exactly $|V|/2$?

Basiclly, YES instance of independent set problem on cubic triangle-free graphs problem must have exactly $|V|/2$ nodes. NO instance has an independent set of size less than $|V|/2$.

Let's start by proving that the maximum independent set is of size at most $|V|/2$. Let $I$ be an independent set. For each vertex $v$, let $\alpha(v)$ be the number of its neighbors in $I$. If $\alpha(v) \geq 1$, then we know that $v \notin I$. Since the graph is cubic, $\sum_v \alpha(v) = 3|I|$. Since $\alpha(v) \leq 3$, the number of vertices such that $\alpha(v) \geq 1$ is at least $|I|$. Hence $|I| \leq |V|/2$.

When can we have equality? We must have $\alpha(v) \in \{0,3\}$, so for each vertex not in $I$, all its neighbors must be in $I$. The converse is also true - for each vertex in $I$, all its neighbors are not in $I$. In other words, the graph must be bipartite. This can be checked in polynomial time.


Comparing growth of two sums of functions Does $n+n^4$ grow faster than $n^2+n^3$? If so, why?

Yes, asymptotically. You can see that $n + n^4 = \omega(n^3 + n^2)$ by taking the limit:

$$
\lim_{n \to \infty} \frac{n^4 +n}{n^3 + n^2} =  \lim_{n \to \infty}\frac{n + n^{-2}}{1 + n^{-1}} = + \infty
$$.

See also this answer.


Adding an ordered into a relationship without violating the functional dependencies Assuming that we have the relationship $R(A,B,C,D)$, the tuple $(W,X,Y,NULL)$ and the following functional dependencies:

$$A \to C$$
$$A \to B,D$$

is it possible to insert a tuple with $NULL$ values, without violating the functional dependencies? I understand the definition of functional dependencies but I've never actually thought about what would happen for $NULL$ values. On the one hand, if you consider $NULL$ as a value then yes but if you say that it's the absence of value, then you can't. But in the case of the possibility of adding the tuple, mentioned above, without violating the functional dependencies, what could you do?

First of all, the classical relational theory does not include null values, and for this reason the concept of functional dependency (and violation of FD) is not defined in presence of such values.

Note that NULL is not a constant, neither a different value each time it is used. This can be seen if you try something like:

SELECT NULL = NULL;

the result is neither TRUE (the two values are in effect the same value) nor FALSE (the two values are different), but NULL, which means that we have no information at all about the real values (even if they exist or not!). And this is the foundamental reason for which it has no sense to consider or not a violation of a FD in presence of a null value.

For instance, considering your question, let's think about the meaning of a functional dependency. Since from the dependencies that you have listed we can derive A -> D, this means that each time in a tuple there is a certain value of the attribute A, there should be the same value of the attribute D. But if we have two tuples with the same value of A, and one of them has a NULL value for D, while the other has a normal value, this means that we do not know if the dependency is violated or not, since we do not know nothing about the value of the attribute specified as NULL. It could be unknown, and be the same, or different, or it could not be present. So nothing can be said about the violation.


Proof that language is not context-free with Parikh's theorem I want to prove that the language $L = \{ a^{n}(ab)^{{n}^{2}}b^{n} \mid n \geq 0 \}$ is not context-free by using Parikh's theorem.

My first assumption is that the $(ab)^{{n}^{2}}$ part cannot be written as a subset of linear vectors.
From this it follows that $\psi(L)$ is not semi-linear.

My problem is to show that by a formal proof.

If $L$ were context-free then, applying the homomorphism mapping both letters to $a$, also the following language would be context-free:
$$
L' = \{ a^{2n^2+2n} : n \geq 0 \}.
$$
According to Parikh's theorem, a unary language is context-free iff the corresponding subset of $\mathbb{N}$ is eventually periodic. Yet the sequence $2n^2+2n$ has arbitrarily long gaps, since $2(n+1)^2+2(n+1)-2n^2-2n = 4n+4$. Therefore the set $\{2n^2+2n : n \geq 0\}$ is not eventually periodic, and so $L'$ is not regular or context-free.


Are any two complexity classes equipped with an oracle to solve the halting problem equivalent? Equip any complexity classes $C$ and $B$ (to be more specific: any complexity classes that contain only decidable problems) with the same oracle $O$ that solves the halting problem for a Turing Machine. Is $C^O = B^O$ for any $B$ and $C$ that, again, only contain problems decidable by a TM with no access to an oracle (only the empty oracle)?

No, they are not in general - and focusing on the halting problem specifically makes the situation look more complicated than it actually is. The real point is the following:

There are lots of separation results which relativize to all oracles.

There's a slight technical issue here, actually: how exactly should we treat space-based complexity classes in the oracle context? See the bottom of page $5$ here. I'll only talk about time-based classes here to avoid having to think about this.

For example, the classical argument that $\mathsf{P}\subsetneq\mathsf{EXPTIME}$ in fact shows that $$\mathsf{P}^A\subsetneq\mathsf{EXPTIME}^A$$ for every oracle $A$. In particular, we can take $A$ to be the Halting Problem. Another example of a separation which relativizes to all oracles - including the halting problem - is the time hierarchy theorem.

This topic is treated in chapter $3$ of Arora/Barak:

  "Any result about TMs or complexity classes that uses only Properties I and II above also holds for the set of all TMs with oracle $A$. Such results are called relativizing results.
  All of the results on universal Turing machines and the diagonalizations results in this chapter are of this type."

  (pg. 72; I've replaced their "$O$" with an "$A$" to avoid conflict with your use of "$O$" for the halting problem specifically.)

Of course not everything relativizes - and see in particular Baker-Gill-Solovay - but some things do relativize, and all relativizing separation results yield negative answers to the OP as special cases.

Just for completeness, here's one proof that $\mathsf{P}^A\not=\mathsf{EXPTIME}^A$ for any oracle $A$ goes; unsurprisingly, it's a direct diagonalization. Fix an oracle $A$; we want to show $\mathsf{P}^A\subsetneq\mathsf{EXPTIME}^A$. We'll use an exponential-time machine with oracle $A$ to diagonalize against polytime machines with oracle $A$. Fix appropriate enumerations $(\Phi_i)_{j\in\mathbb{N}}$ and $(p_j)_{j\in\mathbb{N}}$ of oracle machines and polynomials respectively and an appropriate pairing function $\langle\cdot,\cdot\rangle$, and let $$X=\{\langle a,b\rangle: \neg\Phi_a^A(\langle a,b\rangle)[p_b(\lfloor\log (\langle a,b\rangle)\rfloor)]\downarrow=1\}$$ (here "$[s]\downarrow=$" means "halts in $s$ steps and equals"). By construction we have that $X\not\in \mathsf{P}^A$ (suppose $\Phi_a^A$ decided it in time $p_b$ ...); however, the "brute force" calculation of $X$ from $A$ only takes exponential time, so $X\in \mathsf{EXPTIME}^A$.

Note that this is just the usual proof, with an "$A$" superscript added everywhere. The point is that diagonalization is such a "coarse" technique that - when it works at all - it tends to work for all objects like Turing machines. And this includes Turing machines relative to a fixed oracle.


Prove if $\{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$ is regular or not $$L = \{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$$

To Prove: If given language is regular or not.

I know that it is not a regular language but I am not able to come up with the string which I can use in the pumping lemma to prove that it is not regular.

We can also divide $L$ into two parts:
$$\begin{align*}
L_1 &= \{x^iy^jz^k \mid i \le 2j\}\\
L_2 &= \{x^iy^jz^k \mid j \le 3k\}\,,
\end{align*}$$

so I just need the strings to be used in the pumping lemma for $L_1$ and $L_2$.

It's not regular. Hint: Let $p$ be the integer of the pumping lemma and pump the string $x^{6p}y^{3p}z^{2p}$.


Do L-systems have a corresponding automata? So, I was reading about L-systems and it seems that L-systems are in many ways analogous to context-free grammars. Is there a corresponding automata for this? I can't seem to find anything on the Wikipedia page.

Lindenmayer's original papers define them using arrays of finite state machines. The outputs at each time are the states at the next time, which also serve as inputs to the neighbors, much like a cellular automaton. Unlike cellular automata, the machines can output strings, and each additional symbol becomes the state of a new machine in the array.


What does "context" in "context-free grammar" refer to? There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble:

What context is it free of?

To investigate, I Googled "context sensitive grammar" but I still failed to find what the "context" was all about.

Can someone please explain what the context term refers to in these names?

You are right, there always is a context in some sense. I don't think you can understand what "context" means in "context-free" without understanding a production.

A production is a substitution rule.  It says that, to generate strings within the language, you can substitute what is on the left for what is on the right:

A -> xy

This means that the abstract sequence A can be replaced by the character "x" followed by the character "y". You can also have more complex productions:

zA -> xy

This means that the character "z" followed by the abstract sequence A can be replaced by the characters "x" and "y".

A context-free production simply means that there is only one thing on the left hand side. The first example is context-free, because A can be replaced by "x" and "y" no matter what comes before or after it. However, in the second example, the character "z" has to appear before the A, and then the combination can be replaced by "x" and "y", so there is some context involved.

A context-free grammar is then just a grammar with only context-free productions.

The second example is actually an example of an unrestricted production. There is another category that is between context-free and unrestricted called "context-sensitive". An example of a context-sensitive production is:

zA -> zxy

The difference being that what comes before A (and after) on the left hand side has to be preserved on the right. This effectively means that only A is substituted, but can only be substituted in the proper context.


Why $\operatorname{gap-A}[1.5a, 1.5b + 1/4]$ has an efficient solution? Let $0<a < b<1/2$. Suppose that there's an efficient $a/b$-approximation for $A$, where $A$ is a maximization problem. Why does $\operatorname{gap-A}[1.5a, 1.5b +1/4]$ also has a polynomial solution?

We've learned in class that if $gap-A[a,b]$ has a polynomial solution then there's a $\frac{a}{b}$ approximation. That is,

$$\frac{a}{b} opt(x) \le val(y_x) \le opt(x)$$

So let's assume by contradiction that $\operatorname{gap-A}[1.5a, 1.5b +1/4]$ is hard.
Then, there's no polynomial time $\frac{1.5a}{1.5b + 1/4} $-approximation algorithm.

$$\frac{1.5a}{1.5b + 1/4} = \frac{a}{b+1/6}$$

Then, $gap-A[a,b+1/6]$ is hard to decide, but that doesn't help with reaching a contradiction.

EDIT:
We define for a maximization problem $A$ the decision problem $\operatorname{gap-A}[a,b]$ as:

Let $Y$ to be the set of solutions for $x$.

for a given $x$, the algorithm needs to decide:

there's a $y_x\in Y$ such that $y_x > b$.
for every $y_x\in Y$: $y_x < a$

If $x$ is not in one of the above the result could be arbitrary.

Given an instance $x$ of $\mathsf{gap\text{-}A}(1.5a,1.5b+1/4)$, calculate $y_x$ using the $a/b$ approximation algorithm, so that
$$
\frac{a}{b} opt(x) \leq val(y_x) \leq opt(x).
$$
If $opt(x) \geq 1.5b+1/4$ then
$$
val(y_x) \geq \frac{a}{b} (1.5b+1/4) > 1.5a.
$$
Conversely, if $opt(x) \leq 1.5a$ then
$$
val(y_x) \leq 1.5a.
$$
You take it from here.


Given set of grammar rules, how to find if they correspond to Context-free or unrestricted Given set of grammar rules, how to find if they correspond to Context-free or unrestricted?

Just for Understanding (don't solve the below one),
eg:

\begin{align}
S &\rightarrow B/A, \\
1B &\rightarrow 111B, \\
1A0 &\rightarrow 00
\end{align}

It is undecidable to determine whether the language generated by a given grammar has a context-free grammar.

However, if you are simply asking whether a grammar itself is context-free, look no further than the left hand side of each production. A grammar is context free iff the left hand side of each production is a single non-terminal.


Reference request: Monads, continuations, and other functional CS concepts I've been using Clojure for about 18 months. Recently, I've come across terms such as Monads, Continuations, et al which I'd like to learn about.

I could visit Wikipedia and read about these two topics, but I'm looking for a reference which also help me learn about related matters that I don't even know exist. Is there a book on this particular topic (if it even qualifies as one)? Would I pick these things up by learning about type systems or language design in general? Should I just learn Haskell to get exposure?

I would focus on learning a functional language in order to learn these. There's no need for it to be Haskell. It could be Scheme or ML, or even Coq or Agda. Frankly, Clojure will probably do. But to me, monads and continuations are only programming tools. They don't let you do any new computations, they just let you do them in a different way. So understanding them outside of the context of a particular style of programming to me doesn't make much sense.

I'd recommend Real World Haskell as an introduction to some of these concepts, particularly in how they can be used in programming. I'm not sure how much it has on continuations. I learned continuations from Essentials of Programming Languages, which I quite liked, but deals with Scheme rather than Haskell, and doesn't do anything monadically.


CFG for all strings of a’s and b’s that contain a different number of a’s and b’s I am trying to write CFG for all strings on {a,b} that contains different numbers of a’s and b’s? After two hours of brainstorming, I came up with this:

S→A|B
A→aE|aA|EA
B→bE|bB|EB
E→aEbE|bEaE|Λ

I tried running few strings on this, it worked, But then I run string "abbab" and it failed.
 Kindly someone point out at my mistake or tell me the correct CFG for this as I don't know how to correct this.

In fact, your grammar is correct and clean!

Here is how your grammar generates $abbab$.

$$S\Rightarrow B\Rightarrow EB\Rightarrow^* abB
\Rightarrow abbE\Rightarrow^* abbab $$

Exercise. Show your grammar is correct.


Can Deterministic Context free Grammars be ambiguous? I know that DCFL are unambiguous languages and DCFL languages have one-to-one correspondence with LR grammars.

But I wanted to know if there can be an instance that deterministic context free grammar is ambiguous.

No, there is no deterministic context-free grammar that is ambiguous since any deterministic context free grammar (DCFG) must be unambiguous.

Here is definition 2.47 of the book introduction to the theory of computation, third edition, by Michael Sipser.

  A deterministic context-free grammar is a context-free grammar such that every valid string has a forced handle.

Furthermore, here is definition 2.62.

  An LR($k$) grammar is a context-free grammar such that the handle of every valid string is forced by lookahead $k$.

A DCFG is the same as an LR(0) grammar. All LR($k$) grammars are unambiguous, by definition.


Turing machine with possible transitions to the final state Let's say we want to draw the transition graph of a Turing Machine that accepts that language L and then write the sequence of moves done by the TM when the input sequence is $w = abbcbba$ so I had some thoughts on how this could be built.

$q0 - q1: a,a,R$

$q1-q2: b,b,R$

$q2 (loop): b,b,R$

$q2-q3: c,c,R$

$q3-q4: b,b,R$

But then I'm getting stuck here, I could see $b,b,R$ to the final state and then add a separate node to account for the case $m=3$, but I'm teaching this to myself so maybe someone can step in here and get me back on track.

EDIT:

This might work:

I would define F(set of final states)={$q_4,q_5,q_6$} then:

$ q_4-q_5:b,b,R$

$q_4-q_7:X,X,R$ for X=a,c

$q_5-q_6:b,b,R$

$q_5-q_7:X,X,R$ for X=a,c

$q_6-q_7:X,X,R$ for X=a,b,c


Converting a 32-bit bit pattern into floating point number In The Scientist and Engineer's Guide to
Digital Signal Processing
By Steven W. Smith, Ph.D. i have read something like that,

Single precision or 32-bit floating point forms the floating point number, $v$, by the following relation:
$$ v = (-1)^S \times M \times 2^{E-127} $$

The term: $(-1)^S$, simply means that the sign bit, $S$, is $0$ for a positive number and $1$ for a negative number. The variable, $E$, is the number between $0$ and $255$ represented by the eight exponent bits. Subtracting $127$ from this number allows the exponent term to run from to In other words, the exponent is stored in offset binary with an offset of $127$.

Everything I have understood but this,

  Subtracting 127 from this number allows the exponent term to run from 128 to −127. In other words, the exponent is stored in offset binary with an offset of 127.

I need an easy to understand explanation of subtracting 127 from $E$ and binary offset.

Suppose you didn't include that shift of $127$, i.e. your number $\nu$ would have the form $\nu = (-1)^S \cdot M \cdot 2^x$ with $x$ being the exponent.

With $8$ bits for the exponent $x$ can have a value from $0$ to $255$. This means you can represent numbers from $\nu = (-1)^S \cdot M \cdot 2^0$ to $\nu = (-1)^S \cdot M \cdot 2^{255}$ .

However, what if you wanted $\nu$ to be $2^{-10}$? It would not be possible.

For this to be possible you want to allow negative exponents $x$. Instead of $x$ ranging from $0$ to $255$ you introduce a shift of 127 such that $x$ ranges from $-127$ to $+128$ .

Now you can represent numbers $\nu$ that range from $(-1)^S \cdot M \cdot 2^{-127}$ to $(-1)^S \cdot M \cdot 2^{+128}$ .


Compute minimum hamming distance of a code How do you find the minimum hamming distance of a code?
A naive way is computing the distance of each pair of codewords in our code.

It becomes hard when the code is sufficiently large. Is there a formula for minimum hamming distance?

When the code is linear, there is no need to go over all pairs of codewords, due to linearity. Indeed, since $d(x,y) = d(x\oplus y, 0)$ and for any two codewords $x,y \in C$, linearity implies that $x\oplus y \in C$, we see that the minimal distance is the minimal weight of a non-zero codeword. There are other ways characterization of the minimal distance, for example in terms of the generator matrix. See also this question.

By the way, an $(n,k,d)$-code is one with $2^k$ codewords of length $n$ and minimal distance $d$. So if you have a $(7,4,3)$-code, the minimal distance must be...?


Proof that $\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ is not (co-)recursively enumerable I would like to use your help with the following problem:

$L=\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$. Show that $L \notin RE \cup  CoRE$.

I know that to prove $L\notin RE$, it is enough to find a language $L'$ such that $L'\notin RE$ and show that there is a reduction from $L'$ to $L$ $(L'\leq _M L)$.

I started to think of languages which I already know that they are not in $RE$, and I know that $Halt^* =\{⟨M⟩ ∣ M\mbox{ halts for every input} \} \notin RE$. I thought of this reduction from $Halt^*$ to $L$: $f(⟨M⟩)=(M')$. for every $⟨M⟩$: if $M$ halts for every input  $L(M')=0^n1^n$ otherwise it would be $o^n1^n0^n$, but this is not correct, Isn't it? How can I check that $M$ halts for every input to begin with? and- is this the way to do that?

I think the question is how to show that $L$ is not r.e. One way to do that is to reduce the complement of the halting problem to $L$, because the complement of the halting problem is not r.e.

Here's a hint about one way to do that reduction: given $M$ and $x$, we want to make a language that is context free if and only if $M(x)$ does not halt. So start simulating $M$ on input $x$. As long as $M(x)$ does not halt, we make a language that looks like $\{ 0^n : n \in \mathbb{N}\}$. But if $M(x)$ does halt, we change the language we're generating after that point to be some r.e. but not context free language.


Topology vs sigma-algebra's as a framework for approximate information? In the book "topology via logic" by Steven Vickers, topology is introduced for computer scientists, with the idea that topology captures the idea of approximate information.

I am somewhat confused by the explanation. In particular, I'm confused by how it relates to sigma-algebra's, which are also a way to express approximate information. In the case of sigma-algebra's, we can think of each set in the sigma-algebra as the sigma as a "signal" that we may receive, and the elements of that set as the "possible worlds" in which we would receive that signal. The sigma algebra then denotes the fact that we don't know in which exact world we are, but we know what subset of possible worlds we are. The axiom of closure under complementation follows intuitively from this: If we don't get the signal that we're in subset of worlds $A$ then we must be in $A^c$.

What is the rationale behind using topology instead of sigma-algebra's for capturing approximate information in computer science?

In particular, how are the differences between topology and sigma-algebra's imply for how they are used as frameworks for talking about approximate information?

closure under complementation in sigma-algebra's but not in topology
closure under countable unions in sigma-algebra but arbitrary unions in topology.
closure under countable intersections in sigma-algebra but finite intersections in topology.

What sort of structure we get depends on what we are trying to model. Your starting assumptions may well lead to $\sigma$-algebras, but in computer science we have a certain understanding of "approximate information" which is naturally captured by topology.

Consider the following pieces of information:

no information
it is raining
it is not raining

Clearly, "no information" approximates both "it is raining" and "it is not raining". If we think of "it is raining" as an observation that can be made, then the following assymetry is cruicial: having the information "it is not raining" is not equivalent to not having the information "it is raining". That is, if you don't receive some piece of information saying that $P$ holds, then you simply don't know. It is faulty to presume that you know $\lnot P$. This is the root cause of why the $\sigma$-algebra law of complementation is not valid in this context.

Now, to motivate closure under arbitrary unions and finite intersections (but not under arbitrary intersection), we need to take a slightly different point of view. Let us say that we want verifiable information, i.e., we say that we "have information $A$" if we can reasonably verify that $A$ holds.

To verify a binary conjunction $A \land B$, we verify both $A$ and $B$.
To verify an arbitrary disjunction $\bigvee_i A_i$ it is sufficient to verify a single $A_j$.

However:

To verify an infinite conjunction $\bigwedge_i A_i$ we would have to verify all $A_i$'s, and this may not be doable algorithmically (or in a physically realistic manner).
Just because we know how to verify $A$ does not mean that we also know how to verify $\lnot A$.

Example: to verify that a given machine $T$ halts it suffices to run the machine and wait until it stops. At this point we have verified that $T$ stops. (It is irrelevant what would have happened if $T$ did not stop!) But how could we verify that $T$ does not stop? It's not in general verifiable whether $T$ stops.

Another example: "$x > 0$" is a verifiable property of computable reals, but "$x \leq 0$" is not. (Recall that $x \in \mathbb{R}$ is computable if there is an algorithm which, for any given $n \in \mathbb{N}$ gives an interval $[a_n,b_n]$ with rational endpoints such that $a_n < x < b_n$ and $b_n - a_n < 2^{-n}$.) The verification algorithm works as follows: given an algorithm for computing $x$, find $n \in \mathbb{N}$ such that $0 < a_n$. If $x > 0$ then this algorithm will terminate after a finite time, thereby confirm that $x > 0$. If $x \leq 0$ then the algorithm will run forever, but that is OK because we only need to confirm $x > 0$, we are not trying to deny $x > 0$ in case it does not hold. In contrast, we cannot confirm $x \leq 0$ because there is no algorithm which takes as input $x \in \mathbb{R}$ and terminates if, and only if, $x \leq 0$.


Proving $\Omega(cf) = \Omega(f)$ I'm trying to prove the following lemma:

$c$ is a positive real number and $f, g$ are functions from natural numbers to non-negative real numbers. I'm trying to prove rigorously that:

$\Omega(cf(n))$ = $\Omega(f(n))$.

I know that it is obvious but I'm trying to construct a proof that is as complete as possible. My current approach is like this:

This lemma is equivalent to saying that: $f(n) \in \Omega(cf(n))$ iff $cf(n) \in \Omega(f(n))$.

We can also restate that as:

If $t(n) \in \Omega(cf(n))$ then $t(n) \in \Omega(f(n))$.
If $t(n) \in \Omega(f(n))$ then $t(n) \in \Omega(cf(n))$.

For 1.,

$(*)$ $\exists d_1, d_2 \gt 0, \forall n \gt n_0, n_1, \forall n \in N$:

$t(n) \ge d_1cf(n)$ and $t(n) \ge d_2f(n)$

Now let's fix $d_1, d_2$ and $n_0, n_1$ to be any constants that fulfils $(*)$, such that:
$n'=max\{n_0, n_1\}$ and $d_1c \ge d_2$, using this we can say that:

$t(n) \ge d_1cf(n) \ge d_2f(n)$ and hence the 1. is satisfied because $t(n) \in \Omega(cf(n)), \Omega(f(n))$. The proof of 2. is mutatis mutandis.

Do I have a mistake in my proof, is there a better/more elegant way to prove this lemma? Shortly how can I improve this?

I think you're trying to take too many steps at once. Try to think about it one small step at a time.

Always think about:

What are the definitions I have available
What do I know already? What is proven?

Proving sets equal

Since you have two sets, $\Omega(cf)$ and $\Omega(f)$ and you want to prove them equal, you first need to think about what it means for two sets to be equal:

$$A = B \Longleftrightarrow A \subseteq B \land A \supseteq B$$

This tells you, that you need to show two things:

$\Omega(cf) \subseteq \Omega(f)$
$\Omega(cf) \supseteq \Omega(f)$

Proving $A$ to be a subset of $B$

For this, you need to apply the definition of $A \subseteq B$:

$$ A \subseteq B \Longleftrightarrow \forall a  \in A:(a \in B)$$

Nature of our proof

As you can probably see by now, our proof will have the following form:

$$\begin{align*}"\subseteq":\\ & \text{Let } g \in \Omega(cf):\\
&\Rightarrow \dots\\
&\Rightarrow g \in \Omega(f)
\end{align*}
$$

The proof goes the same way for $"\supseteq"$.

Filling in the dots

Keeping this structure in mind, the path you need to follow is already laid out.

Using this definition for \Omega: $ \Omega(f) = \{ g |\, \exists\, n_0 \in \mathbb{N}, c > 0 \forall n \geq n_0: cf(n) \leq g(n) \} $

One direction of the proof could look as follows:

$$\begin{align*}"\subseteq":\\ & \text{Let } g \in \Omega(cf): \\
&\Rightarrow \exists\, n_0\in \mathbb{N}, c'>0: c'cf(n) \leq g(n)\ \ \forall n \geq n_0 &\text{definition of } \Omega\\
&\Rightarrow \exists\, d>0,  n_0\in \mathbb{N}: d f(n) \leq g(n)\ \ \forall n \geq n_0 &\text{Let } d=c'c\\
&\Rightarrow g \in \Omega(f) &\text{definition of } \Omega
\end{align*}
$$