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
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.
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.
Last Revised: 2016-11-30
© Copyright 2016 by Peter C. Chapin <PChapin@vtc.vsc.edu>