Home Courses

Data Structures

# Data Structures

Teacher

Category

### Course Attendees

Still no participant

Still no reviews

# Code(Credit) :CUTM 1603 (1-2-1)

## Course Objectives

• Be familiar with techniques of algorithm analysis and Recursive method
• Be familiar with implementation of linked data structures such as linked lists and binary trees
• Be familiar with several sub-quadratic sorting algorithms including quick sort, merge sort and heap sort
• Be familiar with some graph algorithms such as shortest path and minimum spanning tree

## Learning Outcomes

 Cos Course Outcome Mapping COs with POs (High-3, Medium-2, Low-1) Co1 Able to gain the knowledge to evaluate algorithms and data structures in terms of time and memory complexity of basic operation steps PO1-3 Co2 Ability to formulate programs that cover basic static and dynamic data structures, and relevant algorithms PO2-3 Co3 Able to solve different problems such as search and sorting algorithms, traversal techniques, etc. PO2-3, PO3-3 Co4 Design and demonstrate bugs in program, recognize needed basic operations with hands-on PO3-3, PO5-2

## Course Syllabus

Module I:Basics Of Data Structures and Array (06 hrs)
Data Structures, Types of Data Structures,  Algorithm analysis, Complexity Analysis :Time complexity and Space complexity , Asymptotic Notations (Big Oh, Big Omega, Big Theta, Little Oh, Little Omega), Data Structure Operations, Application of Data structures.

Arrays: Memory Representation of an array, Operations on an array.

Programs:
1.Write a program to perform the following menu driven program on the input array.
a. Insertion
b. Deletion
c. Searching
d. Sorting
e. Merging
f. Display
g. Exit

Module II: Stack & Queue (12 hrs)
Stacks, operations on stack and its applications ( Infix to Postfix Conversion, Infix to prefix conversion, Prefix evaluation and Postfix Evolution).

Queues, Operations on Queue, De-queues, Operations on Dequeue, Priority Queues .

Programs:

1.Write a program to perform the following menu driven program on the STACK.
a. Push
b. Pop
c. Display
d. Exit

2. Write a program to perform the following menu driven program on the Queue.
a. Insertion
b. Deletion
c. Display
d. Exit

Module III: Linked List (14 hrs)

Programs:

1.Write a program to create a single linked list perform the following menu driven program.
a. Insertion at front
b. Insertion at end
c. Insertion at particular position
d. Deletion at front
e. Deletion at end
f. Deletion at particular position
g. Display

2.Write a program to create a circular linked list perform the following menu driven program.
a. Insertion at front
b. Insertion at end
c. Insertion at particular position
d. Deletion at front
e. Deletion at end
f. Deletion at particular position
g. Display

3.Write a program to create a Double linked list perform the following menu driven program .
a. Insertion at front
b. Insertion at end
c. Insertion at particular position
d. Deletion at front
e. Deletion at end
f. Deletion at particular position
g. Display

Module IV: Stack & Queue Implementation Using Linked List (4 hrs)
Stack implementation using Linked List and Queue implementation using Linked List and operations.

Programs:

1.Write a program to implement Stack Using Linked List.
2.Write a program to implement Queue Using Linked List.

Module V: Trees (12 hrs)
Trees and hierarchical orders ,Introduction to trees ,Representation of tree,  Abstract trees , Tree traversals , Forests , Ordered trees , Binary trees , Perfect binary trees , Complete binary trees , Search trees : Binary search trees , AVL trees.

Programs:
1.Write a program to create Binary tree and display it .
2. Write a program to create a BST and display it.
3. Write a program to Print all pairs from two BSTs whose sum is greater than the given value.
4.Write a program to remove duplicate entries from the BST.
5.Write a program to create a AVL tree and display it.

Module VI: Searching & Sorting (14 hrs)
Searching & Sorting algorithms , Objectives of Searching , The Sequential Search , Analysis of Sequential Search , The Binary Search , Analysis of Binary Search , Introduction to sorting , Insertion sort , Bubble sort , Heap sort ,Merge sort ,Quick sort, Radix Sort.

Programs:
1.Write a program to perform linear and binary search.
2. Write a program to perform selection sort , Bubble sort and Insertion sort.
3. Write a program to perform merge and quick sort.
4.Write a program to perform Heap sort.

Module VII: Graphs and Hashing (8 hrs)

Graph Terminology, Graph Traversal Techniques: Breadth First Search, Depth First Search, Hashing: Introduction to hash tables, Hash functions, Collision Resolution : Chained hash tables, Linear Probing.

