Basic data structures such as stacks, queues, linked lists, and trees are studied and applied to problems in data storage and manipulation. Applications include basic searching and sorting algorithms. Design, analysis and implementation techniques are discussed. Three lecture hours and three hours of scheduled laboratory per week, plus extensive programming work outside of class.
Prerequisite: CSC 202J with grade of C+ or higher;   CSC 200 or CSC 200A.

• CG1: to develop an appreciation for the process of data abstraction and its usefulness in software development;
• CG2: to develop the skills and knowledge necessary to perform basic analysis of algorithms;
• CG3: to present a selection of the most common data structures and their standard implementations and uses;
• CG4: to present a selection of the most common algorithms for searching and sorting.

• CO1: applied data abstraction techniques;
• CO2: implemented several classic data structures "from scratch";
• CO3: demonstrated knowledge and use of ADTs available in one or more language libraries;
• CO4: recognized the factors required to perform analysis of algorithms and performed order-of-magnitude analysis;
• CO5: chosen, with justification, an appropriate structure to match the requirements of a given problem, implemented the structure if necessary, and used it in an appropriate way to solve the problem;
• CO6: utilized standard techniques for program validation;
• CO7: demonmstrated the ability to use the UML modeling language;
• CO8: produced documentation for at least one major completed project, including formal class diagrams and rigorous test set specification and results;
• CO9: participated in at least one group project involving problem analysis and design specification and selection.

• review of design concepts
• recursion (review and new examples)
• the hierarchy of data types and the concept of abstract data type (ADT)
• the three levels of data structuring
  • the application level (recognizing the behaviors and features needed to solve the problem at hand)
  • the abstract level (selecting or defining an appropriate abstraction that models these behaviors)
  • the implementation level (realizing the abstraction using standard programming language features)
• abstract data types
  • stacks
  • queues
  • priority queues
  • ordered lists
  • access tables
  • links
  • trees
  • heaps
  • graphs
• data structures and their algorithms
  • linear linked structures: singly linked lists, bidirectional linked lists, multi-list structures
  • non-linear linked structures
    • hierarchical: binary trees, AVL trees, B-trees
    • network: graphs, digraphs, weighted graphs
  • direct access structures: hash tables (direct and indirect)
• ADTs and object-oriented design
• other algorithms:
  • linear search, binary search (review)
  • insertion sort, selection sort (review)
  • quicksort
  • heapsort
• elementary algorithm analysis (efficiency, speed)
• implementing ADTs and data structures:
  • static memory allocation (arrays) vs. dynamic memory allocation vs. files
• pointers and dynamic memory allocation
• use of software libraries

      This course revolves around the notions of data abstraction and the structuring of data, using the concept of abstract data type (ADT). The most common and most useful data structures are defined and classified, and the appropriate manipulation algorithms are presented in general form (in pseudocode). At least one concrete realization for each structure is then discussed.
      Five or six programming assignments are given, emphasizing the choice and/or implementation of a specified structure, such as a stack, queue, binary search tree, or hash table. The final assignment requires the student to make the choice of an appropriate data structure or combination of structures to best solve a specified problem.
      All programs must conform to departmental guidelines for algorithm design and implementation. Laboratory reports must conform to the written guidelines supplied by the instructor. Regardless of numeric average or individual grades on assignments or examinations, a student will not be eligible for a passing grade in the course unless he or she has submitted a lab report for every programming assignment, within the time frame specified by the instructor.

• Budd, Timothy.   Classic Data Structures in Java.   Addison Wesley, 2001.
• Carrano, Frank M.; Prichard, Janet J.   Data Abstraction and Problem Solving with Java.   Walls and Mirrors. McGraw-Hill, 2001.
• Collins, William J.   Data Structures and the Java Collections Framework. McGraw-Hill, 2002.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.   Introduction to Algorithms.   Second Edition.   The MIT Press, 2001.
• Dale, Nell; Walker, Henry M.   Abstract Data Types.   Specifications, Implementations, and Applications.   D. C. Heath, 1996
• Knuth, Donald E.   The Art of Computer Programming, Volume 1 (Third Edition, 1997) and Volume 3 (Second Edition, 1998)   Addison-Wesley.
• Preiss, Bruno R.   Data Structures and Algorithms with Object-Oriented Design Patterns in Java.   John Wiley & Sons, 2000.
• Shaffer, Clifford A.   A Practical Introduction to Data Structures and Algorithm Analysis. Java Edition.   Prentice Hall, 1998.
• Weiss, Mark Allen.   Data Structures and Problem Solving using Java.   Second Edition.   Addison Wesley, 2002.