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鈥檚 shortest path听
- Algorithm: Bellman-Ford鈥檚 shortest path听
- Topological sort听
- Minimum spanning tree (MST)听
- Algorithm: Kruskal鈥檚 MST听
- Algorithm: Prim鈥檚 MST听
- All pairs shortest path听
- Algorithm: Floyd-Warshall鈥檚 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听