CMSC 246 Systems Programming
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) 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:
- Initialize an array of 10 integers so that arr[i] = i.
- Test to see if it is sorted, using the sorted() function.
- 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:
- Make the fifth element of the array equal to -9
- 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 array. The walker should do the following:
For instance, suppose that the sequence of moves is: [5,5], [6,5], [7,5], [7,6], [7,7], [7,6], [7,5], [6,7], [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.
- Walk on a 10x10 array
- Start at the position 5, 5
- Never move to a position it has occupied previously
- Never move off the grid
- 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.
- Print each move made. This may be as simple as "23 [3,2]" which would mean that on move 23 the walker was in position 3,2
- Move randomly from among the legal moves.
- Return the number of steps it takes before the walker gets to a point of having no legal moves.
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 board size can be varied. Then:
- Collect the number of moves before exhaustion for 100 trials of a 10x10 board
- Compute and report the mean and standard deviation
- Collect the number of moves before exhaustion for 100 trials of a 20x20 board when starting at position 10,10
- Compute and report the mean and standard deviation.
- Write a brief report (max 1 paragraph) with your interpretation of this data. For instance, you 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. 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
- Go to your directory containing your assignment 1 programs directory and enter the command: script SESSION
where SESSION is some meaningful name
- You will get your command prompt back.
- Run each of the above programs as you normally would.
- Once done, enter the command: exit
- 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/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 file 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.