MCS 275 Spring 2022 Homework 7¶

Course Instructor: Emily Dumas

Instructions:¶

Complete the problems below, which ask you to write Python scripts.
Upload your python code directly to gradescope, i.e. upload the .py files containing your work. (If you upload a screenshot or other file format, you won't get credit.)

Deadline¶

This homework assignment must be submitted in Gradescope by Noon central time on Tuesday 1 March 2022.

Collaboration¶

Collaboration is prohibited, and you may only access resources (books, online, etc.) listed below.

Resources you may consult¶

The course materials you may refer to for this homework are:

Worksheet 7 Solutions
Lecture 15 - Recursion with backtracking
Lecture 16 - Mergesort
Lecture 17 - Quicksort
Any of the course sample programs; of particular note:
Downey's book
MCS 260 course materials from Fall 2021:
- Slides, homework, worksheets, and projects
- Sample programs

Point distribution¶

This homework assignment has two problems, numbered 2 and 3. The grading breakdown is:

Points	Item
2	Autograder
4	Problem 2
4	Problem 3
10	Total

The part marked "autograder" reflects points assigned to your submission based on some simple automated checks for Python syntax, etc.. The result of these checks is shown immediately after you submit.

What to do if you're stuck¶

Ask your instructor or TA a question by email, in office hours, or on discord.

Problem 1 doesn't exist¶

In Gradescope, the score assigned to your homework submission by the autograder (checking for syntax and docstrings) will be recorded as "Problem 1". Therefore, the numbering of the actual problems begins with 2.

Problem 2: List of accessible locations¶

Suppose that instead of trying to solve a maze (find a path from start to goal), you want to determine all accessible squares in the maze (i.e. all locations that can be reached by a path from start).

In a file called hwk7prob2.py, write a function accessible_locations(M) that takes a maze object M and returns a list of all locations in M that can be reached from M.start. It is fine for this function to have other parameters as long as they have default values, so that the function can be called as accessible_locations(M).

As in solvemaze.py, you should use the interface provided by the Maze class from maze.py.

You aren't required to use recursion here, but the most direct way to solve this problem is to make the minimum necessary changes to solvemaze() and retain the basic recursive strategy. The problems from worksheet 7 may also be useful.

Here is an example of the output of this function when applied to the 7x7 example maze we discussed in lecture.

# Need to import maze and define accessible_locations before this will work!
M = maze.MazeExample1()
accessible_locations(M)

[(1, 1),
 (1, 2),
 (1, 3),
 (2, 3),
 (3, 3),
 (4, 3),
 (5, 3),
 (5, 2),
 (5, 1),
 (4, 1),
 (3, 1),
 (3, 4),
 (3, 5),
 (2, 5),
 (1, 5),
 (4, 5),
 (5, 5)]

As a reminder, here is a picture of this maze, which can be used to check the correctness of the list above. 7x7 maze

As another example, this code creates a 5x5 maze with all its interior squares free, and with (2,2) as the start, and tests the function on it.

M = maze.Maze(5,5)
M.apply_border()
M.start = (2,2)

L = accessible_locations(M)
assert(len(L)==9) # make sure we found all 9 interior squares accessible!
L

[(2, 2), (1, 2), (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3)]

Problem 3: Specialized quicksort for few distinct values¶

Suppose you're quicksorting a list that has only a few distinct values, like

[2, 3, 2, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 3, 1, 2, 2, 3, 3, 3]

(which has 20 entries but only 3 distinct values). In this case, a recursive algorithm that repeatedly partitions the list is likely to sometimes end up working on a sublist in which every value is the same. Once the part of the list you're working on looks like that, e.g. [1,1,1,1] or [2,2,2,2,2], it's already sorted and there's no point in partitioning it further and making recursive calls.

Write a version of quicksort that is adapted to this special case by replacing the step that calls partition with:

Check whether every element of (the current part of) the list is equal to the first element (of the current part) of the list.
If so, then this part of the list is already sorted. Return.
Otherwise, partition the list and proceed as usual with recursive calls.

Call the new function quicksort_few_distinct(L) and put it in a file called hwk7prob3.py.