JeffE
Reputation
346
Top tag
Next privilege 500 Rep.
Access review queues
 May13 answered Properties of this class of graphs May13 comment Is this a sufficient condition for vertex and edge transitivity? The statement is false if the graph can be disconnected. A connected (4,4)-graph can be constructed by drawing a grid on the torus. Consider the disjoint union of two such graphs with different numbers of vertices. May13 answered For any $r,g$, is there an $r$-regular graph of girth $g$? May12 comment How do you go about solving difference equations? These notes might be helpful, especially Section 5. May11 comment Form or asymptotic behaviour of $T(n) =2T(n-1)+n$ Are you allowed to pick more than one option? May8 comment What are some examples of a mathematical result being counterintuitive? But its volume doesn't change! (Connelly's Bellows Theorem) May8 comment How to deal with the temporary nature of my knowledge? Close. I'm suggesting that you let/force yourself get caught in details, instead of only trying to see the "big picture". May8 comment How to deal with the temporary nature of my knowledge? @Self_Learner: If your current school is too rigid, why not change schools? May8 answered How to deal with the temporary nature of my knowledge? May6 comment The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$. Even simpler: A binary tree with depth 0 has 1 node (the root), not 0 nodes. But check your source's definitions. If they define depth as the number of nodes on the longest root-to-leaf path, instead of the (more standard) number of edges on the longest root-to-leaf path, then their statement is correct. May4 comment What is the definition of a cross cap? Then "cross-cap" is just a synonym for "Möbius band". Both are homeomorphic to $RP^2$ minus a disk. May4 comment What is the definition of a cross cap? Do you mean cross-cap as a subspace of an abstract 2-manifold (a Möbius band), or do you mean cross-cap as a geometric feature of a self-intersecting surface in 3-space, or do you mean something else? Apr26 comment A “State Hierarchy” Theorem for Turing Machines? @adcvvc: I believe this is a double-starred homework exercise in the first edition of Hopcroft and Ullman's automata-thoery textbook. Apr25 comment A “State Hierarchy” Theorem for Turing Machines? With a lot more work, you can reduce the number of states to 2. Apr22 comment How to figure out the log of a number without a calculator? To answer the title: Check the CRC Handbook or use a slide rule. Apr22 comment How many possible ways are there Apparently the formula is "6". What is the general question? Apr17 comment Shortest path variation "Note that if two paths use the same vertex $v_i$, the cost $C$ is only paid once." — This makes things complicated. If every path paid for every vertex it traversed, you could just replace each vertex $v$ with a directed edge $v^- \mathord\to v^+$ with cost $C$, and then replace every edge $u \mathord\to v$ with the corresponding edge $u^+ \mathord\to v^-$. Apr17 comment Shortest path variation Is this homework? Apr17 comment Shortest path variation @dtldarek: I don't think so. He's trying to minimize the cost of each $s\leadsto t_i$ path, not the total cost of all vertices and edges in the shortest-path tree. (Also, technically, Steiner trees are only defined for undirected graphs.) Apr16 comment Most general way of selecting 10% of set elements What property? Once a magic black box emits a subset of elements, how can any property of that subset depend on whether the black box is deterministic? (Give me two different black boxes whose outputs always have the property you want. I'll build a bigger black box that chooses one of your black boxes by flipping a coin. The output of my bigger black box always has the property you want.)