CSE 143

Course Info

Getting Help

Check Scores

Other

CSE 143: The Python Strikes Back

NOTE: Check the Python section of the course message board for information about an "Engineering Without Borders" project looking for Python programmers!

Python Books and Tutorials:

If you want to learn more Python on your own, here are some good online books and tutorials to read.

Past Slides:

Homework 7: 20 Questions
Due: Sat 3/13, 11:30pm. Turn in HW7P here.
No late turnins accepted.

In unit 7 of the course we learned about binary trees. Trees are basically the same in Python; just create a node class with left and right references, and build a tree of nodes, like in Java.

For your assignment this week, create a Python file called questiontree.py that defines classes QuestionNode and QuestionTree (one file can define 2 classes in Python), much like in the Java Homework 7. Our solution to this program is 95 lines long including comments and blank lines.

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 () - Constructs an empty tree whose root is Jedi.
  • play() - Plays one game of 20 Questions, traversing the tree and ending with either the computer guessing the player's object, or the computer losing and adding a new question and answer node object to its tree.
  • load(filename) - Loads a question tree from the file with the given name in the current directory, in the same format as on the Java program. This method should raise an exception if the file name passed is None.
  • save(filename) - Saves a question tree to the file with the given name in the current directory, in the same format as on the Java program. This method should raise an exception if the file name passed is None.
  • total_games() - Returns the total number of games played.
  • games_won() - Returns the total number of games that the computer has won by correctly guessing your object.

All of your methods should be recursive as appropriate rather than using loops. Note that in the Python version of this program there is no UserInterface abstraction; the game is always in text mode. You should directly read input from the user using the input function and directly print output to the user using the print function. To detect a yes/no answer, you may want to add the following helper function to your QuestionTree class: 

# Helper; prompts for a yes/no answer and returns true if user types
# a word/phrase that starts with "y", case-insensitive.
def yes_to(self, question):
    answer = input(question + " ").lower()
    return answer.startswith("y")

Files:

Session #4 (weeks 8-9)

In this session Steve briefly introduced Linked Lists and Iterators and recovered topics from last week: Map and Reduce, dictionaries and list comprehensions.

Homework 6: Anagrams
Due: Sat 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 AnagramSolver 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:

Session #3 (weeks 5-6)

In this session Allison covered the map and reduce functions, the MapReduce algorithm, dictionaries and List comprehensions.

Homework 5: Grammar Solver
Due: Sat 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 (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:

Links:

Homework 4: Assassin
Due: Sat 2/20, 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.

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:

Links:

Session #2 (weeks 3-4)

In this session Roy covered Exceptions, built-in methods, lambda functions, higher-order functions including filter, map and reduce.

Files:

Links:

Homework 3: HTML Validator
Due: Sat Feb 6, 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 week's session. (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:

Links:

Homework 2: SortedIntList
Due: Sat 1/30, 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 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
  • 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 throw ("raise") an exception in Python, write the following: 

raise Exception("your error message here")

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:

Links:

Session #1 (weeks 1-2)

In this session Kelly led a quick review of the Python taught last quarter in CSE 142, including basic syntax, functions, loops, if/else, parameters, tuples, file I/O, lists, objects and classes.

  • Lecture Slides: (none; used review slides from above)

Homework 1: Rectangle-Rama
Due: Wed 1/20, 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 rectanglemanager.py that implements a class RectangleManager. Each RectangleManager object stores a list of rectangles. Each rectangle is represented as a Rectangle object; the Rectangle class is defined our provided file rectangle.py. Your rectangle manager will be created by the overall main program that is defined in rectanglemain.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 RectangleManager class:

  • __init__(self) - initialize a new rectangle manager object. Initially the manager is not storing any rectangles.
  • add_rectangle(self, rect) - add the given rectangle to the end of the rectangle manager's list of rectangles.
  • draw_all(self, panel) - should cause all of the rectangles in the rectangle 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 Rectangle object already has a draw method that it can use to draw itself. You just need to pass on the panel object to each rectangle to do the rest of the work. Draw the rectangles 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 rectangle manager when the user left-clicks. It passes you the x/y coordinates the user clicked. If these coordinates touch any rectangles, you should move the topmost of these rectangles to the very top (end) of the list. If the coordinates do not touch any rectangles, no action or error should occur.
  • lower(self, x, y) - The GUI calls this method on your rectangle manager when the user Shift-left-clicks. If these coordinates touch any rectangles, your method should move the topmost of these rectangles to the very bottom (beginning) of the list. If the coordinates do not touch any rectangles, no action or error should occur.
  • delete(self, x, y) - The GUI calls this method on your rectangle manager when the user right-clicks (or Ctrl-clicks). If these coordinates touch any rectangles, your method should delete the topmost of these rectangles from the list. If the coordinates do not touch any rectangles, no action or error should occur.
  • delete_all(self, x, y) - The GUI calls this method on your rectangle manager when the user Shift-right-clicks (or Shift-Ctrl-clicks). If these coordinates touch any rectangles, your method should delete all of these rectangles from the list. If the coordinates do not touch any rectangles, no action or error should occur.

The Python Rectangle 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 rectangle onto the given drawing panel. For example, you could ask a rectangle rect to draw itself on a drawing panel p by writing rect.draw(p) .
  • __str__() - Converts the rectangle into a string. For example, you could print the state of a rectangle rect by writing print("Rect is " + str(rect)) .

Rectangle 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:

Links:

General info about the CSE 143 Python program:

This quarter in CSE 143, we will conduct a special optional program to offer students a chance to learn a second programming language as you're learning Java. The second language's name is Python.

This program is targeted at people who already participated in our Python program during CSE 142 in a past quarter. If you didn't, you can still try to follow along, but it may be more difficult.

What is Python?

Python is a language that's good for writing programs to process text and other data. It's used heavily in the Linux operating system and at companies like Google.

Why would I want to learn Python, in addition to Java?

Learning two programming languages is a bit like growing up in a bilingual family: you'll not only learn those two languages well, but you may also learn some higher concepts about programming and programming languages in general.

In addition, Python is used in a lot of other fields and disciplines, so it can be useful to have experience in it. Lastly, Python is a powerful language that does a lot of things more easily than Java, so it can be fun rewriting your past Java programs in Python and seeing how much shorter and cleaner they can be solved.

What will I do if I participate in this program?

The work involved in this program would be the following:

  • Reading each week's posted links and info for that week's material
  • Completing optional Python programming projects each week as desired

Primarily, these projects will consist of solving the same problem as that week's Java programming assignment, but in Python, and perhaps with minor modifications to the assignment spec.

What reward do I get for doing this? Do I have to do it?

Participation is entirely optional. The reward for doing these projects will be small, to make sure that Python doesn't give students with prior experience an unfair advantage over new programmers. Right now, we're planning to reward students with 1 free late day for each Python program submitted. No grade points will be added or subtracted in any way for participating in this project.

How do I participate or learn more?

Just look at the slides and/or links above, and if you find it interesting, try writing the Python program for that week. If you finish it, you can turn it in from a link that we'll put up above on this page.

If you want to install and run Python programs on your own computer, follow our Python Installation Instructions below: