Hi Guest, 18 July 2019 Thursday IST

About CUSAT | About Department | Alumni | Sitemap | Disclaimer  

  Home > Academic/Programmes > Programme Structure > CIS (2012)
Core/Elective: Core Semester: 1 Credits: 4
Course Description

This course describes the techniques for the design and analysis of efficient algorithms, giving emphasis on methods useful in practice. Topics include graph algorithms; divide-and-conquer algorithms and recurrences; dynamic programming; greedy algorithms; amortized analysis; network flow; randomized and approximation algorithms.

Course Objectives

To know problem solving techniques
To understand techniques for the design and analysis of efficient algorithms
To be able to design algorithms for new problems with volume of data

Course Content

1. Algorithms - Problem Solving and Important problem types-Fundamental Data Structures-Asymptotic Notations and Basic Efficiency classes-Analysis of Recursive and Non-Recursive Algorithms-Probability-Random Variables and Expectations, Moments and Deviations, distributions, conditional probability, Bayes Theorem- Tail Bounds, Chernoff Bound .

2. Problem Solving Techniques- Brute force, divide and conquer, decrease and conquer, transform and conquer, dynamic programming, greedy technique.

3. Limitations of Algorithm power -P, NP and NP complete problems- Back tracking , branch and bound and approximations algorithms- probabilistic analysis , Randomized algorithms, Birthday Paradox, Quick sort, bucket sort, mini-cut, median finding- Random graphs, Ramsey number, Hamiltonian cycles.

4. Modern Algorithms- Markov chain, stochastic process, page rank- Components of evolutionary algorithms, ACO,PCO, TSP problem solving.

5. Algorithms in evolving data streams- Sampling, sketching, data stream models, read-write streams, stream-sort, map-reduce -Large Graph and Social Networks, Parallel Clustering algorithm for large Data sets with Applications.


1. Introduction to Algorithms (3rd Ed):Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press (2009)
2. Algorithm Design: Jon Kleinberg and Eva Tardos, AW (2005)
3. Anany V. Levitin. Introduction to the Design & Analysis of Algorithms (2nd Ed): A W (2006)
4. Randomized Algoritms: Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press; Reprint edition (2010)
5. Data Streams: Algorithms and Applications: S. Muthukrishnan, Now Publishers (2005)
6. Data Streams: Models and Algorithms: Charu C. Aggarwal, Springer (2006)
7. Introduction to evolutioary computing: Agoston E. Eiben, J.E. Smith, Springer (2010)

Copyright © 2009-19 Department of Computer Science,CUSAT
Design,Hosted and Maintained by Department of Computer Science
Cochin University of Science & Technology
Cochin-682022, Kerala, India
E-mail: csdir@cusat.ac.in
Phone: +91-484-2577126
Fax: +91-484-2576368