Problem Detail: While learning binary tree’s properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search. My book specifies some facts about these as follows: $S_n=1+frac{U_0+U_1+…+U_{n-1}}{n}$ For large $n$, $S_n=2 log_en$ Read More …
Category: Uncategorized
[Solved]: Family of types in type theory
Problem Detail: Can anyone simplify the meaning of families of types index by a type. It looks i get it but quite not understood it. What do you mean by a “family” ? I understand index by a value (n length Read More …
[Solved]: What is the difference between cyber security ontologies and scenario ontologies in this system?
Problem Detail: I have been reading the paper Towards a Cognitive System for Decision Support in Cyber Operations. And I have been trying to understand the role of two ontologies proposed here, cyber security ontologies and scenario ontologies. I have asked Read More …
[Solved]: How to determine if a state is a fixed point in a Hopfield network?
Problem Detail: I have been reading a lot and I am still unsure of how to determine this. Let’s say I have an initial binary state vector (1, 1, 1). How would I go about determining whether (1, 1, 1) is Read More …
[Solved]: Given a minimum vertex cover can we find all the others in polynomial time?
Problem Detail: Having found one minimum vertex cover of a connected undirected graph, is there a known polynomial-time algorithm for finding all the other minimum vertex covers of the graph, or is this problem NP-complete as well? Another question: what other Read More …
[Solved]: Why do we need “Bloom Filters” if we can use hash tables?
Problem Detail: A Bloom filter is a probabilistic data structure designed to tell, rapidly and memory-efficiently, whether an element is in the set or no. If we can use hash tables where we have O(1) in best time, O(n) in a Read More …
[Solved]: Interleaving algorithm for 2 stacks
Problem Detail: Suppose I have two stacks $<a_1,a_2,…a_m>$ and $<b_1, b_2,…b_n>$ and a third stack of size $m+n$. I want to have the third stack in the following manner, $$<a_1,b_1,a_2,b_2,…a_n,b_n…a_m-1,a_m>$$ for $$m>n$$ This was easy to do if the two initial Read More …
[Solved]: Can I have a “dependent coproduct type”?
Problem Detail: I’m reading through the HoTT book and I have a (probably very naive) question about the stuff in the chapter one. The chapter introduces the function type $$ f:Ato B $$ and then generalizes it by making $B$ dependent Read More …
[Solved]: Is the codomain/range of a hash function always $mathbb{Z}$ or $mathbb{N}$?
Problem Detail: From Wikipedia A hash function is any algorithm or subroutine that maps large data sets of variable length, called keys, to smaller data sets of a fixed length. For example, a person’s name, having a variable length, could be Read More …
[Solved]: Finding a function which is a mapping reduction of A to B
Problem Detail: How do I precisely define the function which is a mapping reduction of A to B for the following examples? What is the process of figuring this out? Given: A and B are languages over the alphabet {0,1}. Examples: Read More …
