DRAFT TENTATIVE Schedule for Fall 2013:

Last updated: Nov 26
01 Sep 3 Intro., Anatomy of a Computer Sep 5 Data Structures
02 Sep 10 Investigation: Data Structures in Matlab and C Sep 12 Sorting, Searching, etc. HW 1 due.
03 Sep 17 Investigation: Parallelism Quiz 1 Sep 19 Open-MP, synchronization, etc.
04 Sep 24 Open-MP, synchronization, etc. HW 2 due. Sep 26 Investigation: Parallel Programming
05 Oct 1 MPI Programming Quiz 2 Oct 3 GPU Programming
06 Oct 8 CPUs, Compilers, Interpreters, and Assembly-level Operations HW 3 due. Oct 10 Assembly-level Control Quiz 3
07 Oct 15 Assembly-level Functions Oct 17 Assembly-level Data and Investigation
08 Oct 22 Presentations, Quiz 4 Oct 24 Pipelining HW 4 due
09 Oct 29 Code Optimization and Complexity Oct 31 Investigation (code optimization)
10 Nov 5 Memory Management and Virtual Memory Quiz 5 Nov 7 Investigation: Memory Effects
11 Nov 12 Input/Output and Libraries and Linking. HW 5 due Nov 14 Presentations, Quiz 6
12 Nov 19 Presentations Nov 21 Presentations
13 Nov 26 Operating Systems HW 6 due Nov 28 Happy Thanksgiving!
14 Dec 3 Machine Arithmetic Dec 5 Presentations + The Internet
15 Dec 10 Presentations, Quiz 7 Dec 12 Presentations
Dec 17 8-10am: Final Exam.
HW 7 = presentation

