Data Structures and Algorithms

Lab 4: QuickSort and Big-O

Due on Wednesday, October 2nd at 11:59pm. This is a team lab. You and your assigned lab partner(s) will complete this lab together. Make sure that you are familiar with the Partner Etiquette guidelines. You may discuss the concepts of this lab with other classmates, but you may not share your code with anyone other than course staff and your lab partner(s). Do not look at solutions written by students other than your team. If your team needs help, please post on the Courselore forum or reach out to the course staff. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

Overview

This lab consists of three primary parts:

  • Implementing and testing the QuickSort algorithm

  • Proving the Big-O complexity of mathematical functions

  • Analyzing algorithms to understand complexity

Partnered Lab

As you will be working with another student to complete this lab, you will both use the same GitHub repository. The URL for your repository will be

git@github.swarthmore.edu:cs35-f24/lab04-<your-teamname>

where your-teamname is a combination of your two usernames.

For partnered labs you should follow these guidelines:

  • The expectation is that you and your partner are working together side by side in the lab for most, if not all, of the time you work on partnered lab assignments. Remember that both lab partners must learn this material; it will feature prominently on your tests and final exam.

  • We recommend that you do pair programming, where one of you types and one of you watches and assists. You should swap roles periodically, taking turns doing each part.

  • There may be short periods of time where you each go off and implement some small part independently. However, you should frequently come back together, talk through your changes, push and pull each other’s code from the git repository, and test your merged code together.

  • You should not delete or significantly alter code written by your partner when he or she is not present. If there is a problem in the code, then meet together to resolve it.

  • If there is any issue with the partnership, contact the lab instructor.

Part I: QuickSort

Piles of paper

OpenClipArt.org

Your starting repository includes the following files:

  • quickSort.h/quickSort.cpp: The library for your QuickSort algorithm.

  • sortArgs.cpp: A small program to use your algorithm to sort command-line arguments.

  • tests.cpp: A file where you will write your unit tests.

  • Makefile: The file make uses to understand how to build your project.

Files that you will need to modify are bold.

To complete this lab, you should implement the quickSort function in the file quickSort.cpp just as we discussed in class. You’ll need to be careful to follow the algorithm closely and to manipulate array indices accurately. You’ll probably have bugs in your first attempt, so remember the following tools we have discussed for finding and correcting mistakes:

  • valgrind, the program that helps you find memory errors

  • UnitTest++, the unit testing framework (which you are required to use)

Unit Tests

For this lab, you will be graded not only on whether your quickSort implementation is correct but also on whether you have properly tested it. You have been provided a couple tests to start, but you are required to write at least four more tests that investigate different aspects of sorting. Some ideas for additional tests include:

  • Sorting a single-element array to make sure nothing bad happens.

  • Sorting an array that is already in sorted order and seeing whether it stays that way.

  • Sorting an array that contains several duplicates to make sure that they are handled properly.

  • Sorting a large array of numbers that approach a midpoint from opposite directions (e.g. [0,999,1,998,2,997,…​]).

Although you have a minimum number of tests to write, you should ideally write as many as it takes for you to be confident in your code. Remember: each time you change your tests, run make tests before re-running your ./tests program.

Coding Style Requirements

As usual, you will also be required to observe good coding practices:

  • Your C++ code must have proper and consistent indentations.

  • You must have proper and consistent usage of spacing & braces for if, else, for, and while conditions as well as class definitions and code blocks.

Part II: Written Assignment

In this part of your lab, you will apply the Big-O complexity material that we have discussed in class by writing some Big-O proofs about mathematical functions.

Electronic Submissions Only

In order to complete this assignment, you will need to produce a document containing some mathematical expressions and figures. You will commit and push this document to your GitHub repository; the document may take the following forms:

  • A PDF file named WrittenLab.pdf containing your answers in mathematical typesetting

  • A text file named WrittenLab.tex containing your answers as LaTeX source code (see below)

a book

OpenClipArt.org

Your team must submit the document electronically in one of these forms. In particular, you are not permitted to turn in the following (to name a few examples):

  • A raw text document (regardless of formatting)

  • A scan of a written document (even if the scanned document is a PDF)

  • A Microsoft Word file or similar word processor document (although you may write the homework in that format and then export a PDF from it)

  • A piece of paper turned in by hand

A Few Words About LaTeX

LaTeX (pronounced lah-tek or lay-tek) is a document preparation system frequently used to produce research papers, dissertations, and other academic works (in addition to other material). With LaTeX, you code your document much as you would an HTML document or a Python program. For instance, the LaTeX code

I'm \textit{not} making this up: \(e^{i\pi} = -1\)

produces a document which looks like the following image:

latex e26626cb039d365a0d674dc775da2cbb

You are not required to learn LaTeX for this course. However, it is probably easier to use basic LaTeX to complete your homework than to use something like Microsoft Word’s equation editor. In case you’re interested, the following files are already part of your repository:

  • LearningLaTeX.tex: A LaTeX document with some examples of how to use LaTeX to write the things you need to write in this lab. You should look at the .tex file before looking at the .pdf it produces.

  • WrittenLab.tex: A LaTeX document containing your homework problems and places for you to fill them in. These same problems are listed below, but they have been included in this document for your convenience.

Big-O Proofs

Use the formal definition of Big-O notation to prove the following statements:

  1. \(6n^2+6n+3\) is \(O(n^2)\).

  2. \(3n^3-8n^2+6\) is \(O(n^4)\).

Functions

Penguin Detective

OpenClipArt.org

Identify the Big-\(O\) runtime for each of the following functions. Provide a brief justification of your answer; a sentence or two should do. Give the strictest Big-\(O\) you can find: don’t give \(O(2^n)\) if the function is also \(O(n)\) and leave out any unnecessary terms (give \(O(n^2)\) rather than \(O(n^2+3)\)).

To complete the written portion of the lab, list the functions in order from fastest to slowest based on your Big-\(O\) analysis.

  • Function fnA(n):
    For i In 1 to n:
        For j In 1 to 8:
            Set a To i
        EndFor
    EndFor
EndFunction

  • Function fnB(n):
    For i In 1 To 250:
        Set a To i
    EndFor
EndFunction

  • Function fnC(n):
    For i In 1 to n*n:
        For j In 1 to n:
            Set a To j
        EndFor
    EndFor
EndFunction

  • Function fnD(n):
    For i In 1 To n/4:
        Set a To i
    EndFor
EndFunction

  • Function fnE(n):
    For i In 1 to 4n:
        For j In 1 to n:
            Set a To i
        EndFor
    EndFor
EndFunction

  • Function fnF(n):
    Set k To 1
    While k < n:
        For i In 1 To n
            Set a To i
        EndFor
        Set k To k*2
    EndWhile
EndFunction

Summary of Requirements

You must

  • Implement and test QuickSort

  • Provide a PDF or LaTeX file containing the following:

    • Proofs of the Big-O complexity of the functions described above

    • A Big-O analysis of the pseudocode algorithms given above

    • An ordering from fastest to slowest of these pseudocode algorithms

Questionnaire

Once you have submitted your lab, please make sure to complete its corresponding questionnaire. The questionnaire will typically take less than a minute and helps us to understand how much work the labs are so we can adjust appropriately. Completing the questionnaire is part of your participation grade, so don’t forget to fill it out!