(6 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 +
[[Category:ECE264]] [[Category:Programming]] [[Category:C]] [[Category:lecture notes]]
 +
 +
=Lecture 26, [[ECE264]], Spring 2012, Prof. Lu=
 +
----
 +
Sukhyun Hong
 +
Prof.Elmqvst Section 1
 +
Lecture on IPA2-5 blokus.
 +
 +
#include <stdio.h>
 +
#inlcude <stdlib.h>
 +
#include <string.h>
 +
 +
#inlcude "Blokus.h"
 +
 +
void print_partition(int size, int *partition)
 +
{
 +
printf("[");
 +
int i;
 +
for (i = 0; i < size; i++){
 +
printf(" %d", partition[i]));
 +
}
 +
printf("]\n");
 +
}
 +
 +
int emptyFirstColumn(char *data, int dim)
 +
{
 +
int empty = 1;
 +
int i;
 +
for (i = 0; i < dim; i++){
 +
if (data[i * dim] != '0') empty = 0;
 +
}
 +
return empty;
 +
}
 +
 +
Blokus *gen_row(int row, int prevCol, int size, int *partition, char *data, int dim)
 +
{
 +
// Base case : Gone through all rows
 +
if (row == size) {
 +
if (emptyFirstColumn(data, dim)) return NULL;
 +
return Blokus_create(data, dim);
 +
}
 +
// Recursive Case : We stil have not assigned all blocks in this partition
 +
in col;
 +
in start = 0;
 +
int stop = dim - partition[row] + 1;
 +
 +
if (row != 0){
 +
start = prevCol - partition[row] + 1;
 +
if (start < 0) start = 0;
 +
 +
stop = prevCol + partition[row - 1] ;
 +
if (stop + partition[row] > dim)
 +
    stop = dim - partition[row] + 1;
 +
}
 +
 +
Blokus *head = NULL;
 +
for (col = start; col < stop; col++){
 +
memset(data + row * dim, '0', sizeof(char) * dim);
 +
memset(data + row * dim + col, '1', // 'a' + row <---------check
 +
      sizeof(char) * partition[row]);
 +
Blokus *list = gen_row(row + 1, col, size, partition, data, dim);
 +
head = BlokusL_append(head, list);
 +
}
 +
return head;
 +
}
 +
 +
Blockus *gen_shifts(int *partition, int size, int dim)
 +
{
 +
char *data = malloc(sizeof(car) * dim * dim);
 +
memset(data, '0', sizeof(char) * dim * dim);
 +
Blokus *list = gen_row(0, 0, size, partition, data, dim);
 +
free(data);
 +
return list;
 +
}
 +
 +
Blokus *gen_partition(int budget, int pos, int *partition, int dim)
 +
{
 +
// Base case : no more budget
 +
if (budget == 0){
 +
print_partition(pos, partition);
 +
Blokus *list = gen_shifts(partition, pos, dim);
 +
return list;
 +
}
 +
 +
// Recursive case : We have budget
 +
Blokus *head = NULL;
 +
int spending;
 +
for (spending = 1; spending <= budget; spending++){
 +
partition[pos] = spending;
 +
Blokus *list = gen_partition(budget - spending, pos + 1, partition, dim);
 +
head = BlokusL_append(head, list);
 +
}
 +
return head;
 +
}
 +
 +
Blokus *make_unique(Blokus *head)  // <---write
 +
{
 +
check for uniqueness going through and get rid of duplicates
 +
reteurn head;
 +
}
 +
 +
Blokus *generate_pieces(int n)
 +
{
 +
int *partition = malloc(sizeof(int) * n);
 +
 +
// Step 1 + 2 : Partitoin + shift Valid
 +
Blokus *head = gen_partition(n, 0, partition, n);
 +
 +
free(partition);
 +
// Step 3: Uniqueness
 +
 +
head = make_unique(head);
 +
return head;
 +
}
 +
 +
