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

Instructor:
Sriram V. Pemmaraju
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:30-2:30 M, 10:30-11:30 W, 1:00-2:00 Th (and by appointment)

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

Information about TAs

Name		e-mail address				Discussion Sections	
Jayant Parchure jayant-parchure@uiowa.edu		A3 (11-11:50 116 MH), A5 (3:30-4:20, 248 JH)		
Ruchika Salunke ruchika-salunke@uiowa.edu		A1 (8:30-9:20 221 MLH), A2 (9:30-10:20, 213 MLH)		
Momina Tabish	syedamomina-tabish@uiowa.edu		A4 (12:30-1:20, 66 SH), A6 (5-5:50, 346 JH)	

Jayant Parchure			TW 2-3:30                                                          
Ruchika Salunke 		W 5-6:30, F 9-9:30 and 2:30-3:30    
Momina Tabish 			M 2-4; Th 8:30-9:30  

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

• Homework 5 Solution.
• Pop Quiz 5.
• Exam 2 and Exam 2 Solution.
  
• Homework 5. Due via ICON at 4:59 pm on 4/17. Data file: babyNames.txt. Notes on running times and correctness of Problems (a) and (b). A test file for HW5(c): hw5cTest.py.
• Project 1 Phase 2 Solution. Feel free to use in your solution to Phase 3.
• KML tutorial from the developers at Google. Sample kml files: fourPushPins.kml, path.kml, pathAndTwoPushPins.kml.
• Quiz 5, Quiz 6, Quiz 7, Quiz 8, Quiz 9.
• Pop Quiz 4.
• Project 1, Phase 2 test file: Phase2Test.py.
• Project 1 Phase 1 Solution. Feel free to use in your solutions to Phases 2 and 3.
• Homework 4 Solution. This solution llustrates the power of binary Search. It runs in about 5 seconds compared to about 4 minutes for an almost identical solution that uses the Python-provided index function for searching.
• Project 1. Data file: miles.dat. Phase 1 test file: Phase1Test.py.
• Homework 4 Test Files.
• Homework 3 Solutions.
• Pop Quiz 3 (3/5).
• Homework 4. Due via ICON at 4:59 pm on 3/11. hyde.txt, war.txt, and treasure.txt.
• Practice Problem set 6
• Exam 1 and Exam 1 Solution.
  
• Homework 2 Solutions.
• Homework 3. Due via ICON at 4:59 pm on 2/27.
• Practice Problem Set 5.
• Quiz 1, Quiz 2, Quiz 3, Quiz 4.
• Pop Quiz 2 (2/12).
• Exam 1: 6:30-8:30 pm, Fri Feb 20th, W10 PBB. More information on Exam 1.
• Homework 1 Solutions.
• Practice Problem Set 4. isPrime.py, numPrimes.py.
• Homework 2. Due via ICON at 4:59 pm on 2/13.
• Practice Problem Set 3.
• Pop Quiz 1 (1/30).
• Practice Problem Set 2.
• Homework 1. Due via ICON at 4:59 pm on 2/2. binaryToDecimal.py.
• Practice Problem Set 1. Solutions.

Announcements

• 5/3 The final exam is on Friday, 5/15 12:30-2:30 in 100 PH (Philips Hall). Here is more information about the final.
  Spring 2013 Exam and Solution to Spring 2013 Exam.
  Spring 2012 Exam and Solution to Spring 2012 Exam.
• 5/1 Pre-final tentative letter grades are here.
• 4/24 The final exam is on Friday, 5/15 12:30-2:30 in 100 PH (Philips Hall).
• 4/13 Homework 5 handout has been updated based on the discussion in the lecture today (4/13).
• 4/13 Exam 2 performance analyzed: Exam 2 Stats.
• 4/6 No discussion sections tomorrow (4/7).
• 3/25 Exam 2 is on Friday, April 3rd, 6:30 pm-8:30 pm in W10 PBB (our classroom). It is an open notes/book exam. Here is more information on the exam.
• 2/23 Register for and attend the UICC this weekend (Feb 27-28). Write one paragraph describing what your learned from any one of the talks. Turn this in after the lecture on Monday, March 2 for 10 points extra credit.
• 2/11 Exam 1 is on Friday, Feb 20th, 6:30 pm-8:30 pm in W10 PBB (our classroom). It is an open notes/book exam.
• 2/6 The 2015 University of Iowa Computing Conference will take place on Feb 27th and Feb 28th. This is a fabulous opportunity to learn more about computing as a science and as a profession. You should plan to register and attend and as incentive I'll arrange extra credit for attendance. More details on that soon.
• 2/2 TA Jayant Parchure will not hold office hours on Tuesday, 2/3. His replacement office hours will be on Thursday, 2/5 from 3:30-5:00 in 101N.
• 1/21 Instructions on How to install Python and Wing on Windows computer and on How to install Python and Wing on Mac.
• 1/17 There will be no discussion section meetings on Tuesday, 1/20.

Weekly Topics and Links to Lecture Notes

• Week 15 (last week!): 5/4-5/8
  Topics:
  • Using a queue ("FIFO") data structure to obtain shortests paths
  • List-based and dictionary-based implementations of the queue class
  • The power of inheritance
  • Exam review (on Friday, 5/8).
  Lecture Notes: • May 4
  Code: queueList1.py, queueList2.py, queueDict.py
  Readings: To be posted. Practice Problems: None this week.

• Week 14: 4/27-5/1
  Topics:
  • Finishing up exceptions and exception-handling.
  • Introduction to object-oriented programming.
  • Classes, objects, constructors, operator overloading.
  • Example of the point class.
  Lecture Notes: • April 29, May 1
  Code: point.py, queueList1.py, queueList2.py, queueDict.py
  Readings: Chapter on Object-Oriented Program from Prof. Ted Herman's notes; read until and including Page 253.
  Practice Problems: Practice Problem set 13. Solve these problems to practice material on object-oriented programming and prepare for the quiz on Tuesday, 5/5.

• Week 13: 4/20-4/24
  Topics:
  • The quickSort algorithm.
  • The partition algorithm.
  • Why quickSort is efficient. Randomized quickSort.
  • Exceptions and exception-handling.
  Lecture Notes: • April 20 • April 22 • April 24
  Readings: None this week.
  Code: quickSort.py.
  Practice Problems: Practice Problem set 12. Solve these problems to practice material on the partition and quickSort functions.

• Week 12: 4/13-4/17
  Topics:
  • Finishing up the word network example: traversing network.
  • Recursion and recursive functions. Basic examples: factorial, Fibonacci numbers, computing the power efficiently.
  • The divide-and-conquer paradigm. Introduction to recursive sorting: quickSort.
  Lecture Notes: • April 15, • April 17.
  Readings: To be posted.
  Code: fibonacci.py timingFibo.py power.py quickSort.py.
  Practice Problems: Practice Problem set 11. Solve these problems to practice material on network exploration and recursion and to prepare for quiz on Tuesday, April 21st.

• Week 11: 4/6-4/10
  Topics:
  • Dictionaries in Python, dictionary operations.
  • Examples showing off the efficiency of dictionaries for search
  • Building a word network using dictionaries
  • Finishing up the word network example: traversing network.
  Lecture Notes: • April 6 • April 8
  Readings: Read Chapter 11 on Dictionaries (Sections 11.1, 11.2, 11.3, and 11.4 only) from "Think Python: How to Think Like a Computer Scientist" by Allen B. Downey.
  Code: wordNetwork2.py distinctRandomList.py playLaddersGame1.py playLaddersGame2.py Data file: words.dat.
  Practice Problems: Practice Problem set 10. Solve these problems to practice material on dictionaries and prepare for quiz on Tuesday, April 14th.

• Week 10: 3/30-4/3
  Topics:
  • Programming Problem: Building and traversing a word ladder
  • Networks, nodes, edges, building a word network.
  Lecture Notes: • March 30 • April 1
  Readings: Nothing this week. Just exam preparation.
  Code: wordNetwork1.py Data file: words.dat.
  Practice Problems: For Exam 2 on Friday use Spring 2014 Exam 2 as practice. Also, Problems 3 and 4 from Spring 2012 Exam 2 and Problems 2, 3, and 4 from Spring 2013 Exam 2.

