Question Detail: Alright, I thought I understood this concept but now I am confused. I looked up similar problems and their solutions to practice, and that’s what threw me off. The question is a homework problem which says: Below is a Read More …
Category: Uncategorized
What is the fastest algorithm for finding all shortest paths in a sparse graph?
Question Detail: In an unweighted, undirected graph with $V$ vertices and $E$ edges such that $2V gt E$, what is the fastest way to find all shortest paths in a graph? Can it be done in faster than Floyd-Warshall which is Read More …
Normalizing the mantissa in floating point representation
Question Detail: How to represent $0.148 * 2^{14}$ in normalized floating point arithmetic with the format 1 – Sign bit 7 – Exponent in Excess-64 form 8 – Mantissa $(0.148)_{10} = (0.00100101;111…)_2$ We shift it 3 bits to left to make Read More …
Evaluating the average time complexity of a given bubblesort algorithm.
Question Detail: Considering this pseudo-code of a bubblesort: FOR i := 0 TO arraylength(list) STEP 1 switched := false FOR j := 0 TO arraylength(list)-(i+1) STEP 1 IF list[j] > list[j + 1] THEN switch(list,j,j+1) switched := true ENDIF NEXT IF Read More …
The time complexity of finding the diameter of a graph
Question Detail: What is the time complexity of finding the diameter of a graph $G=(V,E)$? ${O}(|V|^2)$ ${O}(|V|^2+|V| cdot |E|)$ ${O}(|V|^2cdot |E|)$ ${O}(|V|cdot |E|^2)$ The diameter of a graph $G$ is the longest distance between two vertices in graph. I have Read More …
Is Morse code without spaces uniquely decipherable?
Question Detail: Are all Morse code strings uniquely decipherable? Without the spaces, ……-…-..—.—–.-..-..-.. could be Hello World but perhaps the first letter is a 5 — in fact it looks very unlikely an arbitrary sequence of dots and dashes should have Read More …
What is the significance of negative weight edges in a graph?
Question Detail: I was doing dynamic programming exercises and found the Floyd-Warshall algorithm. Apparently it finds all-pairs shortest paths for a graph which can have negative weight edges, but no negative cycles. So, I wonder what’s the real world significance of Read More …
Why does a processor have 32 registers?
Question Detail: I’ve always wondered why processors stopped at 32 registers. It’s by far the fastest piece of the machine, why not just make bigger processors with more registers? Wouldn’t that mean less going to the RAM? Asked By : Matt Capone Read More …
Finding shortest and longest paths between two vertices in a DAG
Question Detail: Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time? Path lengths are measured by the Read More …
What is the difference between a ‘page’ or memory and a ‘frame’ of memory?
Question Detail: WP has a adequate discussion of paging, which I think I understand.. However I am confused by the articles repeated use of the term Page Frame. I thought frames and pages were different things. Could someone please clarify the Read More …
