Syllabus for 22C:80 Programming for Informatics

Instructors:
James F. Cremer 14D MLH, cremer@cs.uiowa.edu, 319-335-1713
Sriram V. Pemmaraju 101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: To be announced

Introduction
This course has two main goals: (i) to teach students practical programming skills in a scripting language (Python is our choice this semester) and (ii) to introduce students to algorithm design and analysis, focusing on algorithmic idioms such as greedy algorithms, divide and conquer, backtracking search and basic data structures such as arrays, strings, hashe tables, and graphs. The course also provides a first exposure to relational databases and web programming.

The overall structure of the course is:

• 5 weeks for Python programming
• Exam 1: Friday, Feb 27th
• 5 weeks for data structures and algorithms
• Exam 2: Friday, April 10th
• 4 weeks for applications
• Final Exam: Monday, May 11th, 7:30 am

Teaching Assistant
The teaching assistant (TA) for this course is Donald E. Curtis III. Don's contact information and office hours will be announced shortly. There are two discussion sections associated with this course whose meeting times and locations are as follows:

Section A01	11:30-12:20 M		301 MLH
Section A01	11:30-12:20 T		301 MLH

Required Legalese
This course is run by the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found online here.

Prerequisites
22C:005 is a prerequisite. That means you should have completed this course in fall 2008 or earlier. A math course selected from 22M:005, 22M:009, 22M:010, 22M:013, or 22M:015, (or MPT II score of 17 or higher) is a corequisite. That means that you should be taking one of these math courses this semester (spring 2009) or should have taken it earlier.

Textbook
The textbook for this course is Introduction to Computing and Programming in Python, A Multimedia Approach by Mark Guzdial. The book should be available in the university bookstore and is available online via amazon here.. We will follow this book closely in the first part of the course, but the programming ideas developed in this book will be useful throughout the semester. The book is also available via on-line or downloadable subscription. It is substantially cheaper than the printed book but you only get access for 180 days.

While the goal of this book is to introduce students to computing and programming, Prof. Guzdial use an innovative approach by focusing on computations that involve media (e.g., images, movies, sounds) and the web. Students will quickly be able to write programs that, for example, implement Photoshop-like effects on images or get the current temparature in Iowa City from a weather webpage, while learning the fundamentals of programming. Prof. Guzdial and colleagues have developed a lot of material (software, lecture notes, data sets, etc.) to support the media computation approach to learning to program. At Mark Guzdial's home page you'll find many links to Media Computation material.

If you are looking for a plain introductory Python book, there are a few reasonably good books available free online. Here are two we know about:

1. A Byte of Python by C.H. Swaroop.
2. Think Python: How to Think Like a Computer Scientist by Allen B. Downey.

Prof. Pemmaraju will provide notes for some of the material covered in the second third of the course.

Python and JES
As mentioned before, we will program in Python in this course. Python is a powerful, but easy-to-learn language with lots of in-built tools for web programming, GUI development, database programming, game development, etc. We chose it for this course because with relatively little code students can do fairly complicated and interesting tasks. Our hope is the students will find both the language and media computation approach to learning it, very exciting.

You will use the Jython Environment for Students (JES) for developing your programs. JES was developed by Prof. Guzdial and colleagues and the code examples presented in our textbook are developed on JES. In case, you are interested, Jython is an implementation of Python language written in Java. Jython will run on any machine that runs Java programs. Don't worry: you don't need to learn Java to use Jython. JES has been installed on the machines in the computer science lab in 301 MLH and very soon you will get instructions on how to get started using this environment. To be able to work in 301 MLH, you will need computer science department accounts; some of you already have such accounts; the rest of you will get CS accounts by the end of the first week.

You can also download JES for free on your home machines and laptops from here. But, first you will need to download the latest version of Java on your machine as well. You can do that from here. Both downloads are fairly straightforward, but don't hesitate to ask for help if you are stuck.

Grading
Plus/Minus grading will be used for the course. There are three components that will determine your grade. We reserve the right to change the percentanges of the components by up to 10% each.

• Homework/lab assignments: 40% Every week, on Friday, you will be assigned a homework that is due the following Friday, by 5 pm. In your discussion section meetings (on Mondays or Tuesdays, depending on your section), the TA will help you get started on your homework. You are then expected to complete the homework on your own and submit it according to the submission specifications on the course web page. The homeworks in the first third of the course will mostly consist of writing programs. In the second third of the course, your homeworks will involve a mix of programming and pen-and-paper exercises.

