22C:16 (CS:1210) Computer Science I: Fundamentals

Instructor:
Sriram V. Pemmaraju (morning and evening section)
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 7:00pm-8:00pm M, 2:30pm-3:30pm W, 1:00pm-2:00pm Th

Syllabus document, Information about TAs, Announcements, Quizzes, Projects, and Exams, Weekly Topics, Online Resources

(From xkcd)

Information about TAs

Name		e-mail address				Office Hours	
Sikder Huq 	sikderrezwanul-huq@uiowa.edu		Thurs 3:30-6:30, 301 MLH
Niraj Pandya 	nirajhemantbhai-pandya@uiowa.edu	Wed 8-9:30, Fri 8-9:30, 301 MLH
Naveen Dewda 	naveen-dewda@uiowa.edu			Mon 1-3, Wed 1:30-2:30, 301 MLH
Richa Gandhi 	richa-gandhi@uiowa.edu			Tues 10-11:30, 301 MLH

Practice Problem Sets, Quizzes, Homeworks, Projects, and Exams

• Practice Problem Set 1. Solutions.
• Quiz 1: Version a, Version b, Version c. Solutions
• Practice Problem Set 2. Solutions
• Quiz 2: Version a, Version b, Version c. Solutions
• Homework 1. Due on Feb 13 (Thursday) at 4:59 pm. Solutions
• Practice Problem Set 3. Solutions
• Quiz 3: Version a, Version b, Version c. Solutions
• Practice Problem Set 4. Solutions
• Quiz 4: Version a, Version b, Version c. Solutions
• Homework 2. Due on Feb 27 (Thursday) at 4:59 pm. Extra information on Problem (a), HW2.
• Practice Problem Set 5. Solutions
• Quiz 5: Version a, Version b, Version c.
• Exam 1 and Exam 1 Solution.
• Homework 3. Due on March 13 (Thursday) at 4:59 pm. Input files: war.txt and hyde.txt. My output for homework 3. Homework 3 Solution.
• Practice Problem Set 6. Solutions.
• Quiz 6: Version a, Version b, Version c.
• Practice Problem Set 7.
• Quiz 7: Version a, Version b, Version c.
• Practice Problem Set 8.
• Quiz 8: Version a, Version b.
• Test file for Project 1, Phase 2.
• Exam 2 and Exam 2 Solution.
• Homework 4. Due on April 18 (Friday) at 4:59 pm. Input files: war.txt, hyde.txt, illiad.txt. Extra information on HW 4.
• Practice Problem Set 9.
• Practice Problem Set 10.
• Project 2. Data set: ml-100k.zip. Phase 1 due on Tuesday, 4/29 and Phase 2 due on Thursday, 5/8.
• Project 2, Phase 1, Test File (a). More test files will be posted soon.
• Practice Problem Set 11.
• Project 2, Phase 1, Another Test File. This is useful for testing functions createGenreList, meanUserRating, and meanMovieRating.
• Practice Problem Set 12.
• Project 2, Phase 2, Test File (a). Another test file will be posted soon.
• Project 2, Phase 2, Another Test File.

Announcements

• 1/24 There will be a quiz in the discussion sections next week (1/27-1/31).
• 2/12 Exam 1: Feb 21st, 6:30-8:30 pm, PH 100. Here is more information about Exam 1.
• 2/25 Here is Extra information on Problem (a), HW2.
• 2/28 The 7th Annual University of Iowa Computing Conference hosted by the UI ACM student chapter and the UI Department of Computer Science starts at 6:30 pm on Friday, 2/28.
• 3/12 Here is my output for HW3.
• 3/21 Use this Test file for Phase 1 for testing your solution to Phase 1.
• 3/29 Use this Test file for Phase 2 for testing your solution to Phase 2.
• 3/30 Exam 2: Apr 4th, 6:30-8:30 pm, PH 100. Here is more information about Exam 2.
• 5/5 Tentative pre-final grades.
• 5/8 Project 2 Phase 2 due date is Friday, May 9th at 4:59 pm. You have to submit two additional files (i) output.txt: this file is a simple text file containing the output produced by your program project2Phase2b.py and (ii) project2Phase2bOneRun.py: This file is very similar to project2Phase2b.py, except that it contains code for just one run instead of 10 runs.
• 5/11 Final Exam: May 15th, 5:30-7:30 pm, C20 PC (Pomerantz Center). Here is more information
• 5/11 Finals week office hours: Wednesday (5/14) 2pm-3pm, Thursday (5/15) 10:30am-11:30 am, 1pm-2pm. Please stop by to get help in your final exam preparation.

Weekly Topics and Links to Lecture Notes

• Week 15: 5/5-5/9
  Topics:
  • Introduction to classes and objects in Python
  • Motivation for object-oriented programming in general
  • Operator overloading
  • The point class and the queue class.
  Lecture Notes: • May 5 • May 9
  Links to lecture videos: • May 5
  Code: point.py • queue.py • queueDict.py

