Algorithms and Data Structures

Course Description

Algorithms and data structures emphasizes the following topics: data structures, abstract data types, recursive algorithms, algorithm analysis, sorting and searching, and problem-solving strategies. Labs alternate weeks.

Course Objectives

Introduce the student to the concept of data structures through abstract data structures including lists, sorted lists, stacks, queues, deques, sets/maps, directed acyclic graphs, and graphs; and implementations including the use of linked lists, arrays, binary search trees, M-way search trees, hash tables, complete trees, and adjacency matrices and lists.

Introduce the student to algorithms design including greedy, divide-and-conquer, random and backtracking algorithms and dynamic programming; and specific algorithms including, for example, resizing arrays, balancing search trees, shortest path, and spanning trees.

Suggested Texts and Readings

Cormen, Leiserson, Rivest, and Stein (CLRS), Introduction to Algorithms, 2nd Ed., MIT Press, 2001.

Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, 3rd Ed., Addison Wesley, 2006.

For a free online reference to C++, consider Bruce Eckel's Thinking in C++ 2nd Ed., Volumes 1 and 2. You will find a link to a download site. Of course, if you like the book, you always have the option of purchasing it. Other online resources are at http://www.cplusplus.com:

• A Tutorial,
• A Brief Description,
• A Brief History of C++,
• An FAQ, and
• A Collection of Links.

Download Power Point Slides

1. Introduction and Review

• Introduction
• Mathematical Review
• C++
• Mathematical Induction

2. Algorithm Analysis

• Data Structures and Containers
• Data Relations
• Data Storage
• Data Operations
• Asymptotic Analysis
• Algorithm Analysis

3. Lists, Stacks, and Queues

• Lists
• Stacks
• Queues
• Deques
• Linked Lists (optional reading for Laboratory 1)

4. Trees

• Introduction to Trees
• Abstract Trees
• Tree Traversals
• Binary Trees
• Perfect Binary Trees
• Complete Binary Trees
• N-ary Trees
• Binary Search Trees
• Balanced Trees
• AVL Trees
• M-Way Trees
• B-Trees
• Red-Black Trees (optional)
• kd-Trees (optional)
• Weight-Balanced Trees (optional)
• Splay Trees (self study)
• Binomial Trees (optional)

5. Priority Queues

• Priority Queues (Spanish/Español translated by Christian von Lücken)
• Binary Heaps (Spanish/Español translated by Christian von Lücken)
• d-ary Heaps (optional)
• Leftist Heaps (optional)
• Skew Heaps (optional)
• Binomial Heaps (optional)

6. Hash Tables

• Introduction to Hash Tables
• Hash Functions
• Mapping Down to 0, ..., M - 1
• Hash Tables
• Open Addressing
• Linear Probing
• Quadratic Probing (optional)
• Double Hashing

7. Sorting Algorithms

• Introduction to Sorting
• Insertion Sort
• Bubble Sort
• Heap Sort
• Merge Sort
• Quick Sort
• Bucket Sort
• Radix Sort
• Inversions (optional)

8. Disjoint Sets

• Disjoint Sets (self study)

9. Graph Algorithms

• Introduction to Graph Theory
• Topological Sort (Spanish/Español translated by Christian von Lücken)
• Minimum Spanning Tree Algorithms (Spanish/Español translated by Christian von Lücken)
• Shortest Path Algorithms
• Graph Traversals (connectiveness and bipartite graphs) (optional)
• A* Search Algorithm (optional)

10. Algorithm Design

• Introduction to Algorithms
• Greedy Algorithms
• Divide and Conquer
• Dynamic Programming
• Randomized Algorithms
• Backtracking Algorithms

11. Additional Topics

• NP Completeness
• Sparse Matrices

Concluding Remarks

• Summary and Conclusions