CS 106B: Programming Abstractions in C++
Autumn 2014

09-22

course overview; intro to C++ ( preview)

read Ch. 1-2;
C++ handout

• 00-introduction.pdf
• 00-introduction.ppt
• 01-intro-to-cpp.pdf
• 01-intro-to-cpp.ppt
• all-code-lecture01.zip
• firstprogram.cpp

09-24

C++ functions; strings ( preview)

read Ch. 2-3

C++ docs: cmath, string, cctype
Stanford C++ lib: strlib.h

• 02-function-string.pdf
• 02-function-string.ppt
• all-code-lecture02.zip
• functions.cpp

09-26

streams; Grid ( preview)

HW1 assigned

read Ch. 3-4; 5.1

C++ docs: ifstream, iomanip, sstream
Stanford C++ lib: filelib.h, simpio.h, Grid

• 03-stream-grid.pdf
• 03-stream-grid.ppt
• all-code-lecture03.zip
• knight.cpp
• readfile.cpp

09-29

Vector and LinkedList; abstract data types (ADTs) ( preview)

read 5.1 - 5.2

Wikipedia: data structure, collection, ADT

• 04-vector-adt.pdf
• 04-vector-adt.ppt
• all-code-lecture04.zip
• knight.cpp
• vectorexample.cpp

10-01

stacks and queues ( preview)

read 5.2 - 5.3

Wikipedia: stack, queue

Stanford C++ lib: Stack, Queue

• 05-stack-queue.pdf
• 05-stack-queue.ppt
• all-code-lecture05.zip
• queues.cpp
• stacks.cpp

10-03

sets, lexicons, and maps ( preview)

HW2 assigned

read 5.4 - 5.6

Wikipedia: set, map

Stanford C++ lib: Set, Lexicon, Map

• 06-set-lexicon-map.pdf
• 06-set-lexicon-map.ppt
• all-code-lecture06.zip
• maps.cpp
• sets.cpp

10-06

algorithm analysis and Big-Oh notation ( preview)

read 10.2

Wikipedia: Big-Oh

• 07-complexity.pdf
• 07-complexity.ppt
• all-code-lecture07.zip
• anagrams.cpp
• range.cpp

10-08

*** THIS LECTURE HELD IN ROOM 420-040 ***

recursion ( preview)

read Ch. 7

Wikipedia: recursion

Videos: Julie (C++), Stuart #1, #2, #3 (Java)

• 08-recursion.pdf
• 08-recursion.ppt
• all-code-lecture08.zip
• recursion.cpp

10-10

recursive data; fractals ( preview)

read Ch. 7; 8.4

Wikipedia: fractal

Stanford C++ lib: filelib.h

Videos: Julie on recursion, fractals

• 09-recursion2-fractals.pdf
• 09-recursion2-fractals.ppt
• all-code-lecture09.zip
• recursion.cpp
• recursion2.cpp

10-13

recursive searching and sorting ( preview)

HW3 assigned

read 7.5, 10.1

Wikipedia: binary search, selection sort, merge sort

Videos: Julie on binary search, sorting; Marty on sorting

• 10-search-sort.pdf
• 10-search-sort.ppt
• all-code-lecture10.zip
• fractals.cpp
• searching.cpp

10-15

exhaustive search;
recursive backtracking ( preview)

read 8.2 - 8.3; Ch. 9

Wikipedia: backtracking

• 11-backtracking.pdf
• 11-backtracking.ppt
• all-code-lecture11.zip
• diceroll.cpp
• printbinary.cpp

10-17

recursive backtracking ( preview)

read Ch. 9

Videos: Julie 1, Julie 2

• 12-backtracking2.pdf
• 12-backtracking2.ppt
• all-code-lecture12.zip
• permute.cpp

10-20

recursive backtracking;
classes and objects ( preview)

read Ch. 9; Ch. 6

• 13-backtracking3-classes.pdf
• 13-backtracking3-classes.ppt
• all-code-lecture13.zip
• Date.cpp
• Date.h
• dateclient.cpp
• eightqueens.cpp

10-22

more classes and objects ( preview)

HW4 assigned

read Ch. 6

Wikipedia: operator overloading

• 14-classes2.pdf
• 14-classes2.ppt
• all-code-lecture14.zip
• Date.cpp
• Date.h
• dateclient.cpp

10-24

*** THIS LECTURE HELD IN ROOM 420-040 ***

arrays; implementing a collection class ( preview)

