0512.2510   Data Structures and Algorithms

Credits: 3.5

Prerequisites: Programming in C (0512.1820) and Digital Logic Systems  (0512.3561)

Introduction: Binary Search, Order of growth of functions, Analysis of correctness and running times of algorithms.

The Sorting problem: Insertion sort, Merge sort, Quick sort, lower bound for sorting in the comparison model, sorting in linear time.

Abstract Data Types and Data Structures: stack and queue, priority queue and heap implementation, binary search trees and 2-3 trees, disjoint sets.

Algorithmic Techniques: divide and conquer paradigm, greedy algorithms, dynamic programming.

Graph algorithms: representations of graphs, searching on graphs (in particular, breadth first search), minimum spanning tree, network flow.

Textbooks:

Introduction to Algorithms (2^nd ed.),  Corman, Leiserson, Rivest, Stein
(or Introduction to Algorithms (1^st ed.),  Corman, Leiserson, Rivest                     (

Data Structures and Algorithms,  Aho, Hopcroft, and Ullman