CS 111: Introduction to Computer Science

Winter 2017

Basic Information

Instructor: Jed Yang, Center for Math & Computing 324,
Office hours: Monday 16:20–17:20 (in CMC 306), Thursday 14:35–15:35, Friday 13:00–14:00; or by appointment
Lectures: 6a (MW 15:10–16:20, F 15:30–16:30) in Center for Math & Computing 301
Course website: http://cs.carleton.edu/faculty/jyang/cs111.17w/

Course Information

This course will introduce you to computer programming and the design of algorithms. By writing programs to solve problems in areas such as image processing, text processing, and simple games, you will learn about recursive and iterative algorithms, complexity analysis, graphics, data representation, software engineering, and object-oriented design.

Textbook: Python Programming: an introduction to computer science, 3rd edition, John N. Zelle, 2016.

Calendar

Key dates, tentative:

In-class midterm exam: Friday, Week 5.
Take-home final exam: handed out middle of Week 9; due middle of Week 10.
Final project: demo during final exam slot; due 17:00 last day of finals.

Weekly schedule below to be updated throughout the term; tentative and subject to change.

Week 1: Introduction to introduction to computer science (Chapters 1, 2)

==[ Wednesday, 2017-01-04 ]==
Introduction to CS 111: Introduction to Computer Science
Computer science basics (Zelle 1)
hw00: Getting started, due Friday, 01/06 at 15:30
hw01: Getting to know Unix, due Friday, 01/06 at 15:30
hw02: Counting lines in a file, due Monday, 01/09 at 22:00
==[ Friday, 2017-01-06 ]==
Read before class: Zelle 2.1–2.4: Zelle's book is best read while you have access to a Python interpreter, so you can experiment with the examples given in the book. Note that it will take some time to absorb the material in these chapters, so you should write down your main questions as you go, and ask me or the prefect about them in class, prefect sessions, or office hours.
Remember to post a question or comment to Readings Forum on Moodle. To receive participation credit, this should be done two hours before class.
Python basics (Zelle 2)
lab01: Python basics: Friday in-class activity

Week 2: Python basics: numbers, strings, functions, decision structures, loops (Chapters 3, 5, 6, 7, 8)

==[ Monday, 2017-01-09 ]==
Read before class: Zelle 2.5–2.8
hw02 due tonight
Wrap up lab01
Assignments and eval
lab02: More Python basics
hw03: Making change, due Friday, 01/13 at 22:00
==[ Wednesday, 2017-01-11 ]==
Read before class: Zelle 3.1–3.4
Wrap up lab02
Wrap up hw02
Numbers (Zelle 3)
==[ Friday, 2017-01-13 ]==
Read before class: Zelle 5.1–5.4
hw03 due tonight
Strings (Zelle 5)
lab03: Fun with Python
hw04: Caesar cipher, due Wednesday, 01/18 at 22:00

Week 3: Deeper discussion of functions, decision structures, loops (Chapters 6, 7, 8)

==[ Monday, 2017-01-16 ]==
Read before class: Zelle 6.1–6.2, 6.4: p.187 refers to 6.3, so you may ignore it.
Wrap up hw03, lab03
Functions (Zelle 6)
[code in class]
==[ Wednesday, 2017-01-18 ]==
Read before class: Zelle 7.1–7.3
hw04 due tonight
Decision structures (Zelle 7)
lab04: More fun with Python
hw05: Menu-driven string functions, due Monday, 01/23 at 22:00
Survey: Pairings for hw05: Fill out Moodle survey today if and only if you want to request a change.
==[ Friday, 2017-01-20 ]==
Read before class: Zelle 8.1–8.3
Loops (Zelle 8)
[code in class]

Week 4: Graphics and Objects (Chapter 4).

