Question Detail: In this answer it is mentioned A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is equivalent to saying it requires a full Read More …
Author: ignougroup
Why is binary search faster than ternary search?
Question Detail: Searching an array of $N$ elements using binary search takes, in the worst case $log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used ‘ternary search’, we’d cut away two-thirds of Read More …
Why does Dijkstra’s algorithm fail on a negative weighted graphs?
Question Detail: I know this is probably very basic, I just can’t wrap my head around it. We recently studied about Dijkstra’s algorithm for finding the shortest path between two vertices on a weighted graph. My professor said this algorithm will Read More …
Cache Direct Map (Index, tag, hit/miss)
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 …
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 …
DIfferences between computer vision and image processing
Question Detail: I am basically an Electronics and Communication Engineering student. My relevant coursework include Probability Theory and Stochastic Processes, Engineering Mathematics, Signals and Systems, Digital Signal Processing (this semester). Now, this area Computer Vision – Image Processing – Object recognition 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 …
