# Data Structures

#### Description

Abstract data types, objects, algorithm design and analysis, trees, graphs, sorting and searching. Emphasis on ADT-based and object-oriented design, incremental development and testing, and comparison of data structure implementations. Offered in fall, spring.

#### Prerequisites

C- or higher in CSCI 140 and CSCI 162

#### Course Outcomes

At the end of this course, a successful student will be able to

1. implement elementary data structures such as linked lists, stacks, queues, and binary trees;
2. apply a variety of more advanced data structures, such as hash tables, balanced search trees, and graphs, to solve problems;
3. perform simple algorithm complexity analyses;
4. formulate divide-and-conquer algorithms using recursion; and
5. describe the importance and key points of a code of ethics.

#### Major Topics Covered

1. Review
1. Abstract data types
2. Pointers and memory management
3. Lists
4. Stacks
5. Queues
6. Binary Trees
7. Library support for data structures
2. Extending basic data structures
3. Circular lists
2. Priority queues
3. N-ary trees
4. Heaps
3. Algorithm Design
1. Recursive algorithms
2. Divide and conquer algorithms
3. Greedy algorithms
4. Algorithm Complexity
1. Complexity model
2. Analyzing complexity
3. Profiling program execution
5. Trees
1. Implementations
2. Traversals
3. Balanced trees (e.g. AVL, Red-Black, 2-3-4)
4. Applications
6. Associative data structures
1. Sets
2. Maps
3. Hash Tables
4. Applications
7. Graphs
1. Implementations
3. Path algorithms
4. Applications (e.g. topological sort, minimum spanning tree, shortest path)
8. Sorting
1. Insertion sort
2. Selection sort
3. Quick sort
4. Merge sort
5. Heap sort
9. Searching
1. Linear search
2. Binary search
10. ACM code of ethics

#### Sample Laboratory Projects

1. Write a short program that uses a Stack ADT to reverse an input string.
2. Using a Binary Search Tree, write a program to build an index to a block of English text. Print the index and the resulting tree.
3. Develop your own Binary Search Tree ADT. Link it to the program developed in Lab #2.
4. Using a backtracking algorithm, develop a recursive solution to the Eight-Queens problem.
5. Use the AVL algorithm to develop height-balanced trees. Use this ADT in place of the Binary Search Tree ADT of Lab #3. Compare the resulting binary tree using AVL balancing versus that obtained in Lab #3.
6. Use hash tables with separate chaining to implement a spell checker. Compare the performance with using a balanced search tree.