Class-Discussion

1. Introduction to the course (2 sessions) PPT

   1. Linear and Non-linear data structures: arrays, stack, queue, linked list, tree, graphs, hash tables

   2. Primitive (int, float, char, etc ) and Non Primitive Data Types (array, struct, etc)

2. Arrays (2 sessions) PPT

   1. Properties

   2. addressing i th element in a 1-D array, 2-D array, 3-D array, n-D array

      1. Row Major Order and Column Major Order Organization

3. Stack (5 sessions) PPT

   1. Properties (0.5)

   2. Implementation: push, pop, read, and change functions (1)

   3. Applications:

      1. Infix to Postfix conversion (2)

      2. Evaluation of Postfix expression (0.5)

      3. Infix to Prefix conversion (0.5)

      4. Function calls and recursion: Tower of Hanoi (Trace of Tower Of Hanoi For N=4), GCD, and Factorial (2.5)

4. Queue (2 sessions) PPT

   1. Implementation: insert and delete functions (1)

   2. Circular queue implementation: insert and delete functions (1)

   3. Priority Queue: preliminary implementation and application

   4. Double Ended Queue and its applications: scheduling on multi processor systems (1)

5. Linked List (6 Sessions) PPT

   1. Singly Linked List implementation

      1. insert node (2)

         1. at front

         2. at rear

         3. after node with value v

         4. in an ordered list

      2. Delete Node (1)

         1. from front

         2. from rear

         3. with value v

   2. Circular Linked List Implementation (1)

   3. Doubly Linked List implementation (2)

   4. Application of linked list in polynomial evaluation (1). The code for adding two polynomials can be found HERE

6. A symptotic Analysis of Algorithms: (3 sessions) PPT

   2. 1. Resource: https://www.youtube.com/watch?v=JPyuH4qXLZ0

      2. Chapter 3 Growth of functions, Introduction to Algorithms, Cormen Book, MIT Press

7. Tree

   1. All the PPTs used in class can be found HERE

   2. Concept of Hierarchical data structures (1 session)

   3. Tree (6 sessions)

      1. definition of root, leaf nodes, node degree, tree degree, height of the tree PPT

      2. types of trees: binary tree, n-ary tree, full and complete binary tree, number of nodes in a binary tree with height h PPT

      3. representation of the tree: array and linked representation

      4. tree traversal: inorder, pre-order, post-order, level order; recursive formulation to count number of nodes in a tree; determine height of the tree PPT

   4. Heap Tree: insert, delete and Heap Sort (3 sessions) PPT

   5. Binary search tree: insert node function and create tree PPT1, PPT2 (same as the PPT of AVL node delete)

      1. delete node from a binary search tree

      2. Code for BST operations can be found here, python

   6. Balanced Binary Search Tree:

      1. Introduction (1 session)

      2. 234 Tree (4 sessions)

         1. Example Insertion sequence:

            1. Resource: http://faculty.cs.niu.edu/~freedman/340/340notes/340redblk.htm

         2. Example delete sequence and Delete Algorithm:

            1. Resource: https://azrael.digipen.edu/~mmead/www/Courses/CS280/Trees-2-3-4-delete.html

      3. AVL Tree (6 sessions)

         1. Introduction PPT, Video1, Video2,

         2. Insert node: rotations for dealing with height imbalance Video3, Video4, Video5

         3. Delete node PPT, Video1, Video2, Video3, Video4

http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-delete.html

7. 6. 4. Red-black tree (5 sessions)

         1. Insert Node PPT, Video1, Video2, Video3

         2. Delete Node PPT Video1, Video2, Video3, Video4, Video5, Video6

            1. Other Resource: https://www.cs.purdue.edu/homes/ayg/CS251/slides/chap13c.pdf

            2. https://www.youtube.com/watch?v=bx9uv7As5jc

   7. Hash Table and Search: PPT

   8. Graphs PPT

      1. representation of graphs using adjacency matrix and adjacency list

      2. Graph traversals (breadth/depth first search)

      3. Minimum spanning tree algorithms