Recursos-LCC

Um arquivo de todo material que consegui reunir, pertinente ao curso de LCC da UM.

View on GitHub

1 > Min-heaps


1.

a) 2 * i + 1
b) 2 * i + 2
c) (i - 1) / 2
d) pai(n) + 1

2.

void bubbleUp (int i, int h[]) {
  while(i > 0 && h[i] < h[parent(i)]) {
    swap(h, i, parent(i));
    i = parent(i);
  }
}
// one-liner
void bubbleUp (int i, int h[]) {
  for(; i > 0 && h[i] < h[parent(i)]; swap(h, i, parent(i)), i = parent(i));
}

3.

void bubbleDown (int i, int h[], int N) {
  int m;
  while(left(i) < N) {
    m = (right(i) < N && h[right(i)] < h[left(i)]) ? right(i) : left(i);
    
    if (h[m] > h[i]) break;
    
    swap(h, i, m);
    i = m;
  }
}

4

#define Max 100
typedef struct pQueue {
  int valores [Max];
  int tamanho;
} PriorityQueue;

void empty (PriorityQueue *q) {
  q->tamanho = 0;
}

int isEmpty (PriorityQueue *q) {
  return (q->tamanho == 0);
}

int add (int x, PriorityQueue *q) {
  if(q->tamanho == Max) return 1;
  
  q->valores[q->tamanho] = x;
  bubbleUp(q->tamanho, q->valores);
  q->tamanho++;
  
  return 0;
}

int remove (PriorityQueue *q, int *rem) {
  rem = q->valores[0];
  q->valores[0] = q->valores[q->tamanho - 1];
  q->tamanho--;
  bubbleDown(0, q->valores, q->tamanho);
}

5.

// top-down
void heapify (int v[], int N) {
  for (int i = 1; i < N; i++)
    bubbleUp (i, v);
}

// bottom-up
void heapify (int v[], int N) {
  for(int i = parent(N-1); i >= 0; i--)
    bubbleDown(i, v, N);
}

// falta determinar complexidade

6.

void ordenaHeap(int h[], int N) {
  for (int i = 1; i < N; i++) {
    swap(h, 0, N-i);
    bubbleDown(i, h, N-i);
  }
}

7.

Assumindo add = O(log(N)) e remove = O(log(N)), o pior caso seria dar os elemento de forma crescente. Sendo assim efetuados N add’s e (N-k) remove’s.
O(N*log(k) + (N-k)*log(k)) = O(N*log(k))
No caso de uma lista ligada a inserção na cauda seria O(k) e a remoção da cabeça seria O(1), o pior caso seria dar os elemento de forma crescente. Sendo assim efetuados N insert’s e (N-k) remove’s.
O(N*k + (N-k)) = O(N*k)

2 > Tabelas de Hash

