Carl Sable

Catalog Data:

An introduction to fundamental data structures and algorithms, with an emphasis on practical implementation issues and good programming methodology. Topics include lists, stacks, queues, trees, hash tables and sorting algorithms. Also an introduction to analysis of algorithms with big-O notation. Assignments include programming projects and problem sets.

Topics:

1. Introduction and course overview.
2. Mathematical tools for the analysis of algorithms.
3. Overview of C++ and object oriented programming concepts.
4. Lists, stacks, and queues.
5. Sorting: simple quadratic sorts (bubble sort, selection sort, and insertion sort); linearithmic searches (mergesort and quicksort); radix sort; indirect sort; selection algorithms.
6. Trees: general trees and terminology; binary trees; binary search trees; balanced binary search trees; B+ trees.
7. Hash tables.

Course Outcomes:

This course provides both a theoretical understanding of fundamental data structures and algorithms as well as practical knowledge as to when each is the most appropriate for a specific task. Students learn how to use asymptotic analysis to analyze algorithms and compare worst-case or average-case efficiencies. They become comfortable implementing important data structures and algorithms from scratch, as well as applying existing implementations of data structures and algorithms to solve more general problems.

Students will attain:

1. In depth understanding of fundamental data structures and algorithms.
2. Understanding of the analysis of the time complexities and memory requirements of algorithms.
3. Ability to efficiently implement data structures and algorithms from scratch.
4. Ability to apply data structures and algorithms to solve complex problems.

Assessment Methods:

Individual programming assignments to ensure that students can implement fundamental data structures and algorithms from scratch to solve complex problems; problem sets to test in-depth knowledge involving subtleties of the covered topics.