Does this progressive image compression exists? I want to know if this progressive image compression that I have in mind exists and it it does I want know its name and/or get some references about it.

The algorithm consists of converting one high resolution image in multiple low resolution images (all of the same size, not like in wavelet transform) with the following properties:

If you have one of them, any of them, you can reconstruct a low resolution approximation to the original image.
You can compose many of those in any order to get better approximations to the original image.
If you combine all low resolution images you get the original image or a very good approximation of it without perceptible artifacts.
Algorithm is real-time, i.e. it can display a meaningful partial reconstruction of the original image at any time of the reconstruction process (independently of received sub-images and their order).

Does this algorithm exits? Is it possible at all?

I know about image reconstruction techniques, but those use similar but different images to reconstruct a higher resolution one and the result is always noisy and full of artifacts. This is not I am asking for.

I believe that the Stationary Wavelet Transform (SWT) meets your requirements:
https://en.wikipedia.org/wiki/Stationary_wavelet_transform

1) Any given level of coefficients could be used to reconstruct the original image by running normal reconstruction but assuming zeros for the other levels.

2) Each level of coefficients stores data about a different range of spatial frequencies in the original image, and thus they can be recombined arbitrarily.

3) Unless you quantize when or after you perform the transform, the SWT is lossless.

4) I haven't done any processing time evaluation, but optimized libraries are available: https://www.mathworks.com/help/wavelet/ug/discrete-stationary-wavelet-transform-swt.html

In general though, unless you require translation invariance, you would benefit from the downsampling in the more common Discrete Wavelet Transform (DWT). The downsampling results in smaller images which requires less space to store and time to process. No information is lost by this downsampling as the frequency filters in the DWT filter out and then store (in the higher resolution levels) the frequencies that then get lost in the downsampling. The lower frequencies simply need fewer samples to be accurately reconstructed (https://en.wikipedia.org/wiki/Nyquist_frequency).

If you have one of them, any of them, you can reconstruct a low resolution approximation to the original image.

this means that they duplicate the information. imagine а 8x8 blue area. if each sample carries info that this are is blue, you carry N duplicates of the same info. So, the compression ratio will suffer


Decremental reachability in a grid graph Consider an $n$ by $n$ grid graph. For example, the following.

You can of course reach the top left corner from the bottom right.  Now consider the graph dynamically with an arbitrary number of edges deleted at each step.

  What is the time complexity of determining whether you can still reach
  the top left corner from the bottom right after edge deletions?

Further clarification.

Queries. There is exactly one type of query which gives a Boolean output.  That is whether there is a path from the top left corner to the bottom right.

Updates. An update can delete an arbitrary number of edges greater than $0$.

Complexity.  Each update is followed by a query. The complexity I am interested in is the amortized time over all updates and queries.  The best this could possibly be would be proportional to the number of deleted edges I assume.

I found these lecture notes which say you can get $O(\log{n})$ time for planar graphs per individual edge deletion (the Eppstein et al. reference). However this paper supports many more operations than I need, my graph is a special case of a planar graph and my updates are in batches in a sense.  The most important difference may just be that I am only interested in the decremental version. I haven't found anything specialized for batched, decremental connectivity in a grid graph.

Is there anything simpler than the Eppstein et al. paper for my special case or alternatively faster than $O(\log{n})$ time per edge deletion?

By improving on @emab's idea, you can achieve $\Theta(\alpha(n^2))$ amortized time per deletion and query, where $\alpha$ is the inverse Ackermann function, i.e. almost constant.

Initialize a union-find data structure with an enry for each square of the grid graph and two entries each for the two pairs of outside faces top+right and bottom+left.
For an example of $n=3$, the faces $1,2,3,\ldots,9,A,B$ in the diagram below are initialized. Where $A,B$ are the outside faces split by the dashed lines.

When removing an edge call union() on the two squares (or the sqare and $A$ or $B$) separated by that edge.
To check connectivity, call find() on the faces $A$ and $B$. If the results differ, return true, else return false.

Let's call the top-left node as $s$ and the bottom-right node as $t$.

In the square drawing of this graph, there are four sides (left, right, top, bottom).

Let's call two edges connected, iff they share a square or an endpoint (we can determine if two edges are connected or not in $O(1)$).

As you remove the edges from the graph, you maintain a few lists of those edges.  that are connected, and see if any of them connect one of the four side pairs:

top to bottom
top to left
left to right
bottom to right

In the following figure, by dashed red lines, I tried to demonstrate a series of edge removals (if the red dashed line crosses an edge, it means that the edge is removed at some point).

(Algorithm is below figure)

Algorithm

Component = []
/* Initialize Hit_Sides by 0 */
Hit_Left = []; Hit_Right = []; Hit_Top = []; Hit_Bottom = [];
while ( input >> e; /* there is an edge e to be removed */)
    L = L + {e};
    Component[e] = e;
    if (e hits any side s) then
        Hit_s[e] = 1;
    For each e' in L
        if (e' is connected to e)
            Component[e] = Component[e']
        if (e hits any side s)
            Hit_s[Component[e] = 1;
    For each component c in Component
        if (it hits one of the four disconnecting pairs)
            Output << There is no path from s to t

BTW, the following explanation is clear and precise. However, if you use geometrical techniques, you may be able to get some logarithmic algorithm out of it.

If you maintain a list of edges that are being removed, you can consider the list of connected ones, and see whether they hit any disconnecting sides (top-bottom, top-left, left-right, bottom-right) and answer to that reachability query in $O(1)$.

In the following figure, red lines illustrate the disconnecting sides:


Minimum spanning tree vs Shortest path What is the difference between minimum spanning tree algorithm and a shortest path algorithm?

In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and one shortest path algorithm (Dijkstra's).

Minimum spanning tree is a tree in a graph that spans all the vertices and total weight of a tree is minimal. Shortest path is quite obvious, it is a shortest path from one vertex to another.

What I don't understand is since minimum spanning tree has a minimal total weight, wouldn't the paths in the tree be the shortest paths? Can anybody explain what I'm missing?

Any help is appreciated.

Consider the triangle graph with unit weights - it has three vertices $x,y,z$, and all three edges $\{x,y\},\{x,z\},\{y,z\}$ have weight $1$. The shortest path between any two vertices is the direct path, but if you put all of them together you get a triangle rather than a tree. Every collection of two edges forms a minimum spanning tree in this graph, yet if (for example) you choose $\{x,y\},\{y,z\}$, then you miss the shortest path $\{x,z\}$.

In conclusion, if you put all shortest paths together, you don't necessarily get a tree.

Practical example to show the difference>

Suppose you arrive by train in a town and want to get to your hotel.

Option 1: Get a taxi: The taxi will take the shortest path to you hotel form the station. If the driver should follow a path along the shortest path tree centred on the station.

Option 2: Take a bus. The bus company wants to cater for may people, not just you. The ideal path would take in all the key points in the town. So it will follow (*) a path along the minimum spanning tree. That's why the bus is slower, but as costs are shared it is cheaper.

(*) Actually people would complain if the minimum spanning tree was used (the bus journey would be too long). So in practice it would be a mixed solution and would use an Alpha-Tree (half way between a minimum spanning tree and a shortest path tree).


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.

If I have understood your question correctly, the answer would be no.

Here is a counterexample:
Let C be the complexity class of finite state automata. The halting problem for C is thus computable by a turing machine, hence the problems that C^O can solve is a subset of the problems that a turing machine can solve.
Let B be the complexity class of turing machines. The halting problem for B is not computable by a turing machine, hence B^O contains problems that C^O does not, and hence B^O and C^O are not equivalent.

As it turns out I have misunderstood your question.

If you meant for both oracles to be able to solve the halting problem for any turing machine, the answer is that they are equal.
This is because an oracle for the turing machine can solve any problem a turing machine can solve, as it the oracle can just compute whether a turing machine would return a certain result for a certain input.


Can we use domains other than the naturals in computability theory? I wonder why people assume the domain of a computable function is $\mathbb N$? For example, in Wikipedia.

Can its domain be any countable set rather than $\mathbb N$?

Can its domain be an uncountably infinite set?

The domain is finite strings of symbols from some alphabet – i.e., initial contents of Turing machine tapes. The natural numbers can be easily coded as finite strings: either in unary using length or in some higher base using symbols from the tape alphabet as digits. Other countable sets (e.g., integers and rationals) can be coded if, and only if, there is a computable bijection between that set and the naturals. However, you can't let your domain be any countable set: for example, if you want your domain to be the set of Turing machines that halt on every input, you couldn't even tell which Turing machine a given finite string codes.

There's no way to use an uncountable domain because the initial contents of the tape must be finite and there are only countably many finite strings over any finite alphabet.

Forgive me if  get this wrong because I am here to try and learn as much as possible.

But it seems to me that, regardless of the base used there cannot be an infinte number of characters. As each character is used once (not sure about this) the computer or maybe its to do with chaos theory or the laws of probability or physics or something, but as each character is used once it can not be used again on its own, so each character has to be combined with another to form a string. So if you have 1 million characters and you now using strings of 2 characters you have 2 million possible strings to use, than once they are all used you need to use strings of 3 characters, so you have 3 million possible strings to use (I think but I'm not sure; my basic maths is rubbish) and so on till you have 1 000 000 000 000 possible strings. It would not take a computer a day to go through all possible combinations if it were set up to do just that. But if it is just going through the string combinations as normal it probably uses the same string multiple times so it would probably take years.

Please correct me if I am wrong, I am not great with maths (please see profile) please explain in a conceptual mannor.

This whole concept of a domain for a computable function is intriguing to me, What is the Function of N?


Static scope and dynamic scope I am perpetually confused when it comes to static scoping and dynamic scoping and their differences and Wikipedia isn't of any help, so here's my question:

Given the following pseudo code in a hypothetical programming environment, what are the outputs under the following conditions?

call by need using static scope
call by name using dynamic scope

global int n = 100, m = 5;
void fun(x){
    int n = 10;
    print(x + 10);
    n = 200;
    m = 20;
    print(x);
}
main(){
    fun(n + m);
}

Additionally, what would be two environments where I can run this code to check the output with the conditions? C uses lexical scope, but it does not support call by need while Bash supports dynamic scope, I guess!

Here is the simulation by hand.

call by need using static scope

The function receives as x parameter the thunk [n+m] bound to the
globals. Then local n gets 10. The print statement requires evaluation
of the thunk, which becomes 100+5, i.e. 105. It prints 105+10,
i.e. 115. Local n and global m are changed, but this cannot affect x for two
reasons: the thunk does not depend on the local variable n (because
statically bound to the global variables n and m), and it is already evaluated to 105
anyway, which is printed by the second  print.

Note that, if the first print statement were removed, then x would be evaluated after changing the global variable m, which would then be 20 instead of 5, and the answer for the remaining print statement (formerly the second one) would be 120.

result: 115 105
call by name using dynamic scope

The function receives as x parameter the unbound expression [n+m]. Then
local n gets 10. Then x gets evaluated, with local n=10  and global m=5,
i.e. 15, and added 10 to print 25. Then local n=200 and global m=20. The
parameter x is reevaluated as 200+20, i.e. 220, which gets printed.

result: 25 220

How to test it? One would have to check various implementations of
programming languages. I do not remember off hand.

Call by need is usually found in functional languages, which normally
do not have assignment. But some still allow it. So I would look for
that regarding the first case. I think CAML may provide it.

Call by name is fairly rare, and rather weird in a dynamic scope
context. I do not know of any language that will offer that
combination. The best is to use a dynamic binding langage and simulate
the example by explicitly replacing the call by name argument by a
parameterless function that has the parameter as body.

In the example, you would call in main(): fun(lambda().n+m), and
in the body of the function fun you would replace x by the call x().

resault of static  and dynamic scope:

step 1 : print 115

then n=200 , m=20 it is not affect on x so :

step 2 : print 105


Finding the Largest "Ordered" Difference in Elements of an Array Suppose we are given an array of positive integers $P = [p_1, p_2, \dots, p_N]$ where each $p_i$ represents the price of a product on a different day $i = 1 \dots N$.

I would like to design an algorithm to find the maximum profit that you can given this array of prices. Profit is made by buying at a given date $i$ and selling at a later date $j$ so that $i \leq j$.

One easy solution is the following "exhaustive algorithm":

profit = 0
for i = 1 to N-1
  for j = i+1 to N
    if P(j) - P(i) > profit
      profit = P(j) - P(i)

The issue with this however is that it takes time $\Omega(N^2)$.

Can anyone think of something faster?

The first observation is that the strategy of buying at the lowest price or selling at the highest price does not always maximize the profit. As you also note, the simple brute-force method works by trying every possible pair of buy and sell dates in which the buy date precedes the sell date. A period of $n$ days has $n \choose 2$ dates and $n \choose 2$ is $\Theta(n^2)$.

To achieve $o(n^2)$ running time, a simple transformation is applied to the input array. Instead of looking at the daily prices given, we will instead work with the daily change in price, where change on day $i$ is the difference between the prices after day $i-1$ and after day $i$. With a transformed input array like this, we now want to find the nonempty, contiguous subarray whose values have the largest sum. This contiguous subarray is called the maximum subarray.

For a detailed divide-and-conquer algorithm running in $\Theta(n \log n)$ time, see for example Chapter 4 of the Cormen et al. book, 3rd edition, page 68-74. The Wikipedia page also mentions Kadane's linear time algorithm and gives pseudocode.

You can do it in O(n) time by using Kadane's algorithm. First transform the array A[1..n] to B[1..n] such that B[i] = Sum(A[1] to A[i]). and find the longest common subsequence in the new array


Finding all solutions to subset sum for integers with bounded weights Suppose I have the set of weights $W = \{w_1,w_2,\ldots,w_{50}\}$ where each $1 \le w_i \le 60$ is an integer.  I am interested in determining all subsets (not just one, and not just the number of them) of $W$ with a fixed sum $s$.  I realize this is obviously NP-hard, but are there some efficient ways (e.g. dynamic programming) to obtain this result for these relatively nice conditions (e.g. only 50 items, weights integer and bounded)?

The dynamic programming algorithm can be adapted to give all solutions. You create a table $A$. The cell $A_{k,w}$ contains enough information to enumerate all subsets of $\{w_1,\ldots,w_k\}$ summing to $w$. When $k = 0$, this is trivial. Given $A_{k-1,\cdot}$, $A_{k,w}$ points at the two cells $A_{k-1,w},A_{k-1,w-w_k}$ (if they exist). The second pointer is also annotated with $w_k$. If you look at $A_{50,W}$, you can reconstruct all subsets by considering all paths going all the way to $A_{0,0}$. This can be done using a simple recursive procedure.

Look at the coin change problem.  Solutions are known which will give all results.  If you have a problem with it, I can provide some code.

See http://www.algorithmist.com/index.php/Coin_Change for example


Cardinality of the set of algorithms Someone in a discussion brought up that (he reckons) there can be at least continuum number of strategies to approach a specific problem. The specific problem was trading strategies (not algorithms but strategies) but I think thats beside the point for my question.

This got me thinking about the cardinality of the set of algorithms. I have been searching around a bit but have come up with nothing. I've been thinking that, since turing machines operate with a finite set of alphabet and the tape has to be indexable thus countable, it's impossible to have uncountable number of algorithms. My set theory is admittedly rusty so I am not certain at all my reasoning is valid and I probably wouldn't be able to prove it, but it's an interesting thought.

What is the cardinality of the set of algorithms?

An algorithm is informally described as a finite sequence of written instructions for accomplishing some task. More formally, they're identified as Turing machines, though you could equally well describe them as computer programs.

The precise formalism you use doesn't much matter but the fundamental point is that each algorithm can be written down as a finite sequence of characters, where the characters are chosen from some finite set, e.g., roman letters, ASCII or zeroes and ones. For simplicity, let's assume zeroes and ones. Any sequence of zeroes and ones is just a natural number written in binary. That means there are at most a countable infinity of algorithms, since every algorithm can be represented as a natural number.

For full credit, you should be worried that some natural numbers might not code valid programs, so there might be fewer algorithms than natural numbers. (For bonus credit, you might also be wondering if it's possible that two different natural numbers represent the same algorithm.) However, print 1, print 2, print 3 and so on are all algorithms and all different, so there are at least countably infinitely many algorithms.

So we conclude that the set of algorithms is countably infinite.

since turing machines operate with a finite set of alphabet and the tape has to be indexable thus countable

Given a particular size, there are finitely many Turing machines, and there are countably many sizes. A countable set of numbers, as long which are finite, is countable. The size of the alphabet is a factor in the number of Turing machines, but the size of the tape isn't. If the alphabet were allowed to have countably many characters, then there would be uncountably many machines (each real number could be encoded as a sequence of symbols).

If "algorithm" you merely mean a correspondence between input and output, and not a Turing machine or otherwise something that is the normal sense of "computation", then clearly if there a countably many different inputs, then there are uncountably many algorithms: for each real number, we could define an "algorithm" that takes a natural number as input, and outputs that decimal place. For instance, giving the input "3" to the $\sqrt{.5}$ algorithm would give the output of "7". (Note that while it is possible to design a Turing machine that gives the nth digit of $\sqrt{.5}$, it is not possible to do so for all real numbers; only countably many real numbers are computable).


Longest Repeated (Scattered) Subsequence in a String Informal Problem Statement:

Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right yields the same result as reading only the blue letters.

In the example we could colour them like this: $A\color{blue}{C}\color{red}{CAB}B\color{blue}{AB}$

Therefore, we say $CAB$ is a repeated subsequence of $ACCABBAB$. It is also a longest repeated subsequence (which is easy to check).

Can we compute longest repeated subsequences efficiently?

Formal Question:

Is it NP-hard to decide for a string and some $k$, whether a repeated subsequence of length $k$ exists in the string?

If so: Which problem can be reduced to this problem?
If not: What is an efficient algorithm? (obviously, this algorithm can then be used to compute a longest repeated subsequence)

Bonus Question:

Will their always be a repeated subsequence of length $n/2 - o(n)$ if the size of the alphabet is bounded by a constant?

(This is known to be true for binary alphabets.)

Edit 2: The negative answer to the Bonus Question is already known for alphabets of size at least $5$. In fact for alphabets of size $Σ$, there are strings with longest repeated subsequences of a length of merely $O(n · Σ^{-1/2})$. Random strings suffice to show this. The result already existed, but I overlooked it.

Edit:
Note:

Some people mean "substring" when they say "subsequence". I don't. This is not the problem of finding a substrings twice.

The special case of $k = n/2$ is the same problem as this CST.SE question How hard is unshuffling a string? asks.
Buss and Soltys proved NP-completeness of this problem [1] by reducing 3-Partition problem to this problem.

[1]: Buss, Sam, and Michael Soltys. "Unshuffling a square is NP-hard." Journal of Computer and System Sciences 80.4 (2014): 766-776.

This can be solved in polynomial time by constructing a graph $G$ where each node represents a point $(i,j)$ in some repeated subsequence of $S$ such that $S[i]=S[j]$. Edge between nodes $u$ and $v$ means that $u$ can be continued by $v$ to form a repeated subsequence of length 2.

1. Find the nodes. This can be done in $O(n^2)$ time by building a sorted list of indices for each character $c$, and then enumerating the unique pairs. There are no more than $m=n^2$ nodes.

2. Find the edges. It takes $O(1)$ time to check if node $u$ can be continued by node $v$, so by considering all pairs $(u,v)$ this step takes $O(m^2)$ time.

3. Note that the longest path in $G$ may not be a valid repeated subsequence. Consider paths $ab$ and $bc$. If there exists an edge $ac$ then $abc$ is a valid repeated subsequence of length 3. Therefore it takes $O(m^4)$ time to find all repeated subsequences of length 3. In the general case it takes linear time to check whether two valid paths of length $n$ can be combined into a valid path of length $n+1$.

4. Iterate step 3 until no longer paths can be found.


Decoding bit streams using Hamming Code I want to decode the following bit stream using Hamming code:
01110110

Once using even parity and once odd parity. I will show my work. For even parity:

$p_{1} \; p_{2} \; 0 \; p_{3} \; 1 \; 1 \; 1 \; p_{4} \; 0 \; 1 \; \; 1 \; 0$

Now, we check:

$p_{1}: p_{1}  \; 0 \; 1 \; 1 \; 0 \; 1 $, since there is an odd number of 1's, $p_{1}=1$

$p_{2}: p_{2}  \; 0 \; 1 \; 1 \; 1 \; 1 $, since there is an even number of 1's, $p_{2}=0$

$p_{4}: p_{3}  \; 1 \; 1 \; 1 \;0 $, since there is an odd number of 1's, $p_{3}=1$

$p_{8}: p_{4}  \; 0 \; 1 \; 1 \;0 $, since there is an even number of 1's, $p_{4}=0$

so the following hamming code is
$$1 \; 0 \; 0 \; 1\; 1 \; 1 \; 1 \; 0 \; 0 \; 1 \; \; 1 \; 0$$

As for odd, the parities will just be the opposite and the code will be

$$0\; 1 \; 0 \; 0 \; 1 \; 1 \; 1 \; 1 \; 0 \; 1 \; \; 1 \; 0$$

Can someone tell me if my work is correct? Because I am a bit confused and would appreciate the help.

There are many equivalent Hamming codes depending on the ordering of parity and data bits.
Assuming that:

You are using the specific bit ordering described here: https://en.wikipedia.org/wiki/Hamming_code#General_algorithm
By "even parity" you mean that the parity bits are computed as the sum (modulo 2) of the corresponding groups of bits
By "odd parity" you mean that the parity bits are computed as 1 minus the sum (modulo 2) of the corresponding groups of bits,

then yes, your simulation of the algorithm is correct.

I'm not really understanding some parts of your question, The Hamming algorithm is used to count the number of 1 bits of a binary number. The idea is to create a mask = 1 and check for every of the 32 bits if (mask & n) == 1, then shift the mask to the left by one. If true is returned, it means that the binary representation of n has a 1 at that position, so increase the bit number.
Here is an example:

int hamming(int n) {
        int bits = 0, mask = 1;
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) bits++;
            mask <<= 1; //shift left by one
        }
        return bits;
    }


How do I interpret this question? For any language $L \subset \Sigma^*$, define $S(L)$ to be $$\{x\in L \mid \neg \exists y \in L: \exists z \in \Sigma^*: (z \ne \epsilon) \land (x=yz)  \}$$

Show that $S(L) = S(S(L))$

I'm confused about the question here. The way we define $S(L)$ takes elements from $L$ $(x \mid x \in L)$, but $x=yz$ and $y \notin L$. How is it possible for x to concatenate an element from $\bar{L}$ (complement of $L$ since $y \notin L$) and still be an element of $L$?

The formula means "it is not true that there exists $y \in L$ and $z \in \Sigma^*$ such that $z \ne \epsilon$ and $x=yz$."  That is, there is no way of writing $x=yz$ such that $y\in L$ and $z\neq\epsilon$.

$S(L)$ = $$\{ x\in L: \forall y \in L. \forall z \in \Sigma*. (z \ne \epsilon) \land (x \ne yz)   \}$$

$S(L)$ is all strings $x \in L$ which don't have non-trivial prefixes $y \in L$


Example of an algorithm where a low-order term dominates the runtime for any practical input? Big-O notation hides constant factors, so some $O(n)$ algorithms exist that are infeasible for any reasonable input size because the coefficient on the $n$ term is so huge.

Are there any known algorithms whose runtime is $O(f(n))$ but with some low-order $o(f(n))$ term that is so huge that for reasonable input sizes it completely dominates the runtime?  I'd like to use an algorithm like this an an example in an algorithms course, as it gives a good reason why big-O notation isn't everthing.

Thanks!

Cryptography is an example, if a degenerate one. For example, breaking AES encryption is $O(1)$ — all you have to do is find the right key among a finite number, $2^{128}$ or $2^{192}$ or $2^{256}$ depending on the key size (assume that enough of the plaintext is known to determine the key unambiguously). However even $2^{128}$ operations would take all of the computers today (a billion or thereabouts, each doing about a billion operations per sceond) more than the lifetime of the universe (about a billion billion seconds).

A slightly different way to illustrate why big-O isn't everything is to remark that we sometimes use a different algorithm for small input sizes. For example, take quicksort. With the right choice of pivot (which is a tricky business!), it's $O(n \lg n)$. Quicksort operates by divide-and-conquer: every instance involves doing a lot of sorting of small arrays. For small arrays, quadratic methods such as insertion sort perform better. So for best performance, a quicksort of a large array involves a lot of runs of insertion sort for small sizes.

This is kind of a joke but it has a serious side...

Quicksort. It's useful in practice because the $O(n\log n)$ terms dominate the $O(n^2)$ worst case that results from consistently choosing terrible pivots.


how did they get this answer for the words that don't have bba and abb? I am looking at the answer in solution manual which asked , all the words that don't have both substring bba and abb.

and the answer was a*(baa*)*b+b*(a*ab)*a*

and I'm like wait a minute is that right ? but that can't make abb, which is in the language. So it's gotta wrong.

so I came up with my own , would this be all the words that don't have both substring bba and abb ?

(b+^)(ab+a)*+b*

^ is an empty string by the way

The textbook's answer does appear to be incorrect, as you note it does not generate $abb$ (and just to rule out an alternative interpretation of the exercise - "all strings that include neither $abb$ nor $bba$ - it does generate $bba$).

However your answer is also incorrect unfortunately - it doesn't generate $bba$.

There are a couple of reasonably sensible ways to get a correct answer (of course there's always many many techniques, and different people prefer different ones).

The first is the "intuition" approach, break the problem into the two parts, "the strings that don't have $bba$" and "the strings that don't have $abb$", then combine. With this method you have to then think about how such strings would look, and convince yourself that you haven't missed any cases.

The very formal method is to construct the expression from smaller, verifiable building blocks. In this case, we can easily construct a DFA for the strings that do contain $abb$ and one for the strings that contain $bba$, then we can use the intersection construction to get a DFA for the intersection of the two languages, take the complement DFA, then convert this to a regular expression.

What they seem to have done, and messed up or made a typo in one part, is the formal-but-not-quite-as-silly-as-option-2 method, where we make the two small DFAs, take their complements separately, convert each to a regular expression, then combine. I'll do the half that they seem to have gotten wrong (the bit that allows $abb$ but not $bba$, which is the first half of their expression).

The initial DFA is:

Taking the complement we get:

This second DFA recognises all the strings that don't contain $bba$. Now we convert this to a regular expression using the normal state elimination algorithm. If you haven't seen this yet, it will appear shortly in whatever course you're studying, or you can look over this explanation, but for the moment (and for the sake of keeping this answer on track!) hopefully it's acceptable that there is an algorithm for doing this conversion. In principle this algorithm can result in slightly different regular expressions depending on the order you eliminate the states, so if you have a go at it, you may not end up with quite the same regular expression (if you try one particular order, you get a real mess).

After all that we get the regular expression:
$$
(a+ba)^{\ast}b^{\ast}
$$

If we then proceed and do the DFA for strings containing $abb$, take its complement and derive the regular expression, we get (picking the right elimination ordering) the same as their second half, $b^{\ast}(a^{\ast}ab)^{\ast}a^{\ast}$, and combine them and get the final answer:
$$
(a+ba)^{\ast}b^{\ast}+b^{\ast}(a^{\ast}ab)^{\ast}a^{\ast}
$$

It is a very simple RE.
{a*(ba+a)*(b+^) + (b *) }
Where ^ is null.
JazakAllah :)


What would show a human mind is/is not reducible to a Turing machine? In computer science it is often assumed that a human mind can be reduced to a Turing machine.  This is the assumption that underlies the field of artificial intelligence.

However, it is an assumption, one that has neither been proven or disproven.

Is there any kind of test within our current capabilities where we can prove/disprove this assumption?

If not, is there any evidence that would suggest one way or another?

Here is a similar question I asked awhile back on theoretical computer science:

https://cstheory.stackexchange.com/questions/3170/human-intelligence-and-algorithms

To answer your question:

  Is there any kind of test within our current capabilities where we can prove/disprove this assumption?

The Turing test was conceived as a way to test a particular special case of this assumption: it gives us a way to test whether a particular AI system is successful at behaving indistinguishably from a human.  Thus, this would give a plausible way to prove the assumption -- if we could come up with an AI system that is good enough to pass the Turing test.  Unfortunately, that's something we haven't been able to do, yet.

If we identify a certain task that is non-computable, but the human mind perform, then this proves the human mind is not a Turing machine.

As an example, Turing machines cannot make the distinction between proof and truth.  Yet, we humans can, as with the statement "this statement is unprovable," which is true but unprovable.


How to write an OR constraint in MILP? I want to write a constraint with ORs in a MILP. In particular, the following:

$$x \ge c \lor x \le -c \lor x=0,$$

where $c$ is just a real number.

Can anyone give me some hints?

Tough. You are leaving linear programming.

Solve the problem without these equations and with no restriction for the sign of x. If by coincidence x matches one of the conditions, you are done. Otherwise you will need to solve the problem with one of these equations added.

Calculate how much changing x by eps changes the optimal solution. With that guess how much adding x=0, x>=c, or x<=-c would affect the optimal solution. Add the equation that seems to cause the least damage and solve with an optimal goal function G. Then try adding each of the other equations, with an additional restriction goal >= G.

You could have just tried adding each equation in turn and solving, but this way you might find quicker that one condition can’t lead to an optimal solution. For example if c=100 and your optimal solution was x=80, you can add x>=100, optimise , and you can likely show easy that x=0 or x<= -100 will lead to a worse outcome.


Algorithm to find smallest difference in array We want an algorithm that, given an array of length $n$ of integers, find the minimum difference between two integers in the array.

One such algorithm is to sort the array and check adjacent pairs of numbers. This takes time $O(n\log n)$.

Is there a faster way, e.g., an $O(n)$ algorithm?

This depends on your model of computation. If you only allow arithmetic and comparisons (the algebraic decision tree model) then there is an $\Omega(n\log n)$ lower bound for element distinctness, the problem of deciding whether all elements are distinct. Your problem is of course even harder, so the same lower bound applies.

(There is some fine print: the lower bound only holds if the degree of the polynomials being compared is bounded. If all you're doing is comparing various differences $x_i - x_j$, then you're good to go. The algebraic decision tree model also allows you to compare more general polynomials in the inputs, as long as they have bounded degree.)

There are other models which might perform better — for example, in some models you can sort integers in $o(n\log n)$. But I imagine you don't want to allow the sort of trickery used in such algorithms.

If integers in the array has a limited number of digits you can sort an array with radix sort algorithm, that is O(kN) and than check the adjacent pairs of numbers (O(N))? Resulting complexity will be O((k+1)N), linear.


How are statistics being applied in computer science to evaluate accuracy in research claims? I have noticed in my short academic life that many published papers in our area sometimes do not have much rigor regarding statistics. This is not just an assumption; I have heard professors say the same.

For example, in CS disciplines I see papers being published claiming that methodology X has been observed to be effective and this is proved by ANOVA and ANCOVA, however I see no references for other researchers evaluating that the necessary constraints have been observed. It somewhat feels like as soon as some 'complex function and name' appears, then that shows the researcher is using some highly credible method and approach that 'he must know what is he doing and it is fine if he does not describe the constraints', say, for that given distribution or approach, so that the community can evaluate it.

Sometimes, there are excuses for justifying the hypothesis with such a small sample size.

My question here is thusly posed as a student of CS disciplines as an aspirant to learn more about statistics: How do computer scientists approaches statistics?

This question might seems like I am asking what I have already explained, but that is my opinion. I might be wrong, or I might be focusing on a group of practitioners whereas other groups of CS researchers might be doing something else that follows better practices with respect to statistics rigor.

So specifically, what I want is "Our area is or is not into statistics because of the given facts (papers example, books, or another discussion article about this are fine)". @Patrick answer is closer to this.

As a graduate student in computer science, who has exposure to research in fields other than computer science, and whose research group works in an area of computer science where statistics can be fruitfully applied, I can offer my experience; your mileage may vary.

In general, even the most well-meaning scientific research can fail to rigorously apply statistical analysis to results, and it is my experience that this does not always preclude papers including such poorly-analyzed results from being accepted for publication. The area in which my group operates is mainly in distributed computing and high-performance computer architecture. Often, research involves experimental designs the performance of which cannot easily be understood analytically in the required detail. As such, empirical results are often used as evidence for claims.

Clearly, experiments should be design - and results analyzed - in such a way as to provide some confidence that the results are statistically significant. Most of the time, this is not done, even in some of the most important venues. When statistical analysis is applied, it is almost never rigorous in any meaningful sense; the most one typically sees (and one is glad to see it!) is that an experiment was repeated n times, for some arbitrarily-chosen n, where typically $1 < n < 5$. The selection of error bars (if any are indicated) seems to be mainly a matter of personal preference or taste.

In summary, no, it's not just you; and it's not just software engineering. In general, based on my experience, several areas of computing research seem to err on the side of not doing enough. Indeed, it might be even be detrimental to the viability of a submitted paper to dwell on statistical considerations. That's not to say that I find the situation satisfactory; far from it. But these are my impressions. For instance, you may take a look at section 5 of this paper, which was presented at Supercomputing 2011, one of the most high-profile conferences in the area of high-performance computing. Specifically, take a look at some of the discussion of results in section 5, and see whether you arrive at the same conclusions that I do about the rigor of statistical analysis of experimental results.

More generally, this shortcoming may be symptomatic of a condition in some areas of computing to publish more papers rather than fewer, to target conferences rather than journals, and to emphasize incremental progress rather than significant and fundamental improvements in understanding. You might consult this article, which provides valuable insight along these lines.

My question here is thusly posed as a student of CS disciplines as an aspirant to learn more about statistics: How do computer scientists approaches statistics?

there are several questions above & some not the same as the title question & in some ways this question has an underlying faulty premise/misconception about some lack of connection between statistics and CS. the general question is about the interface of computer science and statistics.

there is a vast, verging on intense overlap in some areas and it is an increasing trend with the new strongly emerging field of big data. at some schools (eg even elite "Ivy League" schools) the CS degree is tightly coupled with the mathematics and statistics departments and some have a joint major. there is a very strong interconnection in the CS/statistical field of Machine Learning. also the relatively new field of bioinformatics has very strong CS+statistical grounding.

there is an entire field Computational statistics focused on the interface!

  Computational statistics, or statistical computing, is the interface between statistics and computer science. It is the area of computational science (or scientific computing) specific to the mathematical science of statistics. This area is also developing rapidly, leading to calls that a broader concept of computing should be taught as part of general statistical education.[1]

yes, agreed, as pointed out in the question, there are many CS papers that dont use statistics, including situations (such as evaluating empirical experiments) where it might be even highly applicable & relevant, but exactly the same can be said of many other scientific fields, eg mathematics, and even more applied fields like physics.

there are many ways to use/apply statistics, some less rigorous than others, and not all contexts call for full application of the very advanced aspects of statistics. for example just running multiple experiments and plotting error bars for statistical deviation (or even merely averages!) is a basic use of statistics. more rigorous uses include hypothesis testing, but there is a general observation in the field that many scientific papers do not do rigorous hypothesis testing even where it might be applicable.

also, this question is tagged with software-engineering. this was my major, and a statistics class was required to pass to complete this degree at my school & to get an engineering-certified major (eg ABET), this is likely the case at many other universities. if one wants more applied and rigorous CS type principles such as applications of statistics, one can go the "software-engineering" route in education.

Combining computer science, statistics creates machines that can learn,
Prof. John Lafferty teaches computers to extract knowledge from data
combined statistics and computer science major, U of Illinois
Dept math, CS, statistics, Purdue

  Computer Science and Statistics, with roots deep in the traditions of mathematics, are exciting, rapidly expanding fields which provide the basis for many contemporary applications which affect us daily in such areas as commerce, industry, medicine, and environmental issues.

what statistics should a computer scientist know stackoverflow


Sequence alignment with one to many characters I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with one character beside allowing character substitution, deletion or insertion.

For example, if I have a set of similarly sounding characters, like

monir, monier, muneer, munir, mounir, mouneer

The alignment algorithm will produce the following output

m u n i - r
| | | |   |
m o n e e r

Is there a way to adapt these algorithms (or an alternative algorithm) to consider aligning/substituting character with more than one character in order to output something like

m u n i  r
| | | |  |
m o n ee r

Please note that, I'm using the standard java implementation for these algorithms and I don't have a predefined list of similarly sounding characters, so I'm trying to aligning the similar words together in order to extract these alignments.

If I understood your problem correctly, a trie data structure may help you. The main challenge would be after the first mismatch, match the upcomming characters. I'm not sure how I would hack it, but it may not be that hard.

Hope it helps. Regards


Why does it seem as if I can apply the Pumping lemma to a language that is regular? We learn about the Pumping Lemma at the class and I tried to make few examples to understand it...

There I make this example:
Let's say: $L=\{w\in L|w=(0+1)^*1\}$ - i.e. - L is the language of all the words that finish with $1$. (The language is regular of course).

Now, I can take the word: $w=0^{n-1} 1$. $w\in L$ and $|w|\ge n$.
I can take: $u=0^{n-1},v=1,z=\varepsilon$.
$|uv|\le n$ and $|v|>0$, but:
$uv^0z\notin L$ because $uv^0z$ ends with $0$...

What I miss here?
I'd like to understand more where is my mistake...

The pumping lemma says that, for every regular language there exists some pumping length $p$* such that blah blah blah.

You made two mistakes. First, you tried to choose $p$ based on a specific word, rather than based on the language as a whole. Second, you chose the wrong value of $p$. In particular, for the language you've given, $p=1$ has the property required of the pumping lemma: for every word $w$ in that language, you can write $w=\epsilon y z$ with $|y|=1$, and you'll find that $\epsilon y^n z$ is in the language for all $n\geq 0$.

En tu caso esta algo mal planteado
Para verificar con el lema de bombeo se sigue los siguientes pasos:
k es un conjunto de estados de A
Primero tiene q cumplir L=t(A)y w € A

A es un AFD con |k|=n y |w| >= n

a) w=uvz

b)|uv|=n

c)v ≠¶ (¶ es el vacío)

d) u(v^i)z i>=0 u(v^i )z  € T(A)

con eso el AFD es
A={{q0,q1,q2},{0,1},d,q1,q3}
Con cadena w=0100111
u(v^i )z   i >=0  y   |uv|<=n
u=0      v=1   z=00111        n=3
al incrementar i aun w € T(A)

espero entiendas :)