• 1 Programming Project: 10% In the last 3-4 weeks of the semester, you will be assigned a substantial programming project that will give you an opportunity to show off the various skills you have acquired over the semester.

• 3 Exams: 50% There will be two in-class exams (each worth 15% of your grade) during the semester and one final (worth 20% of your grade). The exam schedule is as follows:

  Exam 1			Feb 27th, Friday			12:30-1:20 pm (in 205 MLH)
  Exam 2			April 10th, Friday			12:30-1:20 pm (in 205 MLH)
  Final			May 11th, Monday                   	7:30-9:30 am (in 205 MH)
  

  All exams will be open book/notes exams. The final will be cumulative.

Solutions will be provided on the course page for all graded work, including programming assignments.

Students with disabilities
I would like to hear from anyone who has a disability which may require seating modifications or testing accommodations or accommodations of other class requirements, so that appropriate arrangements may be made. Please contact me during my office hours.

Academic Dishonesty
Academic dishonesty will not be tolerated. Under no circumstances should you pass off someone else's work as your own. This also applies to code or other material that you might find on the internet. Note that we will routinely use available software systems for detecting software plagiarism, to test any suspicions we might have. If you are unclear about what constitutes academic dishonesty contact your professor or consult the printed policy in the Schedule of Courses and the CLAS Bulletin (online version). We do want students to talk to each other about concepts and ideas that relate to the class. However, it is important to ensure that these discussions do not lead to the actual exchange of written material.

Student Complaints
If you have any complaints or concerns about how the course is being conducted by the instructors or the TA please feel free to talk. Prof. Segre. If your difficulties are still unresolved after speaking with Profs. Cremer and/or Pemmaraju, then you should next consult Computer Science Professor Prof. Alberto Segre, 335-0737, segre@cs.uiowa.edu. (Normally this step would involve contacting the department chair, but that doesn't work here since it's Prof. Cremer). Your next recourse is a written complaint submitted to (for undergraduates) Helena Dettmer, CLAS Associate Dean for Academic Programs (335-2633), or (for graduates) Dale Wurster, Graduate College Associate Dean for Academic Programs (335-2137). Consult the college policy on Student Complaints Concerning Faculty Actions (online version) for more information.

Tentative List of Topics
This is a relatively new course and neither of the instructors have taught this before. So think of yourselves as "guinea pigs." Here is a tentative list of topics we plan on covering and it is subject to change based on your feedback and how we think things are going.

PART I: Python programming

• Introduction to Python. Elementary values and data types, assignments to variables.
• Conditionals and loop structures, I/O statements.
• Strings, lists, and tuples. Vectors and arrays.
• Functions, parameters, and scope. Recursion.
• Object-oriented design, classes, and methods.

PART II: Data Structures and Algorithms

• Week 1: Introduction to running time analysis.
  • Translating a program into "basic steps" and counting these
  • The notion of input size, asymptotic analysis
  • Worst case analysis
  • Big Oh notation and a little bit on functions commonly encountered in computer science
  • Examples of code that runs in O(n) (linear search), O(n^2) (bubble sort), O(log n) (binary search) and O(c^n), etc.
• Week 2: Approaches to designing data structures.
  • The searching problem: hash tables, hash functions, etc.
  • Some thumb rules for designing good hash functions
  • Binary search trees (BSTs)
  • Balancing BSTs and the height of BSTs under random insertions
• Week 3: The Divide-and-conquer paradigm.
  • Binary search revisited. How about ternary search?
  • merge sort and quick sort and their analysis
  • randomized quick sort
  • Divide and conquer algorithm for closest point pair and its analysis
• Week 4: Greedy Algorithms.
  • Optimization problems: three examples: (i) making coin change, (ii) time-tabling, and (ii) shortest path problem
  • Simple greedy algorithms for these problems, some of which work and some of which don't.
  • A greedy algorithm that works: Dijkstra's shortest path algorithm.
  Week 5: Intractability
  • The notions of P, NP, NP-hardness, and NP-completeness, and reductions
  • Examples: SAT, TSP, Set Cover, etc.
  • Dealing with intractability: brute-force (branch-and-bound), heuristics (e.g., Kerninghan-Lin for TSP), approximation algorithms (e.g., 2-approximation for Euclidean TSP).

PART III: Applications

• Databases.
• Discrete Event Simulation.
  • Modeling and generating social networks: power law vs Poisson degree distributions, clustering coefficient, small-world property, etc.
  • Modeling and simulating disease spread on social networks.
• Image processing and compression.