Problem Detail: I’m a teacher assistant in my university and my next topic is recursion. what way is the best to teach recursion so that the student can grasp the concept easily and can think recursively? I was thinking about explaining Read More …
Category: Uncategorized
[Solved]: Looking for books on creating and understanding theorems targeted at Computer Science
Problem Detail: In studying logic to understand verifying programs I have found that there are books on logic targeted at Computer Science e.g. Logic in Computer Science: Modelling and Reasoning about Systems Mathematical Logic for Computer Science Computability and Logic Handbook Read More …
[Solved]: What is practical difference between NP and PSPACE-complete?
Problem Detail: Here’s something that has puzzled me lately, and perhaps someone can explain what I’m missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$,neq,$NP, PSPACE$,neq,$NP etc. this means that there Read More …
[Solved]: Split-Find: maintaining dynamic graph connectivity information, under edge deletion
Problem Detail: Is there a data structure to keep track of the connected components of a dynamic graph, when the graph might by changing by deleting edges of the graph? Let $G$ be an undirected graph. I have two operations I’d Read More …
[Solved]: Big-O complexity of sqrt(n)
Problem Detail: I’m trying to backfill missing CS knowledge and going through the MIT 6.006 course. It asks me to rank functions by asymptotic complexity and I want to understand how they should be reduced rather than just guessing. The question Read More …
[Solved]: In computer science how is using passive voice regarded?
Problem Detail: A soft question, when I was in high school and in University I took scientific writing classes and people told me I should use passive voice as much as possible to sound objective, but when I entered grad school Read More …
[Solved]: Is there a correlation of zip compression ratio and density of information provided by a text?
Problem Detail: I’ll phrase my question using an intuitive and rather extreme example: Is the expected compression ratio (using zip compression) of a children’s book higher than that of a novel written for adults? I read somewhere that specifically the compression Read More …
[Solved]: Definability of Truth Assignments
Problem Detail: I have a question about definability of truth assignments. Suppose that I am working in the context of propositional logic. Let me give some definitions first. Let $L$ be a propositional language with the set $Prop_{L}$ of propositional variables. Read More …
[Solved]: Quick Sort: Randomized Pivot vs Median of 3/’Ninther’ Pivot vs Uniform Shuffle of Input
Problem Detail: Is the jury still out on this or do we now know which of the above mentioned ways of randomizing Quick Sort is the most optimum as far as average case running time (averaged over all possible input arrays, Read More …
[Solved]: Is linear-time reduction symmetric?
Problem Detail: By reduction I mean the following: Problem X linear reduces to problem Y if X can be solved with: a) Linear number of standard computational steps. b) Constant calls to subroutine for Y. If a problem X reduces to Read More …
