Computing Lab (Programming and Data Structures) - 2018
Course Content
Course Content
Programming Language, Tools and Techniques
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
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
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
Books Consulted
- 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.
- Satya R. Chakravarty, Palash Sarkar and Manipushpak Mitra. A Course on Cooperative Game Theory. Cambridge: Cambridge University Press, 2014. DOI: 10.1017/CBO9781107415997.
- 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.
- Udi Manber. Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989. ISBN: 0201120372, 9780201120370.
- Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009. ISBN: 9780262033848, 9780262533058.