CS 111

Fall 2016

Introduction to Computer Science

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: 5a (MW 13:50–15:00, F 14:20–15:20) in Center for Math & Computing 102
Course website: http://cs.carleton.edu/faculty/jyang/cs111.16f/

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, 2nd edition, John N. Zelle, 2010.

Calendar

Key dates, tentative:

In-class midterm exam: Wednesday, Week 5.
Take-home final exam: handed out beginning of Week 9; due beginning 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)

==[ Monday, 2016-09-12 ]==
hw00: Making introductions, due Wednesday, 9/14 at 13:50
hw01: Getting to know Unix, due Wednesday, 9/14 at 13:50
Reading: Course syllabus [PDF]: Please do this as soon as possible and discuss any concerns with me this week. I will assume you have read and agreed with the policies.
==[ Wednesday, 2016-09-14 ]==
hw02: Counting lines in a file, due Friday, 09/16 at 23:55
Reading: Zelle Chapters 1-3: For best results, read Chapters 1-2 by Friday and Chapter 3 by Monday. 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.
==[ Friday, 2016-09-16 ]==
hw02 due tonight
lab01: Python basics: Friday in-class activity
hw03: Making change, due Wednesday, 09/21 at 23:55: Note extended due date.

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

==[ Monday, 2016-09-19 ]==
Survey: Fill out pair programming survey today.
Wrap-up hw02 and lab01
Numbers (Zelle 3)
Reading: Zelle Chapter 5: Focus on sections 5.1 to 5.5. Bring questions on Wednesday.
==[ Wednesday, 2016-09-21 ]==
hw03 due tonight
Reading: Pair programming guidelines
Pairings for hw04
hw04: Caesar cipher, due Monday, 09/26 at 23:55
Strings (Zelle 5)
Reading: skim Zelle Chapters 6-8: Basic concepts of these chapters have been introduced in lab01 and are needed for hw04. Next week we will have more in-depth discussions of these concepts. Use as reference now and read more carefully by next week.
==[ Friday, 2016-09-23 ]==
lab02: More Python basics
Reading: Zelle Chapter 6: Bring questions on Monday.

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

==[ Monday, 2016-09-26 ]==
hw04 due tonight
Survey: Pairings for hw05: Fill out Moodle survey today if and only if you want to request a change.
Assignments (Zelle 2.5)
Functions (Zelle 6)
Wrap-up hw03
Reading: Zelle Chapter 7: Bring questions on Wednesday.
hw05: Menu-driven string functions, due Friday, 09/30 at 23:55
==[ Wednesday, 2016-09-28 ]==
Wrap-up lab02
Decision structures (Zelle 7)
Reading: Zelle Chapter 8
==[ Friday, 2016-09-30 ]==
hw05 due tonight
Survey: Pairings for hw07: Fill out Moodle survey by noon Sunday.
Loops (Zelle 8)
Reading: Zelle Chapter 4

Week 4: Objects (Chapters 4 and 10).

==[ Monday, 2016-10-03 ]==
lab03: Graphics
hw06: Smiley face, due Wednesday, 10/05 at 23:55
hw07: Weather statistics, due Monday, 10/10 at 23:55
==[ Wednesday, 2016-10-05 ]==
hw06 due tonight
Worksheet 01
Wrap-up lab03
Objects (Zelle 4)
Reading: Zelle Chapter 10
==[ Friday, 2016-10-07 ]==
Wrap-up hw04
Wrap-up worksheet 01

Week 5: In class exam, catch-up.

==[ Monday, 2016-10-10 ]==
hw07 due tonight
Survey: Pairings for hw08: Fill out Moodle survey today if and only if you want to request a change.
Midterm on Wednesday!
Wrap-up hw05
Classes (Zelle 10)
Live-coding demo: marker.py: needs colour.py
Worksheet 02
Reading: Zelle Chapters 1-3 and 5-8
==[ Wednesday, 2016-10-12 ]==
In-class Midterm Exam
==[ Friday, 2016-10-14 ]==
Midterm Evaluations
Wrap-up hw06: A gallery of faces.
lab04: Pacman: A collaborative coding session.

Week 6: Recursion (Chapter 13).

==[ Wednesday, 2016-10-19 ]==
hw08: Ocean simulation, due Monday, 10/24 at 23:55
Wrap-up Midtem Evaluations
Recursion basics (Zelle 13.2)
"Worksheet"
Reading: Zelle Chapter 13: This chapter is dense and difficult. We will move through this slowly this week and next week.
==[ Friday, 2016-10-21 ]==
lab05: Recursion

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

==[ Monday, 2016-10-24 ]==
hw08 due tonight
hw09: Data representation, due Friday, 10/28 at 14:20 on paper
Survey: Pairings for hw10: Fill out Moodle survey today.
Wrap-up hw07 and lab05
fibonacci_smart.py: Smarter Fibonacci recursion
Searching (Zelle 13.1)
==[ Wednesday, 2016-10-26 ]==
hw10: Image processing, due Wednesday, 11/02 at 23:55
Asymptotics and binary search
lab06: Binary Search mini-lab
binary_search_index.py: Recursive binary search returning index
==[ Friday, 2016-10-28 ]==
hw09 due in class
Sorting (Zelle 13.3): We talked about (in this order) Bubble Sort, Insertion Sort, and Selection Sort today. We will talk about some of the other ones later.
Sorting visualization

Week 8: Catch-up, prep for the final project.

==[ Monday, 2016-10-31 ]==
Wrap up hw08
Final Project
Survey: Pairings for final project: Fill out Moodle survey today.
Merge Sort
==[ Wednesday, 2016-11-02 ]==
hw10 due tonight
sort.py: A few simple sorting algorithms
Comparing sorting algorithms
lab07: String Recursion mini-lab
==[ Friday, 2016-11-04 ]==
Final Project proposal due tonight
Wrap-up lab07
Computability and decidability: halting problem

Week 9: Take-home exam, miscellaneous topics.

==[ Monday, 2016-11-07 ]==
lab08: Stacks
Take-home final handed out
==[ Wednesday, 2016-11-09 ]==
Wrap-up lab08
Work on Final Project
==[ Friday, 2016-11-11 ]==
lab09: Higher-order functions

Week 10: Catch-up and miscellaneous topics.

==[ Monday, 2016-11-14 ]==
Take-home final due in class