Princeton University
Computer Science Department

Computer Science 217
Introduction to Programming Systems

Andrew W. Appel

Spring 2007


Directory
General Information | Schedule | Assignments | Announcements | Policies


Week 1: 2/5 - 2/11

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

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

Reading (recommended): Computer Systems (Bryant & O'Hallaron) 1

Lecture 1: (Monday) Introduction to Programming Systems

Precept 1: (Monday/Tuesday) Administrative Matters; A Minimal Computing Environment; The Program Preparation Process

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

Precept 2: (Wednesday/Thursday) UNIX and Bash; Emacs


Week 2: 2/12 - 2/18

Reading (required): C Programming (King) 4, 5, 6, 7

Reading (required): 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

Lecture 4: (Wednesday) Modules

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

(Sunday) Decomment Assignment Due


Week 3: 2/19 - 2/25

Reading (required): C Programming (King) 8, 9, 11, 12, 13, 14

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

Lecture 5: (Monday) Programming Style and Scope in Programming Languages

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

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

Precept 6: (Wednesday/Thursday) C Array and Pointers; C Strings; C Constants

(Sunday) String Functions Assignment Due


Week 4: 2/26 - 3/4

Reading (required): C Programming (King) 15, 16, 17, 19

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

Lecture 7: (Monday) Program Design and Hash Tables

Precept 7: (Monday/Tuesday) C Command-Line Arguments; C Files; C Structures; C Dynamic Memory Management

Lecture 8: (Wednesday) Memory Allocation

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


Week 5: 3/5 - 3/11

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 and Make

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

(Sunday) Symbol Table Assignment Due


Week 6: 3/12 - 3/18

Reading (required): Othello (http://www.pressmangames.com/instructions/instruct_othello.html)

Reading (recommended): Artificial Intelligence (Rich) 12

Lecture 11: (Monday) Game Playing Programs

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

Lecture 12: (Wednesday) Midterm Exam (Exams and Answers from Previous Semesters, This Semester's Exam, Answers for This Semester's Exam)

Precept 12: (Wednesday/Thursday) NO PRECEPT


Week 7: 3/19 - 3/25

(Monday - Sunday) Spring Recess


Week 8: 3/26 - 4/1

Reading (required): The Practice of Programming (Kernighan & Pike) 5, 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: 4/2 - 4/8

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

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

Reading (recommended): Computer Systems (Bryant & O'Hallaron) 5

Lecture 15: (Monday) Timing and Profiling

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

Lecture 16: (Wednesday) Computer Architecture

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

(Sunday) Game Player Assignment Due


Week 10: 4/9 - 4/15

Reading (required): Computer Systems (Bryant & O'Hallaron) 2, 3
Alternate Reading (required): Programming from the Ground Up (Bartlett) 1, 2, 3, 4, 9, 10, B, E, F

Reading (recommended, for reference only): 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/16 - 4/22

Reading (recommended): Computer Systems (Bryant & O'Hallaron) 7

Reading (recommended):  Programming from the Ground Up (Bartlett) 5, 6, 7, 8, 11, 12, 13, C

Reading (recommended, for reference only): IA32 Intel Architecture Software Developer's Manual: Volume 2: Instruction Set Reference

Reading (recommended, for reference only): 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/23 - 4/29

Reading (required): Kuperman et al. "Detection and Prevention of Stack Buffer Overflow Attacks." Communications of the ACM, Volume 48, Number 11. November 2005 (distributed in precepts)

Lecture 21: (Monday) Computer Security

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

Lecture 22: (Wednesday) Hacking Machine Language

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

(Sunday) Buffer Overrun Assignment Due


Week 13: 4/30 - 5/6

Reading (required): Machine Learning (Mitchell) 6.9, 6.10 (available through Blackboard E-Reserves)

Reading (required): Goodman et al. "Stopping Spam." Scientific American. April 2005 (available through Blackboard E-Reserves)

Lecture 23: (Monday) How to Build a Spam Filter

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/7 - 5/13

(Monday - Sunday) Reading Period


Week 15: 5/14 - 5/20

(Monday) Reading Period

(Tuesday) Dean's Date

(Tuesday) Spam Filter Assignment Due

(Wednesday - Sunday) Final Exam Period

(Friday) Exam Prep Session (See also Exams and Answers from Previous Semesters)


Week 16: 5/21 - 5/27

(Monday - Saturday) Final Exam Period

(Tuesday) Final Examination, 1:30 PM, Computer Science Building 104 (This Semester's Exam, Answers for This Semester's Exam)


All lecture notes are copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007 by David August, Vivek Pai, Jennifer Rexford, Kai Li, Andrew W. Appel, Thomas Funkhouser, David R. Hanson, Larry Peterson, and/or Randolph Wang. All precept handouts are copyright 2001, 2002, 2003, 2004, 2005, 2006, 2007 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.