CIS-3050 (Algorithms and Data Structures) Home Page

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.

Topics

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 —

Lessons

Algorithm Performance
— Lessons below are subject to change —

Slides

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

Homework

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 —

Samples

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 —

Resources

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.