Vamos por isso assumir a existência de uma função unsigned hash (char *chave), como por exemplo a seguinte (http://www.cse.yorku.ca/~oz/hash.html)

unsigned hash(char *str){
  unsigned hash = 5381;
  int c;
  
  while (c = *str++)
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
  
  return hash % Size; // alterado aqui por conveniência
}


2.1 > Chaining

#define Size 11

typedef struct nodo {
  char *chave;
  int ocorr;
  struct nodo *prox;
} Nodo, *THash [Size];


1.

void initEmpty (THash t) {
  for (int i = 0; i < Size; i++)
    t[i] = NULL;
}

2.

void add (char *s, THash t) {
  unsigned hashed = hash(s);
  Nodo* ptr, ant = NULL;
  
  for (ptr = t[hashed]; ptr != NULL; ptr = ptr->prox) {
    if (!strcmp(ptr->chave, s)) {
      ptr->ocorr++;
      return;
    }
    
    ant = ptr;
  }
  
  ptr = calloc(sizeof(Nodo));
  strcpy(ptr->chave, s);
  ptr->ocorr = 1;
  ptr->prox = NULL;

  if (ant != NULL)
    ant->prox = ptr;
  else
    t[hashed] = ptr;
}

3.

int lookup (char *s, THash t) {
  unsigned hashed = hash(s);
  
  for (Nodo* ptr = t[hashed]; ptr != NULL; ptr = ptr->prox)
    if (!strcmp(ptr->chave, s))
      return ptr->ocorr;
  
  return 0;
}

4.

int remove (char *s, THash t) {
  unsigned hashed = hash(s);
  Nodo* ptr, ant = NULL;
  
  for (ptr = t[hashed]; !strcmp(ptr->chave, s); ptr = ptr->prox) {
    if (ptr == NULL) return -1;
    ant = ptr;
  }
  
  ptr->ocorr--;
      
  if (ptr->ocorr == 0) {
    if (ant != NULL)
      ant->prox = ptr->prox;
    else
      t[hashed] = ptr->prox;

    free(ptr);
  }

  return 0;
}



2.2 > Open Addressing

#define Size 11
#define Free 0
#define Used 1
#define Del 2

typedef struct bucket {
  int status; // Free | Used | Del
  char *chave;
  int ocorr;
} THash [Size];


1.

int where (char *s, THash t) {
  int c, hash = 5381;

  while (c = *str++)
    hash *= 33 + c;

  return hash % Size;
}

2.

// a)
void initEmpty(THash t) {
  for (int i; i < Size; i++) {
    t[i].status = Free;
    t[i].chave = NULL;
    t[i].ocorr = 0;
  }
}

// b)
void add (char *s, THash t) {
  int i, pos, hashed;
  pos = hashed = where(s);

  for (i = 1; t[pos].status > Free && i <= Size; i++) {
    if(!strcmp(t[pos].chave, s)) {
      (t[pos].ocorr)++;
      return;
    }

    pos = (hashed+i) % Size;
  }

  if (t[pos].status == Free) {
    t[pos].status = Used;
    strcpy(t[pos].chave, s);
    t[pos].ocorr = 1;
  } else {
    printf("
      Erro na inserção:\n
      Table cheia ou a precisar de garbage collection\n
    ");
  }
}

// c)
int lookup (char *s, THash t) {
  int i, pos, hashed;
  pos = hashed = where(s);
  
  for (i = 1; t[pos].status > Free && i <= Size; i++) {
    if(!strcmp(t[pos].chave, s)) {
      return t[pos].ocorr;
    }

    pos = (hashed+i) % Size;
  }
  
  return -1;
}

// d)
int remove (char *s, THash t) {
  int i, pos, hashed;
  pos = hashed = where(s);

  for (i = 1; strcmp(t[pos].chave, s); i++) {
    if(t[pos].status == Free || i == Size)
      return 1;

    pos = (hashed+i) % Size;
  }

  (t[pos].ocorr)--;

  if (t[pos].ocorr == 0) {
    t[pos].status = Del;
    t[pos].chave = NULL;
  }

  return 0;
}

3.

void copy (char *s, int ocorr, THash t) {
  int i;

  for (i = where(s); t[i].status == Used; i = (i+1) % Size);

  t[i].status = Used;
  strcpy(t[i].chave, s);
  t[i].ocorr = ocorr;
}

int garb_collection (THash t) {
  char *keys[Size];
  int i, c = 0, ocorrs[Size];

  for(i = 0; i < Size; i++)
    if (t[i].status == Used) {
      strcpy(keys[c], t[i].chave);
      ocorrs[c] = t[i].ocorr;
      c++;
    }

  initEmpty(t);

  for (i = 0; i < c; i++) {
    copy(keys[i], ocorrs[i], t);
  }

  return 0;
}

4.

typedef struct bucket {
  int status; // Free | Used | Del
  char *chave;
  int ocorr;
  int colided;
} THash [Size];

// Não percebo pelo enunciado qual é a forma que devemos contar as colisões