Course Description: An introduction to the design, analysis, and implementation of data structures. This course teaches you how to build, test, debug, document, and evaluate objects that encapsulate data and their associated operations using programming constructs and data abstractions of a modern programming language. Concepts and techniques covered include linear and non-linear structures, recursive structures and algorithms, traversal algorithms, binary search trees, balanced trees, priority queues, union-find, hash tables, Bloom filters, and graphs. We will also informally compare and contrast the run time efficiency of algorithms and their performance characteristics including the concept of worst-case running time analysis and the classification of algorithms in terms of constant, logarithmic, linear, log linear, quadratic, and exponential time using Big-O notation.
Prerequisites: CICS 160 or INFO 190T with a grade of C or better.
Learning Outcomes: At the completion of this course you will be able to: Design, implement, and analyze fundamental abstract data types and data structures such as lists, stacks, queues, priority queues, trees, sets, hash tables, union-find, heaps, Bloom filters, and graphs; Define and implement recursive structures and algorithms over those structures; Demonstrate an understanding of iteration and traversal to implement iterators for the aforementioned data structures; Define and implement the operations and algorithms associated with fundamental data structures; Compare data structure tradeoffs to select the appropriate implementation for an abstract data type; Informally explain, compare, and contrast the run time efficiency of algorithms and their performance characteristics including the concept of worst-case running time analysis and the classification of algorithms in terms of constant, logarithmic, linear, log linear, quadratic, and exponential time; Explore and use various programming abstraction techniques including object-oriented and functional approaches to implement data structures; Identify and remedy flaws in a data structure implementation that may cause its behavior to differ from the intended design through debugging and testing; Increase your proficiency in writing code including designing, documenting, writing, testing, and debugging.
Language used: Java
Draft Syllabus: CICS 210 Syllabus.pdf
Topics Covered:
- Introduction to Data Structures and Algorithms (Java, abstract data types, generics)
- Linear Structures Review: Stacks and Queues (array and linked implementations)
- Big O Analysis, Searching and Algorithm Analysis (linear, binary search)
- Amortization and Extendable Arrays
- Trees (binary search trees)
- Balanced Trees (AVL and B-trees)
- Priority Queues (heaps and treaps)
- Union-Find / Merge Sort
- Hash Tables
- Bloom Filter
- Graphs (BFS and DFS search algorithms)