Due: Monday, August 5 by 1pm (not 6pm as has been usual). This earlier time allows us to start doing review meetings Monday afternoon. Handin as usual through the Google form.

There is one set of problems for everyone on this assignment. However, the second segment of programming problems (labeled below) is directed at those aiming for As in the course. If you are not trying to get an A, you can focus on the first set of programming problems and skip the second.

Put your answers to this in a text file called tracing.txt

Here is part of a program for managing orders in an online store. There is a data structure for the Items for sale, as well as a catalog of all items. There is a data structure for Orders, which capture the name of a customer and a list of items that the customer wants to buy. There are also two versions of a function to update the price of an item in the catalog.

At the bottom of the file is a sequence of expressions to evaluate.

• Without running the program, predict what will be in each of k_order and e_order (items and their prices) after the four expressions evaluate (you won’t lose points for an inaccurate prediction – the point of the question is to help you calibrate your predictions against the memory contents.)

• There are four comments in the code marked Memory point. Show the contents of memory (known names and memory) at each of these four points.

  You can write these in a text file or draw (and scan to PDF) pictures of memory drawn on paper. Just make the information for each memory point is clearly labeled so we see which memory layout goes with each point.

Put your answers to this in a text file called scheduling.txt

A university wants to set up data structures and programs to manage how students enroll for courses. There is a master catalog that contains the course names/numbers, and descriptions for all approved courses. Separately, there is a schedule for each semester that indicates which courses are being offered and at what times. You may assume that all offered courses are part of the catalog.

In addition to the schedule of offered classes, individual students also have their personal schedules. A student’s personal schedule consists of a collection of 3-5 courses, none of which should be meeting at the same time.

Answer the following questions about how you would design the data structures, choose concrete data types, and design key functions in a Python program to implement the scheduling system. (Don’t write any actual code for this – this is a conceptual exercise, not a coding one.)

• Assume that every student takes four courses every semester, and that students may change which courses they are taking until a couple of days into the semester. In light of this, which of the following data structures do you prefer for a student’s schedule?

  • a list (of something you decide),

  • a dictionary (with a key and value you decide), or

  • a dictionary whose four possible keys are "course1", "course2", "course3", and "course4"

  EDIT: bullets updated 8/2 at 12:45, as per Piazza post.

  Briefly defend your choice, discussing the strengths and weaknesses of all three options. For options 1 and 2, state the types of the list contents, keys, etc. (It is okay to rate multiple options as acceptable, as long as your answers explain the tradeoffs between the options – our goal here is to see how well you understand these different data structures.)

• The university needs to choose a data structure for the schedule. Common operations on schedules are looking up the times of classes and changing class times.

  Someone has proposed storing the courses as follows:

  @dataclass

  class Course:

  name: str

  hour: int

  minute: int

  schedule = [Course("CS50", 9, 0),

  Course("MATH200", 10, 30),

  Course("ENGL150", 1, 0),

  Course("ARTS240", 10, 0),

  ...]

  Comment on this data structure for the schedule, in light of the two common operations described: what are its strengths and limitations? Would you do anything differently? If so, how would you set this up and why?

• The problem statement said that students cannot be registered for multiple courses that meet at the same time. Imagine that you were writing functions to let students add and drop courses (from their personal schedules), and to let the university change the times of courses. Your function to add courses raises an error if students add a course whose time conflicts with an existing course. Is this enough to avoid time clashes? Either justify that it is or give a couple of sentences explaining what else your code would need to do.

Put your answers to this in a text file called banking.py

Your overall goal is to write several programs that handle basic operations at a bank. The bank offers both checking accounts and savings accounts. Each type of account has a (unique) id number, the name of the customer who owns the account, and the current balance. In addition, savings accounts have an interest rate (a float–for this assignment, use .02 as the interest rate for all accounts). Checking accounts are limited to three withdrawals per month, so these accounts also track how many withdrawals remain (for the given month).

Create data structures and variables as needed for managing accounts, then write the following programs. Your data structure choice should enable the programs to run efficiently (ideally, in less than linear time in the number of accounts).

For all of the following programs, you may assume that the requested ID number is already in use (you don’t have to worry about ID numbers not being found, etc.)

