(Assignments are available from the assignments page.)

Handouts for Everyone!

• C++ pointers versus Java references
• "cheat sheet" to help write proofs
• worked induction proof examples (When you write an induction proof, it should have the structure of those proof examples.)

man rand

Lab Handouts

Section 201 (Hu, MWF) Handouts

• April-8-10: Lecture Slides: Parallel Prefix, Pack, and Sorting
• March-27-April-8: Lecture Slides: Analyzing Parallel Programs, Map-Reduce
• March-23-27: Lecture Slides: Parallelism Intro
  Important Notes! Because the parallelism section of this course is not covered in your textbooks, we are providing these
  • Lecture Notes on Parallelism and Concurrency
for you. We'll cover through page 32.

Here are the code examples from the lectures. You'll have to fix count_matches.cpp as shown on the slides. count_matches.cpp Timer.hpp Timer.cpp Makefile
(Note for Mac users: On Hassan's Mac, when he downloaded, it was renaming the files to be .cp and .hh instead. If this happens to you, either rename the files to what they were, or edit the Makefile to reflect the new file names.)

Fun, historical, completely optional background reading:

• The original paper on Moore's Law from 1965! This appeared in the magazine Electronics, Vol. 38, No. 8, April 19, 1965. It's more fun to read if you know that, for example, typical wafers today are 30cm (12in) instead of 1 inch diameter, although individual chips are not that much bigger than they used to be. A modern high-end processor will have a couple billion transistors per chip. The cartoon in the paper is also funny -- back in 1965, the idea that little handheld computers would be sold as a consumer product from a little booth was absurdly hilarious. Imagine what it'd be like for someone from then to see the Richmond Night Market now. And imagine what the world might be like in 50 more years!
• Extended abstract from Pat Gelsinger's ISSCC presentation. Through UBC's Libraries, if you are on a UBC machine, you can get a copy of the extended abstract for the presentation at the 2001 International Solid-State Circuits Conference. This is the origin of the power density slide mentioned in lecture, and it's a great description of the technology trends forcing the move toward parallelism.
• The original 1967 paper giving Amdahl's Law. Again, you need to be on a UBC machine (or other library or way to access IEEE and ACM's digital libraries) to get the full text. This was Amdahl's first paper, and he didn't even write the equation for his famous law.
• March-16-20: Lecture Slides: Hashing
• March-11-13: Lecture Slides: AVL Trees
• March-9-11: Lecture Slides: Dictionary ADT and Binary Search Trees
• March-2-6: Lecture Slides: Sorting
• 2015-February-11-27: Lecture Slides: Recursion and Iteration
  Code snippets: recurse.cpp, stacksmash.cpp, stacksmash2.cpp
  
• 2015-February-2-11: Lecture Slides: Heaps (with a bit on trees and on C++ reference parameters) (very tiny changes to parameter slides updated 2015-02-10)
• 2015-January-26-February-2: Lecture Slides: Analyzing Runtime
• 2015-January-19-23: Big-O Notation Lecture Slides
  recip.cpp, thrash.cpp, fib.cpp
  RECIP.DO, FIB.DO
  

  These are the programs I used for the Runtime Smackdown, in case you're curious. With the thrash.cpp program, if you have access to machines with both a modern processor and something Pentium 4 vintage or older, you can see what happens when you change the stride length to different values. I can't get the BASIC programs off of the Tandy 200 easily, since it only has built-in connections for a 300 baud modem, a cassette tape, and an RS-232 serial port. :-) However, I re-typed them for you.

• 2015-January-16: Motivation for Asymptotic Analysis Lecture Slides (Also has a few slides on linkers.)
• 2015-January-9: Crash Course on Pointers Lecture Slides
  leak.cc -- Note: Please be careful with this program, as it tries to use up all the memory on a machine. Don't run it on any machine that's shared (e.g., the departmental servers).
• 2015-January-7-14: ADTs, Stacks, and Queues Lecture Slides
• 2015-January-7: Crash Course on Arrays Lecture Slides
• 2015-January-5: Intro Lecture Slides
  bigfib.cpp
  

  Note: I typically provide source code as plain text files for Linux/Unix systems, and they will work fine on MacOS as well. If you have problems on a Windows system with the entire file appearing on one super-long line, take a look at this Wikipedia page for an explanation and some quick ways to get around this problem.

Section 202 (Khosravi, TTh) Handouts

Topic	Readings from Epp Sections (3rd ed/4th ed)	Readings from Koffman Sections	Useful Resources, Examples or Articles	Dated Posted
Introduction		Chapters P and 1	fib.cc	Jan 6
Crash course on arrays and pointers		Chapters P and 1	leak.cc	Jan 8
ADTs, Stacks, and Queues Lecture Slides		4.5-4.7, 5, 6.1-6.3, 6.5		Jan 13
Asymptotic Analysis	9.2, 9.3/11.2, 11.3	2.6		Jan 29
Priority Queues and Heaps		8.5	Parameter passing in C++ (ppt)	Feb 10
Recursion and Iteration Optional reading material: Iteration, Induction, and Recursion by Jeffrey Ullman	5.1, 5.2 7.1, 7.2, 4.2, 4.3, 4.5 /6.1, 6.2 7.1, 7.2, 5.2, 5.3, 5.5	Chapter 7	permute.cc endlesslyGreet.cc	Feb 26
Sorting	9.5 /11.5	10.1 - 10.4 and 10.7-10.10		Mar 3
Binary Search Trees	11.5/10.5	8.1-8.4		Mar 12
AVL Trees		11.1, 11.2		Mar 17
Hashing	7.3/9.4	9		Mar 24
Parallelism and Concurrency, part1 Parallelism and Concurrency, part2 Additional Notes on Parallelism and Concurrency			count_matches.zip	Apr 10

---

cs221@ugrad.cs.ubc.ca

Last Modified: Fri 27 Feb, 2015