Class Notes: Discrete Data Structures and Algorithms

Summer-C 1999 - M WRF 2nd Period CSE/E119

Instructor: M.S. Schmalz -- TAs: TA Mailing List

Housekeeping Details

• Syllabus - Rev. 0 (1 May 99)
• Anticipated Class Schedule - Required Reading
• Finalized Lab Schedule
• Lab Section Assignments
• Programming Project Submission Instructions
• TA Office Hours
• Required Class Materials - Textbooks, Notes, etc.
• Optional Class Materials - Textbooks, Periodicals, etc. -- Check this link frequently
• What's New -- Check Class Schedule for New Deadlines
  Thu 08-05-99: Homework #10 due, Project #5 due by midnight
  Wed 08-04-99: Final Exam, in class 9:30am
  Tue 08-03-99: Final Exam Review, special office hours 3:45pm - 5:00 pm
  Sun 08-01-99: Project #4 Sample Code posted
  Fri 07-30-99: Final Exam Topical Review posted
  Fri 07-30-99: Homework #10 Assignment posted
  Fri 07-30-99: Homework #9 due
  Thu 07-28-99: Put examples of 1998 performance analysis reports on reserve at Marston Library
  Tue 07-27-99: Posted codes for Projects 1-3 (see list below)
  Wed 07-28-99: Homework #8 due -- Revised Date
  Fri 07-23-99: Homework #9 Assignment posted
  Fri 07-23-99: Project #4 due
  Wed 07-21-99: Homework #7 due
  Fri 07-16-99: Programming Project #5 Assignment posted
  Fri 07-16-99: Homework #8 Assignment posted
  Wed 07-14-99: Posted tree printing technique and updates for Project #4
  Fri 07-02-99:

• Old Exams, Homeworks, and Programming Assignments:
  Exam #2 Practice Problems
  Exam #2 Review
  Exam #1 Answers
  Exam #1 Practice Problems
  Exam #1 Review
  Project #4 Sample Code
  Programming Project #4
  Project #3 Sample Code
  Programming Project #3
  Project #2 Sample Code
  Programming Project #2
  Project #1 Sample Code
  Programming Project #1
  Homework Assignment #7
  Homework Assignment #6
  Homework Assignment #5(with key)
  Homework Assignment #4(with key)
  Homework Assignment #3(with key)
  Homework Assignment #2(with key)
  Homework Assignment #1(with key)
  
  Homework Grade Information - by SSN, including Histograms

  Overall Grade Information - by SSN, including Histograms

  • Netscape Setup Information - Fonts, Colors, etc.
  • List of Symbols for Netscape

Course Material

• Appendix A -- Review of Discrete Math & Notation

• Appendix B -- Sun Microsystems Java Tutorial

• Appendix C -- Dr. Crummer's Java Tutorial

1. Introductory Material, Recursion, Arrays, and Sorting
   1.1. Introduction and Overview
   1.2. Review of Discrete Math Concepts and Notation
   1.3. Overview of Java Programming Language
   1.4. Overview of Complexity Notation
   1.5. Recursive Computations
   1.6. Arrays and Lists
   1.7. Searching, Selection, and Sorting
   

2. Sets, Strings, Stacks, Heaps, and Queues
   2.1. Sets
   2.2. Strings
   2.3. String Representations of Data Structures
   2.4. Stacks and Queues
   2.5. Sorting with Priority Queues
   2.6. Heaps and Heapsort
   

3. Graphs and Trees
   3.1. Mathematics of Graphs and Trees
   3.2. Binary, n-ary and 2-3 Trees
   3.3. Tree Traversal, Pruning, and Balancing
   3.4. AVL Trees and Red-Black Trees
   3.5. Performance Measures for Tree Operations
   3.6. Forests, Radius, Diameter, etc.
   3.7. Min-Cost Spanning Trees
   3.8. Shortest Path Problems
   3.9. Greedy Algorithms, Strong Components, and Cliques
   

4. Hashing
   4.1. Mathematics of Hash Functions and Hashing
   4.2. Different Types of Hashing
   4.3. Data Structures
   4.4. Example Applications
   4.5. Performance Measures
   

5. Applications and Advanced Topics
   5.1. Data Structure Applications in Simulation, DBMS, and AI
   5.2. Overview of Selected Parallel Algorithms
   5.3. Research in Randomness and Data Structures
   5.4. Isolation of Computational Error
   

---

Bibliography

• References Cited in Class

---

This Web page and all subordinate pages
Copyright © 1998,1999 by Mark S. Schmalz
All rights reserved, except printing by UF/CISE faculty
or UF students officially registered for this class.

---