From 48d05e6975e894587665edfd3b3432d23fb4c782 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sat, 4 Jul 2020 12:29:24 -0600 Subject: Fill out program profile for 1a --- src/01/01a/README.md | 121 +++++++++++++++++++++++++++++++++++---- src/01/01a/main.c | 1 + src/01/01a/priority_queue.c | 3 - src/01/01a/priority_queue_test.c | 10 ---- src/01/01b/README.md | 10 ++++ 5 files changed, 121 insertions(+), 24 deletions(-) create mode 100644 src/01/01b/README.md (limited to 'src/01') diff --git a/src/01/01a/README.md b/src/01/01a/README.md index b0accc8..10a799a 100644 --- a/src/01/01a/README.md +++ b/src/01/01a/README.md @@ -3,18 +3,117 @@ Name: Mo Khan Student ID: 3431709 -1. Problem Statement: +## Problem Statement * Describe the meaning of the essential methods `add(x)`, `deleteMin()`, and `size()` that are supported by the priority queue interface. * Implement those methods using a singly-linked list. * Analyze the running time of the `add(x)` and `deletMin()` operations based on this implementation. - * The `add(x)` method is used to add an element to the queue with a priority. - * The `deleteMin()` method is used to remove the element with the lowest priority from the queue and return it. - * The `size()` method is used to determine how many items are in the queue. - * The `add(x)` function is linear time O(n). - * The `deleteMin(x)` function is constant time O(1). - -2. Description of the Code: -3. Errors and Warnings: -4. Sample Input and Output: -5. Discussion: + +## Description of the Code + +The `add()` function is used to add a new item to the priority queue. +The `deleteMin()` function is used to remove and return the item in the queue with the lowest priority. +The `size()` function is used to determine the total number of items that are currently in the queue. + +This implementation of the `add()` function operates linear time `O(n)`. +This implementation of the `deleteMin(x)` function operates in constant time `O(1)`. + +When an item is added to the queue with a priority that duplicates the priority of another item +in the queue, then the new item is removed in the same order that it was added in. .i.e. it is removed +after each other item that had a duplicate priority that was added before it. + +## Errors and Warnings + +I chose to use [cgreen](https://github.com/cgreen-devs/cgreen) to write unit tests for designing the different +function to support the Queue interface. + +Below is an example run of the test suite: + +```bash +モ make run_test +clang build/priority_queue.o build/priority_queue_test.o -lcgreen -o build/test +cgreen-runner -c -v build/test +Discovered PriorityQueue:adds_a_node (CgreenSpec__PriorityQueue__adds_a_node__) +Discovered PriorityQueue:removes_the_node_with_the_lowest_priority (CgreenSpec__PriorityQueue__removes_the_node_with_the_lowest_priority__) +Discovered PriorityQueue:returns_size (CgreenSpec__PriorityQueue__returns_size__) +Discovered PriorityQueue:when_adding_data_out_of_order (CgreenSpec__PriorityQueue__when_adding_data_out_of_order__) +Discovered PriorityQueue:when_adding_random_values_with_random_priority_it_returns_the_minimum_priority_value_correctly (CgreenSpec__PriorityQueue__when_adding_random_values_with_random_priority_it_returns_the_minimum_priority_value_correctly__) +Discovered PriorityQueue:when_removing_it_decreases_the_size (CgreenSpec__PriorityQueue__when_removing_it_decreases_the_size__) +Discovered PriorityQueue:when_removing_node_from_empty_queue (CgreenSpec__PriorityQueue__when_removing_node_from_empty_queue__) +Discovered PriorityQueue:when_removing_the_last_node_it_decrements_the_count_correctly (CgreenSpec__PriorityQueue__when_removing_the_last_node_it_decrements_the_count_correctly__) +Discovered 8 test(s) +Opening [build/test] to run all 8 discovered tests ... +Running "test" (8 tests)... + "PriorityQueue": 17 passes in 5ms. +Completed "test": 17 passes in 5ms. +``` + +The test cases include + +## Sample Input and Output + +I included a program that generates 10 random numbers with 10 random priorities and +enqueues them onto the queue. + +The program then prints a visual tree of the queue and loops until each item is removed from the queue. +The `deleteMin` function removes the item with the lowest priority until the queue is empty. + +```bash +モ make run +clang build/priority_queue.o build/main.o -o build/program +./build/program +=== COMP-272 - Assignment 1 - Question 1a === +Enqueue: 7 249 +Enqueue: 3 658 +Enqueue: 0 272 +Enqueue: 4 878 +Enqueue: 3 709 +Enqueue: 0 165 +Enqueue: 2 42 +Enqueue: 7 503 +Enqueue: 7 729 +Enqueue: 0 612 + +Dequeue: 272 +Items (9): [ (0,165) (0,612) (2,42) (3,658) (3,709) (4,878) (7,249) (7,503) (7,729) ] +Dequeue: 165 +Items (8): [ (0,612) (2,42) (3,658) (3,709) (4,878) (7,249) (7,503) (7,729) ] +Dequeue: 612 +Items (7): [ (2,42) (3,658) (3,709) (4,878) (7,249) (7,503) (7,729) ] +Dequeue: 42 +Items (6): [ (3,658) (3,709) (4,878) (7,249) (7,503) (7,729) ] +Dequeue: 658 +Items (5): [ (3,709) (4,878) (7,249) (7,503) (7,729) ] +Dequeue: 709 +Items (4): [ (4,878) (7,249) (7,503) (7,729) ] +Dequeue: 878 +Items (3): [ (7,249) (7,503) (7,729) ] +Dequeue: 249 +Items (2): [ (7,503) (7,729) ] +Dequeue: 503 +Items (1): [ (7,729) ] +Dequeue: 729 +Items (0): [ ] +Bye +``` + +## Discussion + +I chose to make this queue store signed `int` data and signed `int` priority. +This means that the maximum value that can be used for either the data or priority component +must fit within the range of an `int`. + +On this computer the `sizeof(int)` is 4 bytes. This gives a range of `4294967296` +possible values. Because this is a signed integer the range of those values are +`-2,147,483,648` to `2,147,483,647`. + +```bash +irb(main):001:0> 2 ** 32 +=> 4294967296 +irb(main):002:0> (2 ** 32) / 2 +=> 2147483648 +``` + +I considered using a `void*` to allow for different data types but I felt that +this would have complicated the solution without enough value to justify the need +for this assignment. diff --git a/src/01/01a/main.c b/src/01/01a/main.c index 717469b..a5e9bfd 100644 --- a/src/01/01a/main.c +++ b/src/01/01a/main.c @@ -5,6 +5,7 @@ int main(int argc, char *argv[]) { printf("=== COMP-272 - Assignment 1 - Question 1a ===\n"); + printf("%lu\n", sizeof(int)); PriorityQueue *queue = initialize(); for (int i = 0; i < 10; i++) { diff --git a/src/01/01a/priority_queue.c b/src/01/01a/priority_queue.c index ec51288..83a3e09 100644 --- a/src/01/01a/priority_queue.c +++ b/src/01/01a/priority_queue.c @@ -17,7 +17,6 @@ static Node *create_node(int priority, int data) { return node; } -// This function is constant time O(1) int size(PriorityQueue *queue) { return queue->size; } @@ -46,7 +45,6 @@ void enqueue(Node *self, int priority, int data) { self->next->next = tmp; } -// This function is linear time O(n) void add(PriorityQueue *queue, int priority, int data) { queue->size++; @@ -63,7 +61,6 @@ void add(PriorityQueue *queue, int priority, int data) { queue->head = node; } -// This function is constant time O(1) int delete_min(PriorityQueue *queue) { if (queue->head) { Node *tmp = queue->head; diff --git a/src/01/01a/priority_queue_test.c b/src/01/01a/priority_queue_test.c index 97e788f..877d956 100644 --- a/src/01/01a/priority_queue_test.c +++ b/src/01/01a/priority_queue_test.c @@ -2,16 +2,6 @@ #include #include "priority_queue.h" -/* -Implement the methods of the priority queue interface using a singly-linked list. - -* `add(x)` -* `deleteMin()` -* `size()` - -Analyze the running time of the `add(x)` and `deletMin()` operations based on this implementation. -*/ - Describe(PriorityQueue); BeforeEach(PriorityQueue){ } AfterEach(PriorityQueue){ } diff --git a/src/01/01b/README.md b/src/01/01b/README.md new file mode 100644 index 0000000..41f7d40 --- /dev/null +++ b/src/01/01b/README.md @@ -0,0 +1,10 @@ +# Learning Profile for Assignment #1 - Question #1b - Computer Science 272: Data Structures and Algorithms + +Name: Mo Khan +Student ID: 3431709 + +1. Problem Statement: +2. Description of the Code: +3. Errors and Warnings: +4. Sample Input and Output: +5. Discussion: -- cgit v1.2.3