CPSC 2108 - Data Structures - Final Study Guide

Study Material

Chapters 1-10 of Object-Oriented Data Structures using Java by Dale, Joyce, & Weems

Material from programming assignments and notes
CHAPTER EXERCISES!!!

Test Format (Saturday, May 8, 2010 @ 10:30 am-12:30 pm in CCT409)
Short Answer Questions (150 points) - evaluate, trace code, compute, write Java code, what is the output? [Most of the questions will be similar to the end of the chapter exercises and/or quizzes]
1 Programming Problem to be completed in class and submitted as .java files (50 pts)

• Students will learn to understand the principles of efficiency of algorithms
• Students will learn to understand how to specify, design and implement Abstract Data Types
• Students will learn to be able to implement and use data structures such as Lists, Stacks and Queues Data Structures
• Students will learn about and learn to use the concept of Recursion
• Students will learn to implement and use Binary Search Trees
• Students will learn to be able to implement and use data structures such as Priority Queues, Heaps, and Graphs
• Students will learn to be able to describe and analyze efficiencies of different algorithms for sorting and searching

• Getting Organized
  • Software Engineering
  • Object Orientation
  • Classes, Objects, and Applications
  • Organizing Classes (inheritance, packages)
  • Data Structures (implementation dependent and independent structures)
  • Basic STructuring Mechanisms (arrays, references)
  • Comparing Algorithms (Big-O Analysis)
• Abstract Data Types
  • Abstraction
  • ADT Specification
  • Array-based ADT Implementation
  • Linked List ADT Implementation
  • Software Testing
  • Software Design (Identification of classes)
• Stack ADT
  • Stacks (operations and uses)
  • Collection Elements
  • Exception Handling
  • Formal Specification
  • Array-based Implementation
  • Linked List Implementation
• Recursion
  • Recursive Definitions, Algorithms, and Programs
  • Three Questions
  • Recursive Linked-List Processing
  • Removing Recursion
  • Deciding whether to use recursion
• Queue ADT
• Queues (operations and uses)
• Formal Specification
• Array-based Implementation
• Linked List Implementation
• List ADT
• Lists
• Formal Specification
• Array-based Implementation
• Reference-Based Implementation
• Binary Search Algorithm
• Storing Objects and Structures in Files (Serializing)
• More Lists
• Circular Linked Lists
• Doubly Linked Lists
• Lists with Headers/Trailers
• Linked List as an Array of Nodes
• Binary Search Trees
• Trees
• Logical Level
• Application Level
• Implementation Level
• Comparing BST and Linear Lists
• Balancing a BST
• Nonlinked Representation of Binary Trees
• Priority Queues, Heaps, and Graphs
• Priority Queues
• Heaps
• Graphs
• Graph Applications (Searching)
• Implementation of Graphs
• Sorting and Searching Algorithms
• Simple Sorts
• O(N log N) sorts
• More Sorting Considerations
• Searching
• Hashing