15110 Principles of Computing

15110
Principles of Computing

FALL 2012

SCHEDULE & EXAMS

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.

DATES TOPICS READINGS

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)