-1
votes
1answer
28 views

Height of H-Tree [closed]

I studied VLSI layout design and in that they discussed the most efficient way to layout is using an H-Tree as the area occupied is smallest compared to for example a binary tree. Can anyone ...
2
votes
1answer
65 views

What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?

Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero ...
5
votes
1answer
517 views

Data structure for storing edges of a graph

I'm currently working on my masters thesis, and it's about clustering on graphs. I'm working with an idea using ants to solve the problem. I'm currently working on the implementation and am wondering ...
2
votes
1answer
209 views

Get nodes that are participating in any cycle in a graph

I have a problem that states the following : Given a cyclic graph , output for each node if the node removes all cycles in the graph. The most trivial way to do this is using a Union-find ...
1
vote
0answers
48 views

Proving that a BST with N>=1 nodes will have log(N+1) levels

I am trying to prove by induction the following theorem: Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels. I've ...
3
votes
1answer
119 views

Is there an efficient method to store large DAGs?

I have a DAG representing strict partial order where each node is an assignment of variables $V$ to their values $v$. Each arc $(u,w)$ represents a change in one variable value such that $u\succ w$. ...
11
votes
1answer
548 views

How many max heaps are there?

How many different max-heaps can I form using a list of $n$ integers. Example: list [1,2,3,4] and max-heap is 4 3 2 1 or ...
3
votes
1answer
470 views

Practical applications of disjoint set datastructure

I know that the disjoint set datastructure is used to keep track of the connected components of an undirected graph when the edges are added to the graph dynamically . I also know that is is used in ...
3
votes
2answers
531 views

How can I prove that a complete binary tree has $\lceil n/2 \rceil$ leaves?

Given a complete binary tree with $n$ nodes. I'm trying to prove that a complete binary tree has exactly $\lceil n/2 \rceil$ leaves. I think I can do this by induction. For $h(t)=0$, the tree is ...
10
votes
2answers
1k views

Proving a binary tree has at most $\lceil n/2 \rceil$ leaves

I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction? For people who were following in the ...