Past Slides:

• ppt pdf Week 1 (Basics; Functions)
• ppt pdf Week 2 (For Loops; String Multiplication)
• ppt pdf Week 3 (Parameters; Graphics)
• ppt pdf Week 4 (If/Else; Logic; Strings)
• ppt pdf Week 5 (While Loops; Random Numbers; Tuples)
• ppt pdf Week 6 (Review; File I/O)
• ppt pdf Week 7 (Lists)
• ppt pdf Week 8 (Classes and Objects)
• ppt pdf Week 9 (Inheritance; Games with Pygame)
• ppt pdf Week 10 (Games with Pygame part 2)
• CSE 142 Autumn 2008's Python page

Homework 6: Anagrams
Due: Fri 3/6, 11:30pm. Turn in HW6P here.
No late turnins accepted.

In unit 6 of the course we learned about recursive backtracking. Recursive backtracking is basically the same in Python; a method can call itself. There is no special syntax for it. The main change involved is in the types of collections used; we often just use lists in Python where in Java we would have used sets, stacks, arrays, etc.

For your assignment this week, create a Python file called anagrams.py that defines a class GrammarSolver much like in the Java Homework 6. Our solution to this program is 60 lines long.

Define the following operations in your class. These are described below in terms of the way they would be called by a client. In your code you must also declare a self parameter for each method.

• constructor (dictionary) - Constructs an anagram solver over the given list of words, a la the constructor in the Java assignment. You may assume that the list of words passed to you is in sorted alphabetical order. You should raise an exception if the list is None.
• words(phrase) - Returns a list of all words contained in the given phrase, a la getWords from the Java assignment. The words must appear in sorted alphabetical order in the list.
• print_anagrams(phrase, max) - prints every anagram contained in the given phrase in the same order and format as in the Java assignment, a la print from the Java assignment. In the Java version we had 2 versions of print, one with a max and one without. In Python it is illegal to have two functions with the same name, but you can specify a parameter as optional by giving it a default value. You should do so with the max parameter, defaulting to 0 if no max is passed. See the week 3 slides for how to do this. This method should raise an exception if the phrase passed is None or if the max passed is less than 0.

In this assignment you will interact with provided LetterInventory objects, so you should say the following at the start of your file: from letterinventory import *

A LetterInventory object has the following constructors and methods:

• constructor (s) - Constructs a letter inventory to count the letters in the given string. Raises an exception if the string passed is None.
• add(other) - Adds the letters in the given string or inventory to those in this one. For example, adding inventories [ehllo] and [hhio] yields [ehhhillo]. Or adding inventory [ehllo] plus string "hi ho" yields [ehhhillo]. Raises an exception if the string or inventory passed is None.
• __contains__(other) - You can test whether a string or inventory s is contained in another inventory inv by writing: if s in inv: ...
• empty() - Returns True if there are no letters in this inventory, or False if the inventory does contain letters.
• __len__() - You can ask how many letters are contained in an inventory inv by writing: len(inv)
• subtract(other) - Removes the letters in the given string or inventory from this one. For example, [ehhhillo] minus [ehho] yields [hill], or [ehhhillo] minus "he ho" yields [hill]. Raises an exception if the string/inventory passed is None or if the letters in the other string/inventory are not contained in this one.
• __str__() - You can see a string representation of an inventory inv by writing: str(inv)

Files:

• anagrammain.py
• letterinventory.pyc (compiled version of LetterInventory class you can use; put it in the same folder as your code)

Homework 5: Grammar Solver
Due: Fri 2/27, 11:30pm. Turn in HW5P here.
No late turnins accepted.

In week 5 of the course we learned about recursion. Recursion is basically the same in Python; a method can call itself. There is no special syntax for it.

For your assignment this week, create a Python file called grammarsolver.py that defines a class GrammarSolver much like in the Java Homework 5.

Define the following operations in your class. These are described below in terms of the way they would be called by a client. In your code you must also declare a self parameter for each method.

• constructor (rules) - constructs a grammar solver over the given list of rules, a la the constructor in the Java assignment. You should break apart the rules and store them into a dictionary (where the key is a non-terminal symbol and the value is some representation of the expansion rules that symbol can be expanded into), much like you would have used a Map in the Java version. You can break apart a string using its split method. Raises an exception if the list is None or has 0 length
• symbols() - returns a list of the non-terminal symbols in your grammar, a la getSymbols from the Java assignment; the symbols must appear in sorted alphabetical order in the list
• contains(symbol) - returns True if the given string represents a non-terminal symbol in this grammar, a la contains from the Java assignment. Raises an exception if the string is None or has 0 length
• generate(symbol) - returns a string representing a randomly chosen expansion of the given symbol, a la generate from the Java assignment. If the given string is not a non-terminal in this grammar, assume it is a terminal and just return it. Must be written recursively. Raises an exception if the string is None or has 0 length

