Pre-requisite(s)

Object Oriented Programming (CS-1143)

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