read 11.2 - 11.3, 12.1, 12.3, 14.1, 14.4

• 15-arrays-arraylist.pdf
• 15-arrays-arraylist.ppt
• all-code-lecture15.zip
• ArrayList.cpp
• ArrayList.h
• arraylistclient.cpp

10-27

pointers and linked nodes ( preview)

read 11.2, 11.4; 12.1 - 12.3

Wikipedia: pointer

• 16-pointers-linked-nodes.pdf
• 16-pointers-linked-nodes.ppt
• all-code-lecture16.zip
• ArrayList.cpp
• ArrayList.h
• linkedlistclient.cpp
• ListNode.h

10-29

linked lists ( preview)

read 12.2 - 12.3; 14.3

Wikipedia: linked list

• 17-linked-lists.pdf
• 17-linked-lists.ppt
• all-code-lecture17.zip
• LinkedList.cpp
• LinkedList.h
• linkedlistclient.cpp

10-31

more linked lists;
priority queues ( preview)

HW5 assigned

read 16.5

Wikipedia: priority queue, heap

Stanford C++ lib: PriorityQueue

• 18-priorityqueue-heap.pdf
• 18-priorityqueue-heap.ppt
• all-code-lecture18.zip
• LinkedList.cpp
• LinkedList.h
• linkedlistclient.cpp

11-03

binary trees ( preview)
(guest lecturer: TA Elmer Le)

read 16.1

Wikipedia: binary tree

Videos: Stuart (Java)

• 19-binary-trees-elmer.pdf
• 19-binary-trees-elmer.ppt
• all-code-lecture19.zip
• BinaryTree.cpp
• BinaryTree.h

11-05

MIDTERM EXAM is Wed Nov 5 at 7-9pm!

LECTURE CANCELED

(section this week is also canceled)

11-07

binary search trees (BSTs);
tree set implementation ( preview)

read 16.2

Wikipedia: BST

Videos: Julie

• 20-binary-search-tree.pdf
• 20-binary-search-tree.ppt
• all-code-lecture20.zip
• treeclient.cpp
• TreeSet.cpp
• TreeSet.h

11-10

tree map implementation;
balanced trees ( preview)

HW6 assigned

read 16.3 - 16.4

Wikipedia: AVL tree

• 21-advanced-trees-huffman.pdf
• 21-advanced-trees-huffman.ppt
• all-code-lecture21.zip
• treeclient.cpp
• TreeSet.cpp
• TreeSet.h

11-12

graphs ( preview)

read 18.1, 18.4

Wikipedia: graph, dfs, bfs

Animations: dfs, bfs

• 22-graphs1.pdf
• 22-graphs1.ppt

11-14

graph implementation ( preview)

read 18.2 - 18.3, 18.5

Wikipedia: adjacency list, matrix

• 23-graphs2-implementation.pdf
• 23-graphs2-implementation.ppt
• all-code-lecture23.zip
• graphmain.cpp

11-17

shortest paths: Dijkstra's algorithm, A* ( preview)

read 18.6

Wikipedia: Dijkstra's algorithm, A*

• 24-graphs3-dijkstra-astar.pdf
• 24-graphs3-dijkstra-astar.ppt

11-19

spanning trees; Kruskal's algorithm ( preview)

HW7 assigned

Wikipedia: Kruskal's algorithm, MST

• 25-graphs4-kruskal.pdf
• 25-graphs4-kruskal.ppt

11-21

hash tables ( preview)

read 15.1-15.2

Wikipedia: hashing

• 26-hashing.pdf
• 26-hashing.ppt

11-24

NO CLASS
Thanksgiving holiday

11-26

NO CLASS
Thanksgiving holiday

11-28

NO CLASS
Thanksgiving holiday

12-01

templates; standard template library (STL);
C++ without Stanford libraries

read Ch. 14.1 - 14.2; Ch. 20 (optional)

Wikipedia: templates, STL

STL reference

• 27-templates-stl.pdf
• 27-templates-stl.ppt

12-03

*** THIS LECTURE HELD IN ROOM 420-040 ***

inheritance and polymorphism ( preview)

read: Ch. 19

Wikipedia: inheritance, polymorphism

• 28-inheritance-polymorphism.pdf
• 28-inheritance-polymorphism.ppt

12-05

course wrap-up; discuss final exam

• 29-whats-next.pdf
• 29-whats-next.ppt

12-10

Final Exam, Wed 12-10, 12:15 - 3:15pm