• open_account, which takes the type of account to open (either "checking" or "savings"), the name of the customer who wants the account, and the initial balance for the account (a float). As long as the initial deposit is not negative, the function creates the new account in your data structure and returns the its ID number. This ID number must not be assigned to any other account opened through this function. Raise a ValueError if the initial balance is negative.

  Note: How you track unused id numbers is up to you. There are at least two ways to do this based on what you know. If you want to update a variable that is defined externally to a function, you have to tell Python this by writing global varname inside the function that does the updating.

  ValueError is a special form of Exception. You raise them the same way:

  raise ValueError("here's what went wrong")

• balance, which takes an account id and returns the current balance in the account.

• deposit, which takes the id of the account to deposit into and the amt to deposit (a float) and adds the given amount to the account balance as long as the deposit amount is positive. Raise a ValueError if the deposit amount is not positive.

• withdraw, which takes the id of the account to withdraw from and the amt to withdraw (a float) and deducts the given amount from the account balance as long as the balance is at least as large as the withdrawal amount. For checking accounts, if the customer still has withdrawals available, decrease the withdrawal limit by 1. Otherwise, reduce the balance by another $2 as an "extra withdrawal" fee. Raise a ValueError if the withdrawal amount plus any fee is larger than the balance.

• new_month, which takes your data structure for a collection of accounts and adjusts each account for the start of a new month. Checking accounts get their number of allowed withdrawals reset to 3. Savings accounts get their balances increased by the interest rate.

  If you are using a hashtable, you may need to know how to loop over all of the keys in the dictionary. You can do this with the following appraoch (where mydict is an existing hashtable/dictionary)

  for key in mydict.keys():

  print(key) # this is an example -- any operation on key is fine

• In addition to the tests you wrote for individual functions, provide three test cases that span across these functions, (i.e., what is the result of balance after various sequences of the other operations). Each test case should check for a different situation that might arise (rather than just being the same test with different numbers).

  To test for ValueErrors you can write tests such as the following (testlight.py supports this):

  testValueError("deposit negative", lambda: deposit(1433, -100))

  The lambda is needed so that the testing function can see the error that you raised; without it, the error occurs before the testing function in testlight gets to check the output of the call to deposit.

This next part is for those aiming for As in the course

Now that the basic banking features are working, the bank manager asks you to add a way to remember the history of transactions made on accounts. The manager wants your code to remember every account creation, deposit, and withdrawal action that has been taken since your code file was last loaded/run. The bank wants to use this information for two purposes: first, to let account holders see a history of their transactions, and second, to let the bank create reports on activity across all of the accounts.

• Extend your existing programs and data structures as needed to track transactions on accounts. You get to decide where to put this information, what data structure/data type to use, etc. Write a few sentences (in a comment) justifying your choices.

• Provide a function account_history, which takes an account id and returns a list of all transactions on the account, from most recent to least recent.

  Note: "recent" is based on the order in which transactions occurred – we are NOT asking you to add dates to the data. If you want to add an item to the beginning of a list, use L.insert(0, item) (you can use this to insert at any position within a list).

• Provide a function total_deposits, which returns the sum of all deposits made at the bank over all time (across all accounts).

Get your solutions to the first set of programming problems done and working before you add the transactions histories. This way, if you don’t get transactions histories done, you still have a solid piece of work to bring to your review meeting. You may want to save a copy of your work on the initial programming problems as a separate Python file in your project (not required).

As the final assignment, this is your chance to pull together what you have learned about data structures, coding, organizing code (into helpers), and testing. We’ll be looking at all of these when we do your in-person review of your work on this project.

During the review, Kathi will ask you to explain certain parts of your work. Other questions may include how/why your code works, what choices you might have made differently, and so on. This isn’t something you need to study for — we’re just going to go over your ideas and solutions for the problems on this assignment.

If you’ve been struggling in the course, we’ll focus on the basic banking functions in your review rather than the transactions history. You can pass the course/assignment without doing the transactions histories, but those aiming for As should do the transactions histories as well.

Upload three files: “scheduling.txt”, “tracing.PDF” (or "tracing.txt"), and “banking.py”.