CS301 Course Calendar

Course Calendar
Topic	Lecture	Resource	Page
Introduction, Array data type, List Abstract Data Type (ADT)	1	Handouts	3-11
List ADT operations, implementation of List ADT with arrays and linked list	2	Handouts	12-19
C++ code for linked lists	3	Handouts	20-31
C++ code for linked list, doubly linked list,  circularly linked list, Josephus problem	4	Handouts	32-45
Stacks, stack operations, implementation with arrays	5	Handouts	46-55
Stack implementation with linked list, prefix, infix and postfix expressions, infix to postfix conversion.	6	Handouts	56-62
Uses of stacks: evaluating postfix expression, converting infix to postfix form	7	Handouts	63-70
C++ templates, using templates in Stack class	8	Handouts	71-81
Assignment # 01
Runtime memory organization, runtime stack layout, Queue ADT, implementing queue ADT using linked list and circular arrays.	9	Handouts	82-92
Uses of queue: simulation, event based simulation of a bank, priority queues	10	Handouts	93-104
Priority queue implementation using arrays, Binary trees	11	Handouts	105-122
Complete Binary tree, application of Binary trees: search for duplicates, Binary Search Tree (BST), implementation using C++.	12	Handouts	123-134
Cost of search in BST, binary tree traversal: pre-order, in-order,  post-order	13	Handouts	135-145
Recursive pre-order, in-order, post-order traversal, non-recursive traversal using explicit stack, level-order traversal	14	Handouts	146-157
Level-order traversal using a queue, deleting node in BST	15	Handouts	158-169
C++ code for delete node in BST. The BST class	16	Handouts	170-188
C++ Reference variables	17	Handouts	189-202
Assignment # 02
C++ Reference variables, the C++ const keyword	18	Handouts	202-210
Degenerate BST, height balanced BST - AVL trees.	19	Handouts	211-219
Inserting in a AVL tree.	20	Handouts	220-230
Inserting in a balanced BST, tree rotation for height balancing	21	Handouts	231-239
Quiz # 01
Various rotation cases, C++ code for insert with rotations	22	Handouts	240-256
Mid Term Exams
C++ code for insert with single and double rotations	23	Handouts	257-272
Deleting node in an AVL tree, other uses of trees: expression trees	24	Handouts	273-283
Constructing expression trees using stacks, Huffman encoding for data compression	25	Handouts	284-295
Building Huffman code tree, generating Huffman code	26	Handouts	296-306
Threaded binary trees.	27	Handouts	307-320
In-order traversal of threaded binary tree, complete binary tree stored in an array	28	Handouts	321-332
Assignment # 03
The Heap ADT, implementation of heap ADT using complete binary tree, inserting into a heap.	29	Handouts	333-347
Delete (min) in a heap. Build heap from a set of data items.	30	Handouts	348-359
Build heap operation. Heap ADT as a C++ class	31	Handouts	360-369
Proof of Build heap being a linear time operation.	32	Handouts	370-378
Priority queue implementation using heap ADT, selection problem, heap sort. Equivalence relations	33	Handouts	379-385
Equivalence relations, Disjoint Sets	34	Handouts	386-392
Disjoint sets implementation using inverted trees, the Union and Find operations on Disjoint Sets.	35	Handouts	393-403
Optimizing Union and Find operation, Union by size, path compression	36	Handouts	404-415
Assignment # 04
Uses of Disjoint Sets: Image segmentation, maze generation	37	Handouts	416-423
The Table ADT, implementation using arrays	38	Handouts	424-429
Table ADT implementations using sorted arrays, binary search algorithm on sorted arrays, skip lists	39	Handouts	430-440
GDB # 01
Skip lists insertion and deletion	40	Handouts	441-448
Table ADT implementation using Hashing	41	Handouts	449-458
Collision resolution in Hashing	42	Handouts	459-467
Quiz # 02
Other uses of Hashing, sorting	43	Handouts	468-473
Selection sort, insertion sort, bubble sort algorithms	44	Handouts	474-484
Divide and conquer strategy: merge sort, quick sort.	45	Handouts	485-504
Final Term