Question Detail: Suppose we’re given two numbers $l$ and $r$ and that we want to find $max{(ioplus j)}$ for $lle i,,jle r$. The naïve algorithm simply checks all possible pairs; for instance in ruby we’d have: def max_xor(l, r) max = Read More …
Blog
Shortest Path on an Undirected Graph?
Question Detail: So I thought this (though somewhat basic) question belonged here: Say I have a graph of size 100 nodes arrayed in a 10×10 pattern (think chessboard). The graph is undirected, and unweighted. Moving through the graph involves moving three Read More …
Is Dijkstra’s algorithm just BFS with a priority queue?
Question Detail: According to this page, Dijkstra’s algorithm is just BFS with a priority queue. Is it really that simple? I think not. Asked By : Barry Fruitman Best Answer from StackOverflow Question Source : http://cs.stackexchange.com/questions/10047 Answered By : Shaull You can implement Dijkstra’s Read More …
How can it be decidable whether $pi$ has some sequence of digits?
Question Detail: We were given the following exercise. Let $qquad displaystyle f(n) = begin{cases} 1 & 0^n text{ occurs in the decimal representation of } pi 0 & text{else}end{cases}$ Prove that $f$ is computable. How is this possible? As far as Read More …
What is the depth of a complete binary tree with $N$ nodes?
Question Detail: This question uses the following definition of a complete binary tree†: A binary tree $T$ with $N$ levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to Read More …
The amount of ROM needed to implement a 4-bit multiplier?
Question Detail: For a 4-bit multiplier there are $2^4 cdot 2^4 = 2^8$ combinations. The output of 4-bit multiplication is 8 bits, so the amount of ROM needed is $2^8 cdot 8 = 2048$ bits. Why is that? Why does the Read More …
Deletion in min/max heaps
Question Detail: I think I’m confused about deletion in heaps, and since I have an exam today, I’m looking for your help to correct me. I will post photos since it will makes it a bit more clear. Note(forget about deleting Read More …
Selection Sort runtime in terms of Big O
Question Detail: I’m trying to understand why the sorting algorithm Selection Sort has asymptotic runtime in $O(n^2)$. Looking at the math, the runtime is $qquad T(n) = (n-1) + (n-2) + dots + 2 + 1$. And this is stated to Read More …
Doubt regarding cache hit ratios and access time
Question Detail: Question 1: What is the average access time for a 3-level memory system with access time $T_1$, $2T_1$ and $3T_1$? (Hit ratio $h_1$ = $h_2$ = 0.9) The solution given is: $0.9[T_1] + 0.1(0.9[2*T_1] + 0.1[3*T_1]) = 1.11[T_1]$ (Method Read More …
How does an admissible heuristic ensure an optimal solution?
Question Detail: When using A* or any other best path finding algorithm we say that the heuristic used should be admissible i.e. it should never overestimate the actual solution path (moves). Can someone tell me how this is true? Please avoid Read More …
