Skip to content

Assignment 8: Walk, Maze

Deadline

9 April 2021 (Friday), 4pm.

Prerequisite

  • You are able to access the CS1010 programming environment.
  • You are familiar with basic UNIX CLI and using terminal-based editor vim.
  • You have gone through Exercise 1 and have already set up your .gitconfig.
  • You are familiar with the steps of accepting, downloading, and submitting your exercise and assignment.
  • You are familiar with the directory structure and the common files included in your assignment skeleton.

Learning Outcomes

  • Be comfortable writing C programs that involve arithmetic operations, long, double, bool, and char types, conditional if/else statements, loops with while/for/do-while statements, arrays (including 2D arrays), strings, dynamic arrays, and assert.
  • Be comfortable breaking down a problem into smaller subproblems that can be resolved using functions, including reusing existing functions written for other programs (with a tweak), writing a function that calls itself, designing what should the inputs and return values/types of a function be.
  • Be able to analyze the running time of your code and design algorithm that avoid duplicated or redundant work, exploiting properties of the data.
  • Be able to solve problems with recursion, particular those involving non-linear recursion and backtracking.

Setup

1
~cs1010/get-as08
  • You should see the folder as08-<github id> in your home directory with the assignment skeleton inside.

Solving The Assignments

  • Edit the files walk.c and maze.c to solve the corresponding question as described in question.md
  • You should break down the problem into smaller subproblems, and write one function for each of the subproblem to solve the problem.
  • To compile and run tests with the sample inputs and outputs:
1
make
  • The test cases are given in the inputs and outputs subdirectory. You can use cat or less to look at the content of these test cases. You can add more test cases or edit the given ones if needed.

Submission

When you are ready, run the following command to submit:

1
~cs1010/submit-as08

The files walk.c and maze.c will be uploaded to GitHub. You can submit multiple times, but only the last submission will be graded.

Editing Your Files in Multiple Locations

You should edit your code only on the CS1010 PE hosts. If you choose to edit your code in other places, such as directly on Github or in a second location (such as your own laptop), you need to be comfortable with various git command to synchronize your code across the different locations, possibly needing to resolve synchronization conflicts.

Only the C files listed above will be submitted. You can create additional C files for testing different solutions, but eventually, you must put your solution into the corresponding C file provided as the skeleton.

Identifying Yourself

In every C file that you submit to CS1010, you need to identify yourself by writing your name and tutorial group. Marks will be deducted if you fail to do so. You need to edit the line:

1
@author XXXX (Group YYYY)

and change it to something like:

1
@author Dana Scully (G11)

Grading

This assignment contributes towards 3% of your final grade. The total mark for this assignment is 30 marks. There are four marking criteria: correctness, documentation, style, efficiency. The distribution of the marks different by question. Please refer to questions.md for details.

  • Documentation: Marks are no longer allocated for documentation. The graders reserves the right to deduct up to two marks if you do not document your code properly. Please refer to the documentation and follow the recommended format. You need to explain the purpose of every file, function, and parameter. Logic in your code that is not obvious should be explained as well.
  • Style: Marks are no longer allocated for style. But the graders reserves the right to deduct up to two marks if your code blatantly violates the style guidelines.
  • Correctness: Note that passing the tests does not guarantee that your code is correct. Correctness here is defined in the broad sense of using the various programming constructs in C (type, function, variable, loops, conditionals, arithmetic expressions, logical expressions) properly, not just producing the correct output and bug-free.
  • Efficiency: Some question has an efficiency requirement. You need to meet the efficiency requirement to obtain the efficiency marks.

New clang-tidy checks

We have been encouraging students to break the solutions down into small functions. Not everyone adhere to this good practice, however. From this assigment onwards, we will generate a warning if your function is too large. We use a threshold of 50 statements and 4 nesting levels. Any function that exceeds this threshold will generate a warning.

Memory checks

We will start checking how you handle the memory returned from malloc and friends (including those returned by the CS1010 I/O library, including checks for NULL and calling free). Penalty applies if you do not manage them correctly.

Remember to return non-zero if your program does not run to its completion and encounters unexpected error.

Reduced test data

We have been providing lots of test data to help you test your program. We will reduce the number of test cases provided from now on. You should come up with your own test cases to test your code to make sure it covers all the cases (especially the edge cases).

We reserve the right to penalize students for using banned C syntax in the assignments. In addition, each grader at his or her own discretion can penalize students for repeating mistakes / bad practices from the student's past assignments (even if it was just a warning with no marks deducted in the earlier assignments).

Responsibility

By now, you should be familiar with how to accept, get, solve, and submit a CS1010 assignment. From this assignment onwards, you need to take full responsibility of submitting the correct version of your assignment before the deadline, or accept the consequences of your actions. We will no longer entertain appeals for marks if you submit an incorrect version of your code, forget to submit the assignment, submit late due to forgotten password, or other reasons due to unprofessional behavior.

Questions

To acclimatize you to the PE2 condition, the questions for this assignment are included in the skeleton instead, in a file named questions.md.

You should learn how to use vim to open both the .c file and the questions.md side-by-side (see https://nus-cs1010.github.io/2021-s1/vim.html#splitting-vims-viewport)