¾Ã¾ÃÈÈÊÓƵ

Catalog description:

Abstract data types and their implementation as data structures using object-oriented programming. Use of object-oriented principles in the selection and analysis of various ADT implementations. Sequential and linked storage representations: lists, stacks, queues, and tables. Nonlinear data structures: trees and graphs. Recursion, sorting, searching, and algorithm complexity.

Prerequisites:

CSE 271 with a grade of C- or higher

Required topics (approximate weeks allocated):

• Object-oriented programming (1.0)
  • Implementing ADT interfaces
  • Generics
  • Inner classes
  • Exception handling
  • equals()
  • Implementing the Comparable interface
• ADTs: bag, maps, set, list, stack, and queue (4.0)
  • Operations
  • Array-based and linked-node-based implementations
  • Traversal algorithms (iterative and recursive)
  • Varieties of linked nodes (singly, circular, doubly)
  • Application of standard Java collection libraries
• Trees (3.0)
  • representations
  • traversal algorithms (iterative and recursive)
  • binary search trees
  • heaps
  • Self-balancing trees (e.g. B-trees, red-blue trees, AVL trees)
• Testing (0.5)
  • Writing JUnit tests to ensure correctness of code 
• Tables (2.0)
  • Dictionaries
  • Hash maps
  • Applications
• Graphs (1.5)
  • implementations: adjacency lists and adjacency matrices
  • algorithms: depth-first search, breadth-first search, Dijkstra's algorithm, topological sort
• Algorithm complexity (1.0)
  • Complexity of ADT implementations
  • Space and time complexity of basic sorting/searching algorithms
• Exams/Review (1.0)

Learning Outcomes:

• Select and use appropriate data structures, abstract data types, and algorithmic methods in problem solving
  • Describe the purpose and semantics of abstract data types, including: matrices, lists, stacks, queues, sets, maps, trees, graphs, and priority queues
  • Describe the purpose and semantics of major data structures including: row-major order representation of matrices, 2D-array representation of matrices, array-based lists, linked lists, hash tables (both chaining and open addressing), binary search trees, adjacency lists, adjacency matrices, heaps, and graphs
  • Create programs that utilize the major data structures
  • Use appropriate data structures for solving problems
  • Describe the purpose and possible alternative implementations of common tree and graph algorithms including tree traversals (inorder, preorder, and postorder), depth first search, breadth first search, Dijkstra’s algorithm, and topological sort
• Implement common data structures and algorithms
  • Implement common data structures, including: row-major order and 2D-array representations of matrices, array-based lists, linked lists, hash tables (both chaining and open addressing), binary search trees, adjacency lists, adjacency matrices, and heaps
  • Implement common tree and graph algorithms including tree traversals (inorder, preorder, and postorder), depth-first search, breadth-first search, Dijkstra’s algorithm, and topological sort
  • Combine multiple data structures to create an efficient solution to a problem (e.g. implementing an LRU cache using a list plus hash table, or efficiently changing the priority of an item in a heap in Dijkstra’s algorithm using an auxiliary array)
  • Create or modify one’s own classes to be used with library collection classes (e.g. create a class that can be used as a key in a hash table or binary search tree)
• Implement data structures and abstract data types using object-oriented programming principles
  • Create data structures using polymorphism and inheritance
  • Create data structures using that use generics
  • Represent abstract data types using interfaces
  • Implement classes and data structures using standard Java interfaces and methods: equals(), Comparable, exceptions, hashCode(), and Iterator
  • Write JUnit tests to help identify and prevent errors.
• Determine time and space requirements of common data structure implementations and algorithms
  • Describe the purpose of asymptotic notations (e.g., O) for algorithm analysis
  • Apply asymptotic notations (e.g., O) to analyze common data structure algorithms (insertion, removal, searching of array-based and link-based implementations), and sorting/searching algorithms
  • Describe the differences between worst-case running time, expected running time, and amortized running time and apply them appropriately