CS 106B: Programming Abstractions (C++)
Spring 2015

3-30

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

4-01

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

4-03

streams; Grid ( preview)

Homework 1 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

4-06

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
• vectorexample.cpp

4-08

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

4-10

sets, lexicons, and maps ( preview)

Homework 2 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
• anagrams.cpp
• maps.cpp
• sets.cpp

4-13

recursion ( preview)

read Ch. 7

Wikipedia: recursion

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

• 07-recursion.pdf
• 07-recursion.ppt
• all-code-lecture07.zip
• recursion.cpp

4-15

recursive data; fractals ( preview)

read Ch. 7; 8.4

Wikipedia: fractal

Stanford C++ lib: filelib.h

Videos: Julie on recursion, fractals

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

4-17

recursive searching and sorting ( preview);
algorithm analysis and Big-Oh notation ( preview)

Homework 3 assigned

read 7.5, 10.1, 10.2

Wikipedia: binary search, selection sort, merge sort, Big-Oh

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

• 09-fractals-search.pdf
• 09-fractals-search.ppt
• all-code-lecture09.zip
• fractals.cpp
• searching.cpp

4-20

exhaustive search; backtracking ( preview)

read 8.2 - 8.3; Ch. 9

Wikipedia: backtracking

• 10-backtracking.pdf
• 10-backtracking.ppt
• all-code-lecture10.zip
• diceroll.cpp
• printbinary.cpp

4-22

recursive backtracking ( preview)

read Ch. 9

Videos: Julie 1, Julie 2

• 11-backtracking2.pdf
• 11-backtracking2.ppt
• all-code-lecture11.zip
• diceroll.cpp
• permute.cpp

4-24

classes and objects ( preview 1, ( preview 2)

read Ch. 9; Ch. 6

Homework 4 assigned

Wikipedia: operator overloading

• 12-classes.pdf
• 12-classes.ppt
• all-code-lecture12.zip
• Date.cpp
• Date.h
• dateclient.cpp
• eightqueens.cpp

4-27

arrays; implementing a collection class ( preview)

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

• 13-arrays-arraylist.pdf
• 13-arrays-arraylist.ppt
• all-code-lecture13.zip
• ArrayList.cpp
• ArrayList.h
• arraylistclient.cpp

4-29

pointers and linked nodes ( preview)

read 11.2, 11.4; 12.1 - 12.3

Wikipedia: pointer

• 14-pointers-linked-nodes.pdf
• 14-pointers-linked-nodes.ppt
• all-code-lecture14.zip
• ListNode.h
• listnodeclient.cpp

5-01

linked lists ( preview)

read 12.2 - 12.3; 14.3

Wikipedia: linked list

• 15-linked-lists.pdf
• 15-linked-lists.ppt
• all-code-lecture15.zip
• LinkedList.cpp
• LinkedList.h
• linkedlistclient.cpp

5-04

more linked lists; priority queues ( preview)

Homework 5 assigned

read 16.5

Wikipedia: priority queue, heap

Stanford C++ lib: PriorityQueue

• #comments.txt#
• 16-priorityqueue-heap.pdf
• 16-priorityqueue-heap.ppt
• all-code-lecture16.zip
• LinkedList.cpp
• LinkedList.h

5-06

sorting

MIDTERM EXAM is Thu 5-07 at 7-9pm!

read Ch. 10

Wikipedia: selection, insertion, merge, quick

• 17-sorting.pdf
• 17-sorting.ppt
• all-code-lecture17.zip
• sorting.cpp

5-08

binary trees ( preview)

read 16.1

Wikipedia: binary tree

Videos: Stuart (Java)

• 18-binary-trees.pdf
• 18-binary-trees.ppt
• all-code-lecture18.zip
• BinaryTree.cpp
• BinaryTree.h
• treeclient.cpp

5-11

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

read 16.2

Wikipedia: BST

Videos: Julie

• 19-binary-search-tree.pdf
• 19-binary-search-tree.ppt
• all-code-lecture19.zip
• treeclient.cpp
• TreeSet.cpp
• TreeSet.h

5-13

balanced trees ( preview); Huffman encoding

Homework 6 assigned

read 16.3 - 16.4

Wikipedia: AVL tree, compression, Huffman

• 20-advanced-trees-huffman.pdf
• 20-advanced-trees-huffman.ppt

5-15

graphs ( preview)

read 18.1

Wikipedia: graph

Stanford C++ lib: BasicGraph

• 21-graphs.pdf
• 21-graphs.ppt
• all-code-lecture21.zip
• graph-twitter.cpp

5-18

graph path searching:
DFS, BFS, Dijkstra's algorithm, A* ( preview)

read 18.4 - 18.6

Wikipedia: DFS, BFS, Dijkstra's algorithm, A*

Animations: DFS, BFS

• #comments.txt#
• 22-graphs-path-searching.pdf
• 22-graphs-path-searching.ppt

5-20

graph paths: A* search

Wikipedia: A*

• 23-graphs-spanning-trees.pdf
• 23-graphs-spanning-trees.ppt

5-22

spanning trees; Kruskal's algorithm;
graph implementation ( preview 1) ( preview 2)

Wikipedia: Kruskal's algorithm, MST

Homework 7 assigned

read 18.2 - 18.3, 18.5

Wikipedia: adjacency list, matrix

• 24-graphs-implementation.pdf
• 24-graphs-implementation.ppt

5-25

NO CLASS
Memorial Day holiday

5-27

hash tables ( preview)

read 15.1-15.2

Wikipedia: hashing

• 25-hashing.pdf
• 25-hashing.ppt

5-29

inheritance and polymorphism ( preview)

read: Ch. 19

Wikipedia: inheritance, polymorphism

• 26-inheritance-polymorphism.pdf
• 26-inheritance-polymorphism.ppt
• all-code-lecture26.zip
• Employee.cpp
• Employee.h
• employeemain.cpp
• Lawyer.cpp
• Lawyer.h
• Programmer.cpp
• Programmer.h

6-01

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

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

Wikipedia: templates, STL

STL reference

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

6-03

course wrap-up; discuss final exam

6-05

NO CLASS

FINAL EXAM is Sat 6-06 at 8:30 - 11:30am!