COURSE SUMMARY
Course Title: 
Foundations of Computer Science
Course Code: 
18CS601
Year Taught: 
2018
Semester: 
1
Degree: 
Postgraduate (PG)
School: 
School of Engineering
Campus: 
Coimbatore

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.

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.

TEXTBOOKS

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

REFERENCES

  • 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

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

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.

TEXTBOOKS

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

REFERENCES

  • 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.

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