Maximum amount of memory that can be allocated to a process DISCLAIMER: The following scenario was taken from an assignment I got in a OS course I'm taking, and it arose a lot of question marks in my head. However non of the questions asked by myself here reflects a question that I'm supposed to answer (alone) as part of the assignment. What I mean is: I'm not asking you to do my HW I'm just asking for help to better understand the concepts.

Given the following scenario:
A system using paging for memory management.
Physical memory size is 128MB
There are 4K frames in physical memory and each frame has 8K words.
Page table of a single process has at most 1024 entries
Virtual memory is not used.

I know from the above that a WORD in such a system must be 4 Bytes long.

Since virtual memory is not being used, I think it is possible that a process can get all the 4K frames if it requests them (assuming obviously that they're available for it when it's loaded) thus it can be allocated all of the available physical memory (128MB). However if Virtual Memory is used then the maximum amount it can get is 32MB because of the structure of the page table (1K entries, each entry has 8K words and each word = 4 Bytes). Is my conclusion correct or not? I reached it while reading Silberschatz, Galvin & Gane book (Operating System Concepts).

The main point I think is here the usage of paging without implementation of virtual memory(VM) techniques.

Nowadays it's rare, but once upon a time when the concept of VM was a dream paging was used for a different purpose. At that time the memory allocated to a process needed to be contiguous which usually lead to fragmentation (external) and hence bad utilization of memory. Then the concept of paging brought a revolution. Memory can be allocated to a process non-contiguously. The process memory space is divided into pages of same size. The Main Memory is also divided into same size frames and page size is equal to frame size. Page table of a process keeps track of the addresses of the frames. To be precise if the page table has $k$ entries it can have at most $k$ frames. For each frame, page table stores the starting memory address of that frame. Unlike the concept of VM all the frames need to be stored in main memory. Note that this might lead to another type of fragmentation (internal) as a process memory space size might not be multiplicative of page size. But, this is not that severe like the external one.

