CSc 22000: Algorithms

Lab 1: In-Place Merge Sort

[ Introduction | Setup | Specification | Guidelines | Collaboration Policy | Submission and Grade ]

Introduction

An in-place sorting algorithm sorts the given input using O(1) additional storage space. Unfortunately, the merge sort algorithm is not in-place when applied to arrays. One can, however, make the merge sort algorithm in-place when sorting linked lists. In this lab, you are doing exactly that.

Setup

We have prepared skeleton files to help you get started with the lab. To set up the lab workflow in your computer, download lab1.tgz and type the following commands to extract the files:

% tar -xf lab1.tgz
% cd lab1

Specification

Inside the lab1 directory, you will find the following files:

% ls
grader.py    output_required.txt    sort.h           test_data
makefile     sort.cpp               sort_test.cpp

Once you've completed the lab by editing the sort.cpp file, you can test it as follows:

% python grader.py
Score: 10 out of 10 = 100%
--------------------------------------------- Summary ----------------------------------------------
All tests passed.
------------------------------------------ Builder Output ------------------------------------------
g++ -Wall -c sort.cpp
g++ -Wall -c sort_test.cpp
g++ -Wall sort.o sort_test.o -o solution

rm -f *.o solution

Guidelines

Now that you've seen how you can test your solution, let's go through some of the guidelines you should follow when implementing the lab.

First and foremost, this lab is designed to be completed on a machine in NAC7105 Linux Lab. Please make sure your solution executes as expected on those machines since your solution will be graded on one of those machines as well.

We have provided a skeleton file sort.cpp as a starting point. Your task is to only complete the following functions found inside sort.cpp file.

1. LinkedListNode *sortLinkedList(LinkedListNode *list);
2. LinkedListNode *mergeSortedLinkedLists(LinkedListNode *firstList, LinkedListNode *secondList);

Remarks:

Testing:

The grader.py script grades your solution by running the following tests:

  1. Merge the linked lists [1 -> 3 -> 5] and [2 -> 4] and print the result
  2. Merge the linked lists [] and [2 -> 4] and print the result
  3. Merge the linked lists [1 -> 3 -> 5] and [] and print the result
  4. Merge the linked lists [3] and [2] and print the result
  5. Sort the linked list [1 -> 4 -> 3 -> 2] and print the result
  6. Sort the linked list [1 -> 4 -> 3] and print the result
  7. Sort the linked list [1] and print the result
  8. Sort the linked list [-2 -> 3 -> 9] and print the result
  9. Sort the linked list [1 -> 3 -> 2 -> 5 -> 4] and print the linked list starting from the node containing 3
  10. Sort the linked list [1 -> 3 -> 2 -> 5 -> 4] and print the linked list starting from the node containing 5

Notice that the last two test cases check whether you reuse the linked list nodes.

After running all the test cases, the script

  1. Shows your grade,
  2. For each test that failed, shows the result computed from your implementation and the required result from the output_required.txt file.

Feel free to examine the output_required.txt file yourself, but make sure not to edit it. This file contains multiple sections separated by the @ symbol with each section describing the required output of a single test case. The sections are ordered in the same order as above.

Before you submit the lab, try to pass all the test cases shown above. You will be graded on those test cases as well as another set of 10 test cases.

Collaboration Policy

You must write all the code you hand in for the programming assignments, except for code that we give you as part of the assignment. You are not allowed to look at anyone else's solution. You may discuss the assignments with other students, but you may not look at or copy each others' code. You may not use code that might be available online.

Submission and Grade

The deadline for the lab is March 16, 2016 11:59 PM.

Please submit only the completed sort.cpp file to the Submission Server. The submission server will stop accepting solutions after the deadline.

You will be notified when the grades will be available during the class.


© 2016: Nelly Fazio and Milinda Perera.