CS 203/MA 213: Data Structures and Algorithms

Course Outline:

•  Introduction to Data Structure and Algorithms   

  • Basic Data types 

  • Overview of Data Structures

  • Abstract Data type

  • Algorithm and Analysis

  • Run time and Space Complexity

  • Compare algorithms

    • Asymptotic Notations and Analysis

    • Divide and Conquer: Substitution, Recurrence and Masters Theorem

• Basic Data Structure

  Array 

• • • • • • Searching (linear, binary), 

          • Sorting (Insertion, Selection, Bubble, Quick, Merge, Linear time sorting: Bucket, Radix, Count), 

          • Comparative Analysis

          • Order Statistics

          Linked List

• • • • • Single linked list, 

        • Difference- Array and Linked List

        •  Doubly linked list, Circular linked list

          Stacks 

• • Introduction, Implementation and Applications

  • Use in expression evaluation and Recursion

          Queues

• • Introduction, Implementation and Applications, Difference with stack

  • Circular Queue

  • Doubly-ended Queue

          Priority Queue (PQ) and Heap

• • PQ introduction and implementation

  • Introduction to heap (max, min) and binary heap

  • Heapsort

 Hashing

• Introduction

• Components of Hashing, Hash Table

• Hash functions

• Collision Resolution techniques

• Comparison of Collision Resolution techniques

Tree 

• • Introduction

  • Binary Tree, Binary Search Tree (BST)

  • Traversals in BST: Inorder, Preorder, Postorder

  • Height Balanced Tree: AVL, Red-Black

  • B-Tree: Introduction

          Special Data Structures

• • Disjoint Sets

  • Union Find

•  Graph Algorithms

  • • Graph representation, 

    • Graph traversal – breadth-first search, depth-first search

    • Topological ordering (sorting)

    • Shortest Path algorithms

    • Minimum Spanning Tree (brief introduction)

     Some Advanced Topics (If time permits)

• Tries

• Skip Lists

• Advanced Algorithms: Dynamic Programming (May be taught as part of Lab)

Textbooks:

1. Cormen book

2. Seymour Lipschutz. Data Structures with C. Schaum's Outlines.

3. Karumanchi, Narasimha. Data Structures and Algorithms Made Easy: 700 Data Structure and Algorithmic Puzzles. CreateSpace, 2011. 

Reference Materials:

1. Algorithms by Robert Sedgewick