• Week 9: 3/23-3/27
  Topics:
  • List comprehensions.
  • Programming Problem: Extracting principal characters in a novel.
  Lecture Notes: • March 23-25 • March 27
  Readings: Read Slice, Split, Join (Chapter 11 from Prof. Ted Herman's notes on CS1) and Python 3 tutorial Sections 5.1.3 and 5.1.4 on list comprehensions.
  Code: characters.py and data file: illiad.txt.
  Practice Problems: Practice Problem set 9. Solve these problems to practice material on list comprehensions and prepare for quiz on Tuesday, March 31st.

• Week 8: 3/9-3/13
  Topics:
  • Binary Search. Comparison with linear search.
  • Generating lists. The range type. List slices.
  • String operations.
  Lecture Notes: • March 9, • March 11 • March 13
  Readings: Operations that modify lists in-place in Python 3 documentation; String methods in Python 3 documentation.
  Code: binarysearch.py.
  Practice Problems: Practice Problem set 8. Solve these problems to practice material on lists and strings and prepare for quiz on Tuesday, March 24th.

• Week 7: 3/2-3/6
  Topics:
  • Lists as mutable objects
  • List operations: append, extend, insert, remove, sort, reverse, etc.
  • Why are lists mutable? Implementation of lists via references.
  • Sorting and searching: selection sort.
  Lecture Notes: • March 4, • March 6
  Readings: Read Section 5.1 (stop before Subsection 5.1.1) and Section 5.2 on list operations in this tutorial from python.org.
  Code: selectionSort.py, timingSelectionSort.py.
  Practice Problems: Practice Problem set 7. Solve these problems to practice material on lists and prepare for quiz on Tuesday, March 10th.

• Week 6: 2/23-2/27
  Topics:
  • Introduction to sequence type: strings and lists
  • Using the [ ] notation to access elements of strings and lists
  • The in, "+", and "*" operators on lists and strings
  • Reading from files
  • Programming Problem 4: reading from a file, parsing lines of text, and counting distinct integers in file.
  Lecture Notes: • Feb 23-25
  Readings: Extra reading on functions: Chapter 8 from Prof. Ted Herman's notes for CS1.
  Code: fileInputExample.py, input.txt, parseFile.py, test.txt.
  Practice Problems: Practice Problem set 6. Solve these problems to practice material on lists and prepare for quiz on Tuesday, March 3rd.

• Week 5: 2/16-2/20
  Topics:
  • Organizing functions within a program
  • The "sticky note" model of variables in Python.
  • Arguments and parameters and the "sticky note" model applied to parameter passing.
  • Scope of variables, local and global variables, declaring variables global
  • Keyword arguments, Keyword parameters
  • Exam 1 review
  Lecture Notes: • Feb 16 • Feb 18
  Readings: To be posted.
  Code: isPrime.py, numPrimes.py.
  Practice Problems: Practice Problem set 5. Solve these problems to prepare for Exam 1 (Feb 20th) and Quiz 5 (Feb 24th).

• Week 4: 2/9-2/14
  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.
  • Defining and calling functions in Python
  • Solution to Programming Problem 3 involving several functions.
  Lecture Notes: • Feb 9 and 11
  Readings: Sections 6.1, 6.2, 6.3, and 6.4 on functions from Think Python: How to Think Like a Computer Scientist.
  Code: • rollSevens.py • randomWalk0.py • randomWalk1.py • randomWalk2.py • randomWalk3.py
  Practice Problems: Practice Problem Set 4. Solve to prepare for Quiz 4 on Tuesday, Feb 17th.

• Week 3: 2/2-2/6
  Topics:
  • Programming Problem 2: Listing primes.
  • More practice with control flow: while-loops, if- and if-else-statements, and break statements.
  • 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.
  • Understading and using nested loops
  Lecture Notes: • Feb 2 • Feb 4 • Feb 6
  Readings: Read about if-statements and while-loops in Chapter 6, Pages 24-27 from the book A byte of Python. Note: This book uses Python 2. What we call input in Python 3 is called raw_input in Python 2.
  Code: • primalityTesting0.py   • primalityTesting1.py   • primalityTesting2.py   • primalityTesting3.py   • primalityTesting4.py   • primalityTestingTimed.py   • listPrimes.py
  Practice Problems: Solve Practice Problem Set 3 to prepare for Quiz 3 in discussion sections on Feb 10th.

• Week 2: 1/26-1/30
  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 26 • Jan 28 • 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  • intToBinary5.py
  Practice Problems: Solve Practice Problem Set 2 to prepare for Quiz 2 in discussion sections on Feb 3rd.

• Week 1: 1/20-1/23
  Topics:
  • Welcome to Computer Science I: Fundamentals: why this is an exciting time to be a computer scientist.
  • Programming Problem 1: 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 21 • 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  • intToBinary5.py
  Practice Problems: Solve Practice Problem Set 1 to get ready for next week's quiz (in the discussion sections on 1/27).
  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:
  • Spring 2014 (Prof. Sriram Pemmaraju).
  • 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.