The syllabus for this course is here.
The programming environment we are going to use for this course is the Express Edition of Microsoft Visual C++. The Express Edition is a free version of Visual C++ that is available for download, so you can install it on your own computer if you wish. Otherwise, Visual C++ is available on the machines in Briggs 419.
When you are ready to turn in a programming assignment, please send me the source files (.h and .cpp files) by email.
I talked about making the transition from Java to C++
Here is the source code for the first example C++ program I showed: greeter.h, greeter.cpp, and main.cpp.
Lecture notes are here.
Lecture notes include the first assignment, which is due on Friday.
Pointers - here are lecture notes that cover the basics of pointers in C++. As a supplement to the lecture notes, you may also want to read section 1.4 in the text. These notes include the second programming assignment, which is due on Monday, April 8.
More discussion of pointers, specifically dealing with classes that contain pointers. Here is a zip file with source code for today's primary example.
Linked Lists - reading is sections 3.1-3.3. Here is source code for the singly linked list class: header file and source file.
Problem 1: The IntSLList class does not come equipped with a copy constructor or an operator=. Add these missing methods to the IntSLList class and write a short test program sufficient to convince me that your IntSLList now does copying the way it should.
These two problems are due on Friday, April 10.I talked about the set of language features needed to make the Standard Template Library work in C++. The Wednesday lecture covered templates and operator overloading. The Friday lecture covered iterators. You can read more about both of these topics in sections 1.7 and 1.8 in the text.
I showed my solution to problem 1 of the third assignment. If you would like a copy, please email me. I also showed a short test program that demonstrates that copying works correctly with the STL list class.
I discussed the STL vector, list, deque, stack, and queue classes. These are discussed in sections 1.8, 3.7, 3.8, 4.4, and 4.5 of the text.
Three applications of stacks: adding large integers, matching braces in source code, and evaluating infix expressions. Here is source code for the infix expression evaluator. Reading is section 4.1.
Write a program designed to implement the algorithm for adding two large integers described in section 4.1 of the text. Use the STL stack class to implement your solution.
Here is the outline of some code designed to read a large integer by reading it one character at a time and then converting the character into an int that stores the digit:
while(cin.peek() != '\n') {
char ch = cin.get();
int x = ch - '0';
// Now do something with x
}
This assignment is due on Monday, April 20.
Chapter 5, Recursion. Here are lecture notes. On Monday I talked about quicksort and explained why quicksort is significantly faster than a standard sorting algorithm. Here is a program that does side-by-side speed comparisons of quicksort and selection sort.
Here is a program that implements the quicksort algorithm using iterators in place of integer array indices. The program demonstrates that you can use this version of quicksort as a generic sorting algorithm that will work with either vectors or lists. Your task in this assignment is to prepare a similar program for selection sort. Take the code for selection sort that you will find in this program and modify it so that it uses only iterators to do its work. Build that code into a test program that demonstrates that you can successfully use your selection sort to sort both vectors and lists.
This assignment is due on Friday, April 24.
We started chapter 6, binary trees. Reading is sections 6.1-6.3 and 6.5-6.6.
I introduced the AVL tree data structure and worked through the details of how to do an insertion into an AVL tree. This material is covered in section 6.7.2 of the text - you should read that section carefully.
Write the necessary code to implement insertions into an AVL tree. You can use this code for the BST class as a starting point, since AVL trees are essentially BSTs with balance factors and an algorithm to rebalance the tree after insertions and deletions.
The BST class I have provided also contains a useful snapshot method that you can use to save a structured text representation of a tree to an output stream such as a file. This example program demonstrates how to make snapshots of trees. The example program saves the snapshots to a text file in the form of Mathematica commands. You can copy and paste the resulting code into Mathematica and press shift-enter to evaluate the Mathematica code to generate visual representations of the original trees. (Mathematica is available on the computers in 419.)
Here is some further code to implement a right rotation about a node in an AVL tree. (Although I think this code is correct, I can't vouch for its correctness.)
Finally, here are some additional lecture notes on the AVL insertion algorithm.
Note that for this assignment you only have to implement insertions. I will eventually show my solution along with code to handle deletions.
This assignment is due by class time on Wednesday, May 6.
Heaps, Priority Queues, and function objects. Reading is sections 6.9 and 1.7.4. Here is the implementation of heap and priority queue classes that I showed in class.
We wrapped up chapter 6 by talking about inorder traversals and iterators that work with BSTs. There are two ways to implement iterators, creating a threaded tree and using a stack of pointers to simulate an inorder traversal. Reading for today is section 6.4.
B-trees - reading is section 7.1.1.
Implement the B-tree data structure as described in section 7.1.1 of the text. Your B-tree should support insertion, deletion, and search operations. Also, write a short test program to demonstrate that your B-tree can correctly perform all of these operations. This assignment is due on Wednesday, May 13.
v-h trees - reading is section 7.1.7.
Tries - reading is section 7.2.
Rework the author's implementation of tries. This assignment is due on Friday, May 22.
Chapter 10, Hash Tables - reading is sections 10.1-10.2.
We started on chapter 8, Graphs. I talked about representations of graphs and showed several algorithms for doing graph traversals. Here is some code that demonstrates how to build a graph read from a text file and do both breadth-first and depth-first traversals. Reading is sections 8.1 and 8.2.
Shortest path algorithms, including Dijkstra and Bellman-Ford. Here is some code that demonstrates how to build a weighted graph read from a text file and find shortest paths in that graph by both methods. Reading is section 8.3.
The second midterm exam will be on Friday, May 29. The exam will cover chapters 6 and 7. Specifically, you will be expected to have some familiarity with each of the major data structures we covered: heaps, binary search trees, AVL trees, B-trees, v-h trees, and Tries. For each of these data structures you should be able to explain what these data structures are used for, how how their major operations work, and how efficient each operation is. (For example, inserting a new key into a heap with N items already in it takes time O(log N).)
Rewrite your B-tree code and make it work. Here are some suggestions on how to proceed. This assignment is due on Wednesday, June 3.
Kruskal's algorithm - reading is sections 8.4 and 8.5
Implement Kruskal's algorithm - here is some code to help you get started. This assignment is due on Wednesday, June 3.
Chapter 12 - memory management algorithms. On Monday I talked about memory word alignment issues and also showed some ways that C++ allows you to work at the level of individual bits. On Wednesday I showed an example of how you can easily implement a custom memory manager for a specific class by overriding operators new and delete. Here is the code for that example. Reading is sections 12.1 and 12.2.