Course Curriculam

Course Code: CSIT365 Credit Units L T P/S SW AS/DS FW No. of PSDA Total Credit Unit
Course Level UG 3 0 2 2 0 0 0 5
Course Title Analysis of Algorithms and Data Structures

Course
Description :

Course Objectives :

SN
Objectives
.
The aim of this course is to ? Impart in-depth knowledge of data structure and its implementation in computer programs. ? Make students understand
1
the concepts of linear and nonlinear data structure. ? Illustrate asymptotic notations and their usage.

Pre-Requisites : General

SN. Course Code Course Name

Course Contents / Syllabus :

Modul
SN. Descriptors / Topics Weightage
e
Module Introduction: Basic Design and Analysis techniques of Algorithms, Correctness of Algorithm, Algorithm Design Techniques:
1 12.00
I Iterative techniques, Divide and Conquer, Dynamic Programming, Greedy Algorithms.
Module Sorting Techniques: Elementary sorting techniques-Bubble Sort, Insertion Sort, Merge Sort, Advanced Sorting techniques-
2 13.00
II Heap Sort, Quick Sort, Sorting in Linear Time-Bucket Sort, Radix Sort and Count Sort.
Module
3 Searching Techniques and Complexity Analysis::Linear and Binary search, Medians & Order Statistics. 12.00
III
Module
4 Arrays Arrays: Single and Multi-dimensional Arrays, Sparse Matrices. 12.00
IV
Stacks and Queues : Implementing stack using array and linked list, Prefix, Infix and Postfix expressions, Utility and
Module
5 conversion of these expressions from one to another; Array and Linked representation of Queue, De-queue, Priority 13.00
V
Queues.
Module
6 Linked Lists: Singly, Doubly and Circular Lists, representation of Stack and Queue as Linked Lists. 13.00
VI
Module Recursion: Developing Recursive Definition of Simple Problems and their implementation; Advantages and Limitations of
7 12.00
VII Recursion.
Module Trees: Introduction to Tree as a data structure; Binary Trees, Binary Search Tree, (Creation, and Traversals of Binary
8 13.00
VIII Search Trees), Graphs.

Course Learning Outcomes :

SN. Course Learning Outcomes

After successful completion of this course, the student will be able to • Apply advance Java programming techniques such as encapsulation,
dynamic memory allocation, structures to developing solutions for problems. • Development of stack and queue data structures for solving real
1
world problems. • Describe and implement abstract data types such as linked list, stack, queue and tree by using ‘Java‘for static and dynamic
implementations. • Analyze, and evaluate appropriate abstract data types and
Pedagogy for Course Delivery :

SN. Pedagogy Methods

Subject will be taught based on lectures and practical will be conducted in blended/flipped mode. Particular emphasis will be given on practical
1
explaining use case scenario for various algorithms. Focus will be on student’s involvement while imparting the course contents.

Theory /VAC / Architecture Assessment (L,T & Self Work): 80.00 Max : 100

Attendance+CE+EE : 5+35+60

SN. Type Component Name Marks

1 Attendance 5.00
2 Attendance 5.00
3 End Term Examination (OMR) 60.00
4 End Term Examination (OMR) 60.00
5 Internal CLASS TEST 10.00
6 Internal HOME ASSIGNMENT 20.00
7 Internal Viva 5.00

Lab/ Practical/ Studio/Arch. Studio/ Field Work Assessment : 20.00 Max : 100

Attendance+CE+EE : 5+35+60

SN. Type Component Name Marks

1 Attendance 5.00
2 Attendance 5.00
3 External PRACTICAL 40.00
4 External Viva 20.00
5 Internal CLASS TEST (PRACTICAL BASED) 10.00
6 Internal PRACTICAL / LAB RECORDS 10.00
7 Internal PERFORMANCE 10.00
8 Internal Viva 5.00

Lab/ Practical details, if applicable :

SN. Lab / Practical Details