• Week 14: 4/28-5/2
  Topics:
  • The divide-and-conquer paradigm; recursive implementation of divide-and-conquer algorithms
  • Case study: quick sort
  • The partition function and randomized partition.
  • Efficiency of quickSort.
  Lecture Notes: • April 28 • April 30 • May 2
  Links to lecture videos: • April 28 • April 30
  Code: quickSort.py, sortTiming.py.
  Practice Problems: Practice Problem Set 12. Use this problem set on recursion to prepare for Quiz 12.
  

• Week 13: 4/21-4/25
  Topics:
  • Introduction to recursion and recursive functions.
  • Basic examples: factorial and fibonacci
  • Why is recursive fibonacci so slow?
  • Recursively computing the power with very few multiplications
  • Binary search
  Lecture Notes: • April 23 • April 25
  Links to lecture videos: • April 21 • April 23 • April 25
  Code: factorial.py, fibonacci.py, power.py, binarySearch.py. Practice Problems: Practice Problem Set 11. Use this problem set on recursion to prepare for Quiz 11.
  

• Week 12: 4/14-4/18
  Topics:
  • Network exploration algorithms: determining if there is path from source to target
  • Using a Python dictionary to store parent information
  • Traversing the Python dictionary with parent information in order to find a source-target path.
  • Completing the program that plays the word ladder game.
  Lecture Notes: • April 14 • April 18
  Links to lecture videos: • April 14
  Code: playLaddersGame1.py, playLaddersGame2.py. Input file: words.dat.
  Practice Problems: Practice Problem Set 10. Use this problem set on dictionaries to prepare for Quiz 10.
  

• Week 11: 4/7-4/11
  Topics:
  • Programming Problem: Playing the word ladder game.
  • Building the word network; a list-based approach
  • Introduction to dictionaries; dictionary operations
  • Building the word network; a dictionary-based approach
  Lecture Notes: • April 7 • April 9 • April 11
  Links to lecture videos: • April 7 • April 11
  Code: wordNetwork1.py (list-based word network), wordNetwork2.py (dictionary-based word network). Input file: words.dat.
  Practice Problems: Practice Problem Set 9. Use this problem set on dictionaries to prepare for Quiz 9.
  

• Week 10: 3/31-4/4
  Topics:
  • ASCII values of characters. The ord and chr functions.
  • Programming Problem: Playing the word ladder game.
  • Exam review.
  Lecture Notes: • April 2
  Links to lecture videos: • March 31
  Code: wordNetwork1.py. Input file: words.dat.
  

• Week 9: 3/24-3/28
  Topics:
  • Review of list operations and string operations
  • List comprehensions
  • Programming Problem: Extracting names of principal characters in a literary text.
  Lecture Notes: • March 24 • March 28
  Links to lecture videos: • March 24 • March 26 • March 28.
  Code: characters.py
  Practice Problems: Practice Problem Set 8. Use this to prepare for Quiz 8.
  

• Week 8: 3/10-3/14
  Topics:
  • Generating lists, list and string slicing, for-loops
  • Overview of list operations and their efficiency
  • String operations
  Lecture Notes: • March 10 • March 12 • March 14
  Code: rollDistribution.py
  Practice Problems: Practice Problem Set 7.

• Week 7: 3/3-3/7
  Topics:
  • Lists as mutable types
  • Mutation in functions
  • Introduction to sorting: selection sort.
  Lecture Notes: • March 3 • March 5
  Links to lecture videos: • March 3 • March 5 • March 7
  Readings: Read Chapter 10 (on Lists) from Think Python: How to Think Like a Computer Scientist.
  Code: selectionSort.py, timingSelectionSort.py
  Practice Problems: Practice Problem Set 6.
  

• Week 6: 2/24-2/28
  Topics:
  • Introduction to sequence type: strings and lists
  • Using the [ ] notation to access elements of strings and lists
  • The append and extend operations on lists
  • Reading from files
  • Programming program 4: reading from a file and counting distinct integers in file.
  Lecture Notes: • Feb 24
  Links to lecture videos: • Feb 24 • Feb 26 • Feb 28
  Readings: Read Chapter 3 (pages 19-30) on Functions from Think Python: How to Think Like a Computer Scientist and Chapter 8 from Prof. Ted Herman's notes for 22C:16.
  Code:fileInputExample.py, input.txt, parseFile.py.
  Practice Problems: Solve Practice Problem Set 5 in preparation for Quiz 5 in your discussion section next week. In addition to evaluating expressions involving lists and list operations, you will also be asked to write a small function that manipulates lists in some manner.
  Miscellaneous: Example problems discussed in this week's discussion sections and their solutions.

