MTHSC 865 - Advanced Data Structures

Professor: Daniel D. Warner Class Room: Martin 301
Office: Jordan Hall G-36 Class Hours 1:25 - 2:15 MWF
Office Hours: 9:30 - 11:00 MWF Phone: 656-5244

Course Objectives

  1. To understand the different types of formal automata, their relative computational power, and their practical implementation.
  2. To learn how to use grammars and formal languages in specifying complex problem descriptions.
  3. To develop better skills in program design by viewing programs as an organization of automata and abstract data structures.

Policies

  1. Attendance is not mandatory, but you will be responsible for all material covered in class. Roll will be taken until I know all the students.
  2. The grade will be based on a mid-term exam and five projects. The mid-term exam will count as 25% of the grade. Most of the projects will be programming exercises. As a general rule projects which are not completed on time will not count toward the final grade.

References

  1. Java In A Nutshell, by David Flanagan, O'Reilly & Associates, Inc., 1997.
  2. Exploring Java, by Patrick Niemeyer and Joshua Peck, O'Reilly & Associates, Inc., 1997.
  3. Algorithms, Robert Sedgewick, 1988.
  4. Algorithms + Data Structures = Programs, Niklaus Wirth, 1976.
  5. Data Structures, Theory and Practice, Berztiss, 1975.
  6. Foundations of Computer Science, Aho and Ullman, 1992.
  7. Introduction to Automata Theory, Languages and Computation, Hopcroft and Ullman, 1979.
  8. Machines, Languages and Computation, Denning, Dennis and Qualitz, 1978.

Topics

  1. Tokens, strings, grammars and formal languages.
  2. Finite state machines, Push down automata, and Turing machines.
  3. Stacks, queues, deques and priority queues.
  4. Recursion and parsing proving.
  5. Abstract Data Types and Object Oriented Design.