## Course Detail

 Course Name Foundations of Computer Science Course Code 18CS601 Program Semester 1 Credits Coimbatore Year Taught 2018

### Syllabus

##### Data Structures

Asymptotic notation. Introduction to Algorithm Analysis Methodologies Review of Data Structures: Linear Data Structures – Linked Lists: – Singly LL, Doubly LL,Circular LL. Implementation–Applications. Stacks:-Implementation using Arrays and Linked Lists –Applications in Recursion. Queues -Implementation and Applications. Binary Trees – Basic tree traversals – Binary tree -Priority queues -Binary search tree. AVL trees.

Graphs -Data Structures for Graphs, Types of Graphs: Directed Graphs, Weighted Graphs, etc.. Basic definitions and properties of Graphs, Graph Traversal –Breadth First Search and their applications, Spanning trees, Shortest Paths. Hashtables – Collision using Chaining – Linear Probing – Quadratic Probing – Double Hashing.

##### Algorithms

Review of sets and relations, and matrices. Logic. Series, counting principles. Basic sorting and searching algorithms

Algorithm Analysis: Recurrence Relations and their solutions. Recursion tree method, substitution method and Master theorem. Introduction to Amortized Analysis. Introduction to Divide and Conquer technique. Mergesort, Quicksort and binary search

Introduction to Greedy Algorithms – Fractional Knapsack – Scheduling Algorithms. Introduction to: DP Algorithms – Matrix Chain – Subsequence Problems – 0-1 Knapsack.

### Data Structures

Upon completion of the course, the student will be able to

 Course Outcome Bloom’s Taxonomy Level CO 1 Understand the concept and functionalities of Data Structures L2 CO 2 Identify and apply appropriate data structures to solve problems and improve their efficiency L3 CO 3 Analyze the complexity of data structures and associated methods L4 CO 4 Analyze the impact of various implementation and design choices on the data structure performance. L5

### Algorithms

Upon completion of the course, the student will be able to

 Course Outcome Bloom’s Taxonomy Level CO 1 Understand the correctness and analyze complexity of algorithms L4 CO 2 Understand various algorithmic design techniques and solve classical problems L3 CO 3 Analyze the complexity of data structures and associated methods L5 CO 4 Solve real world problems by identifying and applying appropriate design techniques L5

### Data Structures

• Michael T Goodrich and Roberto Tamassia and Michael H Goldwsasser, “Data Structures and Algorithms in Python++”, John Wiley publication, 2013.

### Algorithms

• Thomas H Cormen, Charles E Leiserson, Ronald L Rivest and Clifford Stein, “Introduction to Algorithms”, Third Edition, Prentice Hall of India Private Limited, 2009.

### Data Structures

• Goodrich, Michael T., and Roberto Tamassia. Data structures and algorithms in Java. John Wiley & Sons, 2008.
• Tremblay J P and Sorenson P G, “An Introduction to Data Structures with Applications”,Second Edition, Tata McGraw-Hill, 2002.

### Algorithms

• Michael T Goodrich and Roberto Tamassia, “Algorithm Design Foundations – Analysis and Internet Examples”, John Wiley and Sons, 2007.
• Dasgupta S, Papadimitriou C and Vazirani U, “Algorithms”, Tata McGraw-Hill, 2009.

‘Foundations of Computer Science’ is a course offered in the first semester of M. Tech. in Computer Science and Engineering at School of Engineering, Amrita Vishwa Vidyapeetham.

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.