15110 Principles of Computing

Principles of Computing

FALL 2012



Course Schedule & Readings

Exam Information

Written Exam 1: Monday, October 1
Practice Exam (Fall 2011) Sample Answers (Fall 2011)
Exam 1A (Fall 2012)
Exam 1B (Fall 2012)
Sample Answers Version A (Fall 2012)
Sample Answers Version B (Fall 2012)

Lab Exam 1: Thursday, October 18
Practice Exam (Spring 2012) Sample Answers (Spring 2012)
Exam (Fall 2012)

Written Exam 2: Monday, October 29
Practice Exam (Spring 2012) Sample Answers (Spring 2012)
Sample Answers Version A (Fall 2012)
Sample Answers Version B (Fall 2012)

Written Exam 3: Wednesday, November 28
Practice Exam (Spring 2012) Sample Answers (Spring 2012)
Sample Answers Version A (Fall 2012)
Sample Answers Version B (Fall 2012)

Lab Exam 2: Thursday, December 6
Practice Exam (Spring 2012) Sample Answers (Spring 2012)
Version A (Spring 2012) Version B (Spring 2012) Version C (Spring 2012) Version D (Spring 2012)
Sample Answers (Fall 2012)

Final Exam: Friday, December 14, 1:00 pm to 4:00 pm. Locations: DH 2210-2302-2315.
Sample Answers (Fall 2012)

You must take all exams at the times they are given. NO MAKEUPS FOR EXAMS will be allowed except for acceptable documented circumstances (e.g. major illness, death in immediate family, university-sanctioned event with verification from advisor/coach, etc.).

Course Schedule & Readings (subject to change)

Readings are from the textbooks Explorations in Computing (EC) and Blown to Bits (BB). Additional readings will be assigned as necessary.

8/27-8/31 A Brief History of Computation
from Babbage to the World Wide Web
EC Ch. 1, BB Ch. 1
9/3-9/7* An Introduction to Programming using Ruby
variables, types, statements, functions
EC Ch. 2, BB Ch. 2 pp. 19-42
9/10-9/14 Algorithms
loops, conditionals, GCD, Sieve of Eratosthenes
EC Ch. 3
9/17-9/21 Computation using Iteration
using arrays, linear search, selection sort, order of complexity
EC Ch. 4
9/24-9/28 Recursive Thinking
binary search, merge sort, fractals, and other recursive algorithms
EC Ch. 5
10/1-10/5 Data Organization
lists, stacks, queues, hash tables, trees and graphs
EC Ch. 6
Optional: Touretzky 8.1, 8.2, 8.4, 8.6, 8.8, 8.9
10/8-10/12 Data Representation
integers, text, images, sound and compression
EC Ch. 7, BB Ch. 3
10/15-10/19** Computer Organization
Boolean logic, CPU layers as abstractions, instructions as data and data as instructions
EC Ch. 8
10/22-10/26 Randomness in Computation
random number generators, shuffling, games with random numbers, cellular automata
EC Ch. 9
10/29-11/2 Concurrency
sorting networks, pipelining, and mulitasking
BB Ch. 4 pp. 109-137
11/5-11/9 The Internet
design of the Internet, network layers as abstractions, security/RSA
BB Ch. 5 and Appendix A
11/12-11/16 Simulations
graphics in Ruby, N-body simulation
EC Ch. 11
11/19-11/30*** Artificial Intelligence
ELIZA and the Turing Test, games (search space and heuristics), Watson and machine learning
EC Ch. 10
EC Ch. 12/3-12/7 Computability: The Limits of Computation
Map coloring and the traveling salesperson, P vs. NP, The halting problem
EC Ch. 12

*No classes 9/3 (Labor Day)
**No classes 10/19 (Mid-semester Break)
***No classes 11/21-11/24 (Thanksgiving Holiday)