task 8

#include<stdio.h>
#include<stdlib.h>
//#include"list.h"

// List element: a list is a chain of these
typedef struct element
{
  int val;
  struct element* next;
} element_t;
// List header - keep track of the first and last list elements
typedef struct list
{
  element_t* head;
  element_t* tail;
} list_t;

list_t* list_create( void )
{
  list_t* l =  malloc( sizeof(list_t) );
  if(l){
l->head = NULL;
l->tail = NULL;
  }
}

void list_destroy( list_t* list )
{
  element_t* el = list->head;
  while( el )
    {
      element_t* next = el->next;
      free( el );
      el = next;
    }

  free( list );
}
element_t* element_create( int i )
{
  element_t* el = malloc( sizeof(element_t) );
  if( el )
    {
      el->val = i;
      el->next = NULL;
    }
  return el;
}

int list_append( list_t* list, int i )
{
  element_t* el = element_create( i );
  if( el == NULL )
    return 1;

  if( list->head == NULL )
    list->head = el;

  if( list->tail )
    list->tail->next = el;

  list->tail = el;
  return 0;
}

void list_print( list_t* list )
{
  printf( "{" );

  for( element_t* el = list->head;
       el;
       el = el->next )
    printf( " %d", el->val );

  printf( " }\n" );
}

int arrLength(list_t* list)
{
  if(list->head == NULL) return 0;

  element_t* el = list->head;
  int num = 1;
  while(el->next != NULL){
    num++;
    el = el->next;
  }
  return num;
}

void swap(int a[], int i, int j) //swaps values using their indices
{
  int x = a[i];
  a[i] = a[j];
  a[j] = x;
}

/*int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high- 1; j++)
    {
        // If current element is smaller than or
        // equal to pivot
        if (arr[j] <= pivot)
        {
            i++;    // increment index of smaller element
            swap(arr, i, j);
        }
    }
    swap(arr, (i + 1), high);
    return (i + 1);
}*/

int partition(int list[], int low, int high)
{
  int pivot = list[low];
  int pi = low; //pivot starting index
  int i = low; int j = high;
  while(i!=j){
    if(pi == i){
      if(list[j] < pivot){
        swap(list,i,j);
        pi = j;
        i++;
      } else { //when the j->val is greater than pivot
        j--;
      }
    }else{//when the pivot index is at the j value instead
      if(list[i] > pivot){
        swap(list, i, j);
        pi = i;
        j--;
      } else {
        i++;
      }
    }
  }
  return pi;
}

void quicksort(int list[], int low, int high)
{
  if(low < high){
    int pivot = partition(list, low, high);
    quicksort(list, low, pivot-1);
    quicksort(list, pivot+1, high);
  }
}

void list_sort(list_t* list)
{
  int n = arrLength(list)-1;
  int* p = malloc(sizeof(int)*(n+1));
  //appends the elements the elements of the linked list to new array
  element_t* el = list->head;
  for(int i =0; i<=n; i++){
    p[i] = el->val;
    el = el->next;
  }
  //sorts the list
  quicksort(p, 0, n);
  //puts the elements back into linked list

  int k =0;
  //while(el)
  for(element_t* el1 = list->head; el1; (el1 = el1->next) && k++)
    el1->val = p[k];
    //k++;
}

int main()
{
  list_t* list = list_create();

  list_append(list, 3);
  list_append(list, 2);
  list_append(list, 8);
  list_append(list, 5);
  list_append(list, 7);

  list_sort(list);
  list_print(list);
  list_destroy(list);

  return 0;
}

quicksort!!!

#include<stdio.h>
#include<stdlib.h>
#include"list.h"

int arrLength(list_t* list)
{
  if(list->head == NULL) return 0;

  element_t* el = list->head;
  int num = 1;
  while(el->next != NULL){
    num++;
    el = el->next;
  }
  return num;
}

void swap(list_t* list, int i, int j)
{
  int x;
  x = list_index(list, i)->val;
  list_index(list, i)->val = list_index(list, j)->val;
  list_index(list, j)->val = x;
}

int partition(list_t* list, int low, int high)
{
  int pivot = list_index(list, low)->val;
  int i = low; int j = high;
  while(1){
    while(i<high){
      if(list_index(list, i)->val <= pivot){
        i++;
      }
    }
    do j--; while(list_index(list, j)->val > pivot);
    if( i>=j )break;
    swap(list, i, j);
  }
  swap(list, low, j);
  return j;
}

void quicksort(list_t* list, int low, int high)
{
  if(low<high){
    int pivot = partition(list, low, high);
    quicksort(list, low, pivot-1);
    quicksort(list, pivot+1, high);
  }
}

void list_sort(list_t* list)
{
  int n = arrLength(list)-1;
  quicksort(list, 0, n);
}

int main()
{
  list_t* list = list_create();

  list_append(list, 3);
  list_append(list, 2);
  list_append(list, 8);
  list_append(list, 5);
  list_append(list, 7);

  list_sort(list);

  return 0;
}

hellppppp

#include <stdio.h>
#include <stdlib.h>
// List element: a list is a chain of these
typedef struct element
{
  int val;
  struct element* next;
} element_t;
// List header - keep track of the first and last list elements
typedef struct list
{
  element_t* head;
  element_t* tail;
} list_t;

list_t* list_create( void )
{
  list_t* l =  malloc( sizeof(list_t) );
  if(l){
l->head = NULL;
l->tail = NULL;
  }
}

void list_destroy( list_t* list )
{
  element_t* el = list->head;
  while( el )
    {
      element_t* next = el->next;
      free( el );
      el = next;
    }    
 
  free( list );
}

element_t* element_create( int i )
{
  element_t* el = malloc( sizeof(element_t) );
  if( el )
    {
      el->val = i;
      el->next = NULL;
    }
  return el;
}

int list_append( list_t* list, int i )
{
  element_t* el = element_create( i );
  if( el == NULL )
    return 1;

  if( list->head == NULL )
    list->head = el;
 
  if( list->tail )
    list->tail->next = el;

  list->tail = el;
  return 0;
}

int list_prepend( list_t* list, int i )
{
  element_t* el = element_create( i );
  if( el == NULL )
    return 1;

  if( list->tail == NULL )
    list->tail = el;
 
  if( list->head )
    el->next = list->head;

  list->head = el;
 
  return 0;
}

element_t* list_index( list_t* list, unsigned int i )
{
  if( list->head == NULL )
    return NULL;
 
  element_t* el = list->head;
  unsigned int now = 0;
 
  while( now < i )
    {
      if( el->next == NULL )
return NULL;

      now++;
      el = el->next;
    }    
 
  return el;
}

int arrLength(list_t* list)
{
  if(list->head == NULL) return 0;

  element_t* el = list->head;
  int num = 1;
  while(el->next != NULL){
    num++;
    el = el->next;
  }
  return num;
}

void swap(list_t* list, int i, int j)
{
  int x;
  x = list_index(list, i)->val;
  list_index(list, i)->val = list_index(list, j)->val;
  list_index(list, j)->val = x;
}

int partition(list_t* list, int low, int high)
{
  int pivot = list_index(list, low)->val;
  int i = low; int j = high;
  while(1){
    do i++; while((i<high) &&(list_index(list, i)->val <= pivot) );
    do j--; while(list_index(list, j)->val > pivot);
    if( i>=j )break;
    swap(list, i, j);
  }
  swap(list, low, j);
  return j;
}

void quicksort(list_t* list, int low, int high)
{
  if(low<high){
    int pivot = partition(list, low, high);
    quicksort(list, low, pivot-1);
    quicksort(list, pivot+1, high);
  }
}

void list_sort(list_t* list)
{
  int n = arrLength(list)-1;
  quicksort(list, 0, n);
}

int main()
{
  list_t* list = list_create();

  list_append(list, 3);
  list_append(list, 2);
  list_append(list, 8);
  list_append(list, 5);
  list_append(list, 7);

  list_sort(list);

  return 0;
}

quicksort

#include<stdio.h>
#include<stdlib.h>
#include"list.h"

int arrLength(list_t* list)
{
  if(list->head == NULL) return 0;

  element_t* el = list->head;
  int num = 1;
  while(el->next != NULL){
    num++;
    el = el->next;
  }
  return num;
}

void swap(list_t* list, int i, int j)
{
  int x;
  x = list_index(list, i)->val;
  list_index(list, i)->val = list_index(list, j)->val;
  list_index(list, j)->val = x;
}

int partition(list_t* list, int low, int high)
{
  int pivot = list_index(list, low)->val;
  int i = low; int j = high+1;
  while(1){
    do i++; while(list_index(list, i)->val <= pivot && i<=high);
    do j--; while(list_index(list, j)->val > pivot);
    if( i>=j )break;
    swap(list, i, j);
  }
  swap(list, low, j);
  return j;
}

void quicksort(list_t* list, int low, int high)
{
  if(low<high){
    int pivot = partition(list, low, high);
    quicksort(list, low, pivot-1);
    quicksort(list, pivot+1, high);
  }
}

void list_sort(list_t* list)
{
  int n = arrLength(list)-1;
  quicksort(list, 0, n);
}

int main()
{
  list_t* list = list_create();

  list_append(list, 3);
  list_append(list, 2);
  list_append(list, 8);
  list_append(list, 5);
  list_append(list, 7);

  list_sort(list);

  return 0;
}

arrLength

#include<stdio.h>
#include<stdlib.h>
#include"list.h"

int arrLength(list_t* list)
{
  if(list->head == NULL) return 0;

  element_t* el = list->head;
  int num = 1;
  while(el->next != NULL){
    num++;
    el = el->next;
  }
  return num;
}

/*void list_sort(list_t* list)
{
  pivot =
}*/

int main()
{
  list_t* list = list_create();

  for( int i=0; i<5; i++ ){
    list_append( list, i );
    if(list->tail->next != NULL) return 1;
  }
  printf("%d",arrLength(list));
}

list_sort

#include<stdio.h>
#include<stdlib.h>
#include"list.h"

void list_sort(list_t* list)
{

}

circle pls

#include<math.h>

void draw_circle( uint8_t img[],
                  unsigned int cols,
                  unsigned int rows,
                  int x,
                  int y,
                  int r,
                  uint8_t color )
{
  int leftT, rightT, leftB, rightB;
  //vertical = radius
  if(x<cols && x>=0){
    for(int i=y-r; i<=y+r; i++){
      if(i>=0 && i<rows){
        img[x+i*cols]=color;
      }
    }
  }

  //horizontal = radius
  if(y>=0 && y<rows){
    for(int i=x-r; i<=x+r; i++){
      if(i>=0 && i<cols){
        img[i+y*cols]=color;
      }
    }
  }

  // y= y1 + (sqrt)(r^2-x^2)
  for(int xx =1; xx<=r; xx++){
    int yy= (int)(sqrt(r**2 - xx**2)+y);
    // top left to top right - indexes
    leftT = x-xx+(y-yy)*cols;
    rightT = x+xx+(y-yy)*cols;
    //for loop to draw one line across
    for(int i=leftT; i<=rightT; i++){
      if(i>=0 && i<cols*rows){
        img[i]=color;
      }
    }

    //bottom left to bottom right
    leftB = x-xx+(y+yy)*cols;
    rightB = x+xx+(y+yy)*cols;
    for(int i=leftB; i<=rightB; i++){
      if(i>=0 && i<cols*rows){
        img[i]=color;
      }
    }
  }
}

mergesort

void mergesort( int arr[], int len)
{
  int low, mid, high, last;
  for(int i =2; i<len; i*=2){
    low =0; high =i-1;
    mid = (low+high)/2;
    while(high<len){
      merge(arr,low, mid, high);
      low += i;
      high += i;
      mid = (low+high)/2;
    }
    if( high != len-1){
    low -= i;
    mid = high-i;
    high = len-1;
    merge(arr, low, mid, high);
    }
  }

}

