Department of Management Information Systems

University College Dublin

MMS 406: Algorithms and Data Structures

Semester 2 --1999-2000

Lectures : 2.30 - 4.00 Tuesday, 11.30 - 1.00 Wednesday

Lab Class : 2.30 - 4.00 Wednesday

Last updated Saturday, February 09, 2008

Lecturer : Dr Derek O'Connor

Retired Sept 2000 -- See Home Page

Office: D412 Arts/Commerce Building; Telephone 706-8202

[Course Outline] [Assignments] [Required Text] [Recommended Texts]

Course Outline

0. Contents

• Lecture Notes

1. Introduction

• Algorithms
• Structured Programming
• Abstract Data Types
• Data Structures
• Elementary Data Structures
  • Scalars
  • Arrays and Records
  • Pointers and Dynamic Memory Allocation

• Application to Sparse Matrices
  • Implementation Notes
• Lecture Notes

Assignment 1 : Sparse Successive Over-Relaxation

2. Basic Abstract Data Types

• Linked Lists
• Stacks
• Queues
• Deques
• Application to Discrete Event Simulation
  • Implementation Notes
• Lecture Notes

Assignment 2 : Discrete Event Simulator

Sample Program

3. Tables and Hashing

• Lecture Notes

4. Trees

• Introduction and Theory
• Tree Data Structures
• General and Binary Trees
• Tree Traversal Algorithms
• Binary Search Trees
• Heaps
• Application of Heaps to Sorting
• Application of Trees to the Network Simplex Method
  • Implementation Notes
• Lecture Notes

5. Graphs

• Introduction and Theory
• Graph Data Structures
• Graph Traversal Algorithms
• Applications of Graph Traversal Algorithms
  • Connectivity
  • Topological Ordering
  • Diameter of a Graph
• Lecture Notes

6. The Union-Find Set Problem

• Introduction
• Data Structure
• Height Balancing
• Path Compression
• Lecture Notes

7. Minimum Spanning Trees

• Introduction and Theory
• Kruskal's Algorithm
• Prim's Algorithm
• Lecture Notes

8. Shortest Path Spanning Trees

• Introduction and Theory
• A Prototype Algorithm
• Dijkstra's Algorithm
• Bellman-Ford-Moore Algorithm
• Variations
• Implementation Notes
• Lecture Notes

Assignment 3 : Shortest Path Algorithms

9. Sorting & Selection

• Introduction
• Lower Bounds and Information Theory
• O(n²) Algorithms
• O(n log n) Algorithms
• O(n) Algorithms
• Selection
• Lecture Notes

10. Simulation (If time permits)

• Introduction
• Mathematical System Theory
• The Structure of Digital Simulators
• Discrete Event Simulators
• Lecture Notes
• References

Assignments

It is virtually impossible to understand and appreciate algorithms and data structures without implementing them and using them in some program. For this reason three programming assignments will be given in this course which will count for 24% of the grade. The programming language will be Pascal using the Turbo Pascal system. You may need to use the Turbo Pascal manuals from time to time. These are available in the microcomputer center. Also, there are many books on the Turbo Pascal system which contain useful tips and software. It may be worth buying one of these between 2 or 3 students.

General notes on Assignments (broken link)

Notes on Pascal (PDF 1.4 MB) 

Programming Languages : Comparisons and Criticisms (broken link)

Required Text

• Standish, Thomas A : Data Structures, Algorithms, and Software Principles, Addison-Wesley, 1994.

Recommended Texts

1. Aho, A.V., Hopcroft, J.E., and Ullman, J.D. : Data Structures and Algorithms, Addison-Wesley, 1984.
2. Aho, AV., & Ullman, J.D. : Foundations of Computer Science, Computer Science Press, 1992.
3. Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. : Network Flows, Prentice-Hall, 1993.
4. Bentley, J. : Writing Efficient Programs, Prentice-Hall, 1982;
5. Bentley, J. : Programming Pearls, Addison-Wesley, 1986;
6. Bentley, J. : More Programming Pearls, Addison-Wesley, 1989;
7. Bentley, J. : Programming Pearls, 2nd Ed., Addison-Wesley, 2000.
8. Brassard, G. and Bratley P. : Algorithmics, Prentice-Hall, 1988;
9. Cormen, T., Leiserson, C, and Rivest, R : Introduction to Algorithms, MIT Press, 1990.
10. Hall, H.S. : A School Algebra, Macmillan, 1912.
11. Knuth, D.E.: The Art of Computer Programming, Vol.1 : Fundamental Algorithms, 2nd Ed., Addison-Wesley, 1973.
12. Knuth, D.E. : The Art of Computer Programming, Vol.2: Semi-Numerical Algorithms, 2nd. Ed., Addison-Wesley, 1980.
13. Knuth, D.E. : The Art of Computer Programming, Vol.3: Sorting and Searching, Addison-Wesley, 1973.
14. McConnell, S. : Code Complete, Microsoft Press, 1993.
15. Papadimitiou, C., and Steiglitz, K. : Combinatorial Optimization : Algorithms and Complexity, Prentice-Hall, 1982.
16. Parsons, T.W.: Introduction to Algorithms in Pascal, Wiley, 1995.
17. Reingold, E., Nievergelt, J., and Deo, N. : Combinatorial Algorithms : Theory and Practice, Prentice-Hall, 1977.
18. Sedgewick, R. : Algorithms, 2nd Ed., Addison-Wesley, 1988.
19. Tarjan, R.E. : Data Structures and Network Algorithms, SIAM, 1983.

Past Exam Solutions

• Winter 1999 Exam Solutions.

Software

• Turbo Pascal 5.5 : TPDisk1.ZIP and TPDisk2.ZIP   This is provided by Borland.

[MIS Home Page] [Graduate School Home Page] [Faculty of Commerce Home Page]

This page was last updated by Derek O'Connor on 09-Feb-2008