This is the home page for Peter Chapin's CIS-3050 course notes for the Fall 2016 semester. Here you will find slides, homework assignments, program samples, and links to other references of interest.

- The
**course syllabus**gives an overview of the course and its content, lists course resources, and describes the grading policy and related issues. - The homework submission area and grade book are on Moodle but all other course resources are here.
- My home page contains other resources of potential interest.

The topics covered in each lecture, with links to relevant resources, are shown below.

- 2016-08-22. Introduction to the class. Introduction to Visual Studio. Described of the InsertionSort algorithm. Discussed the implementation of the specialized InsertionSort for integers, and reviewed the implementation's performance.
- 2016-08-24. Introduced asymptotic notation. Discussed the implementation of the general InsertionSort for any data type.
- 2016-08-29. Introduced the distinction between best case, average case, and worst case running times. Introduced the sorting unit tests. Described the MergeSort algorithm.
- 2016-08-31. Developed MergeSort's pseudo-code, and converted that pseudo-code to a generic C implementation.
- 2016-09-07. Overview of debugging with Visual Studio. Described QuickSort.
- 2016-09-12. Introduced heaps and HeapSort.
- 2016-09-14. Discussed Homework #4 with details about using heaps as priority queues.
- 2016-09-19. Reviewed pseudo-code of Heapify and introduced linked lists.
- 2016-09-21. Developed code for
`SingleList_push_back`and described SingleList iterators and their use. - 2016-09-26. Introduced the VTC string class.
- 2016-09-28. Introduced doubly linked lists. Developed code for
`DoubleList_insert_before`. - 2016-10-04. Described correspondance between Java and C using the SingleList example.
Developed a test function for
`SingleList_reverse`. - 2016-10-05. No class.
- 2016-10-17. Introduced binary search trees.
- 2016-10-19. More on binary search trees. Described Homework #8 and the BinaryTree sample code used by the homework assignment.
- 2016-10-24. Discussed the SpellCheck sample program that illustrates a real world example of how binary trees can be useful. See the Samples section below for links to the code and supporting materials.
- 2016-10-26. Introduced hash tables and showed some demonstration code for an implementation using linked lists in each bucket.
- 2016-10-31. Discussed hash tables with open addressing and described Homework #10.
- 2016-11-02. Introduced graphs and graph applications.
- 2016-11-07. Described how to represent graphs in programs.
- 2016-11-09. Described the Bellman-Ford algorithm for finding the single-source sortest paths in a directed, weighted graph.
- 2016-11-14. Discussed Depth-First-Search of a graph with comments about cycle detection and topological sorting.
- 2016-11-16. Discussed Breadth-First-Search of a graph.
- 2016-11-28. Described the Huffman encoding method of data compression.
- 2016-11-30. Demonstrated a Huffman encoding program (source code on GitHub). Described the LZW data compression algorithm.
- 2016-12-05. Described the
`print_path_to`function that is part of Homework #13. - 2016-12-07. Discussed Dijkstra's Algorithm and the final exam.
- —
*Topics below are subject to change*—

- Algorithm Performance
- —
*Lessons below are subject to change*—

- Insertion Sort
- Merge Sort
- Linked Lists
- —
*Slides below are subject to change*— - Binary Search Trees

- Homework #01 (Due:
*2016-08-31*) InsertionSort Performance - Homework #02 (Due:
*2016-09-07*) Generic Programming in C - Homework #03 (Due:
*2016-09-14*) QuickSort - Homework #04 (Due:
*2016-09-21*) Heaps - Homework #05 (Due:
*2016-09-28*) Linked Lists - Homework #06 (Due:
*2016-10-05*) Reverse List - Homework #08 (Due:
*2016-10-26*) Binary Search Trees - Homework #10 (Due:
*2016-11-09*) Hash Tables - Homework #13 (Due:
*2016-12-07*) Bellman-Ford - —
*Homeworks below are subject to change*—

A Visual Studio 2015 solution containing some initial projects for this course. You can use this solution throughout the course by adding additional projects to it. I will provide some of those projects later, configured to work with this solution.

- The pseudo-code for MergeSort along with a generic implementation in C.
- The pseudo-code for QuickSort.
- The pseudo-code for Heapify.
- The spell checking sample project shows a real-world application of binary search trees. If you want to try the project you will also need the sample dictionary file and the Scramble program needed to randomize the dictionary.
- A simple but serviceable implementation of hash tables that use linked lists to resolve collisions.
- —
*Samples below are subject to change*—

- My C Tutorial may be a helpful place to review various concepts in C programming. It is intended to be the lectures of a one semester, introductory course on C. It covers the main features of the entire language.
- Here are some nice binary search tree slides from a course at the University of Washington that show (among other things) how to delete nodes in a tree.

Last Revised: 2016-11-30

© Copyright 2016 by Peter C. Chapin <PChapin@vtc.vsc.edu>