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

Instructors:
Sriram V. Pemmaraju (Main section)
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:00pm-2:30pm M, 11:30am-1:00pm Th

Alberto M. Segre (Evening section)
14D MLH, alberto-segre@uiowa.edu, 319-335-1713
Office Hours: 2:30pm-4:00pm Th

Computer Science I: Fundamentals is an introductory course on computer programming with an emphasis on problem solving techniques. During the semester, students will gain proficiency in skills that are fundamental to solving computational problems, namely: (i) reading and understanding descriptions of computational problems that may sometimes be stated incompletely or imprecisely, (ii) breaking down a computational problem into simpler subproblems, (iii) designing algorithms for computational problems, (iv) translating algorithms into pseudocode and then into programs, (v) testing and debugging prgrams, and (vi) understanding time efficiency and memory usage of programs. Students will learn the importance of iterating through the above sequence of steps to build correct, well-documented, efficient, and reusable programs. The key programming topics include variables, expressions, data types, control flow statements, functions, data structures, objects and classes. The course will use the Python programming language. Python can be used interactively and can be accessed on Linux/Unix, Mac, and Windows platforms. The course is the starting point for computer science major and minor curricula, and also useful to other majors as a rigorous introduction to programming and solving computational problems. This semester the course has two sections. The "main section" (CS:1210:0AAA, 22C:016:AAA) consists of three lectures per week, with an additional discussion section that meets once per week. The "evening section" section (CS:1210:0SCA, 22C:016:SCA) meets twice a week, with no separate discussion sections.

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

(From xkcd)

Information about TAs

Quizzes, Homeworks, Projects, and Exams

• 5/13: Quiz10s with solutions
• 5/13: Quiz9s with solutions
• 5/6 The final exam is on Wednesday, May 15th from 10 am to noon in W10 PBAB. Here is more information about the exam.
• 4/30 Project 2, with Stage 2 specified.. Stage 2 due via ICON dropbox on Friday, May 10th at 4:59 pm. Project 2, Stage 2.
• 4/19 Project 2. Stage 1 due via ICON dropbox on Monday, April 29th at 4:59 pm. Here is the data set for the project.
• 4/16 Homework 5 Solution Test File. Use this to test your solution. If your solution passes all tests, then you should expect full score on the homework.
• 4/11 Homework 5. Due by 4:59 pm on April 19th. Data file for homework: miles.dat.
• 4/10 Exam 2 and its solution.
• 3/30: Quiz7s with solutions
• 3/30: Quiz6s with solutions
• 3/30: Quiz5s with solutions
• 3/30: Quiz4s with solutions
• 3/30 Project 1, Stage 2 Solution.
• 3/13 Homework 4.
• 3/9 Homework 3 Solution.
• 3/6 Project 1. Stage 1 due via ICON dropbox on Wednesday, March 13th at 4:59 pm. Be sure to regularly visit this page that provides updates on the project including sample input files and additional clarifications.
• 2/28 Homework 3. Due via ICON dropbox on Friday, March 8th at 4:59 pm. Data files: hyde.txt, war.txt, treasure.txt.
• 2/26: Exam 1 and Exam 1 Solution.
• 2/18: Quiz3s with solutions
• 2/13 Homework 2. Due via ICON dropbox on Friday, Feb 22nd at 4:59 pm. fastPowerMod.py
• 2/11: Quiz2s with solutions
• 1/29: Quiz1s with solutions
• Homework 1. Due via ICON dropbox on Friday, Feb 8th at 4:59 pm.

Announcements

