Problem Detail: For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm. Asked By : Median Read More …
Author: ignougroup
Sabatier conjectures
Problem Detail: While I was doing CLRS (3rd edition), I came across this question on page 629: Professor Sabatier conjectures the following converse of Theorem 23.1: Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ Read More …
Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?
Problem Detail: In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also said that all variants of Read More …
Finding cache block transfer time in a 3 level memory system
Problem Detail: Following question was asked in one of entrance exams for a graduation programme. Please help me try to solve it : A computer system has an L1 cache, an L2 cache, and a main memory unity connected as shown Read More …
NFA or DFA for strings the contain exactly twice substring ab?
Problem Detail: Given the language with alphabet: ${a, b, c}$ Draw an NFA or DFA for all the strings that have exactly twice substrings $ab$ and at least on $c$. I’m stuck with “exactly twice $ab$”. Can somebody give me some Read More …
Algorithm for getting the outer boundary of a large graph
Problem Detail: I am trying to create an isochrone based on the OpenStreetMap data set. Everything works fine, I extracted data, processed it into a DAG, ran a Dijkstra algorithm over it. The result is a subset of the complete graph. Read More …
Do subqueries add expressive power to SQL queries?
Problem Detail: Does SQL need subqueries? Imagine a sufficiently generalized implementation of the structured query language for relation databases. Since the structure of the canonical SQL SELECT statement is actually pretty important for this to make sense, I don’t appeal directly Read More …
What’s a trivial property?
Problem Detail: I have to show a property P is trivial. This problem has to do with Rice’s Theorem, which I do not completely understand. Can someone explain the difference between trivial and non-trivial properties? Asked By : Alex Chumbley Answered By Read More …
Maintaining an efficient ordering where you can insert elements “in between” any two other elements in the ordering?
Problem Detail: Imagine I have an ordering on a bunch of elements like so: Where an arrow $X leftarrow Y$ means $X < Y$. It is also transitive: $left(X < Yright) wedge left(Y < Zright) implies left(X < Zright)$. In order Read More …
How to prove that problem is not in P
Problem Detail: Given some abstract problem how can I prove that this problem is not in P. I mean, what is the method for proving such thesis? Asked By : Ari Answered By : Yuval Filmus The most common technique is to prove Read More …
