CSE326: Data Structures

4

Data types, abstract data types, and data structures. Efficiency of algorithms. Sequential and linked implementation of lists. Binary tree representations and traversals. Searching: dictionaries, priority queues, hashing. Directed graphs, depth-first algorithms. Garbage collection. Dynamic storage allocation. Internal and external sorting. No credit to students who have completed CSE 373, CSE 374, or E E 374.

CSE 321.

Abstract data types and their implementations as data structures. Efficient algorithms employing these data structures, together with their asymptotic analyses. Dictionaries: balanced search trees and hashing. Priority queues: heaps. Disjoint sets with union and find. Graph algorithms: shortest path, minimum spanning tree, topological sort, depth-first and breadth-first search. Sorting. No credit to students who have completed CSE 373, CSE 374, or EE 374.

Data Structures and Algorithm Analysis in Java 2nd Ed., Mark Allen Weiss, Addison Wesley: 2007, ISBN: 0-321-37013-9

The objective of this class is to study the fundamental abstract data types and their implementations as data structures, together with efficient algorithms employing these data structures and their asymptotic analyses.

1. Introduction: Data Structures, Abstraction, Recursion 2. Algorithm Analysis 3. Dictionary Abstract Data Type 4. Search Trees: Binary, AVL, 2-3, Splay, B-trees 5. Hashing 6. Priority Queues: Heaps 7. Disjoint Sets: Weighted Union and Find with Compression 8. Sorting: Heapsort, Mergesort, Quicksort, Decision Trees 9. Graph Algorithms and Graph Representations

3 hours per week of lecture 1 hour per week of discussion section

(m) knowledge of discrete mathematics

(a) an ability to apply knowledge of mathematics, science, and engineering

(e) an ability to identify, formulate, and solve computer engineering problems

(k) an ability to use the techniques, skills, and modern computer engineering tools necessary for engineering practice

rea