CSI 2114 A - Data Structures
(Fall 2003)

Description
Introduction to abstract data types. Trees, binary search trees, balanced trees. Searching. Sorting. Simple examples of complexity analysis. Graphs, simple graph algorithms: depth-first and breadth-first search, minimum spanning tree, shortest path. (Lab work will be done in the Java programming language). Prerequisite: CSI 1101 or 1102.

Objectives
Present in a systematic fashion the most commonly used data structures, emphasizing their abstract properties. Review implementation methods for those data structures. Discuss typical algorithms that operate on each kind of data structures, and analyze their performances.

Textbook
Michael Goodrich, Roberto Tamassia Data Structures and Algorithms in Java (2nd ed.), Wiley, 2000. The textbook is available at AGORA Bookstore.

The textbook has a great web site at http://loki.cs.brown.edu:8081/webdsa/ with on-line demos and hints for exercises.

Other sources

D.E. Knuth, Sorting and Searching , vol. 3 of The Art of Computer Programming, Addison Wesley, 1973.

T.A. Standish: Data Structures in Java. Addison Wesley.

S.Sahni: Data Structures, Algorithms, and Applications in Java. This book has a web site 
http://www.cise.ufl.edu/~sahni/dsaaj/index.html

Assignments
There will be five assignments : two programming assignments and three non programming assignments.
All assignments should be handed to locked box #32 in the SITE building by 5pm on the day they are due.  
All programming questions on assignments must be handed in on a diskette. They will normally consist of short but complete, tested and documented, programs in Java. Remember to hand in also libraries you use in your Java program that are not standard.
Late hand-ins will not be accepted.
All assignments and labs will be posted on the Web.

Assignments--details

Tentative non programming Assignment topics Posted - due
analysis/stacks/queues/dequeues Sept. 19-26
vectors, trees, heaps, AVL trees Oct. 10- 17
hashing, tries, sorting, graphs Nov. 19 - 26
Tentative programming assigments topics Posted - due
stack/queues/dequeues, sequences
Sept 26 - Oct. 10
trees, heaps, search trees
 Oct. 29 - Nov 12

Marking Scheme A maximum of 100 marks will be available. The division is as follows:
 
Assignments 25 marks
midterm exam (closed book, 2 hours) 30 marks
final exam (closed book, 3 hours) 45 marks

To pass the course you have to obtain at least 50 between the midterm and the final exam.

The final exam will be comprehensive, with the emphasis on the material not covered on the midterm exam. 

A student who has an official medical certificate (from the University Health Services) for the absence on the day of the midterm will have the final exam mark scaled up accordingly.  


Topics and Readings

Only reading from the textbook is listed here. The student is expected to read the indicated chapters before the material is discussed in class. Reading slightly ahead of time is recommended. 
  • Overview of the course. 
  • Review of linked lists
  • Stacks, queues, dequeues (sections 4.1-4.5).
  • Algorithm analysis techniques (sections 3.1-3.7).
  • Vectors, lists, sequences (sections 5.1-5.6).
  • Trees (sections 6.1-6.4).
  • Priority Queues and Heaps (sections 7.1- 7.3).
  • Dictionaries (sections 8.1-8.3).
  • Search trees (sections 9.1-9.).
  • Text Processing (sections 11.3-11.4).
  • Sorting (sections 10.1-10.6).
  • Graphs (sections 12.1-12.7).

    •