Class-Discussion
Introduction to the course (2 sessions) PPT
Linear and Non-linear data structures: arrays, stack, queue, linked list, tree, graphs, hash tables
Primitive (int, float, char, etc ) and Non Primitive Data Types (array, struct, etc)
Arrays (2 sessions) PPT
Properties
addressing i th element in a 1-D array, 2-D array, 3-D array, n-D array
Row Major Order and Column Major Order Organization
Stack (5 sessions) PPT
Properties (0.5)
Implementation: push, pop, read, and change functions (1)
Applications:
Infix to Postfix conversion (2)
Evaluation of Postfix expression (0.5)
Infix to Prefix conversion (0.5)
Function calls and recursion: Tower of Hanoi (Trace of Tower Of Hanoi For N=4), GCD, and Factorial (2.5)
Queue (2 sessions) PPT
Implementation: insert and delete functions (1)
Circular queue implementation: insert and delete functions (1)
Priority Queue: preliminary implementation and application
Double Ended Queue and its applications: scheduling on multi processor systems (1)
Linked List (6 Sessions) PPT
Singly Linked List implementation
insert node (2)
at front
at rear
after node with value v
in an ordered list
Delete Node (1)
from front
from rear
with value v
Circular Linked List Implementation (1)
Doubly Linked List implementation (2)
Application of linked list in polynomial evaluation (1). The code for adding two polynomials can be found HERE
A symptotic Analysis of Algorithms: (3 sessions) PPT
Chapter 3 Growth of functions, Introduction to Algorithms, Cormen Book, MIT Press
Tree
All the PPTs used in class can be found HERE
Concept of Hierarchical data structures (1 session)
Tree (6 sessions)
definition of root, leaf nodes, node degree, tree degree, height of the tree PPT
types of trees: binary tree, n-ary tree, full and complete binary tree, number of nodes in a binary tree with height h PPT
representation of the tree: array and linked representation
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
Heap Tree: insert, delete and Heap Sort (3 sessions) PPT
Binary search tree: insert node function and create tree PPT1, PPT2 (same as the PPT of AVL node delete)
Balanced Binary Search Tree:
Introduction (1 session)
234 Tree (4 sessions)
Example Insertion sequence:
Resource: http://faculty.cs.niu.edu/~freedman/340/340notes/340redblk.htm
Example delete sequence and Delete Algorithm:
Resource: https://azrael.digipen.edu/~mmead/www/Courses/CS280/Trees-2-3-4-delete.html
AVL Tree (6 sessions)
http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-delete.html