Home Research Teaching Publications index

CS 113: Data structures and algorithms

January 2020

This course will introduce data structures and algorithms

Books

  1. [CLRS] Introduction to algorithms by Cormen et. al.
  2. [ACP] The art of computer programming by Donald E. Knuth

Grading Policy (tentative)

Academic Honesty

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.

Course Schedule

Week Topic Resources
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
9 Hashing
10 Sets

Assignments

# Problem
Programming assignments
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.