CMSC 246 Systems Programming
Fall 2019

Assignment #2
Due: Friday September 20 before 11:59pm

All code should following the style guidelines in https://cs.brynmawr.edu/Courses/cs246/fall2019/style.html

Part 1: IS THE ARRAY SORTED? (25%)
Write a function sorted(int n, int arr[n]) that returns true/false (or 1/0) depending on whether the array, arr, with number of elements n is sorted.
Create a program that does the following:
1. Initialize an array of 10 integers so that arr[i] = i.
2. Test to see if it is sorted, using the sorted() function.
3. Print out the contents of the array on a single line, followed by the word sorted or unsorted.
Part 2: More with Sorted (5%)
Modify the program from Part 1 to do the following:
1. Make the fifth element of the array equal to -9
2. Run the program again to confirm it now prints "unsorted"
Part 3: Random Walks (50%)
Write a program that takes a random walk on NxN grid. The walker should do the following:
1. Walk on a 10x10 grid
2. Start at the position 5, 5
3. Never move to a position it has occupied previously
4. Never move off the grid
5. Determine the set of legal moves from the current position. Legal moves are one space, either up, down, right or left AND that do not violate either of the preceding conditions.
6. Print each move made on a single line. This may be as simple as "23 [3,2]" which would mean that on move 23 the walker was in position 3,2
7. Move randomly from among the legal moves.
8. Return the number of steps it takes before the walker gets to a point of having no legal moves.
For instance, suppose that the sequence of moves is:
```  s [5,5]
1 [6,5]
2 [7,5]
3 [7,6]
4 [7,7]
5 [6,7]
6 [5,7]
7 [6,6]
8 [6,6]
```
Then at this point there are no remaining legal moves since the walker has already been to every position possible from [6,6]. Hence, program (or function) should return 8. In fact 8 moves is the shortest walk possible (on a 10x10 board) given the rules above.

Part 4: Random Walk statistics (20%)
Adapt the random walk program from part 3 so it can record the number of steps taken before exhaustion. Further adapt the program so that the grid size can be varied. It is OK to vary the grid size by slighlty altering the program and recompiling. However, if you take this approach, "slight" should mean changing no more than 5 characters. Then:
1. Collect the number of moves before exhaustion for 100 trials of a 10x10 grid
2. Compute and report the mean and standard deviation
3. Collect the number of moves before exhaustion for 100 trials of a 20x20 grid when starting at position 10,10
4. Compute and report the mean and standard deviation.
5. Write a brief report (max 1 paragraph) with your interpretation of this data. For instance, your interpretation might discuss a topic like: "how many moves you expect from even bigger (or smaller) boards" or "how rule changes would affect the walker" or even "how many moves it takes for a random walker to have been in every position, given that revisiting positions is allowed". You might find you answers are improved by testing with more board sizes

Scripting in Linux

Once done, you will need to show some sample runs for parts 1, 2, and 3. In order to record the runs, you can use the Linux command script.
To use script
1. Go to your directory containing your assignment 1 programs directory and enter the command: script SESSION
where SESSION is some meaningful name
2. You will get your command prompt back.
3. Run each of the above programs as you normally would.
4. Once done, enter the command: exit
5. This will end your script session. If you now look a the contents of the session file, you will see that the entire interaction has been recorded in it (as a script!).

What to submit:

Collect together is a single directory (assume that this directory is /home/YOU/cs246/a2) all of the following:
• README file. This is a file literally named README. This file should follow the format of https://cs.brynmawr.edu/Courses/cs246/fall2019/README.txt Your README should include instructions for collecting the data used in part 4 and for adjusting the size of the grid.
• Your programs for parts 1-4
• Script files showing one run of your program for parts 1 and 2 and 2 runs for part 3
• The report described in part 4. This report may be in either a PDF or text file. Other formats will not be read with the result that the report will receive 0 credit.
• Do NOT include compiled code.
• Do NOT include emacs temp files, or any other programs temp files. For emacs these are xxxx~ and #xxxx#