This is the home page for CIS-5050 course notes for the Fall 2018 semester. Here you will find class handouts, slides used during the lectures, homework assignments, 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 official course outline: CIS-5050.
- The homework submission area and grade book are on Moodle but all other course resources are here.
- The programming in this course will be in Ada. You may not have used that language
before. However, Ada is a software engineering language with features that are worth
learning and understanding. Knowing Ada will likely make you a better programmer in any
language. Here are some relevant Ada resources:
- The GNAT Ada compiler (and tools). This is a free download. You want to download and install the "GNAT Community" product. Support is provided for Windows, Linux, and MacOS (as well as other platforms).
- Here is an online Ada tutorial by AdaCore.
- I have my own tutorial on Ada along with some corresponding sample programs. The links above are relatively static. The repository on GitHub contains the latest version of my tutorial.

- My Huffman project on GitHub illustrates huffman encoding.

- 2018-08-27. Introduction to the course. Discussed Insertion_Sort, the conventions used in the text, and introduced the Ada programming language.
- 2018-08-29. Introduced loop invariants. Discussed Homework #1. Started discussing asymptotic notation in detail.
- 2018-09-03. No class.
- 2018-09-05. Discussed recurrences. Discussed the Master Theorem and Master Method.
- 2018-09-10. Introduced skip lists. Discussed Ada's handling of access types.
- 2018-09-12. More details on skip lists. Developed and described the specification of a generic package for implementing them.
- 2018-09-17. ?
- 2018-09-19. Developed a test program for Skip_Lists. Introduced red black trees.
- 2018-09-24. Class cancelled (instructor illness).
- 2018-09-26. Class cancelled (instructor illness).
- 2018-10-01. Discussed binary trees (in Ada) and red black trees in more detail.
- 2018-10-03. Introduced dynamic programming.
- 2018-10-15. More on dynamic programming and the longest common subsequence problem.
- 2018-10-17. Review of the Homework #1 solution. Introduction to greedy algorithms.
- 2018-10-22. Class cancelled (instructor illness). Read sections 16.1 and 16.2 in the text with particular attention to the pseudo-code for the greedy activity selector algorithm on page 421.
- 2018-10-24. Review of the Homework #2 solution. Described skeletal code for solving the greedy activity selector problem.
- 2018-10-29. Introduced graphs and made some preliminary comments about the maximum flow problem.
- 2018-10-31. Discussed the Ford-Fulkerson method for computing maximum flow.
- 2018-11-05. Class cancelled (instructor at a conference).
- 2018-11-07. ?
- 2018-11-12. Introduced Fibonacci heaps.
- 2018-11-14. Discussed the Fibonacci heaps starter code. Introduced Turning machines and undecidability.
- 2018-11-26. Discussed the Edmonds Karp starter code. Demonstrated the Turning machine simulation program.
- 2018-11-29. Discussed non-deterministic turing machines.
- 2018-12-03. Discussed data compression via Huffman encoding.
- 2018-12-05. Discussed string matching using finite automata.
- 2018-12-10. Described non-deterministic automata and one way a regular expression can be compiled into a DFA (via an NFA).
- 2018-12-12. Discussed the LZW data compression algorithm.

- ..

A detailed bibliography in BibTeX format.

*Skip Lists: A Probabilistic Alternative to Balanced Trees*by William Pugh- The original paper on the LZ data compression algorithm by Jacob Ziv and Abraham Lempel

Examples of

`Insertion_Sort`and`Merge_Sort`in Ada, as translated from the pseudo-code in the text. The zip archive also contains a GNAT project file and an appropriate build folder. Unzip the archive in some suitable place to use as a framework for future samples (or your own work).The starting point for Homework #2 is a skeletal skip lists package. The specification is complete (although you are free to modify the private section if you choose). The body needs to have

`Search`,`Insert`, and`Delete`completed. The archive also contains a Skip_List test program (named`check`) that you can use.This sample implementation of binary search trees in Ada can be used as a point of inspiration for your red black tree implementation in Homework #3.

The starting point for Homework #3 is a skeletal red black trees package. The specification is complete. The body needs to have

`Search`,`Insert`, and`Delete`completed. The test program also needs to be written.Some variations on computing Fibonacci numbers demonstrates dynamic programming (both top-down memoization and bottom-up styles).

A Turning machine simulator in C++ along with a demonstration program.

- Homework #1 Introduction. Due: 2018-09-07
- Homework #2 Skip Lists. Due: 2018-09-26
- Homework #3 Red Black Trees. Due: 2018-10-15
- Homework #4 Edmonds-Karp. Due: 2018-12-19
- Homework #5 Fibonacci Heaps. Due: 2018-12-19

The following are links to relevant resources for this class.

- ..

Last Revised: 2018-12-12

© Copyright 2018 by Peter C. Chapin