CIS-5050 (Advanced Algorithms and Data Structures) Home Page

This is the home page for CIS-5050 course notes for the Fall 2021 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 Canvas but all other course resources are likely to be here (I may experiment with using Canvas more this semester).
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 repository on GitHub contains the latest version of my tutorial.
Sample code used as the basis for homework assignments can be found in a Git repository on GitHub. If you clone this repository and keep your clone updated, you should have a coherent collection of files from which you can start your work.

Topics

2021-08-23. Introduction to the course. Discussed InsertionSort, MergeSort, and the conventions used in the text. Introduced the Ada programming language.
2021-08-25. Described Homework #1
2021-08-30. Asymptotic notation, recurrences, the Master Theorem, and the Master Method.
2021-09-01. Introduced skip lists, Homework #2, and Ada's handling of access types.
2021-09-08. Reviewed skip list test program. Introduced binary search trees in Ada.
2021-09-13. Discussed the general KV_Stores testing infrastructure. Discussed splay trees.
2021-09-15. Discussed red-black trees and Homework #3.
2021-09-20. Dynamic programming and the rod cutting problem.
2021-09-22. More on dynamic programming via the longest common subsequence problem.
2021-09-27. Introduced greedy algorithms by way of the activity selection problem.
2021-09-29. An Ada solution to the 0/1 knapsack problem and its relationship with the greedy solution to the fractional knapsack problem.
2021-10-11. No class.
2021-11-13. Introduced graphs and BreadthFirstSearch. Started reviewing the Ada implementation of BFS.
2021-10-18. Completed the review of the Ada implementation of BFS.
2021-10-20. Discussed the Depth First Search graph algorithm.
2021-10-25. Discussed Homework #4 and introduced the Ford-Fulkerson method for computing maximum flow.
2021-10-27. More details on the Ford-Fulkerson method. Discussed the Edmonds-Karp algorithm.
2021-11-01. Discussed Homework #5 and the Edmonds-Karp skeleton code.
2021-11-03. Discussed the KV_Stores benchmark program and the performance of earlier KV_Stores data structures on random and ordered inserts.
2021-11-08. Introduced Fibonacci Heaps and Homework #6.
2021-11-10. Continued discussion of Fibonacci Heaps with Decrease-Key and Delete. Also introduced the amortized analysis used to analyze the running time of Fibonacci Heap operations.
2021-11-15. Introduced formal languages and Turing machines.
2021-11-17. Introduced the Lambda Calculus and the concept of non-deterministic Turning machines.
2021-11-29. More on non-determinism. Introduced Hamiltonian paths, 3SAT, and P vs NP.
2021-12-01. More in P vs. NP, 3SAT, SAT, polynomial reductions, and NP-completeness.
2021-12-06. No new material. Class is a question/answer session.
2021-12-08. No new material. Class is a question/answer session.
2021-12-13. No new material. Class is a question/answer session.

Slides

A brief discussion of formal language theory.
Overview of Turing machines.
Overview of Lambda calculus.

Papers

A detailed bibliography in BibTeX format.

Skip Lists: A Probabilistic Alternative to Balanced Trees by William Pugh
Self-Adjusting Binary Search Trees by Daniel Dominic Sleator and Robert Endre Tarjan
The original paper on the LZ data compression algorithm by Jacob Ziv and Abraham Lempel

Homework

Homework #1 Maximum Subarray. Due: 2021-09-03
Homework #2 Skip Lists. Due: 2021-09-17
Homework #3 Red-Black Trees. Due: 2021-10-01
Homework #4 Topological Sort. Due: 2021-11-05
Homework #5 Edmonds-Karp. Due: 2021-11-19
Homework #6 Fibonacci Heaps. Due: 2021-12-17

Samples

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

Resources

The Wikipedia article on Hamiltonian Paths