• Week 5: 2/17-2/21
  Topics:
  • Using randomness in program. The random module and some useful functions defined in this module.
  • Programming Problem 3: Simulating a 1-dimensional random walk.
  • How to define functions in Python
  • Solution to Programming Problem 3 involving several functions.
  Lecture Notes: • Feb 17
  Links to lecture videos: • Feb 17 • Feb 19 Readings: None yet.
  Code: • rollSevens.py • randomWalk1.py • randomWalk2.py • randomWalk3.py • randomWalk4.py
  Practice Problems: None yet. Miscellaneous:

• Week 4: 2/10-2/14
  Topics:
  • Numeric data types: int and float revisited. The long data type.
  • Variables and expressions revisited: the "sticky note" model of variables, rules for variable names, Python's list of keywords, well-formed expressions, order of evaluation of expressions.
  Lecture Notes: • Feb 10 • Feb 12 • Feb 14
  Links to lecture videos: • Feb 10 • Feb 14
  Readings: None yet.
  Code: No new code this week.
  Practice Problems: Solve Practice Problem Set 4 to get ready for next week's quiz.
  Miscellaneous: Here are some links to relevant Python documentation: Python math module and Python built-in functions.

• Week 3: 2/3-2/7
  Topics:
  • Programming problem 2: Listing primes.
  • The break statement.
  • Modules in python; math module and some useful functions in this module, time module and how to time python programs using functions in this module.
  • Boolean variables and the boolean operators: and, or, and not.
  • Nested loops
  Lecture Notes: • Feb 3 • Feb 5 • Feb 7
  Links to lecture videos: • Feb 3 • Feb 5 • Feb 7
  Readings: None yet.
  Code: • primalityTesting0.py   • primalityTesting1.py   • primalityTesting2.py   • primalityTesting3.py   • primalityTesting4.py   • primalityTestingTimed.py   • listPrimes.py
  Practice Problems: Solve Practice Problem Set 3 to get ready for next week's quiz.

• Week 2: 1/27-1/31
  Topics:
  • Understanding the program that converts decimal integers to binary representation.
  • A whirlwind tour of constants, variables, operators, expressions, data types, built-in functions, input statements, output statements, and while-loops in Python
  • Improving the intToBinary program.
  Lecture Notes: • Jan 27 • Jan 29 • Jan 31
  Links to lecture videos: • Jan 27 • Jan 29 • Jan 31
  Readings: Chapter 2 (Pages 11-18) from Think Python: How to Think Like a Computer Scientist. This chapter discusses Python constants, variables, operators, expressions, statements, etc., and is a nice complement to the material we will cover in class this week.
  Code: • intToBinary1.py  • intToBinary2.py  • intToBinary3.py  • intToBinary4.py
  Practice Problems: Solve Practice Problem Set 2 to get ready for next week's quiz.

• Week 1: 1/21-1/24
  Topics:
  • Welcome to Computer Science I: Fundamentals: why this is an exciting time to be a computer scientist.
  • Our first programming problem: converting nonnegative integers into equivalent binary representation.
  • Designing an algorithm to solve this problem and using pseudocode to describe this algorithm.
  • Translating this algorithm into our first Python program.
    
  Lecture Notes: • Jan 22  • Jan 24
  Links to lecture videos: • Jan 24
  Readings: Chapter 1 (Pages 1-8) from Think Python: How to Think Like a Computer Scientist.
  This chapter introduces terminology that we will use throughout the course.
  Code: • intToBinary1.py  • intToBinary2.py  • intToBinary3.py  • intToBinary4.py
  Practice Problems: Solve Practice Problem Set 1 to get ready for next week's quiz.
  Miscellaneous: Here are instructions on How to install Python and Wing on Windows computer and on How to install Python and Wing on Mac.

Online Resources

• Python.org is the authoritative source on all Python matters. You will find links to downloads and tutorials here.

• Previous offerings of the course:
  • Fall 2013 (Prof. Ted Herman).
  • Spring 2013 (Prof. Sriram Pemmaraju).
  • Fall 2012 (Prof. Ted Herman).
  • Spring 2012 (Prof. Sriram Pemmaraju).
  • Fall 2011 (Prof. Ted Herman).
  • Spring 2011 (Prof. Sriram Pemmaraju).

• Free Online textbooks:
  • Think Python: How to Think Like a Computer Scientist by Allen B. Downey.
  • Introduction to Computer Science Using Python and Pygame by Paul Vincent Craven.
  • A Byte of Python by Swaroop C.H.
  • Learn Python the Hard Way by Zed A. Shaw.
  • How to Think Like a Computer Scientist by Brad Miller and David Ranum (This is an interactive textbook).

• Textbooks for purchase: (not required, but useful if you wish to own a book on Python)
  • Python Programming: An Introduction to Computer Science by John Zelle.
  • Exploring Python by Timothy Budd.

• Miscellaneous stuff:
  • Google's Python class.
  • Khan Academy: search for "Python" to find a collection of videos.