Computing Lab (Programming and Data Structures) - 2018

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.