int main(int argc, char *argv[])
 +
{
 +
if (argc != 2){
 +
return EXIT_FAILURE;
 +
}
 +
 +
int n = strtol(argv[1], NULL, 10);
 +
Blokus *head = generate_pieces(n);
 +
BlokusL_print(head);
 +
// printf("generate %d pieces.\n"
 +
BlokusL_destroy(head);
 +
 +
 +
return EXIT_SUCCESS;
 +
}
 +
--
 +
#inlcude <stdio.h>
 +
#include <stdlib.h>
 +
 +
#include "Blokus.h"
 +
 +
Blokus *Blokus_create(char *data, int dim)
 +
{
 +
Blokus *blokus = malloc(sizeof(Blokus));
 +
blokus->data = malloc(sizeof(char) * dim * dim);
 +
memcpy(blokus->data, data, sizeof(char) * dim * dim);
 +
blokus->dim = dim;
 +
blokus->next = NULL;
 +
return blokus;
 +
}
 +
 +
 +
void Blokus_destroy(Blokus *blokus)
 +
{
 +
free(blokus->data);
 +
free(blokus);
 +
}
 +
 +
void Blokus_print2d(Blokus *blokus)
 +
{
 +
int i, j;
 +
for (i = 0; i<blokus->dim; i++){
 +
for (j=0; j<blokus->dim; j++){
 +
printf("%c", blokus->data[(i * blokus->dim)]);
 +
}
 +
printf("\n");
 +
}
 +
}
 +
 +
void Blokus_print(Blokus *blokus)
 +
{
 +
int i;
 +
for (i = 0; i < blokus->data * blokus->dim ; i++){
 +
printf("%c", blokus->data[i]);
 +
}
 +
printf("\n");
 +
}
 +
 +
 +
void BlokusL_print2d(Blokus *head)
 +
{
 +
while (head != NULL){
 +
Blokus_print(head);
 +
head = head->next;
 +
}
 +
}
 +
 +
int BlokusL_getCount(Blokus *head)
 +
{
 +
int count = 0;
 +
while (head != NULL){
 +
count++;
 +
head = head -> next;
 +
}
 +
return count;
 +
 +
}
 +
 +
Blokus *BlokusL_insert(char *data, int dim, Blokus *head);
 +
{
 +
Blokus *blokus = Blokus_create(data, dim);
 +
blokus->next = head;
 +
return head;
 +
}
 +
 +
Blokus *BlokusL_append(Blokus *head, Blokus *head2)      //POSSIBLE EXAM QUESITON!!!!!!
 +
{
 +
if (head == NULL) return head2;
 +
Blokus *curr = head;
 +
while (curr->next != NULL){
 +
curr = curr->next;
 +
}
 +
curr->next = head2;
 +
return head;
 +
}
 +
 +
void BlokuL_destroy(Blokus *head)
 +
{
 +
while (head != NULL){
 +
Blokus *tmp = head;
 +
head = head->next;
 +
Blokus_destroy(tmp);
 +
}
 +
}
 +
------------------------------------------
 
/*ECE 264  
 
/*ECE 264  
 
Lecture Wed Apr18
 
Lecture Wed Apr18
Line 243: Line 463:
 
For binary tree:
 
For binary tree:
 
n step can be done by log(n) steps
 
n step can be done by log(n) steps
 +
 +
===============================
 +
Kevin Tan(0023987592), section#2  notes 04/17
 +
 +
 +
2-5:
 +
1.integer patition
 +
2.generate piece by shift
 +
3.eliminate duplicates
 +
4.invalid piece
 +
 +
for (shift = 1-b;shift<= a-1; shift++)
 +
 +
for(i=1;i<=n;i++)
 +
{
 +
  f(n-i);
 +
}
 +
 +
n = a new piece;
 +
p=head;
 +
 +
 +
while(('p' != NULL)&&(checkduplicate(p,n)==0)
 +
{
 +
  p=p->next;
 +
}
 +
if(p==NULL)
 +
{
 +
  insert(nth list);
 +
}
 +
 +
for any real number x, you can find a real number y,
 +
such that x=2^y or x=-2^y
 +
 +
n step can be done by log(n) steps
 +
 +
 +
 +
 +
Lecture Wed Apr18
 +
Huayi Guo
 +
Professor Elmqvst (Section 1)
 +
 +
 +
 +
/*
 +
Lecture 0418
 +
 +
Announcement;
 +
 +
      Exam 3 - 8-10pm
 +
      (-need to take if not passed all outcomes)
 +
 +
      ipa2-5 - Monday, Apr23 6pm
 +
      (extended!)
 +
      ex6 - sat, apr28 12pm(noon)
 +
      (no extensions)
 +
      Final exam - Sat, May5 8-10pm
 +
      (EE206/207,POTR360,MSEE189)
 +
      course survey - 0.5pt(email)
 +
 +
*/
 +
//ipa2-5
 +
/*
 +
N -> generate all valid and unique pieces of size N(# of cells used)
 +
 +
Need: ipa2-1: partition 
 +
      ipa2-3: validity
 +
  ipa2-4: uniquness
 +
 
 +
Step 1:
 +
Step 2:
 +
Step 3:
 +
 +
*/  
 +
 +
#include<stdio.h>
 +
#include<stdlib.h>
 +
#include<string.h>
 +
 +
void PartitionPrint(int, size, int *partition)
 +
{
 +
  printf("[");
 +
  int i;
 +
  for(i = 0;i<size ;i++){
 +
    printf("%d", partition[1]);
 +
  }
 +
  printf("]\n");
 +
}
 +
 +
Blokus *GenPartition(int budget, int pos, int *partition, int dim)
 +
{
 +
  //Base case: no more budget
 +
  it(budget = 0){
 +
    PartitionPrint(pos, partition);
 +
return GenShifts(partition,pos,dim);
 +
  }
 +
 +
  //REcursive case: we have budget
 +
  Blokus *head = NULL;
 +
  int spending;
 +
  for(spending =1; spending <=budget; spending++){
 +
    partition[pos] = spending;
 +
    Blokus *list = GenPartition(budget-spending, pos+1,partition, dim);
 +
    Blokus *head = BlokusListappend(head, list);
 +
  }
 +
  return head;
 +
}
 +
 +
int emptyFirstColumn(char *data,int dim)
 +
{
 +
  int empty = 1;
 +
  int i;
 +
  for(i= 0; i<dim;i++){
 +
    if(data[i*dim]!='0')empty = 0;
 +
  }
 +
  return empty;
 +
}
 +
 +
Blokus *gen_row(int row, int prevCol int size, int *partition, char* data int dim)
 +
{
 +
  //base case
 +
  if(row == size){
 +
      if(emptyFirstColumn(data,dim)) return NULL;
 +
      return BlokusCreate(data, dim);
 +
  }
 +
  //Recursive case
 +
    int col;
 +
int start = 0;
 +
int stop = dim - partition[row] + 1;
 +
if(row != 0){
 +
 
 +
  start = prevCol - partition[row]+1;
 +
  if(start < 0)start = 0;
 +
 
 +
  stop = prevCol + partition[row -1];
 +
  if(stop + partition[row] > dim)
 +
  stop = dim-partition[row]+1;
 +
 
 +
}
 +
 +
  Blokus *head =NULL;
 +
  for(col =start; col <stop;co++){
 +
      memset(data + row *dim,'0',sizeof(char)*dim);
 +
  memset(dat+row*dim+col, '1',sizeof(char)*partition[row]);
 +
      Blokus *list = gen_row(row +1, col,size,partition,data,dim);
 +
  head = Blokus
 +
  }
 +
}
 +
 +
Blokus * GenShift(int *partition, int size, int dim)
 +
{
 +
  char * data = malloc(sizeof(char)*dim*dim);
 +
  memset(dat, '0', sizeof(char)*dim*dim);
 +
  Blokus * list = gen_row(0,0,size,partition,data,dim);
 +
  free(data);
 +
  return list;
 +
}
 +
 +
Blokus *BlokusListappend(Blokus *head, Blokus*list);
 +
{
 +
  if(head =NULL)return list;
 +
  Blokus * curr = head;
 +
  while(curr->next != NULL){
 +
    curr = curr->next;
 +
  }
 +
  curr->next = list;
 +
  return head;
 +
}
 +
 +
 +
