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

Inheritance and Polymorphism, exceptions, and interfaces

List ADTs and the Collections Framework

Arrays, Linked Lists, and Recursion

Using Arrays

Singly Linked Lists

Doubly Linked Lists

Recursion

Analysis Tools

The Seven Functions Used in The Book

Analysis of Algorithms

Stacks and Queues

Stacks

Queues

Double-Ended Queues

Trees

General Trees

Tree Traversal Algorithms

Binary Trees

Priority Queues

The Priority Queue Abstract Data Type

Implementing a Priority Queue with a List

Heaps

Adaptable Priority Queues

Maps and Dictionaries

The Map Abstract Data Type

Hash Tables

Search Trees

Binary Search Trees

AVL Trees

Sorting, Sets, and Selection

Merge-Sort

Quick-Sort

A Lower Bound on Sorting

Bucket-Sort and Radix-Sort

Comparison of Sorting Algorithms

Introduction to graphs