(2 intermediate revisions by 2 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 482: Line 702:
  
 
n numbers array of n elements
 
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

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett