Course Content

Programming Language, Tools and Techniques

• C programming: loops, arrays, pointers, structures, functions, recursion, file handling.
• Concept of debugging and using debugging tools (GDB).
• Makefiles.

Algorithms

• Introduction to problem - solving and basic algorithms.
• Introduction to running time - basic concepts, order notation.
• Searching: linear search, binary search and its variants.
• Sorting: Non-comparison based sorting: bucket sort and radix sort; Comparison based sorting: insertion sort, selection sort, bubble sort, merge sort and quick sort.
• Elementary graph algorithms: Breadth-first search (BFS), depth-first search (DFS), topological sort, strongly connected components.

Data Structures

• Basic data structures: Stacks, Queues, Linked lists and their applications.
• Hash Tables: Direct-address tables; hash Tables; collision resolution by chaining; hash functions: division method, multiplication method, universal hashing; open addressing: linear probing, quadratic probing, double hashing; perfect hashing.
• Non-linear data structures: Binary search trees: insertion, deletion, search, in-order traversal, pre-order traversal, post-order traversal, finding maximum, minimum, predecessor and successor; Graphs: adjacency matrix, adjacency list.

Books Consulted

1. Al Kelley and Ira Pohl. A Book on C: Programming in C. 3rd Edition, 1994. Benjamin-Cummings Publishing Co. Inc., Redwood City, CA, USA, 1994. ISBN: 0805316779.
2. Satya R. Chakravarty, Palash Sarkar and Manipushpak Mitra. A Course on Cooperative Game Theory. Cambridge: Cambridge University Press, 2014. DOI: 10.1017/CBO9781107415997.
3. Donald E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms. 3rd Edition, 1997. Addison Wesley Longman Publishing Co. Inc., Redwood City, CA, USA. ISBN: 0-201-89683-4.
4. Udi Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989. ISBN: 0201120372, 9780201120370.
5. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009. ISBN: 9780262033848, 9780262533058.