ECE 36800 - Data Structures

Lecture Hours: 3 Credits: 3

Professional Attributes
CMPE Core
EE Elective

Normally Offered: Each Fall, Spring

Requisites:
ECE 26400 Minimum Grade of C

Catalog Description:
Provides insight into the use of data structures. Topics include stacks, queues and lists, trees, graphs, sorting, searching, and hashing.

Course Objectives:
To provide insight into the use of data structures. To prepare the students for advanced software courses. Students use their previous programming experience to design and test software as part of team projects using sorting, searching, tree-based and graph-based techniques learned in this course.

Required Text(s):
  1. Algorithms in C, Part 5: Graph Algorithms, 3rd Edition, Robert Sedgewick, Addison Wesley, 2001, ISBN No. 9780201316636.
  2. Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, 3rd Edition, Robert Sedgewick, Addison Wesley, 1997, ISBN No. 9780201314526.

Recommended Text(s): None.

Learning Outcomes:

A student who successfully fulfills the course requirements will have demonstrated:
  1. an understanding of various basic data structures, including stacks, queues, and trees. [1,6]
  2. an ability to analyze time complexity and space complexity of algorithms. [1,6]
  3. an ability to apply appropriate sorting and searching algorithms for a given application. [1,2,6]
  4. an ability to apply graph theoretic techniques, data structures and algorithms for problem solving. [1,2,6]
  5. an ability to design and implement appropriate data structures and algorithms for engineering applications. [1,2,6]

Lecture Outline:

Hours Major Topics
1 Introduction
3 Complexity and Asymptotic Notation
6 Stacks, Queues, Deques; Abstract Data types; Implementation; Arrays, Pointers, Linked Lists; Applications
3 Stack and Recursion
9 Sorting; Exchange, Selection, Tree, Insertion, Merge
7 Searching; Sequential, Binary, Tree, and Hashing; Balanced Trees, B-Trees, Tries
11 Graphs; Graph Traversal, PERT Diagrams, Spanning Trees, Shortest Paths
2 Advanced Topics: Greedy Algorithms (e.g., Huffman Coding) and Dynamic Programming (e.g., Optimal Search Tree, 0-1 Knapsack Problem)
2 Tests

Engineering Design Content:

Synthesis
Analysis
Construction
Testing
Evaluation