CS 136 - Winter 2018 - Assignment 5

Due Date: Friday, February 16th, 2018 at 11:59am (noon).



LANGUAGE FEATURES

In this assignment, you must only use the C features covered in class up to section 6.

Reminder: read the updated preamble (e.g., regarding the use of scanf) before starting EVERY assignment.


BLACK QUESTION (moderate collaboration allowed)

Question 1: Implementing an I/O-based test client

[10 marks correctness]

From now on, you may be expected to create your own test clients for modules you design.

For this question, you must complete the program test-drawing.c that tests a drawing module that implements some the drawing functions from Assignment 2.

Your program must continuously read in a character and then an integer ("size") from input.

If the character is a 't' then it calls draw_triangle(size) and then prints an extra newline (\n).

For example, the input:

t 3
would call draw_triangle(3) and then print an extra newline.

Similarly, 'b' calls draw_border, 'x' calls draw_x, 'c' calls draw_checker and 'd' calls draw_diamond (all followed by newlines).

For any other character (or when EOF is reached), your program just ends.

Your program does not need to check that the size is valid (or missing).

For this question, the Marmoset basic tests ("public" tests) will be identical to the simple test files provided.


GOLD QUESTION (no collaboration allowed)

Question 2: Creating test files

[10 marks correctness]

Naturally, once you have created an I/O-based test program (like in Q1) you would want to create appropriate test files.

We have provided a cs136grades module that provides two functions:

We have also provided an I/O-based test program for you.

Unfortunately, the functions in the module we have provided always return perfect (100). A student designed this module under the false impression that it would give them 100 in the course.

Your task is to generate appropriate .in and .expect test files (there is NO programming required for this question).

To test your tests, we will be using a wide variety of incorrectly implemented modules that make common mistakes: off-by-one errors, boundary errors (edge cases), integer division errors, etc. Some of these incorrect modules will be drawn from student assignments in previous terms of CS 136. You will pass our tests if your tests can detect the flaws in our modules.

You should generate useful, well-thought out tests. To avoid a "brute-force" approach, you will be limited to 50 tests per function. You may put all of your tests in a single test or split them up over several tests if you prefer.

All of your tests should meet the stated requirements of the functions.

You are NOT allowed to ask on Piazza questions of the nature "What should cs136_final_grade(50, 50, 50, 50) return?" (hint: it's 50).

For this question, the Marmoset basic tests ("public" tests) do not do anything, and always appear "correct".


BLACK QUESTION (moderate collaboration allowed)

Question 3: Building a Simple Module

[15 marks correctness][10 marks style]
LANGUAGE FEATURES: For [only] this question, you may use global mutable variables.

You must complete both the implementation and the interface for the following functions in a module mymodule. Unfortunately, mymodule has low cohesion.

Much of the style marks will be for your interface. Ensure you provide appropriate documentation (including appropriate requirements).

For this question, the Marmoset basic tests ("public" tests) will be identical to the assertions in the .c file provided.

If you are keen, you could create a more sophisticated test client that uses I/O (as in q1 and q2).


GOLD QUESTION (no collaboration allowed)

Question 4: A-MAZE-ing

[20 marks correctness]

For this question, you must write a program that can escape from a maze.

We have provided you a maze module that has functions described in maze.h.

After you read in a maze from input (using read_maze) your position will be at the 'S'tart location and facing DOWN. There will be a wall to your RIGHT (which is actually on the left because you are facing DOWN).

You must escape from the maze using the "right-hand wall follower" algorithm. (See Wikipedia).

For the following maze (with dimensions 10 x 5):

(image courtesy of Wikipedia).

The first few moves would be DOWN DOWN RIGHT DOWN LEFT DOWN RIGHT ....

The last few moves would be (starting from the upper right corner)... DOWN LEFT DOWN DOWN LEFT DOWN LEFT RIGHT RIGHT RIGHT

For the following SIMPLE maze (with dimensions 3 x 2):

The moves would be DOWN RIGHT RIGHT UP.

Carefully review the maze.h interface and the simple test provided, which matches the SIMPLE maze above.

By calling move in the correct sequence the correct output for the SIMPLE maze is: DRRUE where the E indicates that the end has been reached.

You may share your own mazes on Piazza (make sure you take the time to understand the input format), but you are NOT allowed to share (or ask for) the correct path through any mazes.

For this question, the MARMOSET basic tests ("public" tests) will be the same as the simple test client provided.


Question 5: Fun with Stacks

[15 marks correctness]

For this question, you may NOT use recursion. You must use the provided STACK ADT module and iteration.

BLACK QUESTION (moderate collaboration allowed)

  1. Write a program that reads in ints, and prints the numbers in their original order and then in reverse order.
  2. Write a program that reads in symbols, and prints the symbols in their original order and then in reverse order.

GOLD QUESTION (no collaboration allowed)

  1. Write a program that reads in symbols, and prints the symbols in their original order and then in reverse order and then in their original order, and then finally in their reverse order.

For this question, the marmoset basic tests ("public" tests) will use the simple.expect test files provided.


GOLD QUESTION (no collaboration allowed)

Question 6: Balance of the Force

[20 marks correctness]

Implement the following programs. Each program either prints "balanced\n" or "unbalanced\n".

  1. balanced1 determines if the input has balanced parenthesis.

    For example, "(()())" is balanced, but "()())" is not, and neither is ")("

    your function should ignore any non-parenthesis characters. For example,
    "Ben (Obi-Wan) Kenobi" is balanced

    Note: you may not use a stack to solve this question.

    Hint: keeping track of the number of parenthesis currently "open" is enough to solve this problem.

  2. balanced2 is the same as balanced1, except that it determines if the input is balanced for four types of brackets: ()[]{}<>

    For example, "([{<>}])" is balanced, but "([{]})" is not

    For this question, you may NOT use recursion. You must use the provided STACK ADT module and iteration.

    The algorithm you should use is as follows. This algorithm is incomplete, but should provide enough of a hint for you to proceed.

    For each character:

    • if it is an opening bracket ([{< then push the value of the bracket (as an ASCII int) onto the stack
    • if it is a closing bracket )]}> that matches the top bracket on the stack, then pop the corresponding opening bracket
    • if ...

For this question, the MARMOSET basic tests ("public" tests) will be the same as the simple test client provided.