Princeton University
Computer Science Department

Computer Science 217
Introduction to Programming Systems

Andrew W. Appel

Spring 2005
Directory
General Information | Schedule | Assignments | Announcements | Policies

Week 1: 1/31 - 2/6

Reading (required): C Programming (King) 1, 2, 3

Reading (recommended): Programming with GNU Software (Loukides & Oram) 1, 2, 3, 4

Lecture 1: (Monday) Introduction to Programming Systems

Precept 1: (Monday/Tuesday) Introduction; The Program Preparation Process

Lecture 2: (Wednesday) Character I/O in C

Precept 2: (Wednesday/Thursday) UNIX; Emacs

Week 2: 2/7 - 2/13

Reading (required): C Programming (King) 4, 5, 6, 7; The Practice of Programming (Kernighan & Pike) 4

Reading (recommended): Programming with GNU Software (Loukides & Oram) 6

Lecture 3: (Monday) Variables, Pointers, and Arrays

Precept 3: (Monday/Tuesday) C Simple Programs; C Fundamentals

Lecture 4: (Wednesday) Modules

Precept 4: (Wednesday/Thursday) C Fundamentals (cont.); C Multi-File Programs; Gdb

(Sunday) Decomment Assignment Due

Week 3: 2/14 - 2/20

Reading (required): C Programming (King) 8, 9, 11, 12, 13, 14; The Practice of Programming (Kernighan & Pike) 1

Lecture 5: (Monday) Programming Style

Precept 5: (Monday/Tuesday) C Pointers; C Arrays

Lecture 6: (Wednesday) Abstract Data Types, Linked Lists, and Function Pointers

Precept 6: (Wednesday/Thursday) C Arrays (cont.); C Strings; C Constants

(Sunday) String Functions Assignment Due

Week 4: 2/21 - 2/27

Reading (required): C Programming (King) 15, 16, 17, 19; The Practice of Programming (Kernighan & Pike) 2

Lecture 7: (Monday) Program Design and Hash Tables

Precept 7: (Monday/Tuesday) C Files; C Structures; C Dynamic Memory Management

Lecture 8: (Wednesday) Memory Allocation

Precept 8: (Wednesday/Thursday) The Memstat Tool; C Abstract Data Types

Week 5: 2/28 - 3/6

Reading (required): C Programming (King) 10, 18

Lecture 9: (Monday) Interface Specifications and Assertions

Precept 9: (Monday/Tuesday) C Void Pointers and Abstract Data Types; The Symbol Table Assignment

Lecture 10: (Wednesday) Declarations and Definitions

Precept 10: (Wednesday/Thursday) C Function Pointers and Abstract Data Types; A DynArray ADT

(Sunday) Symbol Table Assignment Due

Week 6: 3/7 - 3/13

Reading (required): The Game of Kalah

Reading (recommended): Artificial Intelligence (Rich) 12

Lecture 11: (Monday) Game Playing Programs

Precept 11: (Monday/Tuesday) Midterm Exam Preparation; C Declarations and Definitions

Lecture 12: (Wednesday) Midterm Exam Old Exams and Answer Sheets; This Semester's Exam and Answer Sheet

Precept 12: (Wednesday/Thursday) NO PRECEPT

Week 7: 3/14 - 3/20

(Monday - Sunday) Fall Recess

Week 8: 3/21 - 3/27

Reading (required): The Practice of Programming (Kernighan & Pike) 6

Lecture 13: (Monday) Incremental evaluation in alpha/beta search

Precept 13: (Monday/Tuesday) Game Player Assignment Team Meeting

Lecture 14: (Wednesday) Testing

Precept 14: (Wednesday/Thursday) Game Player Assignment Team Meeting

Week 9: 3/28 - 4/3

Reading (required): The Practice of Programming (Kernighan & Pike) 7

Reading (recommended):  Programming with GNU Software (Loukides & Oram) 7, 9

Lecture 15: (Monday) Timing and profiling

Precept 15: (Monday/Tuesday) Make; Game Player Assignment Team Meeting

Lecture 16: (Wednesday) Computer Architecture

Precept 16: (Wednesday/Thursday) Gprof; Alpha-Beta Search; Game Player Assignment Team Meeting

(Sunday) Game Player Assignment Due

Week 10: 4/4 - 4/10

Reading (required): Programming from the Ground Up (Bartlett) 1, 2, 3, 10, B, E

Reading (recommended): IA32 Intel Architecture Software Developer's Manual: Volume 1: Basic Architecture

Lecture 17: (Monday) Procedure calls

Precept 17: (Monday/Tuesday) Assembly Language: Getting Started

Lecture 18: (Wednesday) Programming in assembly language

Precept 18: (Wednesday/Thursday) Assembly Language: Fundamentals, Control Transfer

Week 11: 4/11 - 4/17

Reading (required):  Programming from the Ground Up (Bartlett) 4, 9, F

Reading (recommended):  Programming from the Ground Up (Bartlett) 5, 6, 7, 8, 11, 12, 13, C; IA32 Intel Architecture Software Developer's Manual: Volume 2: Instruction Set Reference; Tool Interface Standard (TIS) Executable and Linking Format (ELF) Specification

Lecture 19: (Monday) Assemblers and linkers

Precept 19: (Monday/Tuesday) Assembly Language: Instruction Operands, Local Variables

Lecture 20: (Wednesday) Operating systems and protection

Precept 20: (Wednesday/Thursday) Assembly Language: Functions, Gdb for Assembly Language

(Sunday) UNIX Commands in Intel Assembly Language Assignment Due

Week 12: 4/18 - 4/24

Lecture 21: (Monday) Computer security

Precept 21: (Monday/Tuesday) The Buffer Overrun Assignment

Lecture 22: (Wednesday)

Precept 22: (Wednesday/Thursday) Assemblers, Linkers, and Machine Language

(Sunday) Buffer Overrun Assignment Due

Week 13: 4/25 - 5/1

Reading (required): Machine Learning (Mitchell) 6.9, 6.10 (distributed in precepthandouts)

Reading (recommended): Scientific American "Stopping Spam" article (distributed in precepthandouts)

Lecture 23: (Monday) Spam filters

Precept 23: (Monday/Tuesday) The Spam Filter Assignment: Overview

Lecture 24: (Wednesday) Machine learning

Precept 24: (Wednesday/Thursday) The Spam Filter Assignment: Mathematical Foundations

Week 14: 5/2 - 5/8

(Monday - Sunday) Reading Period

Week 15: 5/9 - 5/15

(Monday) Reading Period

(Tuesday) Dean's Date

(Tuesday) Spam Filter Assignment Due

(Friday) Final Exam (May 13, 9:00 AM, Friend Center 006) Old exams and answer sheets; Final exam prep sheet; This Semester's Exam and Answer Sheet

All lecture notes are copyright 2001, 2002, 2003, 2004, 2005 by Andrew W. Appel, Thomas Funkhouser, David R. Hanson, Larry Peterson, and/or Randolph Wang. All precept handouts are copyright 2001, 2002, 2003, 2004, 2005 by Robert M. Dondero, Jr. Permission to reproduce these notes for not-for-profit educational purposes is hereby granted. These notes may not be reproduced for commercial purposes without the express written consent of the author.