COURSE SUMMARY
Course Title: 
Data Structures and Algorithms
Course Code: 
18CSA209
Year Taught: 
2018
Semester: 
3
Degree: 
Undergraduate (UG)
School: 
School of Engineering
Campus: 
Amritapuri

'Data Structures and Algorithms' is a course offered in the third semester of B. C. A. (Bachelor of Computer Applications) program at School of Engineering, Amrita Vishwa Vidyapeetham, Amritapuri.

This course is intended to introduce abstract concepts and shows how those concepts are useful in problem solving, and then shows how the abstractions can be made concrete by using a programming language. Equal emphasis is placed on both the abstract and the concrete versions of a concept. The only prerequisite for students is an understanding in programming.

Unit 1

Algorithm Analysis Basic mathematical review, RAM model of computation, Pseudocode conventions, Worst case, Average case and Best case analysis, Asymptotic Analysis, Back Substitution Method, masters method, Euclid's algorithm, Exponentiation.

Unit 2

 Searching and Sorting Linear Search, Binary Search – Analysis, Bubble Sort, Insertion Sort, Merge sort, Quick Sort

Unit 3

Linear Data Structures Abstract Data Type, List ADT: Singly linked lists, Doubly linked lists, Circular Linked Lists, Stack ADT implementation and applications, Queue ADT: Implementation and Application. Circular Queue, Priority Queue

Unit 4

Non-Linear Data Structures. Basic concepts of trees, Implementation of trees, Traversal, Binary tree, Expression tree, Binary search tree, AVL tree, Heap

Unit 5

Graphs Adjacency matrix, Adjacency list, bfs, dfs, MST Prims and Kruskals, Dijkstras algorithm

Text Book

  • Mark Allen Weiss, "Data Structures and Algorithm Analysis in C", Second Edition, Pearson Education

References

  • Samanta, Debasis. Classic data structures. PHI Learning Pvt. Ltd., 2004.
  • Cormen, Thomas H. Introduction to algorithms. MIT press, 2009.