Project 1: implementing algorithms

Project 1: implementing algorithms
CPSC 335 - Algorithm Engineering

Abstract
In this project you will set up an environment for implementing algorithms in C++, and use that to
implement two algorithms that solve the same problem. The first step is for you to either create your own
Tuffix Linux install, or arrange to use a Tuffix environment on campus. We will use this environment to
submit and grade projects all semester. The second step is for you to translate descriptions of two algorithms
into pseudocode; analyze your pseudocode mathematically; implement each algorithm in C++; test your
implementation; and describe your results.
Installing Tuffix
As described in the syllabus, “Tuffix” is the Computer Science Department’s official Linux development
environment. Instructions on how to install Tuffix or a Tuffix based VM are online at
«http://csufcs.com/tuffixinstall». The Tuffix Titanium Community for Students,
https://communities.fullerton.edu/course/view.php?id=1547 is the best venue to find help with Tuffix.
The first part of this project is installing Tuffix, either using a virtual machine or a bare-metal install. You
should follow the instructions in those documents, and the documents they link to, to build a working Tuffix
environment.
Alternatively, you may opt to use the Tuffix VMs available in the ECS Open Lab in the CS building. If you go
this route, you will need to make arrangements to be able to complete your projects during the lab’s open
hours.
The Alternating Disk Problem
The problem, presented in Levitin’s textbook as Exercise 14 on page 103, is as follows:
You have a row of 2n disks of two colors, n dark and n light. They alternate: dark, light, dark, light,
and so on. You want to get all the dark disks to the right-hand end, and all the light disks to the
left-hand end. The only moves you are allowed to make are those that interchange the positions of
two neighboring disks. Design an algorithm for solving this puzzle and determine the number of
moves it takes.
The alternating disks problem is:
Input: a positive integer n and a list of 2n disks of alternating colors dark-light, starting with dark
Output: a list of 2n disks, the first n disks are light, the next n disks are dark, and an integer m
representing the number of swaps to move the dark ones after the light ones
There are two algorithms, presented below, that solve this problem in in O(n ) time. You need to translate
2
these descriptions into clear pseudocode.
The first algorithm starts with the leftmost disk and proceeds to the right until it reaches the rightmost disk:
compares every two adjacent disks and swaps them only if necessary. Now we have one lighter disk at the
left-hand end and the darker disk at the right-hand end. Once it reaches the right-hand end, it goes back to
the leftmost disk and proceeds to the right, doing the swaps as necessary. It repeats n times.
The second algorithm proceeds like a lawnmower: starts with the leftmost disk and proceeds to the right until
it reaches the rightmost disk: compares every two adjacent disks and swaps them only if necessary. Now we
have one lighter disk at the left-hand end and the darker disk at the right-hand end. Once it reaches the
right-hand end, it starts with the rightmost disk, compares every two adjacent disks and proceeds to the left
until it reaches the leftmost disk, doing the swaps only if necessary. The lawnmower movement is repeated
⌈n/2⌉ times.
For each algorithm, some improvement can be obtained by not going all the way to the left or to the right,
since some disks at the ends are already in the correct position.
The left-to-right algorithm
It starts with the leftmost disk and proceeds to the right, doing the swaps as necessary. Now we have one
lighter disk at the left-hand end and the darker disk at the right-hand end. Once it reaches the right-hand
end, it goes back to the leftmost disk and proceeds to the right, doing the swaps as necessary. It repeats
until there are no more disks to move.
For the example shown, the exact list of disks changes as follows at the end of each run (left-to-right):
The lawnmower algorithm
It starts with the leftmost disk and proceeds to the right, doing the swaps as necessary. Now we have one
lighter disk at the left-hand end and the darker disk at the right-hand end. Once it reaches the right-hand end,
it starts with the disk before the rightmost disk and proceeds to the left, doing the swaps as necessary, until it
reaches the disk before the left-hand end. It repeats until there are no more disks to move.
For the example shown, the exact list of disks changes as follows at the end of each run (left-to-right or
right-to-left):
Algorithm Design
Your first task is to design an algorithm for each of the two problems. Write clear pseudocode for each
algorithm. This is not intended to be difficult; the algorithms I have in mind are all relatively simple, involving
only familiar string operations and loops (nested loops in the case of oreos and substrings). Do not worry
about making these algorithms exceptionally fast; the purpose of this experiment is to see whether observed
timings correspond to big-O trends, not to design impressive algorithms.
Mathematical Analysis
Your next task is to analyze each of your two algorithms mathematically. You should prove a specific big-O
efficiency class for each algorithm. These analyses should be routine, similar to the ones we have done in class
and in the textbook. I expect each algorithm’s efficiency class will be one of O(n), O(n ), or
2 O(n ),
3 O(n ).
4
Obtaining and Submitting Code
This document explains how to obtain and submit your work:
GitHub Education / Tuffix Instructions
Here is the invitation link for this project:
https://classroom.github.com/g/ItOphDhC
Implementation
You are provided with the following files.
1. disks.hpp is a C++ header that defines functions for the two algorithms described above. There
are also classes that represent the input and output of the alternating disk problem. The function
definitions are incomplete skeletons; you will need to rewrite them to actually work properly.
2. disks_test.cpp is a C++ program with a main() function that performs unit tests on the
functions defined in disks.hpp to see whether they work, prints out the outcome, and calculates
a score for the code. You can run this program to see whether your algorithm implementations are
working correctly.
3. rubrictest.hpp is the unit test library used for the test program; you can ignore this file.
4. README.md contains a brief description of the project, and a place to write the names and CSUF
email addresses of the group members. You need to modify this file to identify your group members.
What to Do
First, add your group member names to README.md. Then:
1. Write your own pseudocode for the left-to-right algorithm, and the lawnmower algorithm.
2. Analyze your pseudocode for the algorithm mathematically and prove its efficiency class.
3. Implement all the skeleton functions in disks.hpp. Use the disks_test.cpp program to
test whether your code works.
Finally, produce a brief written project report in PDF format. Submit your PDF by committing it to your
GitHub repository along with your code. Your report should include the following:
1. Your names, CSUF-supplied email address(es), and an indication that the submission is for project 1.
2. A full-screen screenshot, inside Tuffix, showing the Atom editor, with your group member names
inside Atom. One way to make your names appear in Atom is to simply open your README.md.
3. Two pseudocode listings, for the two algorithms.
4. A brief proof argument for the time complexity of your two algorithms.
Your screenshot might look like this:
Grading Rubric
Your grade will be comprised of three parts: Form, Function, and Analysis.
Function refers to whether your code works properly as defined by the test program. We will use the score
reported by the test program, when run inside the Tuffix environment, as your Function grade.
Form refers to the design, organization, and presentation of your code. A grader will read your code and
evaluate these aspects of your submission.
Analysis refers to the correctness of your mathematical and empirical analyses, scatter plots, question answers,
and the presentation of your report document.
The grading rubric is below.
1. Function = 14 points, scored by the unit test program
2. Form = 9 points, divided as follows:
a. README.md completed clearly = 3 points
b. Style (whitespace, variable names, comments, helper functions, etc.) = 3 points
c. C++ Craftsmanship (appropriate handling of encapsulation, memory management, avoids
gross inefficiency and taboo coding practices, etc.) = 3 points
3. Analysis = 17 points, divided as follows
a. Report document presentation = 3 points
b. Screenshot = 3 points
c. Pseudocode = 3 points
d. Mathematical analysis = 8 points
Legibility standard: As stated on the syllabus, submissions that cannot compile in the Tuffix environment are
considered unacceptable and will be assigned an “F” (50%) grade.