Resources:

  • 2011 quizzes and final exam
  • Introduction lecture notes
  • B&H Introductory lecture notes

  • Anatomy of a Computer lecture notes

  • Data Structures
  • Basic Data Structures
  • lecture notes
  • Arrays, Strings, Cell Arrays
  • Pointers and stacks and queues and linked lists and binary trees and hash tables. (See CLR Chapter 3 or Samet)
  • heaps and quadtrees (See CLR Chapter 5 or Samet)
  • Data structures in C lecture notes from Robert Sedgewick (These notes are not covered in lecture but provide additional examples.)
  • Investigation: Data Structures in Matlab
  • Sorting, Searching, Inserting, Deleting, etc.
  • Sorting and Searching: CLR Chapter 2
  • Sorting and searching in an array
  • Sorting and searching in a binary tree lecture notes from Robert Sedgewick (On p.17, the right subtree has larger values, not smaller.) Stop at p.29.
  • Sorting and searching in a linked list lecture notes pp. 13-16, from Robert Sedgewick

  • Parallel Programming
  • Investigation: Parallelism
  • Victorian parallel processing
  • B&H Parallel Computing (supplementary material)
  • B&H Threads and Synchronization (supplementary material)
  • B&H Synchronization (supplementary material)
  • MPI, Open-MP, etc.
  • Introductory lecture notes
  • lecture notes from Chapter 5 of Peter S. Pacheco's An Introduction to Parallel Programming: Programming in OpenMP.
  • lecture notes from Chapter 3 of Peter S. Pacheco's An Introduction to Parallel Programming: Programming in MPI. pp. 1-76, 93-99.
  • Useful summary of OpenMP syntax
  • zip file of template codes from Chapter 5 of Pacheco's book. They are also available from here
  • B&H Chapter 12
  • Helpful solved exercises: TBD
  • Investigation: Parallel Programming
  • matvec.c
  • timing.c
  • GPU Programming My lecture notes
  • lecture notes by Felipe Cruz

  • Assembly-level Programming
  • Very useful 1-page summary of assembly language instructions
  • Assembly-level Operations and Control
  • B&H Chapter 3, Sections 3.2--3.6 Helpful solved exercises: Practice Problems 3.1 -- 3.9, 3.16 -- 3.18, 3.20 -- 3.24, 3.27.
  • B&H Machine Programming: Basics lecture notes pp. 12-21, 24-47.
  • B&H Machine Programming: Arithmetic and Control lecture notes pp. 1-12, 17-31, 36-38.
  • Investigation: Assembly Language Programming:
  • Part 1: Floating point commands , an example main program and function mult2 .
  • Part 2: Adding two vectors or two matrices.
  • Useful reference: Floating point notes to accompany your textbook.
  • Assembly-level Functions
  • B&H Chapter 3, Section 3.7 Helpful solved exercises: Practice Problems 3.30 -- 3.34.
  • B&H Machine Programming: Procedures lecture notes pp. 20-40, 50-53. Later: pp. 41-49
  • Assembly-level Data
  • B&H Chapter 3, Sections 3.8--3.10 Helpful solved exercises: Practice Problems 3.36, 3.39, 3.42.
  • B&H Machine Programming: Data lecture notes pp. 1-7, 14-21, matrices Matlab style, 38-42. See pp. 3-4 for register usage.

  • Computer Memory
  • Memory Management and Virtual Memory
  • B&H Chapter 6 Helpful solved exercises: Practice Problems 6.2 -- 6.5, 6.8, 6.9, 6.11, 6.18 -- 6.22.
  • B&H Memory Hierarchy lecture notes pp. 18-41 (but all of it is interesting).
  • B&H Cache Memories lecture notes
  • B&H Virtual Memory: Concepts lecture notes pp. 1-24, 28-29, 36.
  • Investigation: Memory Effects
  • B&H p.622, Figure 6.42
  • memmountain.zip

  • Hardware and Software Support for Programmers
  • CPUs, Compilers, Interpreters, and Linkers
  • B&H Pipelining lecture notes 1 (all pages except 17, 18. See p. 364 of textbook for help with slide 14.) and
  • B&H Pipelining lecture notes 2 pp. 7-11.
  • Operation of B&H pipeline
  • B&H Chapter 4, Section 4.4 Pipelining (Also, p. 364.) Helpful solved exercises: Practice Problems 4.26, 4.27.
  • B&H Chapter 7 Linking
  • Helpful solved exercises: Practice Problems 7.1, 7.3 -- 7.5.
  • Lecture notes on compiling/interpreting
  • B&H Linking lecture notes (pp. 1-21, 25-37)
  • Input/Output and Libraries
  • B&H Chapter 10
  • Helpful solved exercises: Practice Problems 10.2, 10.3.
  • B&H Input/Output and Library lecture notes (pp. 1-11, 23-29, 38-40, 43-44)
  • Some Useful Libraries:
  • BLAS
  • LAPACK
  • SCALApack
  • FLAME
  • ATLAS
  • FFTW
  • Code Optimization and Complexity: Flops, Access, Power Consumption, and Green Computing
  • B&H Chapter 5 Helpful solved exercises: Practice Problems 5.1 -- 5.8.
  • B&H Program Optimization lecture notes
  • A list of supplementary exercises on assembly language programming, code optimization, and pipelining. You are welcome to work through them on your own.
  • Green computing by Patrick Kurp, Communications of the ACM Volume 51 Issue 10, October 2008 doi: 10.1145/1400181.1400186. (Emphasis on recycling and efficient data centers)
  • Advanced Architectures and Execution Models to Support Green Computing by R. Murphy, T. Sterling, and C. Dekate, Computing in Science & Engineering Nov.-Dec. 2010 Volume: 12 Issue:6 doi: 10.1109/MCSE.2010.124. (Emphasis on high performance computing)

  • Operating Systems
  • lecture notes based on ...
  • ... The role of an operating system
  • Microsoft Variants
  • Apple Variants
  • Unix / Linux Variants lecture notes from Robert Sedgewick (These notes are supplementary.)

  • The Internet
  • B&H Chapter 11
  • Helpful solved exercises: TBD
  • B&H The Internet lecture notes
  • B&H Network Programming lecture notes pp. 1-15.
  • B&H Web Services lecture notes

  • Machine Arithmetic
  • SCCS Chapter 1, Section 1.3
  • B&H Chapter 2
  • Also, there is a terrific book by Michael Overton: Numerical Computing with IEEE Floating Point Arithmetic, SIAM 2001.
  • lecture notes (updated 12/20/13)



    • References:

  • B&H = Computer Systems: A Programmer's Perspective by Randal E. Bryant and David R. O'Hallaron.
  • CLR = An Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, and R. L. Rivest.
  • Samet = Foundations of Multidimensional and Metric Data Structures by Hanan Samet.
  • SCCS = Scientific Computing with Case Studies by Dianne P. O'Leary.
  • A good reference for learning C: "C For Dummies," 2nd Edition by Dan Gookin