• 5/8 Here are Project 2, Stage 2 clarifications.
• 5/7 Project 2, Stage 2 test files: test1.py, test2.py More test files will be posted soon.
• 5/6 The final exam is on Wednesday, May 15th from 10 am to noon in W10 PBAB. Here is more information about the exam.
• 4/29 Here are the solutions to Practice Problem Set 10.
• 4/10 Exam 2 and its solution.
• 4/8 Here are tentative midterm scores and letter grades. Please report errors right away.
• 4/1 There is no quiz in the discussion sections this week. The TAs will solve a practice exam to help you get ready for Exam 2 on Friday (4/5).
• 3/30 Exam 2 is on Friday, April 5th from 6:30 to 8:30 in W10 PBAB. Students in morning and evening sections will take the exam together. Here is all you need to know about the exam.
• 3/28 Homework 4 is now due at 4:59 pm on Monday, 4/1 and Project 1, Stage 2 is now due at 4:59 on Friday, 4/5.
• 3/11 Here are the solutions to Practice Problem Set 6.
• 3/9 Next week (3/11-3/15) Prof. Pemmaraju will not have office hours. The TAs will have office hours according to the following schedule: Renjitha Nair: Monday 11.15-1.15, Wednesday 2.30 to 3.30; Jamie Moore: Monday 1:00-3:00, Wednesday 1:30-2:30.
• 3/9 We have started this pagethat contains updates on Project 1. Be sure to visit this page regularly.
• 3/4 Here are the solutions to Practice Problem Set 5.
• 2/19 Exam 1 is on Friday, Feb 22nd from 6:30 pm to 8:30 pm in W10 PBAB. Students in the morning section and the evening section will take the exam together. Here is more information about the exam. You should use this exam from Spring 12 and this exam from Spring 11 as study guides and a source of practice problems. Solutions are available on the respective course pages.
• 2/18 Here are the solutions to Practice Problem Set 4.
• 2/13 The University of Iowa Computing Conference is on Feb 22nd, 23rd.
• 2/10 Here are the solutions to Practice Problem Set 3.
• 2/4 Here are the solutions to Practice Problem Set 2.
• 1/28 Office hours of TAs: Renjitha Nair: 11:30am-12:30pm W, 2:30pm-4:00pm F and Jamie Moore: 1:30pm-2:30pm W and 11:30am-1:30pm F. TAs will hold office hours in the Computer Science Lab, 301 MLH.
• 1/28 Here are the solutions to Practice Problem Set 1.
• 1/26 Office hours of instructors: Sriram Pemmaraju : 1:00pm-2:30pm M, 11:30am-1:00pm Th in 101G MLH and Alberto Segre: 2:30pm-4:00pm Th in 14D MLH.
• 1/22 Here are instructions on How to install Python and Wing on Windows computers and on How to install Python and Wing on Macs.
• 1/21 There will no discussion section meetings on Tuesday, 1/22.

Weekly Topics and Links to Lecture Notes

• Week 15 (last week!): 5/6-5/10
  Topics:
  • Object-oriented programming in Python
  • The point class
  • Operator overloading
  • The queue class
  Lecture Notes: • May 6   • May 8
  Code: queue.py   • queueDict.py
  Links to lecture videos:
  
  • Prof. Pemmaraju: • May 6   • May 8   • May 10.
  • Prof. Segre: • May 6   • May 8

• Week 14: 4/29-5/3
  Topics:
  • The quick sort algorithm and its implementation.
  • The importance of the choice of the pivot; choosing a pivot at random.
  • Introduction, motivation, history: object oriented programming.
  • Objects and class in Python.
  • The point class.
  Lecture Notes: • April 29   • May 1   • May 3
  Code: quickSort.py   • The point class
  Links to lecture videos:
  
  • Prof. Pemmaraju: • April 29   • May 1   • May 3.
  • Prof. Segre: • April 29   • May 1.
    Practice Problems: Solve Practice Problem Set 11 to better understand recursion. This is also preparation for next week's quiz.

• Week 13: 4/22-4/26
  Topics:
  • Implementing "divide-and-conquer" using recursion.
  • Merge sort.
  Lecture Notes: • April 22   • April 24
  Code: recursiveBinarySearch.py   • mergeSort.py   • mergeSortTiming.py
  Links to lecture videos:
  
  • Prof. Pemmaraju: • April 22   • April 24   • April 26
  • Prof. Segre: • April 22   • April 24
  Practice Problems: Solve Practice Problem Set 10 to better understand recursion. This is also preparation for next week's quiz. Here are the solutions to Practice Problem Set 10.

• Week 12: 4/15-4/19
  Topics:
  • Completing the implementation of the program that plays the "word ladder" game.
  • Introduction to recursion and inductive thinking.
  • Simple examples of recursive functions: factorial, fibonacci, power.
  Lecture Notes: • April 17   • April 19
  Code: • playLaddersGame2.py
  Links to lecture videos:
  
  • Prof. Pemmaraju: • April 15   • April 17   • April 19
  • Prof. Segre: • April 15   • April 17
  Practice Problems: Solve Practice Problem Set 9 to better understand the program that plays the word ladder game. This is also preparation for next week's quiz.

• Week 11: 4/8-4/12
  Topics:
  • Tuples
  • Dictionaries
  • Storing the "word network" using Dictionary-based data structure; comparing the running time of the Dictionary-based and list-based data structures.
  • Network exploration: algorithm, pseudocode, and implementation
  Lecture Notes: • April 8   • April 10
  Code: wordNetwork2.py   • playLaddersGame1.py
  Links to lecture videos:
  
  • Prof. Pemmaraju: • April 8   • April 10   • April 12
  • Prof. Segre: • April 10
  Practice Problems: Solve Practice Problem Set 8 to practice evaluating expressions involving dictionary operations, writing functions involving dictionaries, and in order to get ready for next week's quiz.

• Week 10: 4/1-4/5
  Topics:
  • Playing the "word ladder" game.
  • Reviewing for Exam 2.
  Lecture Notes: • April 1   • April 3
  Code: wordNetwork1.py
  Data files: words.dat
  

• Week 9: 3/25-3/29
  Topics:
  • List comprehensions.
  • String operations.
  • Example problem: Given the text of a novel (e.g., "War and Peace"), extract the names of the principal characters in the novel. Solution to the problem is provided in characters.py. The code is deliberately written in a "Pythonic" style that utilizes many of recently discussed Python features including list comprehensions and string operations.
  Lecture Notes: • March 25   • March 27   • March 29
  Code: characters.py
  Links to lecture videos:
  
  • Prof. Pemmaraju: • March 25   • March 27   • March 29
  • Prof. Segre: • March 27
  Practice Problems: None this week.

• Week 8: 3/11-3/15
  Topics:
  • A review of insert, delete, search, and misc. list operations in Python.
  • Efficiency of list operations: a mental model of how lists are implemented in Python.
  • Speeding up search using binary search.
  • Improving the efficiency of computeFrequencies by using binary search.
  • Functional programming in Python: the map, filter, and reduce operations.
  Lecture Notes: • March 11   • March 13   • March 15
  Code: binarySearch.py • timeSlowSearch.py • timeFastSearch.py
  Links to lecture videos:
  
  • Prof. Pemmaraju: • March 11   • March 13   • March 15
  • Prof. Segre: • March 11   • March 13
    
  Practice Problems: Solve Practice Problem Set 7 to practice evaluating expressions involving list operations and in order to get ready for next week's quiz.

• Week 7: 3/4-3/8
  Topics:
  • Finishing up the problem of parsing a file.
  • Introduction to sorting: selection sort.
  • Generating lists, the range function, slices of lists and strings, for-loops.
  • Other list methods for inserting into, searching and deleting from lists.
  • In the discussion sections, the discussion will be on ASCII codes for characters, the ord() and chr() functions, and how to use these in string manipulations.
  Lecture Notes: • March 4   • March 6   • March 8
  Code: selectionSort.py • timingSelectionSort.py • rollDistribution.py.
  Links to lecture videos:
  
  • Prof. Pemmaraju: • March 4   • March 6   • March 8
  • Prof. Segre: • March 4   • March 6
  Practice Problems: Solve Practice Problem Set 6 to practice writing functions for accessing and manipulating strings and lists and in order to get ready for next week's quiz. Here are the solutions to Practice Problem Set 6.
  Miscellaneous: Slides on ASCII values of characters and on ord() and chr() functions used in discussion sections on Tuesday, 3/5 and by Prof. Segre on Monday, 3/4.

• Week 6: 2/25-3/1
  Topics:
  • More on functions: local and global variables
  • Basic file I/O in Python
  • Introduction to sequence types: lists and strings
  • Basic list operations: indexing into a list, the in operator, appending to a list in-place.
  • Problem: Parsing an input file to compile a list of distinct numbers.
  Lecture Notes: • Feb 25   • Feb 27
  There are no notes for Friday, March 1st because we spent Wednesday (2/27) and Friday (3/1) covering the material in the Feb 27th notes.
  Links to lecture videos:
  
  • Prof. Pemmaraju: • Feb 25   • Feb 27   • March 1
  • Prof. Segre: • Feb 25   • Feb 27
  Readings: Chapter 14 from Prof. Ted Herman's notes on scope of variables in the context of functions.
  Code: parseFile.py
  Practice Problems: Solve Practice Problem Set 5 to review the material on keyword parameters and arguments and local and global variables in order to get ready for next week's quiz. Here are the solutions to Practice Problem Set 5.