Files:

• grammarmain.py

Links:

• Random numbers and values: http://docs.python.org/library/random.html
• String methods: http://docs.python.org/library/string.html

Homework 4: Assassin
Due: Sat 2/14, 11:30pm. Turn in HW4P here.
No late turnins accepted.

In week 4 of the course we learned about implementing linked lists. Python can do much the same thing, since variables that store objects in Python also do so by reference. So you can create a linked list in Python by creating many node objects, each with a next reference to another node.

The equivalent of null in Python is called None, and it behaves much the same way. You can test whether a variable is equal to None (best done by writing: if myVariable is None: ... rather than using ==), and you can store None in a variable, but None is not an object and cannot be dereferenced.

We are also going to practice exceptions in this assignment. To throw ("raise") an exception in Python, write the following:

raise Exception("your message here")

For your assignment this week, create a Python file called assassinmanager.py that defines a class AssassinManager much like in the Java Homework 4. You must implement your class using a collection of linked nodes; you may not create any Python lists or other collection objects.

Define the following operations in your class. These are described below in terms of the way they would be called by a client. In your code you must also declare a self parameter for each method.

• constructor (names) - constructs an assassin manager over the given list of names, a la the constructor in the Java assignment; raises an exception if the list is None or is empty (0 length)
• print_kill_ring() - prints the current contents of your kill ring, a la printKillRing from the Java assignment
• print_graveyard() - prints the current contents of your graveyard, a la printGraveyard from the Java assignment
• kill_ring_contains(name) - returns True if your kill ring contains the given name and False if not, a la killRingContains from the Java assignment
• graveyard_contains(name) - returns True if your graveyard contains the given name and False if not, a la graveyardContains from the Java assignment
• game_over() - returns True if the game has ended and False otherwise, a la isGameOver from the Java assignment
• winner() - returns a string representing the name of the person who has won the game (or None if the game is not over yet), a la getWinner from the Java assignment
• kill(name) - removes the given name from the kill ring and puts it into the front of the graveyard, a la kill from the Java assignment. Raises an exception if the game is not over or if the kill ring does not contain the given name

You will interact with AssassinNode objects, so you should say the following at the start of your program: from assassinnode import *

An AssassinNode object has the following constructors and fields:

• constructor (name, next = None) - constructs a new node to store the given name. You can optionally pass a reference to a next node, or if no next node is passed, None is used
• name - a public data field representing this node's name as a string
• killer - a public data field representing the person who killed this node as a string; initially None
• next - a public data field representing a reference to the AssassinNode after this one, or None if there is no next node

Files:

• assassinnode.py
• assassinmain.py

Links:

• Raising errors and exceptions: http://docs.python.org/tutorial/errors.html

Homework 3: Stable Marriage
Due: Wed 2/11, 11:30pm. Turn in HW3P here.
No late turnins accepted.

In week 3 of the course we learned about using Java's Set and Map collections. Python has two built-in types called set and dict (short for "dictionary") that correspond to Sets and Maps. You can create a new empty dictionary by storing the value {}. You can store a key/value pair using [] brackets, such as my_map["Marty"] = "Stepp". You can use the len function to see how many key/value pairs are in a set or dictionary. You can use if ... in and for ... in to ask whether a dictionary contains a key or to loop over the keys respectively. Sets and dictionaries have other methods and properties you can read about from the links below.

For your assignment this week, create a Python file called matchmaker.py that defines a class MatchMaker much like in the Java Homework 3.

Define the following operations in your class. These are described below in terms of the way they would be called by a client. In your code you must also declare a self parameter for each method.

• constructor (men, women) - constructs a match maker over the given list of men and list of women
• round() - returns the current round number a la getRound from the Java assignment
• next() - performs the next round of the Gale-Shapley algorithm, a la nextMatchRound from the Java assignment
• stable() - returns a boolean value of True if the last call to next had no changes and False otherwise, a la isStable from the Java assignment
• __str__() - returns a string representation of the match maker, a la toString from the Java assignment

You will interact with Person objects, so you should say the following at the start of your program: from person import *

A Person object has the following useful members:

