EECS 2510 - Nonlinear Data Structures Course Syllabus
Credits/Contact Hours
4 credit hours & 3 50-minute lecture contact hours per week.
Textbook
The required textbook for this course is a web-based interactive zyBook
Other Related textbooks:
- Anany Levitin. Introduction to the Design and Analysis of Algorithms, 3rd edition, Pearson, 2012. ISBN 13: 978-0137541133.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,. Introduction to algorithms, 3rd edition, MIT Press, 2009. ISBN-13: 978-0262033848
- Pat Morin, Open Data Structures: An Introduction (C++ edition). Freely available in HTML and PDF formats at https://opendatastructures.org/. This textbook is open source and comes with C++ source code (beta version).
Course Information
The data structures introduced in EECS 2500 are extended to include trees (binary,
balanced, and n-ary), graphs, and advanced sorting techniques. In addition, the C++
language is used as the main vehicle and is introduced in the course. Students are
expected to have a strong background in Java prior to this course.
Prerequisites:
Undergraduate level EECS 2500 (Linear Data Structures): Minimum grade of C-
Undergraduate level EECS 2520 (Discrete Structures): Maybe taken concurrently – with a minimum grade of C-
Required course for CSE program
Specific Goals - Student Learning Objectives (SLOs)
Upon successful completion of this course, the student will be able to:
- Use an IDE.
- Learn how to construct and apply a binary (and n-ary) tree to the storage, organization, and lookup of data using C++.
- Learn how to implement special cases of binary trees, such as parse trees, height-balanced trees, and B-trees to solve problems.
- Learn how to apply O(nlogn) and O(n) sorting methods to data.
- Learn the fundamentals of input and output using streams in C++.
- Learn how to use pointers in C++ effectively.
- Learn how to solve a limited class of recurrence relations.
- Learn how to apply graphs and their related algorithms including single source, all-pairs shortest paths, and minimum spanning tree algorithms to solve practical problems.
- Learn how to implement heaps and its use in priority queues.
Topics
- Data structures
- Introduction to algorithms
- Relation between data structures and algorithms
- Abstract data types (ADTs)
- Algorithm efficiency
- Searching and algorithms
- Binary search
- Growth of functions and complexity
- O notation
- Algorithm analysis
- Analyzing the time complexity of recursive algorithms
- Sorting algorithms
- Bucket sort
- Radix sort
- Overview of fast sorting algorithms
- List abstract data type (ADT)
- Linked lists
- Hash tables
- Common hash functions
- Direct hashing
- Binary trees
- Application of trees
- Binary search trees
- BST search algorithm
- BST insert algorithm
- BST remove algorithm
- BST height and insertion order
- BST parent node pointers
- BST: recursion
- AVL: A balanced tree
- Red-black tree: A balanced tree
- Heaps and Heap sort
- Priority queue abstract data type (ADT)
- Treaps
- Graphs: Introduction
- Applications of graphs
- Graph representations: Adjacency lists
- Graph representations: Adjacency matrices
- Directed graphs
- Weighted graphs
- Graphs: Breadth-first search
- Graphs: Depth-first search
- Algorithm: Dijkstra’s shortest path
- Algorithm: Bellman-Ford’s shortest path
- Topological sort
- Minimum spanning tree (MST)
- Algorithm: Kruskal’s MST
- Algorithm: Prim’s MST
- All pairs shortest path
- Algorithm: Floyd-Warshall’s all-pair shortest path
- Huffman compression
- Heuristics
- Greedy algorithms
- Dynamic programming
- B-trees
- 2-3-4 tree search algorithm
- 2-3-4 tree insert algorithm
- 2-3-4 tree rotations and fusion
- 2-3-4 tree removal