Problem Detail: We were asked this question in exam and I am not satisfied with the answer the teacher gave. Let me justify my point of view. Let there be a polynomial time function having time complexity $n^{c_1}$. If we call Read More …
Blog
[Solved]: What were the research outcomes of the Univalent Foundations Program year (Homotopy Type Theory)
Problem Detail: The Institute for Advanced Study has had a year-long special program devoted to the Univalent Foundations Program. At the end of this they have produced a book and a code repository. At the end of this we see a Read More …
[Solved]: How to replace one symbol with two on Turing machine’s tape
Problem Detail: I want to implement following algorithm on Turing machine: rewrite binary numbers to their unary counterparts. For example: 101 will be rewritten to a string of 5 consecutive bars (wikipedia) But I don’t know how to make the replacement Read More …
[Solved]: Find which vertices to delete from graph to get smallest largest component
Problem Detail: Given a graph $G = (V, E)$, find $k$ vertices ${v^*_1,dots,v^*_k}$, which removal would result in a graph with smallest largest component. I assume for large $n = |V|$ and large $k$ the problem is difficult (NP-hard), but I Read More …
[Solved]: “Not in big theta but in big O”
Problem Detail: Can somebody please help me understand ways I can attempt to find two functions f(x) and g(x) in which f(x) is in big O of g(x) but not big theta of g(x). I get that this is asking me Read More …
[Solved]: Would removing the branch delay slots change the instructions set architecture?
Problem Detail: I am trying to study for an exam and I noticed a lot of the questions follow the idea of “Changing the ISA“. From my understanding the ISA dictates the structure and format of instructions, so changing instructions or Read More …
[Solved]: Intuition behind Relativization
Problem Detail: I take course on Computational Complexity. My problem is I don’t understand Relativization method. I tried to find a bit of intuition in many textbooks, unfortunately, so far with no success. I will appreciate if someone could shed the Read More …
[Solved]: Building a Red Black tree out of a sorted array
Problem Detail: If I have a sorted array of size $n$, can I build a Red Black tree out of it in $O(n)$ time in a different algorithm rather than splitting the tree in half every time or the straightforward way Read More …
[Solved]: How to recognize a STRIPS planning problem has no solution?
Problem Detail: Strips –Stands for STanford Research Institute Problem Solver (1971). STRIPS Pseudo code – STRIPS(stateListstart, stateListgoals) 1.Set state = start 2.Set plan = [] 3.Set stack = goals 4.while stack is not empty do 1.STRIPS-Step() 5.Return plan STRIPS-Step() switch Read More …
[Solved]: What is a clairvoyant algorithm?
Problem Detail: When talking about general data structure design, my lecture notes talk about one of the concerns being cost of operations. As well as the individual cost, it mentions amortized cost. But then it goes on to say: Amortized cost Read More …
