ComputerScienceExpert
$18/per page/
Computer Science 1- Cop 3502, Programming
See attachment below. This is all in C. The header file attached is what my professor used when he solved the problem but it is not necessary to use every function prototype on there. Thanks in advance.
Assignment 2 Due Date: Sunday, March 19th 2017, 11:59pm Objectives
The purpose of this assignment is twofold. First, I’d like to increase your familiarity with stacks,
queues, and linked lists. Second, I would like to expose you to an idea for sorting data not
discussed in class.
This assignment will challenge your implementation skills, building on the skills obtained in the
last homework and developing them further. You will also have a tricky sub-problem to tackle.
How do you combine runs efficiently? This will challenge you to think creatively. Deliverables
Submit two files.
The file named “zigzag.h” is your header file. Place all function declarations in this header with
comments on how you designed the header. You may use the header I provide or design your
own. In either case, include a header.
The file named is “zigzag.c” is your source file. Implement all functions defined in the header
file. Include a main function in this file.
All input should be read from a file named “zigzag.txt”. The input specification will define
precisely what is allowed for input to your program. You need not guard against cases not
allowed in the input. Scoring
I will run your program multiple times on multiple test files. Your grade will be awarded based
on the number of tests you pass with some points allocated to fulfilling the special
requirements for sorting. Be sure to test your program on more than just the sample cases
provided.
To guard against infinite loops and inefficient implementations, your program will be run for seconds per test case. Upon grading, you will receive a “results.txt” file detailing which tests
where passed and which failed. Here is a table of possible results:
Error Code
AC
WA
RTE
TLE
CTE Meaning
Accepted! :D All is wonderful in the world and your code worked correctly.
Wrong Answer: The code executed but produced faulty output.
Runtime Error: The code crashed spewing memory and guts everywhere.
Time Limit Exceeded: I killed the program after seconds. I feel betrayed.
Compile Time Error: Your code did not compile. Zigzag filename: zigzag
timelimit: 3 seconds
In class, we discussed numerous techniques for sorting data. In this problem, we will use a
clever idea to speed up the best case in sorting algorithms. With any lucky, we will also keep
the worst case of sort as ( log ). (At the very least, that is my challenge to you.) In sorting, we explored ordering sequences of integers. In particular, the merge sort algorithm
took two sorted sequences and combined them as a sub problem to sorting. But often in real
world data, pieces of the data are partially sorted. Observe:
1, 3, 7, 100, 8, 100, 200, 7, 8, 9, 10 Notice we can split the sequence into three contiguous regions where the data is already
sorted:
1, 3, 7, 100, 8, 100, 200, 7, 7, 8, 9, 10 Aha! Now we can form a modified merge sort were we can avoid sorting already sorted data.
Notice that because we are decomposing the data into contiguous runs, the algorithm runs
best case in () on already sorted data.
But our algorithm has a weakness, an Achilles heel of sorts. By making the runs strictly
decreasing, everything is a run! Uh oh!
5, 4, 3, 2, 1 We can solve this problem as well. When identifying runs, we can look at the first two numbers
to determine if the run will be increasing or decreasing. From then on, continue adding the
next numbers to the run until it changes direction. Now we have a solution that works in ()
best case on data sorted in reverse order! Observe:
5, 4, 3, 2, 1 It also improves its average runtime on cases that zigzag back and forth:
1, 2, 3, 4, 5, 4, 3, 2, 1, 8, 9, 10, 3, 2 Though it’s probably prudent to put the reverse runs in sorted order first, for easy
combination:
1, 2, 3, 4, 5, 1, 2, 3, 4, 8, 9, 10, 2, 3 So now your challenge is: combine these sorted runs of data efficiently to sort all the data.
Keep in mind what happened in class with our “dumb” merge sort that ran in (2 ). Try to find
a way around that behavior. What other types of cases might be tricky for such an approach? Oh, and one more thing. When I said check the direction based on the first two elements in the
run, I lied. That will work in most cases, but won’t work here:
4, 4, 4, 7, 8, 9, 4, 4, 4, 3, 2, 1 The above sequence should be decomposed into two runs: Additional Requirements
•
• 4, 4, 4, 7, 8, 9, 4, 4, 4, 3, 2, 1 You must read the data into a linked list data structure and sort that structure. Don’t
use an array!
When reversing runs, don’t uses recursion. Use a stack instead! Input “zigzag.txt”
The first line of the input file contains a single integer (1 ≤ ≤ 105 ) representing the number
values in the sequence of data.
This is followed by a line with integers (1 ≤ ≤ 109), separated by spaces, representing
the data to be sorted Output (stdout)
Output integers in sorted order using the algorithm described in the specification. Sample 1 5
5 2 3 4 1
Output 1 2 3 4 5
Input Sample 2
10
2 3 3 10 9 8 7 8 9 10
Output 2 3 3 7 8 8 9 9 10 10
Input Tips
Try getting a version that works in (2 ) time first. Such a solution will decompose the data
into runs, but won’t combine them in a smart way. What kinds of cases cause your algorithm to
run in (2 )? If you cannot get the program to work faster than (2 ), turn that version in! You
may pass a subset of the tests and still get a good grade.
I recommend making a suite of tests for your program. Try making tests that cause your
approach to be slow. Is your algorithm fast on other types of data? It is surely better than
bubble sort! Write comments in your code detailing what kinds of data is fast versus slower
data. If something in the problem appears unclear, please come see me or send me an email. I’ll do
my best to clarify either the specification or provide further clarification in class or through
WebCourses.
Don’t use the whole header file immediately. Only copy in what you need while you’re getting
things working. Use it as a guide for how to design your program. Checkpoints
This problem requires several major steps. When dealing with a larger project, it is best to
make checkpoints for yourself. Try to set a schedule for when you can expect each piece to be
complete. Do your best to meet each milestone.
•
•
•
• (02/24) Get a working stack and queue.
(03/03) Work on reading in the data and identifying runs. Reverse each of the
decreasing runs using a stack.
(03/10) Use the ideas from Mergesort to combine runs together. Get a working sort
algorithm even if it is slow.
(03/19) Hopefully you have identified the slow cases. Attempt to find a smart way to
handle the merging efficiently. If you don’t break up the work like this or set your own milestones, you will fail to complete this
project. The trick is to break things into small manageable chunks and get pieces working
systematically. Use what you learned from Assignment 1 about testing small blocks of your
code before moving on to more complex sub-problems.
#include <stdio.h>
#include <stdlib.h>
// This is a node from our in class linked list example.
// Here I will reuse code to implement a linked list structure.
typedef struct node_t
{
int value;
struct node_t * next;
} node_t;
// I'll use a struct to keep track of a stack
// Here I do my stack linked list style.
typedef struct stack_t
{
node_t * top;
} stack_t;
// Here are the stack functions. Notice that the functions
// are almost exactly the same but I'm using a linked list to store
// the data in the backend. This is what is meant by an abstract
// data type. The concept can be hidden from the underlying
// implementation.
//
// We make one extra distinction here. There is no capacity because
// such a notion makes no sense in a stack.
stack_t * stack_create();
void stack_destroy(stack_t * stack);
void stack_push(stack_t * stack, int data);
int stack_pop(stack_t * stack);
int stack_peek(stack_t * stack);
int stack_is_empty(stack_t * stack);
// I'll use the queue's here linked list style.
// My code will read in the data as a queue and sort
// it.
typedef struct queue_t
{
node_t *head, *tail;
} queue_t;
// Functions for creating and dealing with queues.
queue_t * queue_create();
void queue_destroy(queue_t * queue);
void queue_enqueue(queue_t * queue, int data);
int queue_dequeue(queue_t * queue);
int queue_peek(queue_t * queue);
int queue_is_empty(queue_t * queue);
int queue_size(queue_t * queue);
// Here I make a queue of runs. I need two pieces:
//
// 1) A node to store the individual run and a pointer to the next run.
// 2) A list struct to group together all of the runs.
// // This structure (in practice) is a linked list of linked lists.
//
// Another option to reduce redundant code is to use a (void *)
// to store the data in node. You are welcome to attempt that
// if you like. Then you will only have one queue implementation.
//
// Another option is to make this structure a stack. But why would
// that be helpful? (Hint: there is a fast solution that makes this
// a stack.) You are of course allowed to make this part any structure
// you want.
typedef struct run_node_t
{
queue_t * run;
struct run_node_t * next;
} run_node_t;
typedef struct run_queue_t
{
run_node_t *head, *tail;
} run_queue_t;
// Here are functions for dealing with our run queue.
// Notice the naming problems. We have to give different names
// for each function. Good grief! Other languages handle this much
// better. Hopefully this program will get you to appreciate other
// languages in the future.
run_queue_t * run_queue_create();
void run_queue_destroy(run_queue_t * queue);
void run_queue_enqueue(run_queue_t * queue, queue_t * run);
queue_t * run_queue_dequeue(run_queue_t * queue);
queue_t * run_queue_peek(run_queue_t * queue);
int run_queue_is_empty(run_queue_t * queue);
// Here are functions for extracting a run from a list of data.
// --------------// This first function takes in a queue and remove the frontmost run.
// The return value is a new queue of that first run.
// The input queue should be modified to no longer contain this first run.
//
// (TIP): Don't access the linked list directly. Only use the enqueue/dequeue
functions.
// (TIP): My version of extract next assumes the queue given is not empty.
queue_t * extract_next_run(queue_t * data_queue);
// This function extracts all runs from the given queue.
// It should call extract_next
run_queue_t * extract_runs(queue_t * data_queue);
// Other functions will go here for combining runs into a single (queue_t *).
// I'm not giving these to you as I want you to figure out combination.