< Back

Test 3

If you do not currently have a directory for tests, create one in your cs170 directory, and also create a directory for test3:

$ mkdir ~/cs170/tests
$ mkdir ~/cs170/tests/test3
$ cd ~/cs170/test/test3

This portion of the test is worth 30 total points. In addition to this file, you may only access the C++ documentation website and the Qt documentation documentation website. NO OTHER WEBSITES ARE PERMITTED. You are also not allowed to access any personal files in your CS account. As usual, you are not allowed to directly copy any code from the Internet or another individual. You should also follow all coding standards discussed thus far.

Test 3

Question 9

Download the LinkedList.cc and LinkedList.h files. Your should add a new method void doubleAllAdjacent(), which duplicates every value in the list. Pay special attention to the ordering of the newly placed values!

Only 80% of the points will be awarded for solutions that result in a \(O(n^2)\) solution. Full credit will only be awarded for a \(O(n)\) solution.

(10 points)

  #include "LinkedList.h"
#include <iostream>
using namespace std;

int main() {
  LinkedList l;

  l.append(1);
  l.append(1);
  l.append(2);

  cout << l << endl;		// [1, 1, 2]

  l.doubleAllAdjacent();

  cout << l << endl;		// [1, 1, 1, 1, 2, 2]
}

Question 10

ALERT: No credit will be awarded for non-recursive solutions!

Write a recursive function void increaseList(int * list, int length). This function takes an array of positive integers as a parameter. It should modify the array in place. Every location in the array should become the sum of the entire array, starting from its location, and ending at the end of the array.

(10 points)

  int main() {
      int myArray[4] = {1, 2, 3, 4};
      increaseList(myArray, 4);

      for(int i = 0; i < 4; i++) {
          cout << myArray[i] << " ";
      }
      cout << endl;  //10 9 7 4
  }

Question 11

Download the following files into your directory as well:

Create a program in a file called Balanced.cc. Your program should have a function bool balanced(char * parenString, int length). This function should use a Stack to determine if a set of parenthesis is balanced.

Your function should iterate over the characters of the string. Whenever it encounters an open parenthesis, it should push it onto the stack. Whenever it encounters a closing parenthesis, you should pop the stack. The parenthesis are balanced if you never popped an empty stack, and if the stack is empty after iterating over the entire string.

(10 points)

  void printBoolean(bool b) {
    if(b) {
      cout << "True" << endl;
    } else {
      cout << "False" << endl;
    }
  }

  int main() {
    printBoolean(balanced("()()()()", 8));  // True
    printBoolean(balanced("())()()", 7));   // False
    printBoolean(balanced("(()()()()", 9)); // False
    printBoolean(balanced("(())()", 6));    // True
  }

 

 

Challenge

Create a Qt program called SierpinskiCarpet It should draw a Sierpinski Carpet to some maximum depth. The Sierpinski Carpet is similar to the Sierpinski Triangle, except that it uses squares instead of triangles. You divide the square into 9 squares, "remove" the cneter square, and recursively call the algorithm on the 8 surrounding squares.

(8 points)

 

Submission

When you have finished, create a tar file of your test1 directory. To create a tar file, execute the following commands:

cd ~/cs170/tests
tar czvf test3.tgz test3/

To submit your activity, go to inquire.roanoke.edu. You should see an available assignment called Test 3. Make sure you include a header listing the authors of the file.