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
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
Department of Computer Science and Software Engineering