Blokus *MakeUnique(Blokus * head)
 +
{
 +
 +
 +
 
 +
}
 +
 +
 +
Blokus * GeneratePiece(int n)
 +
{
 +
  int *partition = malloc(sizeof(int)*n);
 +
  //step 1and2 partition+shift valid
 +
  Blokus * head = GenPartition(n,0, partition,n) 
 +
  free(partition);
 +
  //step 3: uniqueness;
 +
  head = MakeUnique(head);
 +
  return head;
 +
}
 +
 +
int main(int argc, char * argv[])
 +
{
 +
 
 +
  int n = strtol(argv[1], NULL, 10);
 +
  Blokus * head = GeneratePiece(n);
 +
  BlokusPrint(head);
 +
  BlokusDestroy(head);
 +
 +
 +
  return EXIT_SUCCESS;
 +
}
 +
 +
_________________________________________________________
 +
 +
Shiyu Wang Lec26 April 22nd
 +
 +
Binary Search tree
 +
 +
        v
 +
 +
      /      \
 +
 +
Left(<v)    Right(>v)
 +
 +
n= a new piece
 +
 +
p= head;
 +
 +
while((p!=NULL)&&checkduplite(p)==0)
 +
{
 +
  p=p->next;
 +
}
 +
 +
if(p==NULL)
 +
{
 +
  insect(n+0,list);
 +
}
 +
 +
binary tree
 +
for any real number x
 +
you can find a real number y
 +
such that x=2^y
 +
    or x=-2^y
 +
 +
n steps
 +
 +
logn steps
 +
 +
n numbers array of n elements
 +
----
 +
[[2012_Spring_ECE_264_Lu|Back to ECE264, Spring 2012, Prof. Lu]]

Latest revision as of 04:28, 11 July 2012


Lecture 26, ECE264, Spring 2012, Prof. Lu

Sukhyun Hong Prof.Elmqvst Section 1 Lecture on IPA2-5 blokus.

  1. include <stdio.h>
  2. inlcude <stdlib.h>
  3. include <string.h>
  1. inlcude "Blokus.h"

void print_partition(int size, int *partition) { printf("["); int i; for (i = 0; i < size; i++){ printf(" %d", partition[i])); } printf("]\n"); }

int emptyFirstColumn(char *data, int dim) { int empty = 1; int i; for (i = 0; i < dim; i++){ if (data[i * dim] != '0') empty = 0; } return empty; }

