DUE DATE: 2 October, 2015 @ 11:59pm

Instructions

For this assignment you should place each solution in a separate directory. Each directory should contain a Makefile that builds the code in that directory.

For each problem in the assignment you must include tests using the check lirbary. Your Makefile should have targets to

  1. build your code
  2. build your tests
  3. run your tests
  4. generate code coverage reports in html.

Lab3 explains how to use check, write tests and run them as well as how to generate code coverage reports. Lab2 explains how to use Makefiles.

Problem 1: Binary Trees

You are asked to design a Binary Tree which that can store integers as values and provide the following operations on Binary Trees. The operations below use BT as the type for a Binary Tree node. You are free to design BT in any way you prefer.

  1. bool bt_equal(BT *t1, BT *t2) given two binary trees return true if the trees contain the same integers at corresponding nodes in the tree.
  2. BT *mirror(BT *t) returns the mirror image of t, e.g, Mirrored Tree example
  3. bool is_mirror(BT *t1, BT *t2) returns true if t1 is a mirror image of t2.

Problem 2: Doubly Linked List

You are asked to provide an implementation of a Doubly Linked List of integers. The operations below use Node as the type for a doubly linked list node, you are free to design Node in any way you like. You should provide the following operations on doubly linked lists:

  1. Node *create(int element) creates a new list containing the single element element and returns a pointer to the head of the list.
  2. void add(int element, Node *list) adds element to the end of the list.
  3. bool contains(int element, Node *list) return true if element is found in list, else returns false.
  4. void remove(int element, Node *list) remove element from list. If element is not in list the list remains unchanged.
  5. delete_list(Node *list) deallocates all the element of list. The head pointer should now point to NULL.
  6. int length(Node *list) returns the total number of elements in list. If the list is empty then return 0.
  7. int get_nth_element(int n, Node *list) returns the nth element in the list. If n is greater than the size of the list, or less than 0, the program should exit unsuccessfully.
  8. void add_nth(int element, int n, Node *list) adds element to the n-th index in the list moving all existing elements at indexes greater or equal to n by 1. If n is greater than the size of the list, or less than 0, the program should exit unsuccessfully.
  9. Node *append(Node *list1, Node *list2) append the two lists.
  10. bool equal(Node *list1, Node *list2) return true if the two lists contain the exact same element at each corresponding index, else, return false.

Problem 3: Priority Queue

You are asked to imlpement a Priority Queue for Tasks.

A Task consists of

Your implementation of the priority queue must support the following operations. The operations use the type Task to denote a Task and PQ to denote a priority queue element. You are free to design Task and PQ in any way you prefer.

  1. PQ *create(Task t, int priority) creates a new priority queue with one element t with t having priority priority.
  2. void remove(Task t, PQ *queue) removes task t from queue if t is in queue, else queue remains unchanged.
  3. Task *pop(PQ *queue) returns the task with the highest priority in queue and removes the task from queue.
  4. void push(Task t, int priority, PQ *queue) add task t with priotity priority into queue.
  5. int get_max_priority_value(PQ *queue) returns the value of the highest priority in queue.
  6. int get_min_priority_value(PQ *queue) returns the value of the lowest priority in queue.
  7. void update_priority(int task_id, int priority, PQ *queue) updates the priority of all tasks with task_id to be task_id.
  8. PQ *combine(PQ *queue1, PQ *queue2) combines the two queues into one.
  9. void set_to_suspend(int task_id, PQ *queue) updates the state of task with task id task_id to suspended. If there is not task with task id task_id in the queue, the queue remains unchanged.
  10. void set_to_running(int task_id, PQ *queue) updates the state of task with task id task_id to running. If there is not task with task id task_id in the queue, the queue remains unchanged.
  11. void set_to_stopped(int task_id, PQ *queue) updates the state of task with task id task_id to stopped. If there is not task with task id task_id in the queue, the queue remains unchanged.

Problem 4: Pick your team members

Send a message to the course staff on Piazza with the CCIS logins of your team members. Teams can have a maximum of 3 team members. We reccommend 3 members for each team.

If you would like to form a team with 2 members you will have to first get approval from the instructor.