Course Notes, Practice Problems, and Solutions

Cone of Learning
Explaining end-of-file I/O
Google's C++ Style Guide
Java Coding Style Conventions
342/343 bottom-line Style Guidelines

Linux/computing information
Basic linux - commands and about crashing
How to transfer files and compile under linux
Video showing how to transfer files and compile under linux (from CSS 342)
Expand the tabs to blanks in Visual Studio 2017
Using clang on linux to expand tabs to blanks
Prof Pisan's wiki: C++, OS, IDE, etc. info

Reviewing paramater passing, pointers, and dynamic memory
Pass by value vs. pass byreference
Pointers and memory diagram
When an object has dynamic memory
Valgrind Information (memory checker)
Valgrind of a correct program: Valgrind example
Valgrind error explanation and memory leak: How valgrind works

Trees and Heaps
Binary Search Tree information
Huffman Encoding examples . . . Huffman breakout solution
Drawing execution tree . . . Binary tree breakout solution
BinTree execution tree example
Insert one item into a heap
Remove one item from a heap . . . Heap breakout solution
Building a Heap in O(n) time
Complexity of building a heap in O(n) time

Graphs
Graph Intro and Depth-First Search Algorithm . . . DFS lecture whiteboard
Dijkstra's Alg . . . Dijkstra's Alg performed . . . lecture whiteboard
Another Dijkstra example (Uses C[v][w] for the graph edge cost)
Dijkstra breakout problem . . . Solution
Breadth-first Search Algorithm and uses
BFS lecture whiteboard
Depth/Breadth breakout Solution

AVL Trees, B-trees, Tries
AVL Trees
AVL Left Right diagram . . . AVL Right Left diagram
AVL insert and leftleft rotation code
Example AVL left-right rotation
Example AVL right-left rotation . . . AVL breakout solution
2-3 tree intro . . . 2-3 tree insert example
Why B-trees are useful
Trie example . . . 2-3 tree, trie breakout solution
Trying to understand Tries (external website)

Object-oriented Programming
(Minimal) UML needed in lab4
Object-oriented Design Principles (SOLID)
Quick lesson in Visio (Many students use draw.io .   lucidchart.com is reported to be good too.)
Inheritance and constructors/destructors
Polymorphism and Virtual functions
Design patterns   Gang of Four's original design patterns
You can find some papers on Bob Martin's Design Principles Page
Good design patterns website
From the " Good design patterns website:" Factory design pattern info
The Command design pattern
Designing - problem to code   Design example   Use case pseudocode
How Late Binding (polymorphism) is implemented . . . whiteboard
Multiple inheritance example
An object-oriented design joke

Hashing
Whiteboard notes: Hash Tables, Open Hashing
Whiteboard notes: Linear Probing ... Quadratic Probing
Whiteboard notes: Double Hashing ... Hashing Complexity
Perfect Hash Table for compiler keywords
Another Hash Table example for grades . . . Hash breakout solution

Formal Languages and Automata Theory
Language intro and Regular Expressions . . . Reg Expr breakout solution
Languages and Compilers
Demonstrating compiler phases on an assignment statement
Whiteboard:   Regular expressions . . . More . . . More
Other regular expression operators   (not responsible for)
Regular expression for the language: Odd number of a's, b's, Even c's
Saving the day with regular expressions
Finite Automata . . . Whiteboard examples
Context-free Grammars
Typical context-free grammar of a programming language
Whiteboard: CFG . . decl-list . . set . . expr . . expr parse tree
CF grammar breakout solution

Alan Turing and Turing Machines
Alan Turing, the man -- history and accomplishments     Summary
UK apology to Turing
Turing is the face of new 50 pound banknote
What is a Turing Machine?
Turing Machine example (to add two numbers)
What are Turing Machines good for?
How Dr. Seuss would prove the Halting Problem undecidable?

Exam Information
Midterm exam information
The coding problem #7 came from students having a different lab1. For you, the exam question would be on the IntSet class, for example:   bool result = s2.isSubset(s1);     // true if s1 is a subset of s2
Don't study from the exam. Study, then take it (in two hours).
Old midterm exam   ............   solution

Final exam information
Extra Practice Problems (at home) and Solutions

Final Practice problems     .......................   solutions
CF Grammar problems     ..............................   solutions
More CF Grammar problems     .............................. solution
Regular Expression problems     ..................   solutions

Hash Table problems     ...................   solutions

AVL Tree problems     ................... solution to #1 ..... solution to #2
2-3 Tree problems     .................... solution
Trie problem     .................... solution

Dijkstra shortest distance problem   ............... solution
Another Dijkstra problem   .................. solution
Another Dijkstra problem with solution (Uses C[v][w] for the graph edge cost)

Depth-first, breadth-first practice (start at one)  ....... DFS, BFS ordering (and DFS tree)
Graph problems     .......................... solutions

Heap problems     .......................... solutions
Huffman Encoding problems     .................. solution
Count the nodes at level n in a binary tree (root is at level zero). Sample main:
        BinTree T;
        T.buildTree(...);
        cout << T.numNodesAtLevel(4) << endl;   .........   solutions