So, here in your question I think they try to mean this kind of scenario, paging without VM. Thus here also it is possible to limit the size of a process by using the page table in the similar manner you mentioned in your question for the case where we use VM.

But, my main concern is to convey the idea that we can indeed use paging without VM.


What does "prime" mean in this context? In a lecture video the instructor introduced the quadratic probing method for hash tables. The formula he gave was the following:

$h(k,i) = (h'(k) + c_1 + c_2i^2)$ $\% M$

where $h'$ was h "prime". So, what I am supposed to conclude for $h'(k)$ to be? Is it any different from the value I get by computing $h(k)$

$h'(k)$ is the value returned by the original unmodified hash function when applied to the element $k$. If the $h(k)$ slot is not free then $h(k,i)$ for $i=0,1,2,\dots$ gives a sequence of modified hash values which can be tried in turn until a free slot is found.

h'(k) is mod(k,M)
it is usually represented as h(k)


Terminology for reducing runtime of an algorithm by using a property of the problem? It is a very standard situation that we have a class of problems $P$, and a subclass $\tilde P\subset P$ which has a certain restricted property.

For example, $P$ could be the problem of searching through an arbitrary list of people for someone with height $1.8$ meters, while $\tilde P$ could be the same problem, except that it is known that the list is ordered by height.

Searching through an ordered list is far more efficient than through an arbitrary list.

My question is: what would be the term for an algorithm using/relying on a certain particular structure of the problem in order to run more efficiently than would be needed in the general case?

Or alternatively, what is the term for "omitting calculations" that are necessary to do in the general case but that can be omitted in the restricted problem case?

I'd call it "special-casing".

There are variations. Variation 1 would be: You examine the input, and if the input has a special form, then you use an algorithm that cannot handle every input, but only input like the one you detected.

Variation 2: You run an algorithm that will run fast, but will not be successful for every possible input. You may detect while you run the algorithm or after you ran it that it failed, and use a more general algorithm.

Variation 3: You run a general algorithm, knowing that it will be fast in some cases, and hope your case is a fast one.

The term you are looking for is reduction, which is a central aspect of complexity theory. In particular, what you want are so called efficient (or poly-time) Turing reductions (also called Cook reductions).

We say a problem $A$ is Turing reducible to a problem $B$ if there is a TM which solves $A$ if provided with an oracle for $B$. (An oracle is a device which answers a query in $B$ with runtime cost 1.) The reduction is efficient if the TM can perform it in polynomial time in the length of its input.

Note the above applies not only to decision but also to search problems (as you are probably more interested in the latter.)

For specific problems, you may want to set a stricter asymptotic bound (than simply polynomial) on the reduction depending on the asymptotic lower bound of problem $B$. For example, a reduction of a problem $A$ to sorting should take not only polynomial but actually $o(n \log n)$ time; otherwise, the reduction is meaningless since it is powerful enough to solve $B$ (i.e., sorting) directly.


Algorithm Request: "Shortest non-existing substring over given alphabet" I'm looking for an (efficient) algorithm to solve the following problem:

  Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not contained in $S$.

Try as I might, I can't seem to map this problem to any of the standard CS string problems.

Here is the clean presentation (after going in circles around it).

First you consider all substrings of S that are in M*. From that you
build a trie, which may be understood as a tree structured FA that
recognizes these substrings. You build it so that you complete first the transitions of nodes that are closest to the root. As soon as you have a node from which
there is no arc for a given character in M, you have your answer which
is the string associated with that node concatenated with the missing
character.  Complexity is $O(n^2)$ where $n$ is the length of the
string S, because that is the maximum number of characters you may have to consider while building the trie.

Note regarding complexity: In the trie construction you have to
consider only the longest substring in $M^*$ starting at each position
in $S$, since shorter ones are automatically taken care of. Each state
thus created is an accepting state recognizing one substring. There
are at most $n$ substrings in $M^*$, each having at most $n$ characters. Each is considered in constant time.

Here is another approach that is conceptually simple (you are asking for "standard string problems").

Construct an NFA $A$ for $M^*$ (two states).
Construct an NFA $B$ for $\{ w \mid vwx = S; v,w,x \in \Sigma^* \}$ ($n+2$ states).
Compute $\overline{B}$.
Compute $\overline{B} \cap A$.
Find a shortest path from the starting state to a final state (breadth-first search). The traversed edges make up your solution.

Per se, the time for 3. might be huge (and then also 4.) since inverting NFA takes exponential time in the worst case.


Is it possible to prove Language L context-free? Give a question:
Language L= {a^n b^(n+m) a^m}, where both n and m are >=0. Is L context-free or not.

If the answer is yes, can I use the following PDA to prove it?

Since {a^n b^(n+m) a^m}={a^n b^n b^m a^m}, in the PDA, we first push n a's onto the stack. Then, we pop n a's from the stack by reading n b's. Next, we push m b's onto the stack, and we pop m b's from the stack by reading m a's. Finally, the strings will be accepted in q5.

Conversely, if the language is not context-free, should i use pumping lemma to prove it?

Thank you!

S → AB
A → aAb | ε
B → bBa | ε

This will be the Grammar for that language which follows the context free grammar rules, so the language generated will be CFL.

The language as you told is a union 2 languages (one for a^nb^n and other one is a^mb^m). As cfls are closed under union even your language is regular.
I did not understand your pda notation to validate it.


Minimising height of a 2-3-4 tree I'm wondering how a set  of keys  could  be  assigned  to  nodes  in a 2-3-4 tree  in  order  to  minimize  the  height of the tree?

Does the sequence of insertion matter with 2-3-4 trees?

The insertion order is relevant for the height of the tree.
Inserting (in this order) 1,2,3,4,5,6,7,8 gives a tree of height 3, while inserting these keys in the order 1,3,4,6,7,8,2,5 gives a tree of height 2.

In order to create a tree of minimal height, you can place the keys with ranks $\lceil \frac{n}4\rceil$, $\lceil \frac{n}2\rceil$, and $\lfloor \frac{3n}4\rfloor$ in the root, partition the remaining keys accordingly into the subtrees and apply the this recursively to each of the subtrees. Depending on the number of keys, you may have to shift a few keys around between leaves and their parents to make sure that all leaves are at the same level.

No, the sequence of insertion does not matter, as 2-3-4 trees are self-balancing data structures. A 2-3-4 tree of $N$ nodes has the following height:

$$ \frac{1}{2} \log (N + 1) \leq height \leq \log (N + 1) $$

That holds because as per Wikipedia:

  2–3–4 trees are B-trees of order 4 (Knuth 1998); like B-trees in general, they can search, insert and delete in O(log n) time. One property of a 2–3–4 tree is that all external nodes are at the same depth.


Show that $L$ and $\overline L$ cannot be both finite Let $L$ be any language on a nonempty alphabet. Show that $L$ and $\overline L$ cannot be both finite.

This is exercise 7 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz.
My attempt: $L$ is a subset of $\Sigma^*$, so it can be either finite or infinite. If $L$ is finite, then $\overline L$ is infinite. If $L$ is infinite, that is, $L = \Sigma^*$, then $\overline L = \Sigma^* - L = \Sigma^* - \Sigma^* = \emptyset$. Therefore, $L$ and $\overline L$ cannot be both finite.
Is it correct? I tried to write a direct proof. Thanks in advance.

If $L$ and $\overline{L}$ were both finite, then so would $\Sigma^* = L \cup \overline{L}$ be, which we know is false.
This is a qualitative statement. We can make it quantitative by considering densities. Let us say that a language is dense if for infinitely many $n$, it contains at least half the words of length $n$. It is easy to check that at least one of $L,\overline{L}$ is dense.

Your intuition is correct, however I wouldn't call it a "formal" proof. A really formal proof (but seriously, its too formal) can be stated like that:
If $L$ is infinite, we are done. Otherwise, $|L|<\infty$. In particular, there is some $w\in L$ such that $|w|\ge |w'|$ for every other $w'\in L$ - that is, $w$ is the longest in $L$. Denote $n:=|w|$, and notice that $\{w'\in \Sigma^*\mid |w'|>n\} \subseteq \Sigma^* \setminus L = \bar L$. Define $f:\Sigma^*\rightarrow \{w'\in \Sigma^*\mid |w'|>n\}$ by $f(w)=0^{n+1}w$ (instead of $0$, you can choose some other letter from $\Sigma$). Clearly, $f$ is injective, and therefore $|\Sigma^*|\le |\{w'\in \Sigma^*\mid |w'|>n\}|\le |\bar L|$. Since $\Sigma^*$ is infinite, then $\bar L$ is infinite as well, just as required.
Once again, this is a formal solution to the question. Your solution is still definitely valid, but note that $L$ being infinite does not automatically imply that $L=\Sigma^*$ (Thanks Dmitry for pointing this out in the comments).


How can I explain to my parents that I study programming languages? I am currently finishing my MSc in computer science. I am interested in programming languages, especially in type systems. I got interested in research in this field and next semester I will start a PhD on the subject.

Now here is the real question: how can I explain what I (want to) do to people with no previous knowledge in either computer science or related fields?

The title comes from the facts that I am not even able to explain what I do to my parents, friends and so on. Yeah, I can say "the whole point is to help software developers to write better software", but I do not think it is really useful: they are not aware of "programming", they have not clue of what it means. It feels like I am saying I am an auto mechanic to someone from the Middle Ages: they simply do not know what I am talking about, let alone how to improve it.

Does anyone have good analogies with real-world? Enlightening examples causing "a-ha" moments? Should I actually show a short and simple snippet of code to 60+ year-old with no computer science (nor academic) experience? If so, which language should I use? Did anyone here face similar issues?

If you have a few minutes, most people know how to add and multiply two three-digit numbers on paper. Ask them to do that, (or to admit that they could, if they had to) and ask them to acknowledge that they do this task methodically: if this number is greater than 9, then add a carry, and so forth. This description they just gave of what to do that is an example of an algorithm.

This is how I teach people the word algorithm, and in my experience this has been the best example. Then you can explain that one may imagine there are more complex tasks that computers must do, and that therefore there is a need for an unambiguous language to feed a computer these algorithms. So there has been a proliferation of programming languages because people express their thoughts differently, and you're researching ways to design these languages so that it is harder to make mistakes.

This is a very recognizable situation. Most people have no concept that the computers they use run programs, or that those programs are human-written source code, or that a computer could 'read' source code, or that computation, which they associate with arithmetic, is the only thing computers do (and data movement, and networking, maybe).

My research is in quantum computing, so when people ask me what I do, I don't attempt to explain that. Instead, I try to explain that quantum physics exists (they've usually heard of Schrödinger's cat, and things that are in two places at once), and that because of this strange physics, faster computation might be possible.

My goal is to leave the person feeling a little more knowledeable than they did going in, feeling excited about a world they didn't know existed, but with which you have now familiarized them. I find that that's much more valuable than explaining my particular research questions.

A while back I decided that a good analogy for programming which could be easily understood for people with little or no computer experience, would be writing knitting recipes.

A good knitting recipe contains several sizes in the same list of instructions, which give you loops and if-statements.  It is unreadable to those which do not knit, and if it contains errors you end up with misaligned patterns or an extra sleeve.   It is then up to you - as the recipe writer - to find out where the recipe was wrong based on the incorrect sweaters and fix it.

You can then use the example of "I am looking at how recipes are different for knitting, crocheting, Nålebinding and similar" and learning to X (where you need to find an analogy for what you actually do).


Is it possible to get Nth Fibonacci number in sublinear time? I was researching the topic of Fibonacci numbers and asymptotic complexity of generating them. Coming across a seemingly paradoxical conclusion, I've decided to check out if you agree with my explanation.

The naive algorithms runs in $O(n)$, if we ignore the cost of addition.
The Binet's formula or matrix exponentiation method should both theoretically run in $O(\lg(n))$ (since exponentiation of both matrices and real numbers takes $O(\lg(n))$ steps)

The problem arises when you analyze the size of Nth Fibonacci number by assuming that after first few members of the sequence, the ratio between two numbers is at least 1.5 (picked randomly, I assume it can be easily proved by induction).

We can then bound the number to be at least as big as: $c_1*(1.5)^n$.
Its logarithm gives us the number of digits the Nth Fibonacci number has ($c_2*n$).
Am I right to assume that you can't print out (or calculate) linear number of digits in sublinear time?

My explanation of this "paradox" is that I forgot to add multiplication costs in 2nd algorithm (Binet/matrix), making its complexity $n*\lg(n)$.
I've found out that naive algorithm (1st) runs better for very small inputs, and 2nd algorithm runs better for bigger ones (python3).

Is my explanation of complexity correct, and should the naive algorithm get better running time at even larger inputs ($n>10^9$ or such)?

I do not consider this to be a duplicate question, since it adresses the problem of arbitary values and arbitary integer aritmetic.

Let's assume that you could store such large Fibonacci numbers. In that case, the  length of $n^{th}$ Fibonacci number is $\lfloor n \log_{10}\phi+1\rfloor$. That is the length of the $n^{th}$ Fibonacci number is $\Theta(n)$.

If you go by the naive method, then calculating the $n^{th}$ Fibonacci number would cost you $\Theta(n^2)$ time.

In comparison, matrix exponentiation will take $O(n^2\log n)$ time, assuming you use schoolbook long multiplication to multiply numbers.  (A slightly more refined analysis shows that it is in fact $\Theta(n^2)$, by summing a geometric series.) But if instead we use Karatsuba multiplication , the running time to compute the $n$th Fibonacci number using matrix exponentiation becomes $O(n^{1.585}\log n)$.  (Analogous to before, a slightly more refined analysis shows that the running time is in fact $\Theta(n^{1.585})$.) Thus, if you use sophisticated multiplication algorithms, matrix exponentiation would be better for large $n$ compared to the naive algorithm.

In short: which method is better depends on which multiplication algorithm used.

This formula (from wikipedia) may be much faster, depending on how you manage floating point and exponentiate. The first term dominates.

$$ F_n = \frac1{\sqrt{5}}\cdot\left(\frac{1+\sqrt{5}}2\right)^n - \frac1{\sqrt{5}}\cdot\left(\frac{1-\sqrt{5}}2\right)^n\,.$$

(From Wikipedia.)


Dijkstra's algorithm on huge graphs I am very familiar with Dijkstra and I have a specific question about the algorithm. If I have a huge graph, for example 3.5 billion nodes (all OpenStreetMap data) then I clearly wouldn't be able to have the graph in memory, so the graph is stored on disk in a database.

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

Fetching the adjacency list of each vertex visited would require about 1,500 database queries per 10,000 nodes according to my statistical data, so that clearly is not how they do it. That would be way too slow.

How do they do it? I am trying to implement it myself.

There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?

You can use a DB, a custom file format to be read from disc and an in-memory setting.

But from my experience using a DB is roughly 5 to 10 times slower and a lot more memory intense than writing your own file format based on a 'simple' linked list format.

The good thing is there are several software frameworks using OSM which are open source so you can look right into the code e.g. see here. In the GraphHopper open source routing engine it is very easy to switch from a memory mapped setting (disc based) to the in-memory setting - both using the same format. The "mmap" setting even allows usage on memory restricted mobile devices and the latter performs a lot faster if you have the necessary RAM e.g. on a server. E.g. for a world wide graph (>100mio nodes) you then need around 8-10gb RAM, plus lot of more RAM if you want to speed up everything further e.g. with Contraction Hierarchies - roughly 5-8gb more for every vehicle you want.

The format is very simplistic and basically stores only the data you need with a few tricks to make it compact. Read more about it here. Disclaimer: I'm the author of GraphHopper.

Regarding the other answers:

  Dijkstras algorithm while applicable is regarded as not optimal for this problem

The 'normal' Dijkstra can perform very reasonable (<1s for country-wide queries like your 3mio nodes example) and is optimal in the 'theory sense' but needs a bit tuning to get fast in production scenarios. And techniques like Contraction Hierachies use a bidirectional modification of it and perform very well.

  road networks are hierarchical and planar.

road networks are hierarchical for car only and not planar (bridges, tunnels, ...)

On extremely large data sets like that, to get such fast results, I find it best to use a union-find data structure with path compression. However, if you are looking to only use Djikstra's algorithm and optimize that, it comes down to what information each node in the graph has. You most likely do not need to do all 1,500 queries.

For instance, consider the following example. Lets say I am trying to find the degrees of separation between any 2 actors (the Bacon number) and I want to find the least weighted path(path using the newest movies possible). Now, let's say I have a function called shortestPath(actor A, actor B);. Consider the following scenario.

If Actor A has been acting since 1970 and Actor B has been acting since 2000, then given that info, it would be much more logical to find a path starting from the first movie of Actor B and then traversing your way to Actor A. As opposed to iterating through every movie Actor A has acted in.

Thus, the main point is that the optimization of Djikstra's algorithm really depends on what your data set is. You would need to provide more information on what your data set entails for us to help you optimize your algorithm.

EDIT: Let's say you are trying to find the shortest path between 2 cities in the same country and if this country is longer than it is wider, for instance, Argentina, then you can do your queries based on the longitude and latitude of the countries boundaries. Then you can start to traverse vertically(using longitude) as opposed to horizontally. Ofc, there would need to be exception handling, but you get the general idea.


Why is Radix Sort $O(n)$? In radix sort we first sort by least significant digit then we sort by second least significant digit and so on and end up with sorted list.

Now if we have list of $n$ numbers we need $\log n$ bits to distinguish between those number. So number of radix sort passes we make will be $\log n$. Each pass takes $O(n)$ time and hence running time of radix sort is $O(n \log n)$

But it is well known that it is linear time algorithm. Why?

if we have a list of $n$ numbers we need $\log n$ bits

No: if we have a list of numbers between $0$ and $2^k - 1$, we need $k$ bits. There is no relationship between $k$ and $\log n$ in general.

If the numbers are all distinct, then $\log n \ge k$, and radix sort on distinct numbers therefore has a time complexity of $\Omega(n \log n)$. In general, the complexity of radix sort is $\Theta(n \, k)$ where $n$ is the number of elements to sort and $k$ is the number of bits in each element.

To say that the complexity of radix sort is $O(n)$ means taking a fixed bit size for the numbers. This implies that for large enough $n$, there will be many duplicate values.

There is a general theorem that an array or list sorting method that works by comparing two elements at a time cannot run faster than $\Theta(n \log n)$ in the worst case. Radix sort doesn't work by comparing elements, but the same proof method works. Radix sort is a decision process to determine which permutation to apply to the array; there are $n!$ permutations of the array, and radix sort takes binary decisions, i.e. it decides whether to swap two elements or not at each stage. After $m$ binary decisions, radix sort can decide between $2^m$ permutations. To reach the $n!$ possible permutations, it is necessary that $m \ge \log (n!) = \Theta(n \log n)$.

An assumption in the proof that I did not write out above is that the algorithm must work in the case when the elements are distinct. If it is known a priori that the elements are not all distinct, then the number of potential permutations is less than the full $n!$. When sorting $k$-bit numbers, it is only possible to have $n$ distinct elements when $n \le 2^k$; in that case, the complexity of radix sort is indeed $\Omega(n \log n)$. For larger values of $n$, there must be collisions, which explains how radix sort can have a complexity that's less than $\Theta(n \log n)$ when $n \gt 2^k$.

I think the assumption $k = \log_2(n)$ is wrong. You can perform radix sort with numbers in, e.g., hex. Thus, at each step you split you array of numbers into $16$ buckets.


Why is the complexity of the BFS O(V + E)? Consider the algorithm (from another question):

set start vertex to visited
load it into queue
    while queue not empty
        for each edge incident to vertex
             if its not visited
                 load into queue
                 mark vertex

The complexity of the algorithm is defined as the upper bound of times the inner loop can run, right? Well, considering a complete graph. For each one of its N vertexes, we run the check if its not visited N-1 times. So, that's N * (N-1) tests, which is quadratic. What is wrong with this view?

Overall, BFS accesses (and processes) each edge constant times (twice actually; we assume an undirected graph), costing $O(E)$ total time in edge processing. Similarly, all the vertices are totally accessed (including queue operations and checking operations) $O(E) \cdot O(1)$ times. The overhead for initialization is $O(V)$. Thus the total running time of BFS is $O(V + E)$.

This can be viewed as a simple instance of aggregate analysis.

In BFS algorithm  we begin from a arbitary vertex, so we meet all of vertexes then we claim that $O(v)$.since we must meet all vertexes then we used maximum edges to reach other vertexes . so we have $O(V+E)$


Linear time algorithm for finding $k$ shortest paths in unweighted graphs Definition. Given an unweighted graph $G=(V,E)$ and two vertices $s$ and $t$,
  the $k$-shortest-paths problem is finding the $k$ shortest simple paths
  between $s$ and $t$ in $G$.

Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem (assuming that $k$ is fixed).

I have looked at a few papers in the literature, such as "A New Implementation Of Yen's Ranking Loopless Paths Algorithm" but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein "Finding the k shortest paths" presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$.

Is there a linear-time algorithm for the $k$-simple-shortest-paths problem (in terms of $n$ and $m$) on unweighted graphs, where $k$ is fixed?

No. The best times known can be found in the survey "Implementations and empirical comparison of k shortest loopless path algorithms".

As a note, it is impossible to get linear times in the weighted case. There are lower bounds for the shortest path (i.e., k=1), which are not linear.

In the directed acyclic case you might have linear times for the k-SP, but I think is an open problem.

Cheers


Oblivious Machines and Input Dependency So I know the Oblivious Turing Machines head position depends on the size of the input word and a number of steps. Can it be modified in such a way that it's not dependent on the size of the input word?

According to the WP article on Turing machine equivalents, oblivious machine head position is independent of input and is a function of time instead. To wit:

  An oblivious Turing machine is a Turing machine where movement of the various heads are [sic] fixed functions of time, independent of the input. In other words, there is a predetermined sequence in which the various tapes are scanned, advanced, and written to.

REFERENCES

https://dl.acm.org/citation.cfm?doid=322123.322138

SEE ALSO

Head Position Function of Oblivious Turing Machines
https://stackoverflow.com/questions/14847080/how-does-an-oblivious-turing-machine-work


How to output all longest decreasing sequences Suppose I have an array of integers having length $N$. How can I output all longest decreasing sequences? (A subsequence consists of elements of the array that do not have to be consecustive, for example $(3,2,1)$ is a decreasing subsequence of $(7,3,5,2,0,1)$.) I know how to calculate the length of longest decreasing sequences, but don't know how to report all longest decreasing sequences.

Pseudocode will be helpful.

Consider the following sequence as your input:

$$n,n-2,n-1,n-3,n-5,n-4,n-6,n-8,n-7,n-9, .... , n-3 \cdot k - 2, n-3 \cdot k - 1, n-3 \cdot k - 3, ....$$

for simplicity assume $n = 3\cdot t + 1$, longest decreasing subsequence length will be $t$ and number of decreasing subsequence of length $t$ is $2^t$.

So number of avilable solutions is $\Theta(2^{n/3})$. But why is so, simply model it with DAG, take care there is an edge from $a$ → $b$, if $a > b$ and $b$ is after $a$ in original sequence.

So because output size can be exponential, your best choice is creating DAG, and finding all longest paths in DAG or any other ways which enumerates all acceptable ways.

For every decreasing sequence, store the initial positions in another array.

for( i = 0; i < n-1; i++ ) {
    if ( a[i] > a[i+1] ) {
        temp[j++] = i;
        while( a[i] > a[i+1] ) {
            i++;
        }
        temp[j++] = i;
    }
}

Now the array temp will contain initial and final positions of all the decreasing sequences consecutively. Then print them


Testing two DFAs generate the same language by trying all strings upto a certain length Given the language

$EQ_{\mathrm{dfa}} =$ $\{\langle A, B\rangle\mid A$ and $B$ are two DFAs and $L(A) = L(B)$ $\}$

Prove that $EQ_{\mathrm{dfa}}$ is decidable by testing the two DFAs on all strings upto a certain size. Calculate a size that works.

(This is from Sipser chapter 4)

I make a directed graph as usual but if two transitions $\delta(q_1, c_1) = q_2$ and $\delta(q_1, c_2) = q_2$ then the graph I am making will just have one edge for these two characters. My idea is to walk the directed graph in a way so that every transition is traversed, but when I walk over an edge forming a cycle, I would need to traverse the edges I have previously walked through in the cycle once again. Do this for both the DFAs and choose the greater number of edges traversed. Then enumerate through all the strings of this length (from the given alphabet) and the two DFAs are equal only if they accept and reject on the same strings.

I could probably write some pseudocode, but I'm not sure if this is the correct way to approach the problem even.

It can be tested that way, provided we may use the number of states of both automata $A$ and $B$ to compute the bound.

Note that if a finite automaton $C$ has $n$ states then any state in $C$ is reachable by a string of at most $n-1$ letters, or that state is not reachable at all. Assume I want to check whether $L(C)=\Sigma^*$. If $C$ is deterministic then all reachable states must be accepting. This can be tested by checking that all strings up to length $n-1$ are in the language.

The check $L(A)=L(B)$ can be analyzed similarly by considering the product automaton, i.e., the automaton that simulates $A$ and $B$ in parallel.

The product construction needs a little twist. Rather than accepting if both automata accept (computing the intersection) you need to see whether both automata make the same yes/no decision. Thus accept when both components are accepting or when both components are not accepting. Thus the language is $(L(A)\cap L(B))\cup (L(A)^c\cap L(B)^c)$. If that language is $\Sigma^*$ then both automata are equivalent.

This seems an unusual method of attempting to determine equivalence of the languages of two DFAs and obviously will never do so if the languages are infinite.

It is possible to impose a 'normal form' on DFAs by minimising and sorting transitions: equivalence can then be determined even in the infinite case.


What are the advantages of online learning when training neural networks? Stochastic gradient descent with a batch size of 1 is apparently used to learn from single examples as they arrive, but I don't understand why you would use such a small batch size instead of batching training inputs together.

Batch learning and online learning both have their place.  Generally speaking batch learning will train your neural network to a lower residual error level, because the online training can sometimes have one training undo the effect of another.  However, online training has a few advantages:

Online learning schemes learn "faster."  In some cases, determining how many samples you need can be difficult, and sample gathering may be costly.  Online learning lets you see the progress of your training as the number of samples increases, potentially saving on sample gathering costs once it reaches an acceptable error.
Online learning schemes can be done during operation, which can be valuable.
Online learning schemes are more effective for dealing with data sets that are not stationary.  It is easier for the batch methods to come up with highly specialized solutions which work well for the test samples, but do not capture a general solution.

One reason you'd use online learning is that the samples (data points) only arrive one at a time.  If you have all of the samples (data points) available at once, then batch learning is at least an option: but if the samples arrive in a continuous, streaming fashion, one at a time, and you need to make the best decision you can at each point in time given only the samples you've seen so far, then online learning becomes attractive, because it provides a way to update the neural network as each new sample arrives.

Online learning does not mean "only learning one weight at a time".  Online learning is about learning from one sample at a time (one data point at a time), but you're still updating all the weights of the neural network.


Converting indirect recursion to direct one I want to remove left recursion in grammar:

$G = ({S, A,B,C,D}, {a,b,c},P,S)$

$S → A$

$A → Aa | Bc$

$B → B a |CD$

$C →C b | ε$

$D → Bb | a$

We see that this grammar contains direct recursion ( $A → Aa$ ) and indirect recursion ( $B → CD → D → Bb$ ). We need to remove indirect recursion and convert it into direct recursion.

The problem in this grammar is $C →  ε$ rule , so we remove epsilon rules , after that we are left with

$B → B a |CD |D$ which is another indirect recursion so we remove simple rules.

Then we can remove left recursion step by step by alghoritm.

My question is , having large grammar , finding indirect recursion may be difficult. Is there any universal way how to convert indirect recursion to direct recursion? Thanks for answers

$S\to A$

$A\to aA'|EP$

$B\to CDB'$

$B'\to AB'|EP$

$C\to bC|EP$

$D\to aD'|bC'DB'bD'$

$D'\to B'bD'|EP$

There is a standard algorithm to remove indirect left recursion check here https://en.wikipedia.org/wiki/Left_recursion#Indirect_left_recursion


A d-ary heap problem from CLRS I got confused while solving the following problem (questions 1–3).

Question

  A d-ary heap is like a binary heap, but(with one possible exception) non-leaf nodes have d children instead of 2 children.

  How would you represent a d-ary heap in an array?
  What is the height of a d-ary heap of n elements in terms of n and d?
  Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.
   Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.
   Give an efficient implementation of INCREASE-KEY(A, i, k), which flags an error if k < A[i] = k and then updates the d-ary matrix heap structure appropriately. Analyze its running time in terms of d and n.

My Solution

Give an array $A[a_1 .. a_n]$

$\qquad \begin{align}
 \text{root} &: a_1\\
 \text{level 1} &: a_{2} \dots a_{2+d-1}\\
 \text{level 2} &: a_{2+d} \dots a_{2+d+d^2-1}\\
 &\vdots\\
 \text{level k} &: a_{2+\sum\limits_{i=1}^{k-1}d^i} \dots a_{2+\sum\limits_{i=1}^{k}d^i-1}
 \end{align}$

→ My notation seems a bit sophisticated. Is there any other simpler one?
Let h denotes the height of the d-ary heap.

Suppose that the heap is a complete d-ary tree
$$
 1+d+d^2+..+d^h=n\\
 \dfrac{d^{h+1}-1}{d-1}=n\\
 h=log_d[n{d-1}+1] - 1
 $$
This is my implementation:

EXTRACT-MAX(A)
1  if A.heapsize < 1
2      error "heap underflow"
3  max = A[1]
4  A[1] = A[A.heapsize]
5  A.heap-size = A.heap-size - 1
6  MAX-HEAPIFY(A, 1)
7  return max

MAX-HEAPIFY(A, i)
1  assign depthk-children to AUX[1..d]
2  for k=1 to d
3      compare A[i] with AUX[k]
4      if A[i] <= AUX[k]
5          exchange A[i] with AUX[k]
6          k = largest
7  assign AUX[1..d] back to A[depthk-children]
8  if largest != i
9      MAX-HEAPIFY(A, (2+(1+d+d^2+..+d^{k-1})+(largest-1) )

The running time of MAX-HEAPIFY:

$$T_M = d(c_8*d + (c_9+..+c_13)*d +c_14*d)$$
where $c_i$ denotes the cost of i-th line above.
EXTRACT-MAX:
$$
       T_E = (c_1+..+c_7) + T_M \leq C*d*h\\
       = C*d*(log_d[n(d-1)+1] - 1)\\
       = O(dlog_d[n(d-1)])
       $$

→ Is this an efficient solution? Or there is something wrong within my solution?

Your solution is valid and follows definition of d-ary heap. But as you pointed out your notation is a bit sophisticated.

You might use those two following functions to retrieve parent of i-th element and j-th child of i-th element.

$\text{d-ary-parent}({\it i}) \\
  \ \ \ \ {\bf return}\ \lfloor (i-2)/d + 1 \rfloor$

$\text{d-ary-child}(i, j) \\
  \ \ \ \ {\bf return}\ d(i-1)+j+1$

Obviously $1 \le j \le d$. You can verify those functions checking that $\text{d-ary-parent}(\text{d-ary-child}(i,j)) = i$

Also easy to see is that binary heap is special type of $d$-ary heap where $d=2$, if you substitute $d$ with $2$, then you will see that they match functions PARENT, LEFT and RIGHT mentioned in book.
If I understand your answer correctly you use a geometric progression. In your case you get go $h = log_d(n\,d-1+1) - 1$, which is obviously $\log_d(n\,d) - 1 = \log_d(n) + \log_d(d) - 1 = \log_d(n) + 1 - 1 = \log_d(n)$, which in fact is a valid and correct solution. But just for sake of handling constant fluctuations you might wanna write $\Theta(\log_d(n))$.

The reason for this is that some heaps might not be balanced, so their longest path and shorthest path migt vary by some constant $c$, by using $\Theta$ notation you eliminate this problem.
You don't need to re-implement procedure given in textbook, but you must alter it a bit, eg assigning all children to $AUX$ table using given $\text{d-ary-parent}$ and $\text{d-ary-child}$ functions.

Because $\text{EXTRACT-MAX}$ was not altered, it depends on running time of $\text{MAX-HEAPIFY}$. In your analysis you now you must use worst-case time proportional to hight and number of children which each node must examine (which is at most d). Once again your analysis is very precise, in the end you got $O(d\ \log_d(n(d-1)))$, which can be transformed to:

$O(d\ \log_d(n(d-1))) = O(d(\log_d(n) + \log(d-1))) = O(d\ log_d(n) + d\ \log_d(d-1))$

For practical reasons we can always assume that $d \ll n$, so we can lose the $d \log_d(d-1)$ part of O notation, then we will get $O(d\log_d(n))$. Which is also valid solution. But not surprisingly you can also analyse function run time using Master theorem, which will show that $\text{MAX-HEAPIFY}$ is not only $O$ but even $\Theta$.
CLRS book already provides INSERT procedure.  Which looks like this:

$\text{INSERT}(A, key)\\
  \ \ \ \ A.heap\_size = A.heap\_size + 1 \\
  \ \ \ \ A[A.heap\_size] = -\infty\\
  \ \ \ \ \text{INCREASE-KEY}(A, A.heap\_size, key)$

It can be easy proven but common sense dictates that it's time complexity is $O(\log_d(n))$. It's because heap might be traversed all the way to the root.
Just like INSERT, INCREASE-KEY is also defined in textbook as:

$\text{INCREASE-KEY}(A, i, key)\\
  \ \ \ \ {\bf if}\ key < A[i]\\
  \ \ \ \ \ \ \ \ {\bf error} \text{"new key is smaller then current"}\\
  \ \ \ \ A[i] = key\\
  \ \ \ \ {\bf while}\ i > 1\ and\ A[i] > A[\text{d-ary-parent}(i)]\\
  \ \ \ \ \ \ \ \ A[i] \leftrightarrow A[\text{d-ary-parent(i)}]\\
  \ \ \ \ \ \ \ \ i = \text{d-ary-parent(i)}$

Complexity is obviously $O(\log_d(n))$ (see previous point).

Answer to the second question is h = logd(n(d-1) + 1) - 1
So, h = logd(nd - n + 1) - 1


Consider a social network. The goal is to find in the in the network a largest group of people who are all friends with each other. Describe the problem as a graph problem. I've tried to modify the breadth first search algorithm, but haven't gotten anywhere. Any ideas?

This is the Maximum Clique problem, one of the canonical NP-complete problems. On general graphs it probably cannot be solved efficiently, though social networks, with their very particular structures, may lend themselves to more efficient solutions.

Rather than breadth first search, start with depth first search.

Select your first user , your starting node. This is "Bob".
Go to a random friend. This is "Alice".
This is the modified step. In a list store the nodes you have visited, now it's only "Bob". In Alice's friends search the ones who are also friends with everyone in the list. Go to one of them. This is "Kate".
Now you have "Bob" and "Alice" in your list. Repeat Step 3 for Kate. If Kate does not have any mutual friends return back to Alice and select another friend. Don't add Kate to list. (Depth First Algorithm). In each backtracking save the maximum number of people in list. Change it if you have a new maximum.
In you final step, you won't have anyone who has an unvisited friend that is also friends with everyone in the list. At that step, add the last person and save your list. This list certainly has Bob, and the biggest group that Bob is in. That's why you save the maximum count.
You have to repeat this step for everyone and get the list with maximum number of elements. Someone in one list can also be in another list, so you have to run this for everyone. This step can be improved

You can also check whether a group has the maximum number of people by comparing it with the total number of friendship relations(edges) in the graph. I believe that this whole process can be shortened by using the data from previous groups. For example, after the first run, you will have the biggest group that Bob is in, in your second run you can bypass visiting Bob.

For example if you have a group that has more people than the half of the whole population, it's maximum.

This solution is open to objection and faster algoritms, but if you have enough time or your database is not huge, this algorithm gives you the right answer.


What is the time-complexity of histogram computation? Suppose I have an Image $I$ of $n\times m$ (or a matrix), I would like to compute its histograms in a loop.

Pseudocode:

for i=1:s1:n
      h = hist(I(i:i+s1,m),bins)
end

$I$ is a  matrix (or an image of data). When we say, $I(i:i+s1,m)$ we take the block of the matrix that starts in row from $i$ to $i+s1$ and have $m$ elements in columns.

hist is a function that counts the number of elements in its first parameters and store that number in its $bins$. For example : $hist([1,2 ,1 ,1 ,3],3)$ is equals to $[3, 1, 1]$ because there is three elements of $1$ and just one elements of $2$ and $3$. $hist$ computes the frequency of an element.

So if I understand well ... the time-complexity of this simple algorithm is $O(n/s1) * TC(hist)$.

With the $TC(hist)$ the time-complexity of histogram computation. Since $s1$  is constant. I can deduce that TC of the algorithm is $O(n)*TC(hist)$.

If we use a hash table of size $bins$, (it is a memory, so it won't impact the time complexity). We will have to browse the $s1\times m$ part of the image. So the $TC(hist)$ is equal $O(s1*m)$.

I don't know how to link $O(s1*m)$ to the $n$ and $m$. Is $TC(hist)$ linear following $m$ so equals $O(m) $ since $s1$ is a constant ?

please, check if my reasoning is correct ? and what is the global time-complexity ? do we take in consideration the memory usage in the computation of time-complexity ?

Presumably the time complexity of the function hist applied to data of length $N$ and to $B$ bins is $O(N+B)$ (the exact definition of $B$ depends on the implementation of hist; in your case, it seems to be the maximum of the input). In your case, each of the $n/s_1$ iterations of the loop is applied to data of length $s_1 m$, and so the total running time is
$$ \frac{n}{s_1} O(s_1m + B) = O(nm + \frac{n}{s_1} B). $$
The answer that your teacher expects is $O(nm)$.

[From Mahaj Riad]

I hope you're familiar with C/Java syntax.

So, if I understand your algorithm, it should be composed of 3 nested loops; the first inner loop depends on the former, and the deepest loop is independent.

for ( i = 1; i <= n - s1; i +=s1 ) {
    for ( j = 1; j <= i + s1; j ++ ) {
        for ( k = 1; k <= m; k ++ ) {
            bins[I[j,k]] ++; // frequency counting, symbolized by 'c'
        }
    }
}

Based on the above:

$$
\\
T(n, m) = \frac{1}{s_1} \sum_{i = 1}^{ n - s_1} \sum_{j = 1}^{ i + s_1}  \sum_{k = 1}^{ m}c
\\
T(n,m) = \frac{c}{s_1} \sum_{i = 1}^{ n - s_1} \sum_{j = 1}^{ i + s_1}m
\\
T(n, m) = \frac{cm}{s_1} \sum_{i = 1}^{ n - s_1}(i + s_1)
\\
T(n, m) = \frac{cm}{s_1} \left(\sum_{i = 1}^{ n - s_1}i + \sum_{i = 1}^{ n - s_1}s_1\right)
\\
T(n, m) = \frac{cm}{s_1} \left(\frac{(n - s_1)(n - s_1 + 1)}{2} + s_1(n - s_1)\right)
\\
T(n, m) = \frac{cm}{s_1} \left( \frac{n^2 + n - s_1^2 - s_1}{2} \right)
\\
\text{The order of growth is } \Theta(mn^2).
\\
\text{In other words, when } n = m \text{, we can affirm }  \Theta(n^3) \rightarrow  \text{ Cubic order of growth.}
\\
\text{and when } n < m \rightarrow T(n, m) \in \Omega(n^3)
\\
\text{and when } n > m \rightarrow T(n, m) \in \mathcal{O}(n^3)
$$