Programs:
1.Write a program to perform Linear Probing.
2. Write a program to perform Double Hashing

Text Books:

1. Data Structures, Algorithms and Applications, Sartaj Sahani, 2nd Edition.
2. Data Structures and Algorithms, Michael T.Goodrich, R, Tamassia and D.Mount, wiley Student Edition, 7th edition, John Wiley and Sons.

Reference Books:

1. Data Structures and Algorithms Analysis by Mark Allen Weiss.
2. Data Structures and Algorithms, 3rd edition, Adam Drozdek, Cengage Learning.

Projects:

• Contact book application using Doubly Linked List
• Dictionary using Binary trees
• Snake Game
• Chess Game
• AVL -Insertion and Deletion
• Travel Planner (Graphs)
• Tic-Tac-Toe Game
• Library Management System
• Project Management System
• User Defined (Student Choice)

## Session 1

Introduction to problem solving Video Source-ClickHere      Content Source-ClickHere

## Session 2

Find Creative Solutions using creativity tools Video Source-ClickHere      Content Source-ClickHere

## Session 3

Evaluate and Select solution Video Source-ClickHere      Content Source-ClickHere

## Session 4

Implementing Decisions Video Source-ClickHere      Content Source-ClickHere

## Session 5

Practice : Module 1 - Programs Using Raptor tool Video source: click here

## Session 6

Project: Group Identification and Project Distribution

## Session 7

Asymptotic analysis Video Source-ClickHere      Content Source-ClickHere

## Session 8

Applications of Data Structure Video Source-ClickHere      Content Source-ClickHere

## Session 9

Introduction to data structures in c++ Video Source-ClickHere      Content Source-ClickHere

## Session 10

Types of data structures Video Source-ClickHere      Content Source-ClickHere

## Session 12

Practice : Module 2 - Program-1

## Session 14

Applications of Stack Video Source-ClickHere      Content Source-ClickHere

## Session 15

Practice : Module 2 - Program 2

## Session 16

Project: Review  (Abstract , Existing System , Proposed System and Requirement Analysis)

## Session 17& 18

Queues , Priority Queues Video Source-ClickHere      Content Source-ClickHere

## Session 19

Practice : Module 3 - Program - 1

## Session 20 & 21

Single linked lists Video Source-ClickHere      Content Source-ClickHere

## Session 22

Practice : Module 3 - Program -2

## Session 23

Project: Review (Design phase)

## Session 24 & 25

Double linked lists Video Source-ClickHere      Content Source-ClickHere

## Session 26

Practice : Module 4 - Program - 1

## Session 27

Circular linked lists Video Source-ClickHere      Content Source-ClickHere

## Session 28

Practice : Module 4 - Program - 2

## Session 29

Stack using Linkedlist Video Source-ClickHere      Content Source-ClickHere

## Session 30

Queue using LinkedlistVideo Source-ClickHere      Content Source-ClickHere

## Session 31

Practice : Module 4 - Program - 3,4

## Session 31

Non linear data structures Video Source-ClickHere      Content Source-ClickHere

## Session 32

Introduction to Trees Video Source-ClickHere      Content Source-ClickHere

## Session 33

Abstract Trees, Tree traversals Video Source-ClickHere      Content Source-ClickHere

## Session 35

Binary Search Trees Video Source-ClickHere      Content Source-ClickHere

## Session 36

Practice : Module 5 - 1,2,3,4 Programs

## Session 39

Practice : Module 5 - Program-5

## Session 40

Project: Review (Coding Phase)

## Session 41

Introduction to searching & sorting algorithms Video Source-ClickHere      Content Source-ClickHere

## Session 42

The sequential search Video Source-ClickHere      Content Source-ClickHere

## Session 43

The Binary search Video Source-ClickHere      Content Source-ClickHere

## Session 44

Practice : Module 6 - Program -1

## Session 50

Heap & Radix Sort Video Source-ClickHere      Content Source-ClickHere

## Session 51

Project: Review (Testing and Implementation)

## Session 53

Linear and quadratic ProbingVideo Source-ClickHere      Content Source-ClickHere

## Session 54

Collision Resolution Video Source-ClickHere      Content Source-ClickHere

## Session 55

Graph traversals Video Source-ClickHere      Content Source-ClickHere

## Session 56

Practice : Module 7 - 1,2 Programs

## Session 57

Project: Review ( Documentation , Execution )

VIEW PROFILE