Skip to main content
CPE
207
Data Structures
This course introduces fundamental data structures (stacks; queues; linked lists; hash tables; trees; graphs), Basic algorithmic analysis (asymptotic analysis; identifying differences among best, average, and worst case, empirical measurements of performance; time and space tradeoffs in algorithms), Fundamental computing algorithms, sorting algorithms; hash tables and hashing, heaps, priority queues, binary search trees, balanced binary search trees, AVL trees; representations of graphs and graph traversals, Recursion. The course includes weekly laboratory sessions providing hands-on experience in designing and implementing application of data structures and algorithms to engineering.
Prerequisites:
0612201,0612203
0612207
(3-2-3)

Credits and Contact Hours

3 credits, 43 hours

Course Instructor Name

Dr. Ameer Mohammed

Textbook

  • Data Structures and Algorithms in Java, Michael T. Goodrich and Roberto Tamassia, 6th Edition
  • References
  • Data Structures and Algorithms in Java by Robert Lafore, 2nd Edition, Sams Publishing 2002.
  • Data Structures and Abstractions with Java by Frank Carrano and Timothy Henry, 5th Edition, Pearson 2018.

Catalog Description

Fundamental data structures (stacks; queues; linked lists; hash tables; trees; graphs), Basic algorithmic analysis (asymptotic analysis; identifying differences among best, average, and worst case, empirical measurements of performance; time and space tradeoffs in algorithms), Fundamental computing algorithms, sorting algorithms; hash tables and hashing, heaps, priority queues, binary search trees, balanced binary search trees, AVL trees; representations of graphs and graph traversals, Recursion. The course includes weekly laboratory sessions and a significant programming project with detailed documentation and implementation.

Prerequisite

CpE-201 and CpE-203

Specific Goals for the Course

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

  • Write and debug complex programs using data structures and object-oriented programming techniques. (Student outcomes: 1, 6)
  • Design and implement relatively large software. (Student outcomes: 1, 6)
  • Solve problems using advanced object-oriented concepts (inheritance, polymorphism, interfaces) and generic programming (templates). (Student outcomes: 1, 6)
  • Identify and implement basic data structures (stacks, queues, lists, trees, hash tables) and their applications. (Student outcomes: 1, 6)
  • Understand and apply the concept of algorithmic complexity (big-O). (Student outcomes: 1)
  • Implement and compare several standard sorting algorithms. (Student outcomes: 1, 6)
  • Understand and implement linear and binary search algorithms. (Student outcomes: 1, 6)
  • Analyze simple algorithms and discuss tradeoffs among data structures. (Student outcomes: 1, 6)

Topics to Be Covered

Object-Oriented Design Priority Queues
Inheritance and Polymorphism, exceptions, and interfaces The Priority Queue Abstract Data Type
List ADTs and the Collections Framework Implementing a Priority Queue with a List
Arrays, Linked Lists, and Recursion Heaps
Using Arrays Adaptable Priority Queues
Singly Linked Lists Maps and Dictionaries
Doubly Linked Lists The Map Abstract Data Type
Recursion Hash Tables
Analysis Tools Search Trees
The Seven Functions Used in The Book Binary Search Trees
Analysis of Algorithms AVL Trees
Stacks and Queues Sorting, Sets, and Selection
Stacks Merge-Sort
Queues Quick-Sort
Double-Ended Queues A Lower Bound on Sorting
Trees Bucket-Sort and Radix-Sort
General Trees Comparison of Sorting Algorithms
Tree Traversal Algorithms Introduction to graphs
Binary Trees