Amizone.net



[pic]

|L |T |P/S |SW/FW |TOTAL CREDIT UNITS |

|3 |- |4 |- |5 |

Course Title:- Data Structures Using C Language Credit units:-05

Course level:- PG

Course Type:CSIT633

Course Objectives: The aim of this course is to

• Provide in-depth knowledge of usage, design, and analysis of data structures in computer programs.

• Make students understand the concepts of linear and non linear data structure.

• Impart knowledge about asymptotic notations and their usage.

Pre-requisites: - Computer programming using ‘C’ language

Student Learning Outcomes:

After successful completion of this course, the student will be able to

• Explore how to use the concepts of data structures and its execution in actual environment.

• Apply advance C programming techniques such as pointers, dynamic memory allocation, structures to developing solutions for particular problems.

• Design and implement abstract data types such as linked list, stack, queue and tree by using ‘ for static and dynamic implementations.

• Analyze, and evaluate appropriate abstract data types and algorithms to solve problems.

Course Contents:

| |Weightage (%) |

|Module I: Introduction to Data Structures |15 |

|Data Types in C Language, Abstract data type,Pointers in C, Arrays in C Language, Implementation of Single Dimensional & Multi Dimensional Arrays, Address Calculation in | |

|Single and Multi Dimensional Arrays.,Row major order and column major order, Sparse matrix, Asymtotic notations,Time Complexity. | |

|Module II: Stacks and Queues |15 |

|Definition & Examples, Representing Stack using an Array, Implementing Push and Pop Operation in a Stack, Infix Postfix & Prefix Expressions, Evaluating a Postfix Expression, | |

|Conversion from one form of an expression to another form , Towers of Hanoi, Queues and its Sequential Representation, Insert –Delete- Print Operations, Dequeue and its | |

|implementation ,Circular Queues and their Implementation, Priority Queues with basic operations. | |

|Module III : Programming with Linked Lists |20 |

|Introduction, Insertion and deletion of a node to single linked list, Doubly, Circular & Header linked lists with basic operations, List allocating and freeing dynamic | |

|variables, Addition of two polynomials list,Joseph Problem. | |

|Module IV : Programming with Trees |20 |

|Binary Trees, Operations on Binary Trees, node representation, internal and external nodes, tree traversal ,constructing a tree, Binary Search Tree(BST)- definition, | |

|representation, Implementation of BST. Constructing a binary search tree based on its given infix and pre/post fix order, deletion and insertion of a node in binary search | |

|tree, Threaded binary trees, Height Balanced Tree, Constructing an AVL Tree, Insertion and Deletion of a node, searching a node ,Paged binary tree, Multiway search tree-B | |

|tree, B+ tree, B* tree. | |

|Module V: Searching and Sorting Techniques |15 |

|Insertion Sort, Selection Sort, Merge Sort, Heap Sort, Bubble Sort, Radix Sort,Quick Sort,Count Sort, , Linear Search, Binary Search ,Complexities of Sorting and Searching | |

|Algorithms, Hashing,Hash Functions, Collision Resolution Techniques. | |

|Module VI: Graph and Their Applications |15 |

|Introduction, Graph Theory Terminology, Sequential Representation of Graph (Adjacency and Path Matrix), Warshall Algorithms, Linked Representation of Graph, Different | |

|Operations on Graphs, Traversing A Graph(DFS, BFS),Shortest path algorithm, Spanning Trees-Introduction,Representation of Spanning tree, Constructing A Spanning Tree(Prim’s | |

|Algorithm, Kruskal’s Algorithm). | |

Pedagogy for Course Delivery: Subjects will be taught using lectures and practical based methods. Focus will be on making student understand which data structure needs to be applied in a particular use case scenario.

.

List of Experiments:

1. Write a program to search an element in a given array using linear search.

2. Write a program to search an element in a given array using binary search.

3. Write a program to sort the elements of an array using the following techniques: Bubble Sort, Selection Sort, and Insertion Sort. Compare the time taken by each sorting technique.

4. Write a program using the concept of iteration and recursion to sort the elements of an array using Quick Sort.

5. Write a program to implement Heap sort.

6. Write a program to implement Merge sort.

7. Write a program to delete an element from the kth element of an array.

8. Write a program to insert an element at the kth element in an array.

9. Write a program to remove duplicates in an array.

10. Write a program to merge two sorted arrays.

11. Write a program to perform the following operations on two given matrices: Addition and Multiplication.

12. Write a program to implement a Stack, show overflow and underflow while performing push and pop operations respectively.

13. Write a program to evaluate a postfix expression.

14. Write a program of Towers of Hanoi Problem.

