Problem Detail: I am making database on Disaster Management. There are four tables. DisasterEvent (eventid, name, glideID, status, description, date_occurred, date_ended, disaster_type) People(eventid, num_deaths, num_injuries, num_affected) Homes (eventid, num_homes_destroyed, num_homes_damaged, total_insured_loss, total_uninsured_loss) Place (place_id, city, state, country, postal_code) In my design, Read More …
Blog
[Solved]: How does the runtime of the Ukkonen’s algorithm depend on the alphabet size?
Problem Detail: I am concerned with the question of the asymptotic running time of the Ukkonen’s algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time. Here is a citation from the book “Algorithms on strings, trees Read More …
[Solved]: Approximating NP-complete problems
Problem Detail: Say that for a particular problem, e.g., the independent set problem, it has been shown that no polynomial-time algorithm exists to solve it. Could we get around this by finding an algorithm which approximates the solution to a certain Read More …
[Solved]: What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time
Problem Detail: I know that Big O is used to bound worst case running time. So an algorithm with running time $O(n^5)$ means its running time in worse case is less than $n^5$ asymptotically. Similarly, one can say that for example Read More …
[Solved]: How to prove that $n(log_3(n))^5 = O(n^{1.2})$?
Problem Detail: This a homework question from Udi Manber’s book. Any hint would be nice 🙂 I must show that: $n(log_3(n))^5 = O(n^{1.2})$ I tried using Theorem 3.1 of book: $f(n)^c = O(a^{f(n)})$ (for $c > 0$, $a > 1$) Substituing: Read More …
[Solved]: Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently?
Problem Detail: Yesterday while returning home, I walked past a house that had a camera. For some reason I started thinking about how these cameras work, and how you would use them in case of robbery. While thinking about everything that Read More …
[Solved]: Does the BIOS run on the CPU?
Problem Detail: I was just thinking about this: Does the BIOS execute on the CPU? If so, how does it handle multiple CPU architectures/instruction sets? If not, what does it execute on? Asked By : Zeb McCorkle Answered By : hunch_hunch Yes, the Read More …
[Solved]: Evaluating Statements Using a Parse Tree
Problem Detail: I’m building a compiler. I already have a parse tree which I built using Bison for a grammar similar to the ANSI C grammar in this link. I see that for multiplicative expression in my parse tree, there can Read More …
[Solved]: How would a neural network deal with an arbitrary length output?
Problem Detail: I’ve been looking into Recurrent Neural Networks, but I don’t understand what the architecture of a neural network would look like when the output length is not necessarily fixed. It seems like most networks I’ve read descriptions of require Read More …
[Solved]: Correctness of proof by induction
Problem Detail: Suppose a person states the following: $n^2 = (n * n), forall n > 0$. One can check such equality by saying, via proof by induction, that: for $n := 0: 0^2 = (0 * 0)$; for $n := Read More …
