CSE 274 Data Abstraction and Data Structures (3 credits)

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 C-or above)

CSE 274 is a third-tier course in the CSE2 "Computer Programming" thematic sequence.

Computer software plays an important role in our daily lives: Our mobile phones, laptop computers, online banking, Internet applications such as YouTube, video games and movies, cars, and almost all aspects of daily life are touched by software. In your personal and professional life you will utilize computer software. It is also likely that you will select, or even influence the design of, software that is used in your professional or personal life. This thematic sequence will give you a deep understanding of how software works and is created, its limitations, and its potential. You will be able to read software and therefore be able to make informed decisions when selecting or participating in the design of business, scientific, or information systems that utilize computer software.

The CSE2 thematic sequence consists of both of the following introductory computer programming courses.

  • CSE 174, Fundamentals of Programming and Problem Solving
  • CSE 271, Object-Oriented Programming

Followed by one of the following courses:

  • CSE 274, Data Abstraction and Data Structures
  • CSE 252, Web Application Programming
  • CSE 283, Data Communications and Networks

CSE  274 is a course in which you build upon the programming concepts and techniques learned in CSE 174 and CSE 271 to design and implement more software using sophisticated data structures such as lists, stacks and queues. You will expand your problem solving skills by analyzing and using more sophisticated algorithms and programming techniques.

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:

 

  1. 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
  2. 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)
  3. 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.
  4. 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