CS 301 - Data Structures

Upon successful completion of this course, the student will be able to:

• Use unit testing in software engineering
• Apply asymptotic analysis (Big-O, Big-Omega, Big-Theta) to non-recursive algorithms, considering space and time
• Apply the run-time analysis of algorithms
• Implement data structures as abstract data types (ADT)
• Apply object-oriented principles of polymorphism, inheritance, and generic programming when implementing ADTs for data structures
• Build generic Java classes with parametrized types
• Create alternative representations of ADTs either from implementation or standard libraries
• Demonstrate the ArrayList and LinkedList classes in Java Collections both from the user and developer perspectives
• Apply the following interfaces in Java Collections: Collection, List, Iterator, Comparable, Iterator
• Demonstrate execution frames for recursive algorithms and apply recursion trees to analyze the complexity of recursive algorithms
• Apply recursion as a problem solving technique
• Demonstrate the iterator and backtracking design patterns
• Discuss high-precision arithmetic implementations using ADT
• Demonstrate the Stack class, the ArrayDeque class, and the Deque interface from Java Collections in stacks applications
• Demonstrate the Queue interface in Java Collections in queue applications
• Implement algebraic expressions (infix, postfix, prefix) using stacks and queues
• Apply queues for model simulation
• Demonstrate binary trees properties: recursive definition of binary trees, full and complete binary trees, binary tree theorem, binary search tree, external path length theorem, binary tree traversals (inorder, preorder, postorder)