15. Write a program to implement a queue and show the following: insertion and deletion.

16. Write a program to implement a circular queue and show the following: insertion and deletion.

17. Write a program to implement Linear Linked List and show the following operations: creation, display, insertion, deletion and searching.

18. Write a program to increment the data part of every node in a linked list by 10.

19. Write a program to implement a stack using linked list and show the following operations: Push, Pop, and Display.

20. Write a program to implement a stack using linked list and show the following operations: Insertion, Deletion, and Display.

21. Write a program to count the number of repetitions of a number in a linked list.

22. Write a program to implement Doubly Linked List and show the following operations: creation, display, insertion, deletion and searching.

23. Write a program to implement Joseph Problem.

24. Write a program to implement Binary tree and display the contents using preorder, postorder and inorder traversal techniques.

25. Write a program to construct a Binary Search tree and perform the following operations: Insertion and Deletion of a node.

26. Write a program to construct an AVL tree and perform the following operations: insertion, deletion and searching.

27. Write a program to insert and delete nodes in a graph using adjacency matrix.

28. Write a program that demonstrates Warshall’s algorithm.

29. Write a program to implement Depth First Search using linked representation of graph.

30. Write a program to implement Breadth First Search using linked representation of graph.

31. Write a program to implement Prim ‘s Algorithm

32. Write a program to implement Kruskal Algorithm

.

• Assessment/ Examination Scheme:

|Theory L/T (%) |Lab/Practical/Studio (%) |Total |

|60 |40 |100 |

• Theory Assessment (L&T):

| |Continuous Assessment/Internal Assessment |End Term Examination |

|Components (Drop down) |Assignment |Mid Term |Presentation |Attendance |EE |

|Weightage (%) |5 |10 |10 |5 |70 |

• Lab/ Practical/ Studio Assessment:

| | |Continuous Assessment/Internal Assessment |End Term Examination |

|Components (Drop down |Attendance |Mid term |Lab Record |Continuous Assessment |Viva |Practical |viva |

|Weightage (%) |5 |10 |10 |10 |5 |40 |20 |

| | | | | | | | |

1 Text

• Yashwant Kanetkar,”Data Structure using C”, BPB Publication, 5th Edition ,2011

• A.Tannenbaum,Y. Lanhgsam and A.j. Augenstein ,” Data Structures Using C And C++ “,Prentice Hall of India,2nd Edition,2009.

• R.S Salaria “Data Structures & Algorithms using C”,Khanna Publication,4th edition,2009

• E.Horowitz and S.Sahni,Fundamentals of Data Structures in C “,2nd Edition,Universities Press,2008.

• Jean-Paul Tremblay, P.G Sorenson, “An Introduction to Data Structures with applications” , Mcgraw-Hill ,2nd Edition ,1984.

2 References:

• Shaum’s outline Series,”Data Structure”,TMH,Special Indian Edition,Seventeenth Reprint,2009

• Robert L Kruse “Data Structure and Program Design in C”, Prentice Hall ,1991.

• Noel Kalicharan,”Data Structure in C” ,Ist edition Create space publisher, 2008.

• Mark Allen Weiss,”Data Structure and algorithm Analysis in C”,2nd Edition AddisonWesley,1996

• Jean-Paul Tremblay “An Introduction to Data Structures with applications” , Mcgraw-Hill College, 2nd edition ,1984.

• E. Balagurusamy, “Problem Solving through C language”, TMH publication, Fourth Edition, 2008.

Remarks and Feedback

|S No |Name |Academia/Alumni/Industry |Feedback |

|1 |Vijay Kumar Singh |Industry |PG Data structure using c |

| |Deputy General Manager | |Syllabus of DS looks good, may be stress on |

| |HCL Tech | |more application by including more labs/small |

| | | |projects. It will help students to apply the |

| | | |DS concepts practically |

|2 |Poonam Uniyal |Alumni |I find all the courses as per the industry |

| |Software Engineer | |standards. Students should concentrate more on|

| |LOB- Peoplesoft | |practical work. |

| |HCL Technologies ltd, | | |

| |sector -126,Noida | | |

|3 |Pramod |Industry |I went through all the attached 7 syllabuses, |

| |Manager Engineering | |and as per course objective it looks good to |

| |GlobalLogic | |me. |

| | | |Thank you! |

|4 |Reenu Ranawat |Alumni |Course content of all subjects is very good |

| |Sr. Technical Associate | |and appropriate. |

| |Genpact Headstrong Capital Markets | | |

|5 |Arpita Chakraborty |Alumni |Good |

| |Technical Associate | | |

| |Genpact Headstrong | | |

| |Capital Markets | | |

|6 |Ms Shweta Ravi Shankar |Industry |Are students able to understand all the |

| |Genpect | |contents in one semester only? |

| | | |Rest is fine. |

|7 |Harsh Sharma |Industry |Good |

| |Globallogic | |Focus on Implementation part as well. |

|8 |Monishankar chakraborty |Industry |Overall good |

| |Technical Architect. | | |

| |Target Corporation India Pvt Ltd , Associate | | |

|9 |Ananya Biswas |Industry |Covers all the important accepts. |

| |Senior Software Engineer | | |

| |HSBC software technology | | |

|10 |Mousumi Hazarika |Industry |Covers all the principles |

| |Systems Specialist | | |

| |GE Healthcare, | | |

|11 |Dr. Mithlesh Atulakar |Academics |Systematically planned which will help the |

| |Assosiate Professor | |students to learn and prepare projects |

| |NIT,Raipur | |themselves. |

|12 |Mr. Himangshu Deb |Academics |Syllabus is up to date . |

| |Director (Academics) | | |

| |Epitome College of IT and Management,Guwahati | | |

|13 |Sarvesh Kumar |Industry |OK |

| |SAP Technical Consultant | | |

| |Unisoft Infotech India Pvt Ltd Bangalore | | |

|14 |Ghanashyam Das |Industry |Course is very well defined |

| |Project Lead | | |

| |TechMahindra | | |

|15 |Mr. Kaushlesh Kumar, Project Engineer/CRIS |Industry |a) The Course structure is good. |