List of Professional skill development activities :

No.of PSDA : 8
SN
PSDA Point
.
 1. What is Data Structure? What are their types and subtype? Explain each of subtype with examples in details. 2. Differentiate between greedy and
1
dynamic programming. 3. Explain Iterative technique with example.
1. Write down complexity of all sort and in which situation those sorts should be used? 2. Which sorting techniques is an application of recursion? 3.
Use the selection sort to put the number 3, 2, 4, 1, 5 into increasing order. Illustrate the output returned in each pass clearly. Also, write the pseudo
2
algorithm to it. 4. Write a program to sort the given array using MergeSort. 5. Trace quick sort on the list L= {11, 34, 67, 78, 78, 78, 99}.What are your
observations? 6. Write the program for
Searching Techniques and Complexity Analysis 1. Define O notation of time complexity. 2. Write a program in Java to search item ‘8’ in the given
3 array 12, 7, 9, 5, 16, 8, 52, 67, 90 using Linear Search. 3. Write a program in Java to search item ‘50’ in the given array 10, 20, 30, 40, 50, 60, 70, 80,
90, 100 using Binary search.
Arrays 1. Write a program which accepts an integer array and its size as arguments/parameter and assign the elements into two-dimension array of
integers in the following format. If the array is 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 0 1 2 3 4 0 0 1 2 3 0 0 0 1 2 0 0 0 0 1 0 0 0 0 0 2. Each element of an
4
array DATA [1….10][1….10] requires 8 bytes of storage. If base address of array DATA is 2000, determine the location of DATA[4][5], when the array
is stored i. Row-wise i
Stacks and Queues 1. Evaluate the following postfix expression using a stack and show the contents of stack after execution of each operation:
120,45,20,+,25,15,-,+,* 2. Discuss the various applications of stacks. Also write an algorithm to PUSH and POP an element into the Stack. 3. What is
5
difference between an array and a stack housed n an array? Why stack is called LIFO data structure? Explain how push and pop operation are
implemented on a stack. 4. Write a program to implement Stack using a
Linked Lists 1. What is the limitation of sequential data structures? 2. Define sparse matrix. 3. Write a program to implement Linear Linked List,
showing all the operations, like creation, display, insertion, deletion and searching. 4. Write a program to implement Stack, using Linked List.
6
Implement Push, Pop and display operations. 5. Write a program to implement Queue, using Linked List. Implement Insertion, deletion and display
operations. 6. Write a program to count the number of times an i
Recursion 1. Explain time and space complexity. 2. Explain big O notation. 3. Write a program to calculate factorial of a number using recursion. 4.
7
Differentiate between tailed and non-tailed recursion.
Trees 1. Define tree, degree of node and siblings. 2. List out type’s binary tree. 3. What is the difference between full binary tree & complete binary
tree? 4. Trace the binary tree of preorder traversal: PFBHGSRYTWZ. 5. Create a binary tree using in-order and pre-order traversal Inorder :
8
DBHEAIFJCG Preorder : ABDEHC FIJG 6. Using the following binary tree traverse it into inorder, preorder and postorder: 7. Write an algorithm to
delete an element x from a binary search tree. Discuss your

Text & References :

SN. Type Title/Name Description ISBN/ URL

• Kruse Robert L., "Data Structures and
1 Book
Program Design in C++",Pearson.
• CormenT.H., Leiserson Charles E., Rivest
2 Book Ronald L., Stein Clifford, Introduction to
Algorithms, PH
• Drozdek Adam, "Data Structures and
3 Book
algorithm in C++", Cengage Learning.
• Noel Kalicharan ,“Data Structure in C” ,Ist
4 Book
Edition Create space publisher.
• R.S Salaria ,“Data Structures & Algorithms
5 Book
using C”,Khanna Publication.
• E.Horowitz and S.Sahni,”Fundamentals of
6 Book Data Structures in C “,2nd Edition,
Universities Press.