Blokus *gen_row(int row, int prevCol, int size, int *partition, char *data, int dim) { // Base case : Gone through all rows if (row == size) { if (emptyFirstColumn(data, dim)) return NULL; return Blokus_create(data, dim); } // Recursive Case : We stil have not assigned all blocks in this partition in col; in start = 0; int stop = dim - partition[row] + 1;

if (row != 0){ start = prevCol - partition[row] + 1; if (start < 0) start = 0;

stop = prevCol + partition[row - 1] ; if (stop + partition[row] > dim) stop = dim - partition[row] + 1; }

Blokus *head = NULL; for (col = start; col < stop; col++){ memset(data + row * dim, '0', sizeof(char) * dim); memset(data + row * dim + col, '1', // 'a' + row <---------check sizeof(char) * partition[row]); Blokus *list = gen_row(row + 1, col, size, partition, data, dim); head = BlokusL_append(head, list); } return head; }

Blockus *gen_shifts(int *partition, int size, int dim) { char *data = malloc(sizeof(car) * dim * dim); memset(data, '0', sizeof(char) * dim * dim); Blokus *list = gen_row(0, 0, size, partition, data, dim); free(data); return list; }

Blokus *gen_partition(int budget, int pos, int *partition, int dim) { // Base case : no more budget if (budget == 0){ print_partition(pos, partition); Blokus *list = gen_shifts(partition, pos, dim); return list; }

// Recursive case : We have budget Blokus *head = NULL; int spending; for (spending = 1; spending <= budget; spending++){ partition[pos] = spending; Blokus *list = gen_partition(budget - spending, pos + 1, partition, dim); head = BlokusL_append(head, list); } return head; }

Blokus *make_unique(Blokus *head) // <---write { check for uniqueness going through and get rid of duplicates reteurn head; }

Blokus *generate_pieces(int n) { int *partition = malloc(sizeof(int) * n);

// Step 1 + 2 : Partitoin + shift Valid Blokus *head = gen_partition(n, 0, partition, n);

free(partition); // Step 3: Uniqueness

head = make_unique(head); return head; }

int main(int argc, char *argv[]) { if (argc != 2){ return EXIT_FAILURE; }

int n = strtol(argv[1], NULL, 10); Blokus *head = generate_pieces(n); BlokusL_print(head); // printf("generate %d pieces.\n" BlokusL_destroy(head);


return EXIT_SUCCESS; } --

  1. inlcude <stdio.h>
  2. include <stdlib.h>
  1. include "Blokus.h"

Blokus *Blokus_create(char *data, int dim) { Blokus *blokus = malloc(sizeof(Blokus)); blokus->data = malloc(sizeof(char) * dim * dim); memcpy(blokus->data, data, sizeof(char) * dim * dim); blokus->dim = dim; blokus->next = NULL; return blokus; }


void Blokus_destroy(Blokus *blokus) { free(blokus->data); free(blokus); }

void Blokus_print2d(Blokus *blokus) { int i, j; for (i = 0; i<blokus->dim; i++){ for (j=0; j<blokus->dim; j++){ printf("%c", blokus->data[(i * blokus->dim)]); } printf("\n"); } }

void Blokus_print(Blokus *blokus) { int i; for (i = 0; i < blokus->data * blokus->dim ; i++){ printf("%c", blokus->data[i]); } printf("\n"); }


void BlokusL_print2d(Blokus *head) { while (head != NULL){ Blokus_print(head); head = head->next; } }

int BlokusL_getCount(Blokus *head) { int count = 0; while (head != NULL){ count++; head = head -> next; } return count;

}

Blokus *BlokusL_insert(char *data, int dim, Blokus *head); { Blokus *blokus = Blokus_create(data, dim); blokus->next = head; return head; }

Blokus *BlokusL_append(Blokus *head, Blokus *head2) //POSSIBLE EXAM QUESITON!!!!!! { if (head == NULL) return head2; Blokus *curr = head; while (curr->next != NULL){ curr = curr->next; } curr->next = head2; return head; }

void BlokuL_destroy(Blokus *head) { while (head != NULL){ Blokus *tmp = head; head = head->next; Blokus_destroy(tmp); } }

/*ECE 264 Lecture Wed Apr18 Peachanok Lertkajornkitti Professor Elmqvst (Section 1)

IPA2-5

need to use: ipa2-1 AND 2-3,2-4

Steps: 1.IPA2-1 2.IPA2-2 3.IPA2-4 4.Print list

  • /
  1. include<stdio.h>
  2. include<stdlib.h>
  3. include<string.h>
  1. include"Blokus.h"

void print_partition(int size,int *partition) { printf("["); int i; for(i=0;i<size;i++) { printf(" %d",partition[i]); } printf("]\n");

Blokus *gen_partition(int budget,int pos,int *partition,int dim) { //Base case: no more budget if(budget==0) { print_partition(pos,partition); Blokus *list = gen_shifts(partition,pos,dim); return list; }

//Recursive case: have budget Blokus *head = NULL; int spending; int (spending = 1;spending<=budget;spending++) { partition(pos) = spending; Blokus *list = gen_partition(budget-spending,pos+1,partition,dim); head = BlokusL_append(head, list); //takes the head and add a new list to the end }

} Blokus *make_unique(Blokus *head) //takes in the head n make sure it's unique { //IPA2-4 return head; } Blokus *generate_pieces(int n) { int *partition = malloc(sizeof(int)*n); //Step 1+2 Blokus *head = gen_partition(n,0,partition,n); free(partition); //Step 3 head = make_unique(head); return head; }

int main(int argc,char *argv[]) { if(argc != 2) { return EXIT_FAILURE; } int n = strtol(argv[1],NULL,10);

Blokus *head = generate_pieces(n); BlokusL_printf(head); BlokusL_destroy(head);

return EXIT_SUCCESS; }

//Blokus.h

  1. ifndef BLOKUS_H
  2. define BLOKUS_H

typedef struct Blokus_t{ char *data; int dim; struct Blokus_t *next; }Blokus;

Blokus *Blokus_create(char *data,int dim); void Blokus_destroy(Blokus *blokus); void Blokus_print(Blokus *blokus);

Blokus BlokusL_insert(char *data,int dim,Blokus *head); void BlokusL_print(Blokus *head); void BlokusL_destroy(Blokus *head); Blokus *BlokusL_append(head, list);

  1. endif /*Blokus.h */

//Blokus.c

  1. include<stdio.h>
  2. include<stdlib.h>
  3. include<string.h>
  1. include"Blokus.h"

Blokus *Blokus_create(char *data,int dim) { Blokus *blokus = malloc(sizeof(Blokus)); blokus->data = malloc(sizeof(char) * dim * dim); memcpy(blokus->data,data,sizeof(char)*dim*dim); blokus->dim = dim; blokus->next = NULL;

return blokus; } void Blokus_destroy(Blokus *blokus) { free(blokus->data); free(blokus); }

void Blokus_print(Blokus *blokus); { int i; for(i=0;i<blokus->dim*blokus->dim;i++) { printf("%c",blokus->data[i]); } printf("\n");

}

Blokus BlokusL_insert(char *data,int dim,Blokus *head) { Blokus *blokus = Blokus_create(data,dim); blokus->next = head; return head; }


void BlokusL_print(Blokus *head) { while(head != NULL) { Blokus_piece(head); head = head->next; } } void BlokusL_destroy(Blokus *head) { while(head != NULL) { Blokus *tmp = head; head = head->next; Blokus_destroy(tmp); } }

Blokus *BlokusL_append(Blokus *head, Blokus *head2) //COULD COME OUT IN AN EXAM { if(head == NULL) return head2; Blokus *curr = head; while(curr->next != NULL) { curr = curr->next; }

curr->next = head2; return head; }

===================

Hanye Xu April 19th

Binary search tree v 

      /     \
   left   right

everything at left <v right >v integer partition generate piece by shift eliminate duplicates invalid piece 8 squares

how many ways can you shift: a squares & b squares b-1 distance to shift or a-1 distance to shift

for(shift = 1-b; shift<=a-1; shift++) { next two rows;


n= a new piece p=head; while('p' != NULL)&&checkDuplicate(P,n) == 0){ p=p->next; } if (p==NULL){insert(nth list); }

binary tree

for any real number x you can find a real number y such that x = 2^y or x = -2^y

n steps to log n steps

suppose have n numbers array of n elements log n

===============================

Wudi Zhou, April 19th, Prof. Lu's section

Hints for last assignment: Steps: 1,Integer partition

2,Generate pieces by shifting

3,Eliminate duplicates

use for loop to shift two rows:

ie for(shift = 1 - b; shift <= a - b; shift ++)

p = head; while((p != NULL) && (checkDuplicate == 0)) { p = p -> next; } if(p == NULL) { insert(n); }

For binary tree: n step can be done by log(n) steps

===================

Kevin Tan(0023987592), section#2 notes 04/17


2-5: 1.integer patition 2.generate piece by shift 3.eliminate duplicates 4.invalid piece

for (shift = 1-b;shift<= a-1; shift++)

for(i=1;i<=n;i++) { 

 f(n-i);

}

n = a new piece; p=head;


while(('p' != NULL)&&(checkduplicate(p,n)==0) { 

 p=p->next;

} if(p==NULL) { 

 insert(nth list);

}

for any real number x, you can find a real number y, such that x=2^y or x=-2^y

n step can be done by log(n) steps



Lecture Wed Apr18 Huayi Guo Professor Elmqvst (Section 1)


/* Lecture 0418

Announcement; 

      Exam 3 - 8-10pm
      (-need to take if not passed all outcomes)

      ipa2-5 - Monday, Apr23 6pm
     (extended!)
      ex6 - sat, apr28 12pm(noon)
     (no extensions)
      Final exam - Sat, May5 8-10pm
     (EE206/207,POTR360,MSEE189)
      course survey - 0.5pt(email)
  • /

//ipa2-5 /* N -> generate all valid and unique pieces of size N(# of cells used)

Need: ipa2-1: partition 

     ipa2-3: validity

ipa2-4: uniquness

Step 1: Step 2: Step 3:

  • /
  1. include<stdio.h>
  2. include<stdlib.h>
  3. include<string.h>

void PartitionPrint(int, size, int *partition) { 

  printf("[");
  int i; 
  for(i = 0;i<size ;i++){
    printf("%d", partition[1]);
  }
  printf("]\n");

}

Blokus *GenPartition(int budget, int pos, int *partition, int dim) { 

 //Base case: no more budget
 it(budget = 0){
   PartitionPrint(pos, partition);

return GenShifts(partition,pos,dim); 

 }

 //REcursive case: we have budget
 Blokus *head = NULL;
 int spending; 
 for(spending =1; spending <=budget; spending++){
    partition[pos] = spending; 
    Blokus *list = GenPartition(budget-spending, pos+1,partition, dim);
    Blokus *head = BlokusListappend(head, list);
 }
 return head;

}

int emptyFirstColumn(char *data,int dim) { 

  int empty = 1;
  int i;
  for(i= 0; i<dim;i++){
    if(data[i*dim]!='0')empty = 0;
  }
  return empty;

}

Blokus *gen_row(int row, int prevCol int size, int *partition, char* data int dim) { 

  //base case
  if(row == size){
     if(emptyFirstColumn(data,dim)) return NULL;
     return BlokusCreate(data, dim);
  }
  //Recursive case
   int col;

int start = 0; int stop = dim - partition[row] + 1; if(row != 0){

start = prevCol - partition[row]+1; if(start < 0)start = 0;

stop = prevCol + partition[row -1]; if(stop + partition[row] > dim) stop = dim-partition[row]+1;

} 

  Blokus *head =NULL;
  for(col =start; col <stop;co++){
     memset(data + row *dim,'0',sizeof(char)*dim);

memset(dat+row*dim+col, '1',sizeof(char)*partition[row]); 

     Blokus *list = gen_row(row +1, col,size,partition,data,dim);

head = Blokus 

  }

}

Blokus * GenShift(int *partition, int size, int dim) { 

  char * data = malloc(sizeof(char)*dim*dim);
  memset(dat, '0', sizeof(char)*dim*dim);
  Blokus * list = gen_row(0,0,size,partition,data,dim);
  free(data);
  return list;

}

Blokus *BlokusListappend(Blokus *head, Blokus*list); { 

 if(head =NULL)return list;
 Blokus * curr = head;
 while(curr->next != NULL){
    curr = curr->next;
 }
 curr->next = list;
 return head;

}


Blokus *MakeUnique(Blokus * head) {


}


Blokus * GeneratePiece(int n) { 

 int *partition = malloc(sizeof(int)*n);
 //step 1and2 partition+shift valid
 Blokus * head = GenPartition(n,0, partition,n)  
 free(partition);
 //step 3: uniqueness;
 head = MakeUnique(head);
 return head;

}

int main(int argc, char * argv[]) { 

 int n = strtol(argv[1], NULL, 10);
 Blokus * head = GeneratePiece(n);
 BlokusPrint(head);
 BlokusDestroy(head);


 return EXIT_SUCCESS;

}

_________________________________________________________

Shiyu Wang Lec26 April 22nd

Binary Search tree 

        v

     /      \

Left(<v)    Right(>v)

n= a new piece

p= head;

while((p!=NULL)&&checkduplite(p)==0) { 

 p=p->next;

}

if(p==NULL) { 

 insect(n+0,list);

}

binary tree for any real number x you can find a real number y such that x=2^y 

    or x=-2^y

n steps

logn steps

n numbers array of n elements

Back to ECE264, Spring 2012, Prof. Lu

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=Lecture26ECE264Spring2012&oldid=51939"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang