Depth–first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each Read More …
Blog
What is a stack ? Explain the various operations of stack with an example for each operation.
Stack Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the Read More …
[Solved]: How can I tell who is a truth teller and who is a liar?
Problem Detail: This is a problem that I was given for my data structures and algorithms class. I am not sure how to tackle this problem. Can I get some assistance? At Hogwarts a new shipment of $n$ goblins has arrived. Read More …
[Solved]: Checking whether a digraph on $n$ vertices contains exactly $10sqrt{n}$ strongly connected components in NL
Problem Detail: I am studying now for a test in my complexity course. When I solved previous exams I saw the following question: Prove that the language $L$ of all directed graphs on $n$ vertices that contain exactly $10sqrt{n}$ strongly connected Read More …
[Solved]: What guarantees do “soft” real-time operating systems actually provide
Problem Detail: I think I know what a “hard” real-time operating system is. It is an operating system with a scheduler that provides a contract with the application programmer. An application provides a deadline with each resource allocation request. If the Read More …
[Solved]: How to understand the SR Latch
Problem Detail: I can’t wrap my head around how the SR Latch works. Seemingly, you plug an input line from R, and another from S, and you are supposed to get results in $Q$ and $Q’$. However, both R and S Read More …
[Solved]: What is the difference between RAM and TM
Problem Detail: In case of algorithm analysis we assume a generic one processor Random Access Machine(RAM). As I know RAM is machine which is no more efficient than the Turing machine.All algorithms can be implemented in the Turing machine.So my question Read More …
[Solved]: Can a program language be malleable enough to allow programs to extend language semantics
Problem Detail: With reference to features in languages like ruby (and javascript), which allow a programmer to extend/override classes any time after defining it (including classes like String), is it theoretically feasible to design a language which can allow programs to Read More …
[Solved]: Dynamic subtraction game
Problem Detail: I came across the following dynamic subtraction game: There is one pile of n chips. The first player to move may remove as many chips as desired, at least one chip but not the whole pile. Thereafter, the players Read More …
[Solved]: Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree
Problem Detail: I’m trying to reproduce the synthetic networks (graphs) described in some papers. The topic is the same as a previous question of mine, but with a different focus. It is stated that the Erdos-Renyi model was used to create Read More …