| | | |b) The syllabus is planned in such a way that |

| | | |will help students to prove themselves in |

| | | |industry. |

|16 |Mr. Sonu Singh Patel, Project Engineer/CRIS |Industry |Course content is good. |

|17 |Mr. Sant Lal, Sr. Project Engineer/CRIS |Industry |a) The syllabus is well organized and covers |

| | | |all the aspects which are important for |

| | | |industry perspective also |

| | | |b) The contents are up to the mark. |

|18 |Ms.Pooja Malik, Assistant Consulltant/TCS |Industry |a) The syllabus is designed in such a manner |

| | | |that will provide students in-depth knowledge |

| | | |of the subject. |

|19 |5) Mr.Akash Rastogi, Sr.Software Engineer/FIS |Industry |The contents of the syllabus are very well |

| |Global | |defined.The best part is ,since the subject is|

| | | |data structures using C language ,the first |

| | | |unit is covering basic concepts about C |

| | | |Laguage that will be helpful for the students |

| | | |in better understanding. |

|20 |Mr.Saurabh Singh, Sr.Software Test Engineer/Sapient|Industry |The syllabus is well defined and covers all |

| |Coorporation | |aspects as per industry also. |

|21 | Ms.Shalini Maurya,Sr.Software Engineer/Hitachi |Industry |OK |

|22 |Rahul Saini |Industry |I have gone through the Syllabus and |

| |Sr. Systems Analyst Steria India Ltd. | |acknowledge that Syllabus is good and as per |

| |(Rahul.saini@steria.co.in) | |the required industry standards. |

| |+91 9899174794 | | |

|23 |Amit Gupta |Industry |I have gone through the Syllabus and |

| |Sr. System Lead Steria India Ltd | |acknowledge that Syllabus is very good and as |

| |(amit.gupta@steria.co.in ) | |per the required industry standards. |

| |+91 9999000349 | | |

|24 |Virendra Singh |Industry |I have gone through the Syllabus and |

| |Systems Analyst Steria India Ltd | |acknowledge that Syllabus is very good and as |

| |(Virendra.singh@steria.co.in) | |per the required industry standards. |

| |+91 9654360145 | | |

|25 |Mr Sunil Kr Pandey |Academics |Change the prerequisite. |

| |Director – IT | | |

| |ITS Ghaziabad | | |

|26 |Ritesh Singhal |Academics |Good. Revisit the lab file. |

| |Asst Prof | | |

| |AKGIT | | |

|27 |Abhishek Datta |Industry |Industry |

| |Manager – Solutions Delivery & Support | | |

| |Guavus Network Systems Pvt. Ltd, Gurgaon. | | |

|28 |Dr Arun Sharma |Academics |Academics |

| |Professor and Head, | | |

| |Department of CSE, | | |

| |Krishna Institute of Engineering and Technology, | | |

| |Ghaziabad. | | |

|29 |Ms Sonal Chhoda Consultant,TCS |Industry |Course content good. |

|30 |Gyan Vikas Gogoi |Industry |Good for basic Java. |

| |Lead S/W Engg. | |Focus on OOPS relationship |

| |Synchron Technologies, Pune | | |

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download