• Week 5: 2/18-2/22
  Topics:
  • Solution to the problem of simulating a random walk using functions.
  • More on functions: arguments, parameters, keyword arguments and parameters.
  • Review for Exam 1
  Lecture Notes: • Feb 18 • Feb 20
  Links to lecture videos:
  
  • Prof. Pemmaraju: • Feb 18   • Feb 20
  • Prof. Segre: Feb 18   • Feb 20.
  Readings: 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: • randomWalk1.py   • randomWalk2.py   • randomWalk3.py   • randomWalk4.py
  Practice Problems: None this week.
  Miscellaneous: Function Examples covered in discussion sections on Tuesday, 2/19 and by Prof. Segre on Monday, 2/18.

• Week 4: 2/11-2/15
  Topics:
  • Variables in Python revisited: a mental model of how they work, issues of naming, and scope.
  • Expressions in Python and how they are evaluated. Short-circuit evaluation of boolean expressions.
  • Functions and modules revisted.
  • Functions defined in the random modules.
  • Programming Problem 3: Simulating a random walk.
  Lecture Notes: • Feb 11 • Feb 13 • Feb 15
  Links to lecture videos:
  
  • Prof. Pemmaraju: • Feb 11   • Feb 13   • Feb 15
  • Prof. Segre: Feb 11   • Feb 13
    
  Code: • randomWalk1.py   • randomWalk2.py   • randomWalk3.py   • randomWalk4.py
  Practice Problems: Solve Practice Problem Set 4 to review the material covered this week and to get ready for next week's quiz. Here are the solutions to Practice Problem Set 4.

• Week 3: 2/4-2/8
  Topics:
  • Working through several versions of the primality testing program.
  • Using the the break statement.
  • Using modules in Python; a glimpse at the math module.
  • Timing programs in Python; using the time module.
  • Boolean operators: and, not, or.
  • A more in-depth look at numeric data types.
  Lecture Notes: • Feb 4 • Feb 6 • Feb 8
  Links to lecture videos:
  
  • Prof. Pemmaraju: Feb 4   • Feb 6   • Feb 8
  • Prof. Segre: Feb 4   • Feb 6
  Readings: There are no assigned readings this week.
  Code: • primalityTesting0.py   • primalityTesting1.py   • primalityTesting2.py   • primalityTesting3.py   • primalityTesting4.py   • primalityTestingTimed.py
  Practice Problems: Solve Practice Problem Set 3 to review the material covered this week and to get ready for next week's quiz. Here are the solutions to Practice Problem Set 3.
  Miscellaneous: Nothing.

• Week 2: 1/28-2/1
  Topics:
  • Understanding the program that converts decimal integers to binary representation.
  • A whirlwind tour of constant, variables, operators, expressions, data types, built-in functions, input statements, output statements, and while-loops in Python
  • Improving the intToBinary program.
  • Our second programming problem: testing if a given postive integer is a prime (primality testing).
  Lecture Notes: • Jan 28 • Jan 30 • Feb 1
  Links to lecture videos:
  
  • Prof. Pemmaraju: Jan 28   • Jan 30   • Feb 1
    
  • Prof. Segre: Jan 30.
  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  • primalityTesting1.py
  Practice Problems: Solve Practice Problem Set 2 to review the material covered this week and to get ready for next week's quiz. Here are solutions to this problem set.
  Miscellaneous: Here are instructions on how to use Python and Wing on machines in the Division of Mathematical Sciences Labs.

• Week 1: 1/21-1/25
  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 23  • Jan 25
  Links to lecture videos:
  
  • Prof. Pemmaraju: Jan 25
  • Prof. Segre: Jan 23
  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. And here are the solutions to this problem set.
  Miscellaneous: Here are instructions on How to install Python and Wing on Windows computers and on How to install Python and Wing on Macs.

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 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.