Home Research Teaching Publications index
This course will introduce data structures and algorithms
We expect every student to follow the highest standards of integrity and academic honesty. Copying/sharing code in exams, homeworks, labs are not allowed. See the IIT Goa policy for academic malpractices.
|1||Course Introduction. Basic sorting, searching algorithm.||chap. 2. CLRS, Prof. Navin Garg's NPTEL|
|Time/Space analysis - Best case, worst case scenario. Order notation- Big O, omega, theta notation||chap. 3. CLRS, Prof. Navin Garg's NPTEL|
|2||Recursion - Factorial, Fibonacci, print all subsets, print all permutations||MIT OCW - Recursion|
|Linked list. Stacks and Queues using linked list||chap. 10. CLRS, NPTEL lecture 1, lecture 2, lecture 3|
|3||Graphs and Representations - Adjacancy matrix, adjacancy list||chap. 22. CLRS, NPTEL lecture 1, lecture 2|
|Graphs traversals - Breadth first search (BFS) and Depth first search (DFS)||chap. 22. CLRS, NPTEL lecture|
|4||Trees. Binary tree - Representations||chap. 10.4. CLRS, NPTEL lecture|
|Tree traversals - Preorder, Inorder, Postorder||NPTEL lecture|
|5||Tree traversals in detail||same as above|
|6||Heap - Definition, Insert, delete, find maximum. Running time analysis. Heap Sort, Priority queue|
|7||Binary search tree - Search, insert, successor and predecessor. Run time analysis|
|8||Red black trees - Search, insert, delete. Run time analysis|
|1||1. Implement add, remove elements in the front and back of linked list.
2. Create C++ class which simulates basic operations of stack and queue using linked list.
3. Create a BigInteger class which stores as big an integer we want and write operations for addition and multiplication.
|2||Family tree - Build a data structure to store information about father, mother and children. Note that a person can have children with more than one person.
You will then need to write a function, which takes two person and tell their relationship.
The output can be one of the following: father, mother, grand father/mother, i-th great grand father/mother, or i-th cousin j-removed.
See https://www.genealogy.com/articles/research/16_cousn.html for proper terminology about family relationships.
|3||From inorder and postorder information build the tree|
|4||1. Write an algorithm to print all k size permutations of an n element set (with and without repetitions).
2. Implement a stack using two queues.
3. Implement a queue using two stacks.