CAS 765

CAS 765 DATA STRUCTURES AND ALGORITHMS

Objectives:

  • To design and implement different data structures.
  • To study various searching, sorting techniques and their Applications.
  • To compute complexity of algorithms.
  • To be taught algorithm design methodologies.

 

Introduction – Arrays – Structures – Stack: Definition and examples, Representing Stacks - Queues and lists: Queue and its Representation, lists – Applications of Stack, Queue and Linked Lists.

Binary Trees – Binary Tree Representations – node representation, internal and external nodes, implicit array representation - Operations on binary trees – Binary tree Traversals - Representing Lists as Binary Trees–Search Trees.

Algorithms – Analyzing and Designing algorithms – Asymptotic notations – Recurrences – Methods to solve recurrences – Basic sorting techniques – selection sort, bubble sort, insertion sort and merge sort – Basic Search Techniques – linear search and binary search.

Revisiting various operations of different data structures with time complexity analysis – Design and Analysis of Heap Sort - Quick Sort – Sorting in linear time – Radix sort – Selection in linear time.

Design Strategies: Recursion - Divide and conquer methodology – Multiplication of large integers – Strassen's matrix multiplication – Greedy method – Prim's algorithm – Kruskal's algorithm – algorithm for Huffman codes – Dynamic Programming – Backtracking and Branch and bound method.

 

References

 

        1.T.H.Cormen, C.E.Leiserson, R.L.Rivest and C. Stein, “Introduction to algorithms”, 3rd edition, MIT Press, 2009.

        2. P. H. Dave and H. B.Dave, “Design and Analysis of Algorithms”, Pearson Education India.2009

        3. S. Lipschutz and G.A.V. Pai, “Data Structures”, Tata McGraw-Hill, 2010.

        4. Clifford A. Shaffer, “Practical Introduction to Data Structures and Algorithm Analysis”, 2nd edition, Prentice Hall, 2000.

        5. P. Brass, “Advanced Data Structures”, Cambridge University Press, 2008.

       

        Outcomes:

Students will be able to:

               Understand common data structures and algorithms, implement them.

               Choose among variety of data structures to design algorithms and solve problems in scientific computing.

               Comprehend algorithmic complexity and choose the best among various data structures and algorithms for problem solving, based on complexity.