Course Detail

 Course Name Data Structures and Algorithms Course Code 19EAC203 Program B. Tech. in Electronics and Computer Engineering Semester 3 Year Taught 2019

Syllabus

Module I

Introduction: Overview of Data Structures – A Philosophy of Data Structures – The Need for Data Structures – Cost and Benefits – Abstract Data Types and Data Structures – Principles, and Patterns. Basic complexity analysis – Best, Worst, and Average Cases – Asymptotic Analysis – Analyzing Programs – Space Bounds, Arrays, Linked Lists and Recursion: Using Arrays – Lists – Array based List Implementation – Linked Lists – LL ADT – Singly Linked List – Doubly Linked List – Circular Linked List – recursion – linear, binary, and multiple recursions. Stacks and Queues: Stack ADT – Array based Stacks, Linked Stacks – Implementing Recursion using Stacks, Queues – ADT, Array based Queue, Linked Queue, Double-ended queue, Circular queue. Lab component to focus primarily on implementation of Dynamic arrays, inked lists, recursive operations, and queues.

Module II

Trees: Tree Definition and Properties – Tree ADT – Basic tree traversals – Binary tree – Data structure for representing trees – Linked Structure for Binary Tree – Array based implementation. Priority queues: ADT – Implementing Priority Queue using List – Heaps. Maps and Dictionaries: Map ADT – List based Implementation – Hash Tables – Dictionary ADT – Skip List – Complexity. Lab component to focus primarily on implementation of trees, queues, and lists and corresponding topics covered in this unit.

Module III

Search trees – Binary search tree, AVL tree, Trees – K-D Trees – B-Trees. Sorting and Selection – Linear Sorting – Heap Sort – Divide and Conquer Strategy – Analysis using Recurrence Tree based Method – Merge Sort – Quick Sort – Studying Sorting through an Algorithmic Lens – Selection – External Memory Sorting and Searching. Graphs: ADT- Data structure for graphs – Graph traversal – Transitive Closure – Directed Acyclic graphs – Weighted graphs – Shortest Paths – Minimum spanning tree – Greedy Methods for MST. Lab component focuses primarily on implementation of algorithms covered in this unit. Final project lab exercise to build a real-life use-case using data structures and algorithms covered in this class.

Objectives and Outcomes

Course Objectives

• To Develop a solid understanding of the theory and implementation of data structures, algorithms and associated implementation.
• To Cover the theory of data structures and algorithms and complement it with an implementation of each topic covered in the units below.

Course Outcomes

• CO1: Ability to implement linear and non-linear data structure operations using C
• CO2: Ability to solve problems using appropriate data structures
• CO3: Ability to analyze the algorithms and its complexity
• CO4: Ability to employ sorting and searching algorithms using relevant data structures

CO – PO Mapping

 PO/PSO/ CO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 CO1 3 3 3 3 3 3 3 3 CO2 3 3 3 3 3 3 CO3 3 3 3 3 3 3 3 3 CO4 3 3 3 3 3 3

Textbook / References

Textbook

• Goodrich M T and Tamassia R, “Data Structures and Algorithms in Java”, Fifth edition, Wiley publication, 2010.
• Clifford A. Shaffer, “Data Structures and Algorithm Analysis”, Third Edition, Dover Publications, 2012.

Reference

• Goodrich M T, Tamassia R and Michael H. Goldwasser, “Data Structures and Algorithms in Python++”, Wiley publication, 2013.
• Tremblay J P and Sorenson P G, “An Introduction to Data Structures with Applications”, Second Edition, Tata McGraw-Hill, 2002.

Evaluation Pattern 50:50 (Internal: External)

 Assessment Internal External Periodical 1 (P1) 15 – Periodical 2 (P2) 15 – *Continuous Assessment (CA) 20 – End Semester – 50 *CA – Can be Quizzes, Assignment, Projects, and Reports.

DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.