CSE 143: Computer Programming II, Winter 2012

CSE 142 Python Slides (for review):

• 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 (SAGE)
• ppt pdf Week 9 (Classes and Objects)
• ppt pdf Week 10 (Games with Pygame)
• CSE 142 Autumn 2011's Python page

Homework 6: Anagrams
Due: Sat 3/3, 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 Anagrams 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. (We have to change the method name because print is a keyword in Python.) 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 past 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 get 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)
• dict1.txt

Session #7 (Tuesday, February 21)

In this section we disscussed how networks work and looked at a sample program in python.

• Files: server.py , client.py

Homework 5: Grammar Solver
Due: Tue 2/18, 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 (see the keys method of Python dictionaries)
• 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 a length of 0
• 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

Session #5 (Tuesday, February 7)

In this session we talked about MapReduce, stacks, queues, dictionaries, sets and list comprehensions.

• Lecture Slides: ppt , pdf

Homework 4: Assassin
Due: Sat 2/11, 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
• names.txt

Links:

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

Session #4 (Tuesday, January 31)

In this session we continued talking about the functional aspects of Python. We discussed map, reduce and filter in more depth and introduced MapReduce.

Provided files:

• Lecture Slides: ppt , pdf

Homework 3: HTML Validator
Due: Sat Feb 4, 11:30pm. Turn in HW3P here.
No late turnins accepted.

In week 3 of CSE 143 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 3.

Define the following operations in your class:

• tags - a field storing the current list of HTML tags to process (no getTags method is required; the client can access the tags field directly)
• __init__(self, tags) - constructor that accepts a list of HTML tags (objects of type HtmlTag) to process; raises an exception if the queue of tags is None; if no queue is passed, defaults to an empty queue of []
• add_tag(self, tag) - adds the given HtmlTag object to the end of the validator's queue; raises an exception if the tag is None
• remove_all(self, element) - removes all tags that match the given element; raises an exception if element is None
• validate(self) - prints indented output and errors in the list of HTML tags, much like the same method in the Java assignment

If you really implement these methods in the "Pythonic" way, you shouldn't need any loops in methods other than validate. You can solve them using built-in functions taught in this future sessions. (You also shouldn't need a for loop to print spaces for indentation.)

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>.
• is_self_closing() - Returns True if this tag doesn't require a matching closing tag; this will be True only 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.

The other "get" methods are missing because the data in a tag such as its element and is_open_tag can be accessed directly through the fields.

Files:

• htmltag.py
• validatormain.py

Links:

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

Session #3 (Tuesday, January 25)

In this session we talked about some of the functional aspects of Python including passing methods as parameters.

• Lecture Slides: ppt , pdf

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

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 can use our provided ArrayIntList class from the file arrayintlist.py as a starting point. (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 from this week before writing your program. Make sure to comment your class and methods.

Define 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
• max(self) - return the maximum element from the list; if list is empty, raises an exception
• min(self) - return the minimum element from the list; if list is empty, raises an exception
• __str__(self) - return a string representation of the list, such as "S:[4, 5, 5, 17, 17]" or "S:[4, 5, 17]U"

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

Session #2 (Tuesday, January 17)

In this session we talked about OOP in Python and how it differs from OOP in Java.

• Lecture Slides: ppt , pdf

Homework 1: Tiles
Due: Sat 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 using ArrayList. In week 2 we implemented an ArrayIntList collection together. Python also has collections built in; in particular, its built-in list type is much like an ArrayList.

For your assignment this week, create a Python file called tilemanager.py that implements a class TileManager. Each TileManager object stores a list of tiles. Each tile is represented as a Tile object; the Tile class is defined our provided file tile.py. Your tile manager will be created by the overall main program that is defined in tilemain.py. You'll want to review the syntax for classes and objects from 142 week 8 before writing this program.

Define the following operations in your TileManager class:

• __init__(self) - initialize a new tile manager object. Initially the manager is not storing any tile.
• add_tile(self, rect) - add the given tile to the end of the tile manager's list of tiles.
• draw_all(self, panel) - should cause all of the tiles in the tile manager to draw themselves onto the given drawing panel. You do not need to do this yourself directly by calling methods on the panel object; each Tile object already has a draw method that it can use to draw itself. You just need to pass on the panel object to each tile to do the rest of the work. Draw the tiles in order from bottom (start) to top (end) of your manager's list.
• rise(self, x, y) - This is exactly the same as the raise method in the Java version, but Python uses raise as a keyword so the name had to be changed. The graphical user interface ("GUI") calls this method on your tile manager when the user left-clicks. It passes you the x/y coordinates the user clicked. If these coordinates touch any tiles, you should move the topmost of these tiles to the very top (end) of the list. If the coordinates do not touch any tiles, no action or error should occur.
• lower(self, x, y) - The GUI calls this method on your tiles manager when the user Shift-left-clicks. If these coordinates touch any tiles, your method should move the topmost of these tiles to the very bottom (beginning) of the list. If the coordinates do not touch any tiles, no action or error should occur.
• delete(self, x, y) - The GUI calls this method on your tile manager when the user right-clicks (or Ctrl-clicks). If these coordinates touch any tiles, your method should delete the topmost of these tiles from the list. If the coordinates do not touch any tiles, no action or error should occur.
• delete_all(self, x, y) - The GUI calls this method on your tile manager when the user Shift-right-clicks (or Shift-Ctrl-clicks). If these coordinates touch any tiles, your method should delete all of these tiles from the list. If the coordinates do not touch any tiles, no action or error should occur.

The Python Tile class has the following fields and methods:

• x, y, width, height, color - Fields of the object. You may access them directly, because Python doesn't do encapsulation as well as Java.
• draw(panel) - Draws the tile onto the given drawing panel. For example, you could ask a tile my_tile to draw itself on a drawing panel p by writing my_tile.draw(p) .
• __str__() - Converts the tile into a string. For example, you could print the state of a tile my_tile by writing print("Tile is " + str(my_tile)) .

Tile doesn't have any accessor methods like getX or getHeight. The Python way to do this is to just have public fields and refer to them directly. (Gasp!)

Provided files:

• drawingpanel.py
• tile.py
• tilemain.py

Links:

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

Session #1 (Tuesday, January 11)

In this session we reviewed all of the 142 material in Python.

• Lecture Slides: ppt , pdf