Algorithm analysis and structure identification

Question

public class Structure <E extends Comparable<? super E>>{
  private E[] d;

  public Structure() { d = getArray(1); }

  public void show() { show(0); }

  private void show(int p){
    if( p < d.length && d[p] != null) {
      show(r(p));
      show(l(p));
      System.out.print(d[p] + " ");
    }
  }
  public void add(E obj) {
    int p = getPos(obj);
    if(p >= d.length)
      resize();
    d[p] = obj;
  }

  public boolean present(E obj){
    int p = getPos(obj);
    return p < d.length && d[p] != null;
  }

  private int getPos(E obj){
    int p = 0;
    while(p < d.length && d[p] != null){
      int dir = <*1>;
      if(dir < 0)
        p = l(p);
      else if(dir >0)
        p = r(p);
      else
        return p;
    }
    return p;
  }
  private E[] getArray(int size) {
    return (E[]) new Comparable[size];
  }

  private void resize(){
    E[] temp = getArray(d.length*2 + 1);
    for( int i = 0; i < d.length; i++)
      temp[i] = d[i];
    d = temp;
  }

  private int l(int i) { return 2 * i + 1;}
  private int r(int i) { return 2 * i + 2;}
}

Take that data structure. What is it? I think it's a binary search tree, but I'm pretty sure it's that or a max heap. I'm largely leaning BST, though.

public void fillCol (int n, Collection<Integer> col){
    for(int i = 0; i < n; i++)
    col.add (i);
}

What is the big O for that method if col is a linked list? I think it's O (N).

And is col a tree set? I think it's O (N log N).

public void sort (List<Double> data){
  int lim = data.size();
  for(int i = 0; i < lim; i++){
    int m = i;
    for(int j = i + 1; j < lim; j++)
      if(data.get(j) < data.get(m) )
        m = j;
    data.set( i, data.set(m, data.get(i)));
  }
}

and big o for each type of list. I think it's O (N²) for ArrayList and O (N³) for Linked list.

A class that represents a graph uses an adjacency matrix to represent the connections between verticies. What are the space requirements for a graph that contains N nodes with an average of M connections per node?

I think it's O (N²)

Please help! Confirm if I'm right, or correct me if I'm wrong.

what does int dir = <*1>; mean?

andrew cooke
– andrew cooke

2012-04-27 16:22:30 +00:00
Commented Apr 27, 2012 at 16:22 — andrew cooke
– andrew cooke, Commented Apr 27, 2012 at 16:22

user1277476 · Accepted Answer · 2012-04-26 23:14:37Z

2

It looks like a (not-necessarily-balanced) binary tree, implemented in a manner similar to how a binary heap is often done - in an array where the children of i are 2i and 2i+1.

Someone should've documented what they were doing better.

I agree with your assessment of fillCol.

That sort callable seems like an unrelated question, and yes it does look O(n^2) with a normal data structure.

answered Apr 26, 2012 at 23:14

user1277476

2,90714 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Algorithm analysis and structure identification

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related