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):

  • Review of dynamic variables and principles of object-oriented programming (3)
  • ADTs: vector, bag, set, list, stack, and queue (4)
    • operations
    • various implementations and their comparisons
    • traversal algorithms (iterative and recursive)
    • varieties of linked list (singly, circular, doubly)
    • application of standard class libraries
  • Trees (3)
    • representations
    • traversal algorithms (iterative and recursive)
    • binary search trees
    • heaps
    • B-trees
  • Tables (2)
    • internal vs. external access
    • access methods: hashing and indexing
  • Graphs (1.5)
    • implementations: adjacency lists and adjacency matrices
    • traversals: DFS and BFS
  • Sorting/searching and algorithm complexity (.5)
    • space and time complexity of basic sorting/searching algorithms
  • Exams/Review (1)

Learning Outcomes:

1: Select and use appropriate data structures, abstract data types, and algorithmic methods in problem solving

1.1: Describe the purpose and semantics of abstract data types, including: matrices, lists (aka sequences), stacks, queues, sets, maps (aka dictionaries), trees, graphs, and priority queues

1.2: 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, and heaps

1.3: Create programs that utilize the major data structures

1.4: Use the appropriate data structures for solving search problems

1.5: 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, topological sort, minimum spanning trees, and all-pairs shortest paths.

2: Implement common data structures and algorithms

2.1: Implement common 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, and heaps

2.2: Implement common tree and graph algorithms including tree traversals (inorder, preorder, and postorder), depth first search, breadth first search, Dijkstra’s algorithm, topological sort, minimum spanning trees, and all-pairs shortest paths.

2.3: 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)

2.4: 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

3.1: Create data structures using polymorphism

3.2: Create data structures using inheritance

3.3: Create data structures using generic programming

3.4 Represent abstract data types using interfaces or abstract classes

4: Determine time and space requirements of common data structure implementations and algorithms

4.1: Describe the purpose of asymptotic notations (e.g., O) for algorithm analysis

4.2: Apply asymptotic notations (e.g., O) to analyze algorithms

4.3: Describe the differences between worst-case running time, expected running time, and amortized running time and apply them appropriately