Please note that this schedule and the topics covered
are likely to change. Changes will be announced in class. If you are not able
to attend class, it is your responsibility to find out what was covered.
A more detailed schedule is provided on the course website. Assignment
descriptions and due dates will also be posted on the course web site.
| Week |
Date |
Topics |
Reading |
| 1 |
1/16, 1/18 |
I/O and formatting
- School closed on 1/16/17 for MLK observance
- review syllabus
- compiling and running programs on the remote server
- assignment submission
- using cin, get, and ignore
- using peek and putback
- detecting input stream failure and using the clear function
- formatting output: setprecision, fixed, showpoint, setw, setfill, left, right
- additional formatting manipulators: dec, hex, oct, showbase, boolalpha, etc.
- I/O using string objects
- debugging using cout statements
- text file input and output
|
Syllabus
Chapter 3 |
| 2 |
1/23, 1/25 |
User-defined functions
- function prototypes
- void vs. value returning functions
- formal paramter lists
- parameters vs. arguments
- default values for parameters
- function overloading
- passing by value, passing by reference, and reference variables
- "returning" more than one value from a function
- variable/identifier scope (global, local)
- variable lifetime (static, automatic)
- how/where variables are stored in memory: stack vs. heap
- testing functions
- a brief introduction to recursion
|
Chapter 6 |
| 3 |
1/30, 2/1 |
User-defined simple types, namespaces, string objects
- declaring enumerations
- declaring variables with an enumeration data type
- using enumerations (operators, I/O, passing to/from functions)
- the importance of using enumerations
- creating and using namespaces (example: kishio I/O library)
- declaring and using C++ string objects
|
Chapter 7 |
| 4 |
2/6, 2/8 |
Arrays and C-style strings
- declaring one-dimension arrays
- accessing a member of a one-dimension array
- initializing a one-dimension array during declaration
- passing one-dimension arrays to functions (passed by reference)
- using a loop to iterate through the elements of a one-dimension array
- common errors trying to access non-existent array elements
- using an array name as a pointer to the first element
- using the const keyword to prevent changes to a passed array
- declaring and using C-style strings (arrays of type char)
- comparing C-style strings
- performing I/O with C-style strings
- declaring and using parallel arrays
- declaring two-dimension arrays
- accessing a member of a two-dimension array
- initializing a two-dimension array during declaration
- passing two-dimension arrays to functions (passed by reference)
- using nested loops to iterate through the elements of a two-dimension array
- arrays of objects (such as C++ string objects)
- extending array concepts beyond two dimensions
|
Chapter 8 |
| 5 |
2/13, 2/15 |
Structs and classes
- defining a struct or class
- declaring variables with a struct or class data type
- accessing members of a struct or class
- specifying public and private access
- the differences between a struct and a class
- passing structs and classes to and from functions
- creating an array of a struct or class type
- using assignment with a struct or class
- built-in operations
- struct/class scope
- accessor and mutator functions
- constructors
- default constructor
- destructors
- static class members (including initialization of static variables)
- the importance of information hiding
- UML diagrams of classes
|
Chapters 9, 10 |
| 6 |
2/20, 2/22 |
Inheritance and composition
- overriding member functions
- constructors of derived and base classes
- destructors in a derived class
- header files and header guards
- protected class members
- public vs. private vs. protected
- composition
|
Chapter 11 |
| 7 |
2/27, 3/1 |
Exception handling
- throwing an exception
- using try/catch blocks
- rethrowing an exception
- creating your own exception class
- exception handling techniques
- using assertions
- exceptions vs. assertions
- error handling techniques (terminate, fix and continue, log and continue)
|
Chapter 14 |
| 8 |
3/6, 3/8 |
Pointers, classes, virtual functions, lists, midterm exam
- declaring and initializing pointer variables
- the address-of operator (&)
- the dereferencing operator (*)
- dynamic memory; using new and delete
- operations on pointer variables
- creating and using dynamic arrays
- shallow vs. deep copies
- functions that objects with dynamic memory should implement/override
- functions that need special care when using pointers (constructor, copy constructor, assignment operator, destructor)
- inheritance, pointers, and virtual functions
- abstract classes and pure virtual functions
- demonstrate polymorphism
- array-based lists
- unordered lists
- ordered lists
- midterm exam
|
Chapter 12 |
| |
3/13-3/19 |
School closed for Spring break |
|
| 9 |
3/20, 3/22 |
Overloading and templates
- the reasons for operator overloading
- restrictions on operator overloading
- overloading binary operators
- overloading unary operators
- overloading binary operators
- member vs. non-member syntax for overloading funtions
- friend functions
- overloading the stream insertion operator (<<)
- overloading the stream extraction operator (>>)
- specifying post-increment and post-decrement operator overloads
- overloading the assignment operator
- overloading the array index operator ([])
- function templates
- class templates
|
Chapter 13 |
| 10 |
3/27, 3/29 |
Recursion
- definition of recursion
- direct and indirect recursion
- avoiding infinite recursion
- recursion vs. iteration
- when to use (or not use) recursion
|
Chapter 15 |
| 11 |
4/3, 4/5 |
Linked lists
- header and implementation files (revisited)
- structure of a linked list and its nodes
- basic implementation of a linked list
- implementing a copy constructor, assignment operator, and destructor
- operations on a linked list (insertion, deletion, access elements, display, etc.)
- basic introduction to algorithm complexity analysis: linked list operations
- templating a linked list
- linked list iterators
- linked list variation: doubly linked list
- linked list variation: unordered list base class
- linked list variation: ordered list derived class
|
Chapter 16 |
| 12 |
4/10, 4/12 |
Stacks, queues
- structure of a stack (LIFO)
- basic implementation of a stack
- implementing a copy constructor, assignment operator, and destructor
- operations on a stack (push, pop, peek/top, isEmpty/empty)
- templating a stack
- implementing a stack using a linked list
- implementing a stack using an array
- stack applications
- structure of a queue (FIFO)
- basic implementation of a queue
- implementing a copy constructor, assignment operator, and destructor
- operations on a queue (add, remove, isEmpty/empty)
- templating a queue
- implementing a queue using a linked list
- implementing a queue using an array
- queue applications
- queue variation: ring buffer
- queue variation: double ended queue (deque)
|
Chapter 17 |
| 13 |
4/17, 4/19 |
Searching and sorting
- sequential search
- binary search
- restrictions on binary search (data must be in sorted order)
- algorithm complexity analysis of linear and binary search
- basic sorting algorithm implementation: insertion sort
- basic sorting algorithm implementation: selection sort
- basic sorting algorithm implementation: bubble sort
- advanced sorting algorithm walk-through: quick sort
- advanced sorting algorithm walk-through: merge sort
- introduction to binary tree structure and properties
- binary tree variation: the heap data structure
- minheaps vs. maxheaps
- implementing a heap using an array
- advanced sorting algorithm walk-through: heap sort
- advanced sorting algorithm walk-through: bogosort/Robsort
- algorithm complexity analysis of sorting algorithms
- sorting arrays vs. linked lists
|
Chapter 18 |
| 14 |
4/24, 4/26 |
Binary trees
- properties of a binary tree (revisted)
- properties of a binary search tree (BST)
- implementation of a binary search tree
- operations on a binary search tree: insert, delete, search, traverse, isEmpty
- avoiding degenerate binary search trees when inserting sorted data: balanced BSTs
- BST traversal: inorder, preorder, postorder
- finding a BST's minimum and maximum values
- finding the successor or predecessor of a node in a BST
- various ways of handling duplicate values in a BST
- using recursion vs. iteration when traversing a BST
- algorithm complexity analysis for BST operations
- BST applications
|
Chapter 19 |
| 15 |
5/1, 5/3 |
Graphs
- graph terminology: vertex, edge, neighbor, weighted, directed, acyclic, connected, etc.
- graph data structures: vertex list, edge list, adjacency list, adjacency matrix
- adding a vertex
- adding an edge
- breadth-first traversal
- depth-first traversal
- determining if a path exists
- determining if a graph is connected
- finding a minimum spanning tree
- finding a shortest path
- graph applications
|
Chapter 20 |
| 16 |
5/8, 5/10 |
Binary files and random access files
- writing binary data
- reading binary data
- writing to a random access file
- reading from a random access file
- advantages and disadvantages of binary files
- advantages and disadvantages of random access files
|
Appendix E |
| Finals |
5/15/17 |
Final exam: Noon - 1:50 P.M., Rm. A-1374 |
|