CS 112 – Spring 2020 – Programming Assignment 7
1 | Multi-dimensional lists |
Assignment basics file:
https://piazza.com/class_profile/get_resource/k4wblafqtoj2cx/k5x3ennufm34cg
Tester file:
will be available in a few days
Background
The purpose of this assignment is to practice building, inspecting, and modifying multi-dimensional
lists effectively. This often requires nested for-loops, but not always. It involves thinking of the
structure like an M x N matrix of labeled spots, each with a row and column index, or a higher
dimensional structure like a 3D matrix (e.g. M x N x K ) that has indexes for height, width and depth.
Multi-dimensional lists aren’t conceptually more difficult than single-dimension lists, but in practice
the nested loops, aliasing, and more complex traversals and interactions merit some extra practice
and thought.
Guidelines
You are not allowed to import anything.
You are not allowed to use sets and dictionaries
You are not allowed to use anything that hasn’t been covered in class, including the list
comprehension construct (if you don’t know what this is, don’t worry, it’s impossible to use it by
accident!)
From built-in functions, you are allowed to call only range() , len() , int(), str()
From list methods, you are allowed to use only .append() and .insert(). Please do not
ask on piazza whether you can use .sort(), .remove(), .pop() .count() etc.
You are not allowed to use slicing in any form.
The only allowed method to remove an item from a list is the del operator.
You are not allowed to hard-code exhaustive if-elif-elif statements to handle all possible
list lengths. Your code should work with any list length.
Assumptions
You may assume that:
- The types of the values that are sent to the functions are the proper ones, you don’t have to
validate them (e.g. word is a string, not an integer, etc.).
- The functions are going to be called with usable values , you don’t have to validate them (e.g.
table contains single-character strings only).
Testing
In this assignment testing will be done as before. You will start working on the assignment without a
tester, and you will do your own testing based on the examples we provide in this document as well
as other examples you can come up with. A few days later we will provide an actual tester but don’t
wait for it in order to start working on the assignment as there won’t be enough time to complete it
before the deadline. The purpose of the delayed release of the tester is for you to put more emphasis/
effort on writing logically correct programs instead of trying to pass certain tests only. When we post
the tester, we’re going to omit some of the test cases that will be used for grading. This means that
there might be errors in your code even if the tester is giving you no errors. You must do your own
checks to make sure that you haven’t missed anything and your code is correct. You do not need to
modify the tester, just test on your own any way you like. Again, the goal is to help you put more focus
on writing logically correct programs instead of trying to pass certain tests only.
Grading Rubric
Submitted correctly:
Code is well commented:
Tester calculations correct:
Unknown test cases
TOTAL:
2
8
60
30
100
# see assignment basics file for file requirements!
# see assignment basics file for how to comment!
# see assignment basics file for how to test!
# test cases that are omitted from the tester
Note : If your code does not run and crashes due to errors, it will receive zero points. Turning in
running code is essential.
Functions
The signature of each function is provided below, do not make any changes to them otherwise the
tester will not work properly. The following are the functions you must implement.
create_3D(H,W,D)
Description: It creates a list of list of list of ints (i.e. a 3D matrix) with dimensions H x W x D. The value of
each item is the sum of its three indexes.
1 | Parameters: H (int) is the height, W (int) is the width, D (int) is the depth |
1 | Return value: list of list of list of int |
1 | Example: |
copy_3D(xs)
Description: It creates a deep copy of a 3D matrix xs. Make sure the copy you make is not an alias or a
shallow copy.
1 | Parameters: xs (list of list of list of int). Sublists can have different sizes, i.e. do not assume |
1 | Return value: list of list of list of int |
1 | Example: |
sublist(xs, total)
Description: It finds the smallest square-size sublist of a 2D list xs that the sum of its values is greater
than or equal to total. Minimum size of a sublist is 2x2. If there are more than one equally sized
sublists that satisfy the requirements, it returns the one with the largest sum. If no sublist satisfies the
requirements it returns False.
1 | Parameters: xs (list of list of int), total (int). You’re not allowed to modify xs. |
1 | Return value: a square size list of list of int or False |
1 | Example: |
crossword(table, word)
Description: Given table , a 2D list of unordered characters, and a single word , it searches each row of
the table individually to see if some or all of its characters can put together to form the word. It
returns the number of the first row that holds the required characters, or False if no row has the
necessary characters.
1 | Parameters: table (list of list of string), word (string). Modification of table is allowed. |
1 | Return value: int or False |
1 | Example: |
1 | crossword([['t','b','c','a'], |
1 | crossword([['t','b','c','a'], |
sparse(compact)
Description: A sparse matrix is a 2D matrix that has many zeros. Assume that for storage efficiency
someone has converted a sparse matrix into a compact 2D matrix with dimensions Nx3 where _N_ is the
number of non-zero items in the original sparse matrix. In each row of compact , the first column holds
the value of a non-zero item of the sparse matrix, the second column holds the row that this item
resides in the sparse matrix, and the third column holds the column that this item resides in the sparse
matrix. Write a function that given a compact matrix it returns the original sparse matrix. Assume the
last row and the last column of the sparse matrix contain at least one non-zero item.
1 | Parameters: compact (list of list of int). |
1 | Return value: a sparse list of list of int |
1 | Example: |