15110: Principles of Computing - Spring 2013

SCHEDULE

The schedule is subject to minor changes. Readings are from the textbook Explorations in Computing (EC) and Blown to Bits (BB) . Additional readings will be assigned as necessary.

WEEK DATES TOPICS/READINGS HOMEWORKS/EXAMS
Week 1 1/14-1/18 A Brief History of Computation
from Babbage to the World Wide Web
Course Overview
History of Computing (Part 1)
Article Computational Thinking by Wing (optional).
History of Computing (Part 2)
History of Computing (Part 3)
EC Chapter 1, BB Chapter 1
Programming Assignment 1 , due Tue Jan 22 at 11:59 pm
Problem Set 1 due Fri Jan 25 in class
Lab 1
Week 2 1/21-1/25* An Introduction to Programming using Ruby
variables, types, statements, functions
Basic data types, expressions, functions   Ruby code from class
For loops   Ruby code from class (1)   Ruby code from class (2)
EC Chapter 2, BB Chapter 2 pages 19-42.
Programming Assignment 2 , due Tue Jan 29 at 11:59 pm
Problem Set 2 due Fri Feb 1 in class
Lab 2
Week 3 1/28-2/1 Algorithms
loops, conditionals, algorithm examples,
Algorithmic Thinking   Annotated Notes 2:30/3:30
Implementation of algorithms   Annotated Notes 2:30   3:30
Algorithms ctd..   Annotated Notes 2:30   3:30
week 3 code
EC Chapter 3
Programming Assignment 3 , due Tue Feb 5 at 11:59 pm
Problem Set 3 due Fri Feb 8 in class
Lab 3
Optional exercises (recommended)
Week 4 2/4-2/8 Computation using Iteration
using arrays, linear search, selection sort, order of complexity
Introduction to search   Annotated Notes 2:30   3:30
Sorting things   Annotated Notes 2:30   3:30
week 4 code
Scalibility and Big O
EC Chapter 4
Programming Assignment 4 , due Tue Feb 12 at 11:59 pm
Problem Set 4 due Fri Feb 15 in class
Lab 4
Week 5 2/11-2/15 Recursive Thinking
binary search, merge sort, fractals, and other recursive algorithms
Recursion: Basics
Binary Search
Merge Sort
EC Chapter 5
No Programming Assignment going out this week
Problem Set 5 due Fri Feb 22 in class
Lab 5
Week 6 2/18-2/22 Data Organization
lists, stacks, queues, hash tables, trees and graphs
Introduction to Data Structures   Annotated Notes 2:30   3:30
Hash Tables
EC Chapter 6
Written Exam 1 (Wed Feb 20)
Sample Exam 1 (Fall 2012)
Sample Answers
Extra Exercises
Programming Assignment 5 due Tue Feb 26 11:59 pm
Online Assignment due Wed Feb 27 2:30 pm
Corrections for the online mdule
Problem Set 6 due Fri Mar 1 in class
Lab 6
Week 7 2/25-3/1 Data Organization continued
Trees and Graphs
Data Representation
Binary Representation Review and Compression
integers, text, images, sound and compression   Annotated notes   2:30   3:30
EC Chapter 7, BB Chapter 3
Lab Exam 1
Sample Lab Exam (Fall 2012)
Sample Answers (Fall 2012)
Programming Assignment 6 due Thursday Mar 7 11:59 pm
Problem Set 7 due Wednesday March 20 in class
Week 8 3/4-3/8** Computer Organization
CPU layers as abstractions, instructions as data and data as instructions
Boolean Logic   Annotated notes   2:30   3:30
Circuits, Adders and CPU   Annotated notes   2:30   3:30
EC Chapter 8
Programming Assignment 7 due Thursday Mar 28 11:59 pm
No new problem set going out this week
Lab 7
Week 9 3/18-3/22 Randomness in Computation
shuffling, games with random numbers, cellular automata
Random Number Generators   Annotated notes   2:30   3:30
Games with Random Numbers
Cellular Automata
EC Chapter 9
No new programming assignment going out this week
Problem Set 8 due Friday March 29 in class
Lab 8
Week 10 3/25-3/29 Concurrency
sorting networks, pipelining, and mulitasking
Multiprocessing & Deadlock (by Jim Morris)
Review and Pipelining
BB Chapter 4, pages 109-137
Written Exam 2 (Wed March 27)
Sample Exam 2 (Spring 2012)
Sample Answers
Programming Assignment 8 due Tuesday April 2 11:59 pm
Problem Set 9 due Friday April 5 in class
Lab 9
Week 11 4/1-4/5 The Internet Security
Design of the Internet   Annotated notes   2:30   3:30
Packets and Protocols   Annotated notes   2:30   3:30
Security

BB Chapter 5 and Appendix A
Programming Assignment 9 due Tuesday April 9 11:59 pm
Problem Set 10 due Friday April 12 in class
Lab 10
Week 12 4/8-4/12 Simulations
graphics in Ruby, N-body simulation
Simulation: Basics, Example
Continuous-time Simulations
EC Chapter 11
Programming Assignment 10 due Wednesday April 17 11:59 pm
Problem Set 11 due Mon April 22 in class
Lab 11
Weeks 13
and Week 14
4/15-4/26*** Artificial Intelligence
ELIZA and the Turing Test, games (search space and heuristics), Watson and machine learning
EC Chapter 10
Intractability
AI: Games and Search Strategies
AI: Natural Language Processing
AI: Watson and Machine Learning
The lecture slides for Intractability is grouped with Week 15 material EC Chapter 12
Written Exam 3 (Wed April 24)
Sample Exam 3 (Fall 2012)
Programming Assignment 11 due date Friday May 3
Problem Set 12 not for credit
No lab on Thursday April 18
Lab 12 (Thursday April 25)
Week 15 4/29-5/3 Computability: The Limits of Computation
Intractability, Map coloring and the traveling salesperson, P vs. NP, The halting problem Limits of Computing: Intractability
Limits of Computing: P versus NP
Limits of Computing: Uncomputable Functions
Summary
EC Chapter 12
Lab Exam 2
Sample Lab Exam 2 (Fall 2012)
Sample Answers (Fall 2012)
No assignments going out. Last week of classes.
Optional OLI module available on Computability

*No classes 1/21 after 12:30PM (Martin Luther King Day events)
**No classes 3/8-3/15 (Midterm Break and Spring Break)
***No classes 4/18-4/19 (Spring Carnival)