Course: Data Structures (3408) Semester: Spring, 2012
Level: BS (CS) Total Marks: 100
Pass Marks: 50
ASSIGNMENT No. 1
(Units: 1–4)

Note: All questions are compulsory. All questions carry equal marks.

Q. 1 (a) Define data structure. Name and explain different types of data structure. Explain operations that can be performed on these data structures.
(b) What is an algorithm? What is time and space analysis of an algorithm? Elaborate the concept of the best, average & worst cases analysis.

Q. 2 (a) What are the principle differences between arrays and structures? How address calculations are performed for the access of an item for each?
(b) A dynamically declared array A is defined with row and column subscripts varying from 1 to 5. Give the storage mapping function to map A into memory assuming column-major and row-major storage order.

Q. 3 (a) Define and explain stack. Give representation of a stack in memory.
(b) Write an algorithm and a program for the insertion (push) and deletion (pop) of an element from a stack.

Q. 4 (a) What are infix, postfix and prefix notations? Write an algorithm for the conversion of infix expression to polish or reverse polish expression.
(b) Give a trace for the translation of given infix string to polish and reverse polish string. A / B – C * D + A

Q. 5 (a) Define and explain queue and de-queue. Give memory representation of each.
(b) Formulate an algorithm and a program for the insertion and deletion of an element from a queue.
ASSIGNMENT No. 2
(Units: 5–8)
Total Marks: 100 Pass Marks: 50

Note: All questions carry equal marks.

Q. 1 (a) What is linked list? What are its types? Give representation of a linked list in memory.
(b) Formulate an algorithm to insert an element at the start of the linked list and to delete an element from the middle of the linked list.

Q. 2 (a) Define arid explain tree and its types. Give linked representation of a binary tree in memory.
(b) Formulate an algorithm and a program for the pre-order, post-order and in-order traversal of binary tree. Illustrate with the help of diagrams.

Q. 3 (a) Give time complexities of Bubble sort, Insertion sort, Selection sort, Quick sort, Merge sort, Radix sort, Binary search, and Sequential search in tabular form.
(b) Give trace of Bubble sort, Insertion sort, and Selection sort using one suitable example for each.

Q. 4 (a) Give trace of Binary search and Sequential search using examples.
(b) What is a graph and what are its types? Give matrix and adjacency list representation of an example graph in memory?

Q. 5 Explain each step with graph example for the trace of Breadth first search and Depth first search graph traversal algorithms.

3408 Data Structure Credit Hours: 4 (4+0)

Recommended Book:
Introduction to Data Structure with Application by Paul Trembley Sorenson

Course Outlines:
Unit No. 1 Introduction
Basic Terminologies, Introduction to Data Structures, Data Structure (Classification, Types, Operation), Basics of Algorithms, Notation used, Importance of Algorithms for Optimized Application Development, Introduction to Analysis of Algorithms

Unit No. 2 Arrays
Arrays (Definition and Examples), Representation of array in Memory, Accessing & Traversing Array, Inserting & Deleting, Multi Dimensional Arrays & their Representation in Memory

Unit No. 3 Stacks
Stack, Importance of Stack, Array Representation of Stacks, Stack Operations (PUSH and POP operations), Infix, Postfix and Prefix Expressions

Unit No. 4 Queues
Queue, Representation of Queues, Operation Perform on Queue (Inserting and Removing Nodes), De-queues, Priority queues

Unit No. 5 Linked Lists
Linked Lists Concept, Representation of Linked Lists in Memory, Traversing & Searching a Lined List Insertion & Deletion in Linked List, types of Linked Lists

Unit No. 6 Trees
Tree, Tree Types (simple, Binary, General), Representation of Binary Tree in Memory, Traversing (Pre order, In order), Basic Operation (Insertion Deletion)

Unit No.7 Sorting & Searching
Bubble Sort, Quick Sort, Insertion Sort, Selection Sorting, Sequential Search, Binary Search

Unit No. 8 Graphs
Graph Theory Terminology, Linked Representation of Graphs, Directed and Undirected Graphs, Traversal Methods

Unit No. 9 Files and Data Storage
Basic Operations on Different Files Organizations, Add, Update and Delete Record, File Organizations, Sequential, Indexed Sequential, Direct (Hashing), Merging Files

Sponsored Links