==[ Monday, 2017-01-23 ]==
Read before class: Zelle 8.4–8.5
hw05 due tonight
More loops (Zelle 8)
Survey: Pair programming evaluation: Fill out Moodle survey by noon Tuesday.
You have no homework currently out, so I suggest reviewing for the exam next week.: The (long) reading for Friday is a good place to start.
[code in class]
==[ Wednesday, 2017-01-25 ]==
Read before class: Zelle 4.1–4.4: 4.5 is a long summative example that you may want to consider reading.
lab05: Graphics
hw06: Smiley face, due Friday, 01/27 at 22:00
hw07: Weather statistics, due Wednesday, 02/01 at 22:00
==[ Friday, 2017-01-27 ]==
Read before class: Zelle 5.5–5.10: This reading is substantially longer than usual, but it is mostly review.
hw06 due tonight
Wrap up lab05
Objects (Zelle 4)
Worksheet 1

Week 5: Classes (Chapter 10); in class exam, catch-up.

==[ Monday, 2017-01-30 ]==
Read before class: Zelle 10.1–10.3
Wrap up worksheet 1
Worksheet 2
[code in class]
==[ Wednesday, 2017-02-01 ]==
Read before class: Zelle 6.3, 6.5–6.8; 7.5–7.6: Another long reading that is mostly review.
hw07 due tonight
Classes (Zelle 10)
Wrap up worksheet 2
hw08: Data representation, due Friday, 02/10 at 15:30 on paper
[code in class]
==[ Friday, 2017-02-03 ]==
Read before class: Zelle Chapters 1–3 and 5–8: You do NOT need to write a forum post.
In-class Midterm Exam

Week 6: Recursion (Chapter 13).

==[ Wednesday, 2017-02-08 ]==
Read before class: Zelle 10.7: You do not need to fully understand 10.7.3--focus on other subsections. setCoords is explained in 4.6, Button is constructed in 10.6.2; you may read those if you like.
Midterm Evaluations
lab06: Pacman: A collaborative coding session.
hw09: Ocean simulation, due Wednesday, 02/15 at 22:00
==[ Friday, 2017-02-10 ]==
Read before class: Zelle 13.2.1–13.2.2
hw08 due in class
Wrap up Midtem Evaluations
Recursion basics (Zelle 13.2)
Worksheet
[code in class]

Week 7: Algorithms: recursion, searching, and some complexity theory.

==[ Monday, 2017-02-13 ]==
Read before class: Zelle 13.2.3, 13.2.5
lab07: Recursion
[code in class]
==[ Wednesday, 2017-02-15 ]==
Read before class: Zelle 13.1–13.1.2, 13.2.7
hw09 due tonight
Wrap up lab07
Searching (Zelle 13.1)
Advanced: Knuth–Morris–Pratt algorithm for fast string search
hw10: Image processing, due Wednesday, 02/22 at 22:00
[code in class]
==[ Friday, 2017-02-17 ]==
Read before class: Zelle 13.1.3–13.1.4
Asymptotics and binary search
lab08: Binary search

Week 8: Sorting, prep for the final project.

==[ Monday, 2017-02-20 ]==
Read before class: Zelle 13.2.4, 13.2.6
Sorting!
Sorting visualization
Final Project
Survey: Pairings for final project: Fill out Moodle survey by noon Tuesday.
==[ Wednesday, 2017-02-22 ]==
Read before class: Zelle 13.3–13.3.2
hw10 due tonight
Merge Sort
Sorting visualizations:: step-by-step explanations, side-by-side comparisons
Computational fairy tales: Why tailors use insertion sort
[code in class]
==[ Friday, 2017-02-24 ]==
Read before class: Zelle 13.3.3
Final Project proposal due tonight
Comparing sorting algorithms
Comparison-based sorting algorithms: Worst-case behaviour n log n is as good as it gets.

Week 9: Take-home exam, miscellaneous topics.

==[ Monday, 2017-02-27 ]==
Read before class: Zelle 13.4: I will give a slightly different presentation of 13.4.2 in class.
Computability and decidability: halting problem
lab09: Recursion review
[code in class]
==[ Wednesday, 2017-03-01 ]==
Read before class: Nothing!
lab10: Stacks
Take-home final handed out
==[ Friday, 2017-03-03 ]==
Work on Final Project

Week 10: Catch-up and miscellaneous topics.

==[ Monday, 2017-03-06 ]==