t1.c

#include<intarr.h>
#include<stdio.h>

/* LAB 6 TASK 1 */

/*
  Save the entire array ia into a file called 'filename' in a binary
  file format that can be loaded by intarr_load_binary(). Returns
  zero on success, or a non-zero error code on failure. Arrays of
  length 0 should produce an output file containing an empty array.
*/
int intarr_save_binary( intarr_t* ia, const char* filename )
{
  unsigned int length = ia->len;
  FILE* f = fopen(filename, "w");
  if(f == NULL){
    return 1;
  }
  // write the length header
  int hdr[1];
  hdr[0] = ia->len;

  if( fwrite(hdr, sizeof(intarr_t), 1, f) != 1){
    return 1;
  }

  if(fwrite(ia->data, sizeof(intarr_t),length, f) != length){
    return 1;
  }
  fclose(f);
  return 0;
}

/*
  Load a new array from the file called 'filename', that was
  previously saved using intarr_save_binary(). Returns a pointer to a
  newly-allocated intarr_t on success, or NULL on failure.
*/
intarr_t* intarr_load_binary( const char* filename )
{
  FILE* f = fopen(filename, "r");
  if(f == NULL){
    return NULL;
  }
  int hdr[1];
  if( fread(hdr, sizeof(intarr_t), 1, f) != 1){
    return 1;
  }

  intarr_t ia;
  ia->len = hdr[0];
  ia->data = malloc((ia->len)*sizeof(int));
  if(ia->len != 0){
    if(ia->data == NULL){
      return NULL;
    }
  }

  if(fread(ia->data, sizeof(intarr_t),length, f) != length){
    return NULL;
  }
  fclose(f);
  return ia;
}

merge

int* mergeTwo(int arr1[], int arr2[], int len1, int len2)
{
  int j=0, k=0;
  int* newArr = malloc((len1+len2)*sizeof(int));
  int newLen = len1+len2;
  for(int i=0; i<newLen; i++){
    if(j<len1 && k<len2){
    if (arr1[j] <= arr2[k]){
              newArr[i] = arr1[j];
              j++;
    }else{
        newArr[i] = arr2[k];
        k++;
    }
    }else if(j>=len1){
      newArr[i]=arr2[k];
      k++;
    }else{
    newArr[i]=arr1[j];
    j++;
    }
  }
  return newArr;
}

intarr

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

/* Structure type that encapsulates our safe int array. */
typedef struct {
  int* data;
  unsigned int len;
} intarr_t;

/* A type for returning status codes */
typedef enum {
  INTARR_OK,
  INTARR_BADARRAY,
  INTARR_BADINDEX,
  INTARR_BADALLOC,
  INTARR_NOTFOUND
} intarr_result_t;

/* LAB 5 TASK 1 */

// Create a new intarr_t with initial size len.  If successful
// (i.e. memory allocation succeeds), returns a pointer to a
// newly-allocated intarr_t.  If unsuccessful, returns a null pointer.
intarr_t* intarr_create( unsigned int len )
{
  intarr_t*pointer = malloc(sizeof(intarr_t));
  if (pointer == NULL){
      return NULL;
  }
  pointer->data = malloc(sizeof(unsigned int)*len);
  if(pointer->data == NULL){
    return NULL;
  }
  pointer->len = len;
  return pointer;
}

// frees all memory allocated for ia. If the pointer is null, do
// nothing. If the ia->data is null, do not attempt to free it.
void intarr_destroy( intarr_t* ia )
{
    if(ia->data != NULL){
        free(ia);
    }
}

/* LAB 5 TASK 2 */

// If index is valid, set the value at ia->data[index] to val and return
// INTARR_OK. Otherwise, leave the array unmodified and return
// INTARR_BADINDEX. If ia is null, return INTARR_BADARRAY.
intarr_result_t intarr_set( intarr_t* ia,
                unsigned int index,
                int val )
{
  unsigned int length = ia->len;
  if(ia->data == NULL){
    return INTARR_BADARRAY;
  }
  if(index<length){
    ia->data[index] = val;
    return INTARR_OK;
  }else{
    return INTARR_BADINDEX;
  }
}

// If index is valid and i is non-null, set *i to ia->data[index] and return
// INTARR_OK. Otherwise no not modify *i and return
// INTARR_BADINDEX. If ia is null, return INTARR_BADARRAY.
intarr_result_t intarr_get( const intarr_t* ia,
                unsigned int index,
                int* i )
{
  if(ia->data == NULL){
    return INTARR_BADARRAY;
  }
  if(index< ia->len){
    *i = ia->data[index];
    return INTARR_OK;
  }else{
    return INTARR_BADINDEX;
  }
}

/* LAB 5 TASK 3 */

// Return a duplicate of ia, allocating new storage for the duplicate
// data (we call this a "deep copy"). If unsuccessful (i.e. memory
// allocation for the copy fails, or ia is null), return a null pointer.
intarr_t* intarr_copy( const intarr_t* ia )
{
  if((ia->data ==NULL)|| ia == NULL){
    return NULL;
  }
  intarr_t* newArr = intarr_create(ia->len);
  newArr->len = ia->len;
  const unsigned int bytes = (ia->len)*sizeof(unsigned int);
  memcpy(newArr->data, ia->data, bytes);
  return newArr;
}

/* LAB 5 TASK 4 */

// sort ia by value smallest-to-largest, so that data[i] < data[i+1]
// for all valid i, then return INTARR_OK. Works in-place: contents of
// ia are sorted on return. If ia is null, return
// INTARR_BADARRAY.
intarr_result_t intarr_sort( intarr_t* ia )
{
  if(ia == NULL){
    return INTARR_BADARRAY;
  }
  if(ia->data == NULL){
    return INTARR_BADARRAY;
  }
  for(int i=0; i< (ia->len)-1; i++){
    for(int k=i+1; k< ia->len; k++){
      if(ia->data[k]< ia->data[i]){
        int temp = ia->data[i];
        ia->data[i] = ia->data[k];
        ia->data[k] = temp;
      }
    }
  }
  return INTARR_OK;
}

/* LAB 5 TASK 5 */

// Find the first occurence of the target in the array, searching from
// index 0. If the target is found and i is non-null, set *i to the
// location index and return INTARR_OK. If target does not occur in
// the array, leave *i unmodified and return INTARR_NOTFOUND. If ia is
// null, return INTARR_BADARRAY.
intarr_result_t intarr_find( intarr_t* ia, int target, int* i )
{
  if(ia == NULL || ia->data == NULL){
    return INTARR_BADARRAY;
  }
  for(int k=0; k< ia->len; k++){
    if(ia->data[k] == target){
      *i = k;
      return INTARR_OK;
    }
  }
  return INTARR_NOTFOUND;
}

/* LAB 5 TASK 6 */

// Append val to the end of ia (allocating space for it). If
// successful, return INTARR_OK, otherwise return
// INTARR_BADALLOC. If ia is null, return INTARR_BADARRAY.
// Take a look at TASK 7 below and see if it might be helpful
intarr_result_t intarr_push( intarr_t* ia, int val )
{
  if(ia == NULL || ia->data == NULL){
    return INTARR_BADARRAY;
  }
  ia->data = realloc(ia->data, sizeof(int)*((ia->len)+1));
  if(ia == NULL|| ia->data == NULL){
    return INTARR_BADALLOC;
  }
  ia->data[(ia->len)] = val;
  return INTARR_OK;
}

// If the array is not empty, remove the value with the highest index
// from the array, and, if i is non-null, set *i to the removed value,
// then return INTARR_OK. If the array is empty, leave *i unmodified
// and return INTARR_BADINDEX. If ia is null, return INTARR_BADARRAY.
// Take a look at TASK 7 below and see if it might be helpful
intarr_result_t intarr_pop( intarr_t* ia, int* i )
{
  if(ia == NULL || ia->data == NULL){
    return INTARR_BADARRAY;
  }
  if(ia->len != 0 || i != NULL){
    *i = ia->data[(ia->len)-1];
    ia->data = realloc(ia->data, sizeof(unsigned int)*((ia->len) -1));
    if(ia == NULL || ia->data == NULL){
       return INTARR_BADARRAY;
    }
    return INTARR_OK;
  }else{
    return INTARR_BADINDEX;
  }
}

/* LAB 5 TASK 7 */

// Resize ia to contain newlen values. If newlen is less than the
// original array length, the end of the array is discarded. If newlen
// is greater than the original array length, intialize all the new
// integers to zero. If the allocation is successful, return
// INTARR_OK, otherwise return INTARR_BADALLOC. If ia is null, return
// INTARR_BADARRAY.
intarr_result_t intarr_resize( intarr_t* ia, unsigned int newlen )
{
  if(ia == NULL || ia->data == NULL){
    return INTARR_BADARRAY;
  }
  ia->data = realloc(ia->data, sizeof(int)*newlen);
  if(ia == NULL || ia->data == NULL){
    return INTARR_BADALLOC;
  }
  if(ia->len < newlen){
    for(int i= ia->len ; i<newlen; i++){
      ia->data[i] = 0;
    }
  }
  return INTARR_OK;
}

/* LAB 5 TASK 8 */

// Get a deep copy of a portion of ia from index first to index last
// inclusive. If successful, return a pointer to a newly-allocated
// intarr_t containing a copy of the specfied section. If an error
// occurs, i.e. ia is null, first or last are out of bounds, last <
// first, or memory allocation fails, return a null pointer.
intarr_t* intarr_copy_subarray( intarr_t* ia,
                unsigned int first,
                unsigned int last )
{
  if(ia == NULL || ia->data == NULL){
    return NULL;
  }
  if(last<first){
    return NULL;
  }
  if(last>= ia->len || first>= ia->len){
    return NULL;
  }
  unsigned int newLen = last-first+1;
  intarr_t* newData = intarr_create(newLen);
  if(newData != NULL){
    for(int i=0; i<newLen; i++){
      newData->data[i]= ia->data[first+i];
    }
  }
  return newData;
}

/* LAB 5 ENDS HERE */

/* -------------------------------------------------------------- */

/* LAB 6 TASK 1 */

/*
  Save the entire array ia into a file called 'filename' in a binary
  file format that can be loaded by intarr_load_binary(). Returns
  zero on success, or a non-zero error code on failure. Arrays of
  length 0 should produce an output file containing an empty array.
*/
int intarr_save_binary( intarr_t* ia, const char* filename )
{
  return 0;
}

/*
  Load a new array from the file called 'filename', that was
  previously saved using intarr_save_binary(). Returns a pointer to a
  newly-allocated intarr_t on success, or NULL on failure.
*/
intarr_t* intarr_load_binary( const char* filename )
{
  return NULL;
}


/* LAB 6 TASK 2 */

/*
  Save the entire array ia into a file called 'filename' in a JSON
  text file array file format that can be loaded by
  intarr_load_json(). Returns zero on success, or a non-zero error
  code on failure. Arrays of length 0 should produce an output file
  containing an empty array.

  The JSON output should be human-readable.

  Examples:

  The following line is a valid JSON array:
  [ 100, 200, 300 ]

  The following lines are a valid JSON array:
  [
   100,
   200,
   300
  ]
*/
int intarr_save_json( intarr_t* ia, const char* filename )
{
  return 0;
}

/*
  Load a new array from the file called 'filename', that was
  previously saved using intarr_save_json(). The file may contain an array
  of length 0. Returns a pointer to a newly-allocated intarr_t on
  success (even if that array has length 0), or NULL on failure.
*/
intarr_t* intarr_load_json( const char* filename )
{
  return NULL;
}