CS 220 01/Zelle Winter 2020

OOP and Intro Data Structures


Read Sections 1.1, 1.2

Elapsed Days functions (due 1/13)

You should try your hand at implementing these functions, which will be useful for the elapsed days problem that we are tackling in class.

	 def make_date(datestring):
	     """ Convert string to date.
	         datestr is a date in month/day/year form (e.g. "1/10/2019").
	         Returns 3 ints: day, month, and year, representing the date.
	 def days_in_year(year):
	         Calculate days in year.
	         year is an int. 
	         Returns the number of days in year.

	 def is_leap_year(year):
	         Determine whether year is a leap year
                 year is an int.
	         Returns a Boolean indicating leap year status of year

Note: You will not be handing in this code yet, but I will ask for volunteers to put some code on the boards for us to discuss.

Elapsed Days program (due 1/20, midnight)

Implement and test the complete elapsed days program that we have been designing in class. The input to the program is two dates entered by the user. The output is the total elapsed days between the two dates. Here are the rest of the function specifications from our design:

	    def days_in_month(month):
	            Calculate number of days in month.
	            month is an int in range(1, 13) representing a month number.
	            Returns the number of days in the month in a non-leap year.

	    def day_number(date):
	           Calculate the ordinal day number of the date
	           date is a triple of ints (day, month, year) representing a date.
	           Returns an int in range(1, 367) that corresponds to the ordinal
	               position of date in year. For example, January 1st produces 1, 
	               and December 31 produces 365 or366, depending on whether it 
                       is a leap year or not.

	    def elapsed_days(start_date, end_date):
	           Calculate number of days between start_ and end_date.
	           Both parameters are triples of ints (day, month, year).
	           Returns an int, which is the elapsed time in days.

You have considerable latitude in how to implement each function in this design, including your main program, but you must implement the 6 functions as specified. If you have any questions about the design, ask for clarification.

You should strive to adhere to the guidelines for good program design that you learned in CS 120. Use descriptive variable names, good explanations/prompts for your users, and readable code layout. Use functions to avoid code duplication, and be sure to include descriptions of the functions as docstrings (see specifications above for help with that). You do not need to express these descriptions as pre- and post- conditions (ala Section 1.2 of our tetbook), but you certainly may do that if you want to.

(due 1/17, classtime) pre-post homework

Finish the functions in from the prepost.py file that is posted under handouts. Once you think you have correctly implemented the functions, test them using the program fractal.py also available in the handouts/prepost folder. Then turn in a written report detailing:

Your report is due at the beginning of Friday's class.

(due 1/22) Chapter 1 revew (part 1)

Do Chapter 1 Review Exercises (p 33): T/F 1--5, Multiple Choice 1--3.
have these on-paper suitable for hand-in at the start of class.

(due 1/29) wavefns.py and tonelib.py

Complete and test the implementation of the functions in wavefns.py and tonelib.py from the handouts/tonelib folder. The standard waveforms should look like this.

You will have to test your tonelib functions "by ear."

(due 1/31) Chapter 1 Review (part 2)

Finish reading Chapter 1 and do Chapter 1 Review Exercises (p 33): T/F 6--10, Multiple Choice 4--10.
have these on-paper suitable for hand-in at the start of class.

(due 2/5) Read Chapter 2

(due 2/7) piano.py modifications

This is the second part of the pianolab. We will handle this in class on 2-7, so don't be concerned about that link on Socrates :-).

(due 2/12) Chapter 2 Review Questions

Answer the T/F and multiple choice questions at the end of Chapter 2. Have your answers on paper suitable for hand-in at the start of class.

(due 2/14) Rational Lab

Complete the Rational.py and test_Rational.py classes such that all Rationals are stored in simplified form (reduced with positive denominator) and implement addition and subtraction. We will spend some time in class on 2/12 working on this.

(due 2/14) Chapter 3 Reading

Read 3.1--3.3.

(due 2/21, midnight) soundwave.py

You are to write a SoundWave class as discussed in class. The basic idea is to encapsulate our list of audio samples in a class so that we can add operations that are useful for creating and playing sounds.

Rather than working from detailed specifications, for this project you will be working from a file of testing code that exercises the various features of the SoundWave class. You can find the test file here. Most of that file has been "commented out" by putting it in triple quotes. You should work on getting the tests to work one at a time. Once you get a test working, move the triple quote down below the next test, and get it working.

(due 2/24) read section 3.6 -- dictionaries

Read the first part of the optional section of Chapter 3. You may safely skip the extended Markov chain example.

(due 2/24) keys and frequencies

Read this wikipedia page: Piano Key Frequencies.

(due 2/28) synth.py

Complete the synth.py file to pass the tests in testsynth.py. Note: you will have to listen to the files that are created by the tests to determine whether they all "passed." You can find the see files here.

(due 3/9) Read (parts of) Chapter 4

Read Sections 4.1--4.3, 4.5, and 4.7.

(due 3/11) tune.py

In the handouts/tune folder you will find a set of files for the next phase of our audio project. As discussed in class, we are implementing a Tune class that stores a sequence of notes which can then be turned into sound using a synthesizer.

The main point of the Tune class is that it accepts note specifications using abc notation (see the parsenote function) and then allows access to the tune as a sequence of (key_number, duration) pairs suitable for use on a synthesizer. The actual pairs produced from the sequence is dertemined by the transpose and tempo attributes. Where transpose shifts the key by a fixed integer amount and tempo (given in beats per minute) determines the duration of the notes. See the testing code for details.

The handouts include the following files:


A unittest file that tests the required methods of the Tune class.


A little example application that uses the Tune class to produce a wav file with a simple, familiar melody.


A (nearly) complete implementation of the Tune class that uses a Python list as the underlying data structure. This file passes all of the tests in testtune except for duration, which is left unimplemented. You should be able to run tune_example using this implementation. Do you recognize the song?


This is the main file you will be working on. It is a shell of a re-implementation of the Tune class, but storing the sequence of notes in a linked structure (ala Chapter 4.)


My implementation of the Basic_Synth. This is provided just in case yours is not yet working.

You should do the following:

  1. Study the supplied example and testing code to understand exactly what a Tune does and how it is used.
  2. Implement the duration method in Tunelist so that all tests in testtune pass cleanly.
  3. Use ideas from Chapter 4 to complete tune.py using a linked implementation of the note sequence. Note: you should NOT use a Python list or any other collection to store the notes. Use the supplied _NoteNode class and linking. Your Tune class should pass all the tests and work with the example program.
You only need to turn in your final tune.py file.

(3/13) Reminder: Exam 2

Remember our second exam is now scheduled for Friday the 13th (horrors!). That is one class day later than listed on the syllabus. It will cover the portions of Chapters 2--4 that we have discussed and used.

Announcement on "going remote"

As I explained in class this morning, I will be doing my best to make sure that everyone can successfully complete CS 220 via remote learning. I do not yet know exactly what form everything will take, but my plan at the moment is to use our existing online resources, mainly this page and Socrates. I am asking you to become a somewhat more independent learner, but I will also do everything I can to help out so that everyone can learn the material.

For the foreseeable future, I will continue to be available at class times to answer questions and discuss material with those students who feel they need in-person guidance. We will follow social distancing standards for those sessions. Students will sit at separate tables and I will disinfect our tables beforehand. If you are in a higher risk group or have ANY cold-like symptoms, I would ask you not to attend. Really, you do not need to be there. Stay home if you can. Any information discussed in-person will be shared with everyone via online mechanisms.

Keep watching this page for updates on how our class will proceed in remote mode. This is just as new for me as it is for you, and I will need to make adjustments.

(due 3/18) Stacks

Start reading Chapter 5 through section 2.5.4. I will start a discussion thread for this material on Socrates. If you have any questions about the reading, post them there and I will try to directly address them. Also feel free to try to answer your classmates questions, in the case that I have not yet had a chance to respond. I will be posting some specific assignments for you sometime tomorrow. Nothing will be due before Friday at midnight. So you have some time to transition.

(3/17) Announcements NO IN-PERSON MEETINGS

Given recent guidance from both the federal government and the State of Iowa with respect to group gatherings, I will NOT be doing any in-person meetings during class time as I had previously thought. My apologies for the change in plans. I am working on an alternative and may offer some "virtual class meetings" next week, for those who would like some personal help. Stay tuned.

I will be posting a series of "study guides" for you to apply the ideas that you are reading in the textbook. These questions will emphasize the material that I will hold you responsible for, come final time. You can either type up your answers or write them out (neatly) by hand and take a picture of them (use an app like camscanner for best results) for hand-in. I will grade these on "effort," not correctness, and solutions will be posted sometime after the due date. The grades on these will count as quizzes.

(due 3/23, midnight) chapt5_sg_a

Answer the questions in the study guide: chapt5_sg_a Turn this in on Socrates under the assignment: chapter5_sg_a. Please refer to previous announcement for how this will be graded. (edit: The deadline has been extended)

(due 3/25, midnight) postfixeval.py

Study the postfix evaluation algorithm as discussed on the bottom of page 161. Then complete postfixeval.py program found in the handouts/chapter5 folder. (edit: The deadline has been extended).

(due 3/20) Read Sections 5.3 and 5.4

As you read these sections, pay articular attention to the "circular array" implementation technique discussed on pages 173 and 174.

(due 3/25, midnight) chapt5_sg_b

Answer the questions in the study guide: chapt5_sg_b Turn this in on Socrates under the assignment: chapter5_sg_b. Please refer to previous announcement for how this will be graded.

(due 3/27, midnight) bqueue.py

A BoundedQueue is a queue with a fixed maximum capacity. It is easily implemented using the "circular list" technique that was explored in the study guide. Complete the BoundedQueue implementation in bqueue.py which is in the handouts/chapter5 folder. In that folder you will also find test_bqueue.py which contains unit tests for your implementation. Studying and understanding the test code would be a good place to start.

(due 3/27, midnight) Exam 2 Second Chance

For those of you who wish to improve your score on the second exam. Your redo is due in 1 week. I will put a link on Socrates to turn it in.

(3/23) UPDATE

Due to having to attend to some unexpected departmental business, I did not get to assignment updates today (as promised in my email this morning). Look for updates tomorrow.

(due 3/30) Read Sections 6.1--6.3

(due 3/30, midnight) chapt6_sg_a

Answer the questions in the study guide: chapt6_sg_a Turn this in on Socrates under the assignment: chapt6_sg_a.

(due 4/8) OPTIONAL Project: StringSynth

This is an OPTIONAL project. If you choose to do it, it is worth up to 10 points of extra-credit applied to your project scores. Since it is extra-credit, I will not be providing detailed individual help or spending a lot of time on it in our class help sessions. I am putting it out there for those who are looking for extra challlenges or have missing project scores that they would like to "fix."

This project is an application of bqueue.py and is an extension of our audio project. The assignment is to create a new StringSynth class that implements a simple version of the Karplus-Strong algorithm to simulate the physics of a vibration of a plucked string. Here is the basic algorithm to produce a toneof a given frequency, freq:

	   q = a BoundedQueue with capacity of samplerate/freq
	   fill q to capacity with random float values between -1 and 1
	   samples = []
	   for number of samples desired:
	       sample = q.dequeue()
	       add sample to samples
	       filter_sample = (sample + q.front())/2 * decay

	   return a Soundwave created from samples

The decay value in this algorithm represents a damping factor that is provided when the Synthesizer is created. A good default value is 0.996. Also note that the queue stays the same size during sample generation, as there is exactly one dequeue and one enqueue each time through the loop.

Starter code and example outputs can be found in the folder: handouts/string_synth. The StringSynth class to complete is in the synth.py file. Note, that since it inherits from the BasicSynth class, you only have to write the __init__ and key methods. The other methods can be inherited unchanged.

(due 4/1, midnight) chapt6_sg_b

Answer the questions in the study guide: chapt6_sg_b Turn this in on Socrates under the assignment: chapt6_sg_b.

(due 4/3, midnight) ccurve.py

Look at excercises 10 and 11, starting on page 217. I have provided a solution to Exercise 10 using a simple Turtle module based on graphics.py. You can find all the code in the Chapter 6 folder. Using the snoflake.py file as an example, write a program to draw a c_curve, as explained in exercise 11.

(due 4/6, midnight) chapt7_sg_a

Answer the questions in the study guide: chapt7_sg_a Turn this in on Socrates under the assignment: chapt7_sg_a.

(due 4/8, midnight) chapt7_sg_b

Answer the questions in the study guide: chapt7_sg_b Turn this in on Socrates under the assignment: chapt7_sg_b.

(due 4/10, midnight) mset.py.py

Your project is to modify the binary search tree code to implement a multiset ADT, and then use it to write a sorting algorithm. A detailed description, along with the starting code, is in the folder handouts/chapter7.