CS 3190 Programming Language Workshop in Python (1 Credit)

· Office Hrs : TTh, 2-3pm , 395 Joshi (or by appointment)

· One and Only Class :  January 20, Wednesday, 1pm-1:30pm, 399 Joshi

Course Description

This course is designed as a self-study in Python. You are expected to learn the language and solve a set of simple programming problems assigned to you  using Python available from http://www.python.org. There are no exams. We officially meet only once in the semester. However, I will be available in the posted office hours for clarifications and discussions about the programming problems.

Prerequisite

Reference Text

Grading

Each programming assignment will be graded as Pass/Unsatisfactory, and the letter grade 'P' or 'U' will be assigned at the end of the course.

Course Policies

  1. All work must be turned-in by April 14, 2016. 
  2. Do not expect an incomplete for any reason. Each assignment will also have a separate deadline.
  3. You must pass all the assignments to pass the course. The code you turnin must be your own creation. Copying code from available books, or cutting and pasting code from the Internet is strictly prohibited because it defeats the whole purpose of the course.
  4. Each program should be well-documented and adequately tested.
  5. You must turnin well-documented source code runnable using Python, and a separate README.txt (containing a brief description of the program, and where applicable, sample test inputs and outputs to indicate that you have tested your code adequately), as a single zip-archive for each assignment. To turnin the ith assignment (where i = 1,2,3,4), create the archive asgi.zip, and upload to the corresponding DropBox on Pilot
  6. You may also be required to demonstrate your code in my office hours after the due date.

Assignments (You must provide a transcript of adequately testing your program, by providing test inputs and outputs generated by your solution, to get a "P" grade.)

Problem Set 1 (Due Feb 4)

(1) Write a program that computes the day of the week on which a given date will fall. Assume that the date is input in MM-DD-YYYY format. Make sure it works correctly for leap years. Specifically, check the days for dates such as 02/29/2000 and 02/29/2004.

(2) The goal of this exercise is to write a cyclic cipher to encrypt messages. This type of cipher was used by Julius Caesar to communicate with his generals. It is very simple to generate and can be easily broken. The key idea behind the Caesar cipher is to replace each letter by a letter some fixed number of positions down the alphabet. For example, if we want to create a cipher shifting by 3, you will get the following mapping:
Plain: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Cipher: DEFGHIJKLMNOPQRSTUVWXYZABC
Write a program that takes a string and a shift value to generate the Cipher.  Read up and check out  ROT13, an invertible cipher.

Problem Set 2 (Due Feb 25) (REF: http://ceasarjames.wordpress.com/2011/03/18/the-gamblers-ruin)

(1) A classic problem in statistics is the random walk. Imagine a drunken man standing on the center square of a sidewalk consisting of 11 squares. At each step, the drunk can elect to go right or left. How long will it be until he reaches the end of the sidewalk, and how many times will he have stood on each square? To solve the problem, represent the number of times the drunk has stood on a square as an array, and use the function random.randint to compute random numbers. Display the value of the array at the beginning, at the end, and a few intermediate steps. (Make the latter programmable by defining a constant increment at the beginning of the program.)

(2) Now repeat the same for a two-dimensional variation on the random walk using an 11-by-11 array, and four moves: up, down, left, and right.

(3)  Another related problem is called the Gambler’s Ruin problem.

Two gamblers, Alice and Bob, bet on the outcomes of successive flips of a coin. On each flip, if the coin comes up heads, Alice collects $1 from Bob, whereas if it comes up tails, Bob collects $1 from Alice. They continue to do this until one of them runs out of money. If it is assumed that the sucessive flips are independent and each flip results in a head with probability p (= 1 - q), what is the probability that Alice ends up with all the money if she starts with $A and Bob starts with $B?

The solution, in all its glory, is explained here for the statistically inclined. For those who’d rather just know the answer though, it ends up working out to be that Alice will beat Bob with probability 1 – (q/p)^A / ( 1 – (q/p)^(A + B) ) if her probability of winning a flip isn’t 1/2, and simply A / (A + B) if the game is fair. Verify these claims by simulating the Gambler's Ruin problem.

Problem Set 3 (Due Mar 17)

(1) Write a program that reads a text file data.txt and prints out an inverted index, which is the sorted list of words and the line numbers in which they appear (in one word-occurrences per line format).

(2) Write and time the program to compute first n numbers of the Fibonacci sequence (i) using recursion, (ii) using iteration, and (iii) using memoization. The code for (iii) is essentially recursive except that we save the values computed for the recursive calls so that we look it up when we need it again as opposed to recompute it. Verify that (i) exhibits exponential time complexity, while (ii) and (iii) exhibit linear time complexity.

(3) Write three versions of a function that will take a list as an argument and retunrs a list containing the cubes of the elements that are even. First write the funtion using standard loops and conditional statetments. Then write the function usign a combination of filter and map. Finally write the function using a list comprehension.

(4) Provide a class definition for a deque (double-ended queue), which allows insertions and removals from both ends of a queue. Your class should support the operations addFront, addBack, removeFront, removeBack, and isEmpty. You can use a list for the underlying implementation.

Problem Set 4 (Due Apr 14)

 http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/unit-1/lecture-4-machine-interpretation-of-a-program/MIT6_00SCS11_ps1.pdf

Or you may propose a substantial project you are interested in carrying out.