Week | Date | Content |
---|---|---|
1 | Jan 28 |
Slides:
Course objectives; software to install; assignments;
quizzes; exams; grading; what is C++; Hello World program;
Pods and Peas program; identifier, variables, and
keywords; assignment statements; input and output;
#include and using namespace; formatting numbers; cin
input; basic data types; string type; type compatibilities
and conversions; arithmetic; operator shorthand; if
statement; while loops; named constants; Boolean
operators; precedence rules; enumeration types; nested
if statements; switch statement; increment and decrement
operators; for loops; break statement
Savitch slides: 01 02 03 Example programs: helloworld.cpp nestedloop.cpp Savitch_01-08.cpp Savitch_03-06.cpp Savitch_03-14.cpp |
2 | Feb 4 |
Slides:
Predefined functions; random numbers; type casting;
programmer-defined functions: declarations, definitions,
calls; void functions; top-down design; number translator
example; scope and local variables; block scope; global
constants and variables; overloading function names;
call-by-value; call-by-reference; procedural abstraction;
testing and debugging functions; assert macro;
Assignment #2
Savitch slides: 04 05 Top-down design example: translator1.cpp translator2.cpp translator3.cpp translator4.cpp translator5.cpp Pass by value example: swap.cpp Pass by reference example: exchange.cpp Assert example: assert.cpp |
3 | Feb 11 |
Slides:
Assignment #2 sample solution; streams; file I/O; stream
name vs. file name; formatting output; output manipulators;
passing streams to functions; character I/O; predefined
character functions; eof function; arrays; array initialization;
array function parameters; multidimensional arrays;
C strings; the standard string class; vectors;
Assignment #3: War and Peace
Savitch slides: 06 07 08 |
4 | Feb 18 |
Slides:
Assignment #3 sample solutions;
pointers; int vs. pointer to int;
declaring and assigning pointers; pointers are
addresses; address-of and dereferencing operators; new
and delete operators; pointer parameters; use typedef;
using pointers to pass-by-reference; pointers and arrays;
pointer arithmetic; dynamic arrays; 2-D dynamic array;
use typedefs; char* and char**; Assignment #4: Student Scores
Savitch slides: 09 Dynamic array examples: DynamicArray1.cpp DynamicArray2.cpp DynamicArray3.cpp |
5 | Feb 25 |
Slides:
Assignment #4 sample solution; structures;
structures are types; scope of member names; structure
variables; object-oriented programming (OOP); classes;
member functions; public and private members; constructors;
abstract data types (ADT); friend functions; operator
overloading; overload <<; overload >>;
Assignment #5 Roman Numerals
Savitch slides: 10 11 Example classes: Birthday1.cpp Birthday2.cpp Birthday3.zip |
6 | Mar 3 |
Slides:
Assignment #5 sample solution; static class members;
destructors; array of objects; vector of objects;
copy constructor; "extra" constructor and destructor calls;
how a vector grows; namespaces; search an array: linear
search and binary search; Assignment #6 Book Catalog
Savitch slides: 12 Example classes: Birthday4.zip Birthday5.zip BirthdayArray.zip BirthdayVector.zip BirthdayCopyCtor.zip BinarySearchIterative.cpp |
7 | Mar 10 |
Video recording
Slides: Assignment #6 sample solution; a "safe" array type; assignment operator; overload the subscript operator []; copy constructor; the "big three"; linked list insertion and deletion; queue; stack; Assignment #7 Savitch slides: 13 SafeArray example 1: (crashes) SafeArray1.h SafeArray2.cpp SafeArrayTests1.cpp SafeArray example 2 (operator =): SafeArray2.h SafeArray2.cpp SafeArrayTests2.cpp SafeArray example 3 (fix operator =): SafeArray3.h SafeArray3.cpp SafeArrayTests3.cpp SafeArray example 4 (another fix operator =): SafeArray4.h SafeArray4.cpp SafeArrayTests4.cpp SafeArray example 5 (overload []): SafeArray5.h SafeArray5.cpp SafeArrayTests5.cpp SafeArray example 6 (copy constructor): SafeArray6.h SafeArray6.cpp SafeArrayTests6.cpp |
8 | Mar 17 |
Video recording
Slides: Midterm; template function; template class "safe array" version 7; object-oriented programming; inheritance; subclasses; polymorphism; virtual destructors Savitch slides: 15 Template function example: TemplateExchange.cpp Template class example: Pair.h PairTests.cpp SafeArray example 7 (template): SafeArray7.zip Virtual destructors: VirtualDestructor1.zip VirtualDestructor2.zip |
9 | Mar 24 |
Video recording
Slides: Midterm solutions; Assignment #7 sample solution; calculation puzzle; chrono; auto; decltype; Assignment #9; exception handling; exception classes; throwing exceptions in a function; review of iteration; recursion; think recursively; recursive examples: factorials, multiplication, Fibonacci (iterative and recursive), member of, unique, reverse, Towers of Hanoi; recursive binary search; mergesort Savitch slides: 14 16 Malik slides: 06 Calculation puzzle: roundoff.cpp Exception handling examples: exception1.cpp exception2.cpp exception3.cpp Timed vector examples: TimeVector1.cpp TimeVector2.cpp Recursion examples: Factorial.cpp Multiply.cpp Fibonacci1.cpp Fibonacci2.cpp Fibonacci3.cpp MemberOf.cpp Unique.cpp Reverse.cpp Permutations.cpp Hanoi.cpp BinarySearchRecursive.cpp |
10 | Apr 7 |
Video recording
Slides: Pointer to a function; Assignment #9 suggested solution; binary search: iterative and recursive; Towers of Hanoi; mergesort; the Standard Template Library (STL); iterators; containers; STL list template class; Assignment #10 Sample programs: FunctionParm1.cpp FunctionParm2.cpp |
11 | Apr 14 |
Video recording
Password M9.N#3G^
Slides: Introduction to algorithm analysis; how well an algorithm scales; Towers of Hanoi puzzle recurrence relation; proofs by induction; big-O notation and its cousins; rates of growth; rules for computing running time; scalability of different algorithms; hash tables; hash function; collisions; keys for successful hashing; collision resolution; separate chaining; open addressing: linear probing and quadratic probing; load factor; Assignment #11 Malik slides: 09 |
12 | Apr 21 |
Video recording
Password 3N@UEb82
Slides: Nasty C++ puzzle; sorting algorithms; selection sort; insertion sort; Shellsort; insertion sort vs. Shellsort; suboptimal and optimal Shellsort; mergesort for linked lists; analysis of mergesort; partitioning a list; partition using a pivot; quicksort; pivot strategy; suboptimal and optimal quicksort; median-of-three pivot strategy; sorting animations; Assignment #12 Malik slides: 10 Nasty C++ puzzle: Thing.h Thing.cpp IteratorEndTest.cpp |
13 | Apr 28 |
Video recording Password 2u%42+C4
Slides: Trees; implementation; traversals: preorder and postorder; binary trees; infix ==> postfix; binary search trees; inorder tree traversal; min and max; contains; insert; remove; AVL trees; balancing: cases 1 - 4; AVL tree implementation; Assignment #13 Malik slides: 11 |
14 | May 5 |
Video recording Password 8P^+YH95
Slides: Assignment #13 solution; graphs: terms, examples, and representation; topological sort; unweighted shortest path algorithms; weighted least cost path; Dijkstra's algorithm; minimum spanning tree (MST); Prim's algorithm for MST; depth-first and breadth-first searches; function definitions in header files; inline keyword; more modern C++ features Savitch slides: 17 18 Malik slides: 12 Inline examples: Inline1.h InlineTest1.cpp Inline2.h InlineTest2.cpp InlineTest3.cpp |
Department policy is to enforce
all course prerequisites strictly
Problem Solving with C++, 10th edition Walter Savitch Pearson, 2017 ISBN: 978-0134710747 |
Data Structures Using C++, 2nd edition D.S. Malik Cengage Learning, 2010 ISBN: 978-0324782011 |
Do not use Apple's Xcode on the Mac, or you run the risk of writing programs that will not port to other platforms.
On Windows, do not use Microsoft Visual C++, or you run the risk of writing programs that will not port to other platforms. Windows users should install Ubuntu.