22C:80 Programming for Informatics
12:30-1:20 MWF, Room 205 MLH
Instructors:
James Cremer, 14D MLH, cremer@cs.uiowa.edu, 319-335-1713, Office hours: T 9-10, Th 1-2
Sriram V. Pemmaraju, 101G MLH, sriram@cs.uiowa.edu, 319-353-2956, office hours: M 10-11, W 2-3
TA:
Donald E. Curtis III, office: 201C MLH, dcurtis@cs.uiowa.edu, 319-353-2546, office hours: Th 11-12, F 11-12
There are two discussion sections associated with this course:
Section A01 11:30-12:20 M 301 MLH
Section A01 11:30-12:20 T 301 MLH
Don will lead both of these discussion section meetings, grade some of the homework,
and hold regular office hours. He is a Ph.D. student in computer science and an expert Python programmer
(more so than the other instructors!) so you should make use of his expertise.
- 5/6 Added file hw11part2help.py, which contains a very useful function
for part two of HW11. The function constructs a URL for a Google Maps query to determine the driving distance between two
cities, uses the URL to get the distance, and then returns it.
- 5/1 HW11 is available, due Friday, May 8. I also posted my showMap.py
program code that serves as a good basis for HW11. It's just like the code I demonstrated in class but
has been cleaned up a bit, documented with more comments, etc.
- 4/27 You should be using the posted Dijkstra's shortest path algorithm implementation
for HW 10.
- 4/22 Some instructions
on how to create and view KML files.
- 4/22 Some code to help with hw10 is here. This shows
(i) partial code for how to parse the data file and build a graph from it and (ii) how to produce an output kml file.
- 4/8 Python code for the dictionary-based implementation of greedy endsFirst covered in class on 4/8 is available
below.
- 4/8 The due date for HW9 has been changed to Wed., 4/15.
- 4/8 Quiz 2 and solutions posted. Look below.
- 4/3 Here is a Study Guide for Quiz 2 and Exam 2.
- 4/2 Exam 2 is on Friday, April 10th. There will be a quiz (Quiz 2) in the discussion sections on
Monday (4/6) and Tuesday (4/7).
- 3/12 The "What to submit" section of HW7 has been updated.
- 3/11 Sriram's Monday office hours are moved to Thursdays. So his office hours
are now W 2-3 and Th 10-11.
- 3/9 Check out HW7, new code and lecture notes for the week of
3/9-3/13.
- 3/4 Here is the "skeleton" of my solution to homework 6: hy6Skeleton.py.
I obtained this by leaving function headers and comments in my code, so that you know how my code is organized.
- 3/4 I have posted a number of Python programs pertaining to
linear and binary search (see Lecture notes and other class supplements).
Read and experiment with these programs
- 2/26 To prepare for next week (3/2-3/6) read pages 89-93
(Chapter 10, until, but not including 10.7) on Lists from
Think
Python: How to Think Like a Computer Scientist.
- 2/26 Discussion section on Monday(3/2) and Tuesday(3/3) will
(i) get you started on HW6 and (ii) teach you how to do file input in
Python.
- 2/20 HW4 (and HW2 and HW3) solution is available in the Homework section.
- 2/18 HW5 is available, due Wednesday, Feb. 25.
- 2/6 HW4 is available, due Friday, Feb. 13.
- 2/2 HW3 is available, due Friday, Feb. 6.
- 1/28 & 1/30: HW2 is due Monday, Feb. 2 instead of Friday, Jan. 30. HW3 (available 2/1) will simply add a couple of additional functions to HW2. For a significant proportion of the class, the "scaling" portion of "AddImageToCollage" will be pretty difficult. As a path to success, you should first
complete a version of "AddImage..." that works when the scaleFactor is 1.0. This is much easier and was essentially given in class. Make your best attempt
at scaling the image as well, but if you don't complete that by Monday, you
won't be penalized much and you'll get a chance to finish the scaling as
part of HW3.
- 1/25: Two small changes were made to the Homework 2 assignment (the arguments to
addPictureToCollage, and requirement to provide a jpg collage as part of your ICON submission)
- 1/23: Homework 2 is available, due Friday, 1/30.
- 1/23: Sample image and sound files are contained in directory /opt/jes/MediaSources on the CS Linux machines
- 1/23: Modified programming assignment submission requirements - only ICON submission is required, not hardcopy
- 1/23: Added information about using JES on CS Linux machine, transferring files between CS and non-CS machines, and making zip files.
- 1/22: Office hours: Cremer T 9-10, Th 1-2, Pemmaraju M 10-11, W 2-3, Curtis Th 11-12, F 11-12.
- 1/21: Homework 1 is available, due Monday, 1/26.
- 1/19: The discussion section on Tuesday, 1/20 will not meet.
Discussion sections will start meeting regularly, the week of Jan 26th.
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
Prof. Cremer will lead the first five weeks, Prof. Pemmaraju the second five
weeks and the two instructors will split the last four weeks.
- 4/8 class programs: Here are three Python implementations of the
greedy endsFirst algorithm.
jobScheduling.py is the basic version covered in class.
jobScheduling2.py and
jobScheduling3.py are slight variations (both 2 and 3 don't bother
putting left endpoints in the dictionary, and 3 works even when one or
more intervals share endpoints)
- Week 6, 3/2-3/6: The Searching Problem.
The central role of search in CS, linear search, binary search,
recursion, the divide-and-conquer paradigm
Python stuff: Review of lists, file input.
Sample code:
search1.py: linear search on a randomly
generated list,
search2.py: linear search on a list
obtained via interaction with the user,
search3.py: linear search on a list
obtained from a text file; the search is timed,
search4.py: binary search on a list
obtained from a text file; the search is timed,
search5.py: recursive binary search
on a list; binary search is timed and running times of binary and linear search are
compared.
Discussion section: will (i) discuss HW6 and help you
get you started on this homework and (ii) teach you how to do file input in
Python.
- Week 6, 3/9-3/14: Running Time Analysis.
Introduction to running time analysis, primitive operations,
translating Python code into machine code,
worst case anaylysis, examples of linear search, bubble sort, and
binary search.
Python Stuff: Generating random input, timing your programs.
Sample code:
timing.py: "profiles" Python code
in order to measure the running time of linear search and binary search.
Lecture notes: March 9th,
March 11th
Discussion section: will (i) discuss HW7 and help you
get you started on this homework and (ii) teach you how generate a random bitonic
list of a desired size.
- Week 7, 3/23-3/27: The Sorting Problem.
Big Oh notation, why binary search takes O(log n) time, exponential time
algorithms (recursive Fibonacci), the divide-and-conque paradigm revisited,
the quickSort algorithm.
Sample code: counting_sort.py,
bubbleQuickSort.py,
timingSorts.py.
Lecture notes:
March 25th,
March 27th.
Discussion section: will present sorting without
comparisons, e.g., counting sort, bucket sort, radix sort, etc.
- Week 8, 3/30-4/3: Greedy Algorithms.
The importance of the choice of a pivot in quickSort, choosing the
pivot at random, Las Vegas and Monte Carlo randomized algorithms,
The job scheduling problem. Two greedy algorithms for the
problem that are suboptimal and one that is optimal.
- Week 10-11, 4/13-4/17, 4/20-4/24: Google Maps and Shortest Path Algorithms.
Peering under the hood of a system such as Google Maps, to understand the
technology, data structures, algorithms, etc., that make this work.
Road networks, graphs, representing graphs (adjacency matrix versus
adjacency list), shortest path algorithms: breadth-first search
and Dijkstra's shortest path algorithm.
Sample code: buildGraph.py,
sample input for buildGraph,
output from buildGraph,
breadthFirstSearch.py, and
Dijkstra.py.
output from shortest path computations.
- Homework 1, due Monday 1/26
- Homework 2, due Monday 2/2. Sample HW2 (incl. HW3) solution
- Homework 3, due Friday 2/6. Sample HW3 (incl. HW2) solution
- Homework 4, due Friday 2/13. Sample HW4 solution
- Homework 5, due Friday 2/25
- Homework 6, due Friday 3/6. Sample HW6 solution
- Homework 7, due Friday 3/13
- Homework 8, due Wednesday 4/1. Sample HW8 solution
- Homework 9, due Wednesday 4/15.
- Homework 10, due Wednesday 4/29. Homework 10 Solution.
- Homework 11, due Friday 5/8.
Computers available
For implementing homework assignments, there are Linux PCs in 301 MLH, though many of you will find it most convenient to
install and use JES on your own machines.
You can access departmental Linux machines remotely using a secure shell program (e.g. you can download a good one, SecureCRT, from the ITS software download site. Rather than trying to remember the names of particular departmental Linux machines, you should simply use "linux.divms.uiowa.edu" as the host name when you connect; our system will then automatically connect you to one of the Linux machines (not always the same one).
If you access departmental Linux machines using a simple secure shell program, you will not be able to run the JES python environments. It is possible to run JES while remotely logged in to departmental Linux machines if you are using NoMachine or similar software that provides X Windows support. For many of you, however, it would be simpler and more effective to install and run JES directly on whatever machine you are using.
To transfer files between your CS department home directory/folder and non-CS computers, read this information.
Documenting and submitting programs
For assignments that contain programming components, you must submit via
the appropriate ICON dropbox, a zipfile (an introduction to creating zipfiles is here) containing:
- your program code (and test data files, when appropriate)
- a short README file documenting the
- the status of your program (e.g. you think it works completely, it
compiles but doesn't run, it compiles and runs but doesn't work in certain
cases, etc.)
- what hardware platform(s) you tested it on
- how to run the the program (e.g. what is the name of the main procedure, what
kind of arguments does it expect, in what order, etc.?)
Note: It is very important that programs be well-written and clear. Programs
should be readable by people, not just compters. Coding style and organization may
be considered in grading programs. Your code should include comments where appropriate, but
avoid the approach of ritualistically filling your code with unhelpful (e.g. "this
is a variable") or imprecise (e.g. "this loop goes around and around
until it figures out the answer") comments. Ambiguous or inaccurate comments can be worse
than none at all.
- You can download the Python programming environment used for this class, JES, and related media files and tools here.
- A short introduction to using JES on the CS Linux computers is available here.
- Sample image and sound files used in many of the textbook examples are contained in directory /opt/jes/MediaSources on the CS Linux machines
Scores will be available on ICON only.