• name - a public data field representing this person's name as a string, a la getName from the Java assignment
• fiancee - a public data field representing this person's fiancee as a Person object (stores the value None if single), a la getFiancee from the Java assignment
• preferences - a public data field representing this person's ordered mate preferences as a list of strings, a la getPreferences from the Java assignment. For example, if you have a Person object p you can learn his first-preferred mate's name by writing: mate_name = p.preferences[0]
• rankings - a public data field that is a dictionary (map) where the keys are persons' names and the values are this person's integer rankings for that person, a la getRankings from the Java assignment. For example, if you have a Person object p and you want to know his ranking for Suzie, you'd write: suzie_rank = p.rankings["Suzie"]
• engage(mate) - sets this person to be engaged to the given other person, a la engageTo from the Java assignment
• single() - returns True if this person does not have a fiancee (if the fiancee field's value is None), a la isSingle from the Java assignment
• __str__() - returns a string representation of the person, a la toString from the Java assignment

Files:

• person.py
• stablemarriagemain.py

Links:

• More information about dictionaries: http://docs.python.org/tutorial/datastructures.html#dictionaries
• More information about sets: http://docs.python.org/tutorial/datastructures.html#sets

Homework 2: HTML Validator
Due: Wed 1/28, 11:30pm. Turn in HW2P here.
No late turnins accepted.

In week 2 of the course we learned about using Java's collections such as lists, stacks, and queues. Python's built-in list type essentially serves as all of these structures. A list can serve as a queue just by looping over its elements. It can serve as a stack by using its append method to push and its pop method to pop. To peek, just examine the element at index [0] for a queue or the element at index [-1] for a stack.

For your assignment this week, create a Python file called htmlvalidator.py that defines a class HtmlValidator much like in the Java Homework 2.

Define the following operations in your class:

• tags - a field storing the current list of HTML tags to process (replaces getTags, setTags methods)
• __init__(self, tags) - constructor that accepts a list of HTML tags (objects of type HtmlTag) to process
• validate(self) - prints indented output and errors in the list of HTML tags, much like the same method in Java's HW2

You will interact with HtmlTag objects, so you should say the following at the start of your program: from htmltag import *

An HtmlTag object has the following methods:

• matches(other) - returns True if the given other tag matches this tag; that is, if they have the same element but opposite types, such as <body> and </body>.
• requires_closing_tag() - Returns True if this tag requires a matching closing tag; usually this is True, except for certain elements such as br and img.
• __str__() - Returns a string representation of this HTML tag, such as "</table>". Allows the str() conversion function to be used on HtmlTag objects.

Files:

• htmltag.py
• testvalidator.py

Links:

• More information about lists and other data structures: http://docs.python.org/tutorial/datastructures.html

Homework 1: SortedIntList
Due: Wed 1/21, 11:30pm. Turn in HW1P here.
No late turnins accepted.

In week 1 of the course we learned about the idea of collections and implemented an ArrayIntList collection together. Python also has collections built in; in particular, its built-in list type is much like an ArrayIntList, but it can store any type of data.

For your assignment this week, create a Python file called sortedintlist.py that implements a class SortedIntList. Each SortedIntList object stores a sorted list of values. You should extend our provided ArrayIntList class from the file arrayintlist.py. (The file names are misnomers because you could store any type of sortable value in the lists.) Your file should work with the provided testlist.py. You'll want to review the syntax for classes and (briefly) inheritance from weeks 8-9 before writing this program.

Define (and/or override from ArrayIntList) the following operations on your list:

• __init__(self, unique=False) - constructor with optional unique boolean parameter
• append(self, value) - adds given value in sorted order
• __contains__(self, value) - searches the list for a value using binary search
• get_unique(self) - return whether only unique values are allowed
• set_unique(self, unique) - set whether only unique values are allowed; if True, removes all duplicates from the list

To do a binary search in Python, use the bisect, bisect_left, or insort functions. Documentation for these functions is at the link below. To use them, remember to write: from bisect import *

Since the provided testlist.py is not a very good or exhaustive test, you are encouraged to write your own testing code to make sure your list works. If you like, you can turn in your own testlist.py or share your testing code with others on the message board.

Files:

• arrayintlist.py
• testlist.py

Links:

• Implementing a sequence type: http://docs.python.org/reference/datamodel.html#sequence-types
• The bisect library (binary search): http://docs.python.org/library/bisect.html
• More information about lists and other data structures: http://docs.python.org/tutorial/datastructures.html