Purdue University - Department of Computer Science - CS 251: Data Structures

CS 251: Data Structures

Revised June 13, 2016


CS 18200 (Foundations of Computer Science)

CS 24000 (Programming in C)

Detailed Syllabus:

1. Running time analysis of algorithms and their implementations

a. Review of proof methods and mathematics concepts

b. Mathematical induction and recursion

c. Experimental running time analysis

i. Benchmarking, counting instructions

ii. Importance of constants

d. Asymptotic running time analysis

i. Big-O and Theta notations

ii. Best, expected, worst case running times.

iii. Comparison of log n vs. constants, linear vs. quadratic vs. exponential running times.

2. Review of basic data structures

a. Abstract data types (ADTs) and common operations

i. 1- and 2-dimensional arrays; dynamic arrays

ii. Linked lists

iii. Stacks

iv. Queues

b. Comparison of different implementations of stacks and queues

3. Trees

a. Trees

i. Definitions and ADT

ii. Pointer-based implementations

iii. Different traversals and tree explorations

b. Binary trees

i. Properties of binary trees

ii. ADT

iii. Inorder traversal

iv. Representing and manipulating arithmetic expressions

4. Searching and Sorting

a. Binary search

b. Basic sorting algorithms

i. Bubble Sort

ii. Selection Sort

iii. Insertion Sort

c. Sorting Algorithms with a good performance

i. Mergesort

ii. Quicksort

d. Sorting algorithms not based on comparisons

i. Bucket and Counting sort

ii. Radix sort

5. Heaps

a. Definition, properties, ADT

b. Array implementation of heaps

c. Priority queue operations: Insertion and min/max extraction

d. Building a heap (insertions versus bottom-up heap construction)

e. Heapsort

6. Binary search trees

a. Binary search trees

i. ADT

ii. Properties and performance

iii. Basic operations including search, insert, delete

b. Balanced search trees

i. Red-black trees, 2-3 trees

ii. ADT

iii. Properties and performance

iv. Keeping a search tree balanced under insertions and deletions

7. Hashing

a. ADT and implementation

b. Hash functions

c. Collision handling schemas (open hashing, linear probing, double hashing)

d. Impact of hash table size and load factors on performance

8. Other data structures

a. Data structures for Union-Find operations

b. Spatial data structures and spatial queries

9. Strings

a. Tries

i. Representations

ii. Operations

ii. Variations: ternary and suffix tries

b. Data compression

i. Overview

ii. Generating Huffman codes

c. Substring searches and other operations on string

i. Simple algorithms

ii. Boyer-Moore, Knuth-Morris-Pratt

10. Introduction to graphs

a. Definitions, terminology, properties

b. ADT

c. Implementations

i. Edge list

ii. Adjacency list

iii. Adjacency matrix

11. Undirected graphs

a. Depth-first search

b. Breadth-first search

c. Finding connected components

12. Directed graphs

a. Depth- and breadth-first search revisited

b. Topological sorting and its applications

c. Strongly-connected components (optional)

13. Selected graph algorithms

a. Shortest paths (Dijkstra and Bellman Ford)

b. Minimum-cost spanning trees (Prim and Kruskal)

Last Updated: Apr 25, 2017 4:43 PM

Department of Computer Science, 305 N. University Street, West Lafayette, IN 47907

Phone:(765) 494-6010 • Fax: (765) 494-0739

Copyright © 2016 Purdue University | An equal access/equal opportunity university | Copyright Complaints

Trouble with this page? Disability-related accessibility issue? Please contact the College of Science.