Pre-requisite(s)

Object Oriented Programming (CS-1143)
Object Oriented Programming Lab (CS-1141)

Recommended Book(s)

Object Oriented Data Structures Using C++ By K S Easwarakumar
Data Structures Using C++ By D. S. Malik
Data Structures And Algorithm Analysis In C++ By Mark Allen Weiss\
Benjamin/Cummings Publishing Company, Inc.

Reference Book(s)

Data Structures And Algorithm In C++   By Adam Drozdek, 2nd Edition

COURSE OBJECTIVES

Main objective of this course is to enable students to understand and implement common data structures and algorithms to manipulate those data structures using C++ techniques. Emphasis will be on a lot of practice in writing codes to implement all the major data structures.

COURSE LEARNING OUTCOMES (CLO)

Course Objectives

COURSE CONTENTS

Introduction to the course and course objectives

  • What is Data Structures?
  • Why it is important to study data structures?

Linear data structures

  • Stack

What is stack?
Common stack examples.
Implementation of stack both static and dynamic
Applications of stack

  • Linked List

What is linked list?
Advantages of linked list over static list.
Implementation of linked list.
Singly linked list
Double linked list
Circular doubly linked list

  • Queue

What is a queue?
Implementation of Queue both static and dynamic
Circular queue
Priority queue
Deques

Recursion

  • What is recursion?
  • How to implement a recursion?
  • Basic Rules of Recursion

Non Linear Data Structures

  • Trees
    What are trees?
    Implementation of following type of trees.
    Binary trees
    Binary search Trees
    AVL trees
    Splay trees
    B trees

Graphs

  • What are graphs?
  • Implementation of graphs?
  • Depth first search
  • Breadth first search

Tables and Hashing

  • What are tables?
  • Index function and index table.
  • Inverted Tables
  • Hash tables
  • Hash function
  • Collision resolving techniques

Heaps

  • What is heap?
  • Priority Queue
  • Implementation of heap?
  • Heap Sort

Some searching and sorting algorithms (if time permits)

  • Basic Search
  • Binary Search
  • Quick Sort
  • Selection Sort

MAPPING OF CLOs TO ASSESSMENT MODULES

Final Exam
Assignments
Surprise Tests/Quizzes
Project
Midterm Exam