CMPE/CMSE 231 Tentative Schedule

/CMSE WEEK OF	TOPICS	Slides (Reference - Various Sources)	Slides actually covered in class	Notes (Reference - Various Sources)	LABS
	Primitive data structures. Binary and Decimal Integers, Real numbers, Character strings, Memory representation of information, pointers.	SL3 Mathematical background SL6 Pointer Basics 1 SL6 Pointer Basics 2 -Arrays - Structures	SL6 Pointer Basics 1 SL6 Pointer Basics 2 -Arrays - Structures	All topics
	Arrays and Pointers. Structures, Array of structures. Memory allocation (storage) of arrays. Multi- dimensional arrays (row-major, column-major). Self-referential structures. Dynamic memory allocation in C. Linked lists.	SL6 Pointer Basics 2 -Arrays - Structures SL6 Structures in C SL4 Arrays and Structures SL 5 - Data structures (Prentice Hall): Dynamic Memory Allocation Slides 1-14	SL6 Pointer Basics 2 -Arrays - Structures SL6 Structures in C SL 5 - Data structures (Prentice Hall): Dynamic Memory Allocation Slides 1-14 (pdf)
	Doubly linked lists, circular linked lists, abstract data types	SL1 Linked Lists (1-14) linked lists and stacks implemeted as linked lists) (pdf) SL4 Functions - Dynamic Memory allocation in C - Pointers (v) SL 5 - Data structures (Prentice Hall): Introduction - Self-Referential Structures -Dynamic Memory Allocation - Linked Lists - Stacks -Queues - Trees SL4 Linked List (slides 1-10) SL4 Circular Linked list - doubly linked list SL6 Abstract Data Types	SL6 Linked Lists (single - double) SL4 Linked List (slides 1-10) (pdf) SL4 Circular Linked list - doubly linked list (pdf)	Linked List Notes
	Stack as an Abstract Data Type. Primitive operations. Stack applications. Infıx-postfix conversion.	SL6 Stacks - Queues (Array + Pointer Implementation) - Circular Queues SL6 Stack Applications - parenthesis matching - evaluating expressions - infix to postfix conversion - postfix expression evaluation SL 5 - Data structures (Prentice Hall) SL1 Stacks - Recursion SL4 Infix to postfix conversion	SL6 Stacks - Queues (Array + Pointer Implementation) - Circular Queues SL6 Stack Applications - parenthesis matching - evaluating expressions - infix to postfix conversion - postfix expression evaluation
	Stacks continued. Functions. Recursive definitions. Factorial function. Fibonacci sequence. Binary search. The Towers of Hanoi problem. Recursion versus Iteration.	SL1 Functions as Data Types SL 5 - Data structures (Prentice Hall) SL1 Stacks - Recursion Factorial Fibonacci Sum Towers of Hanoi SL4 Linear and Binary Search	SL 5 - Data structures (Prentice Hall) (pdf) SL1 Stacks - Recursion (pdf) Factorial Fibonacci Sum Towers of Hanoi SL4 Linear and Binary Search (pdf)	Stacks and Queues Notes
	Recursion continued. Binary search. The Queue as an Abstract Data Type. C implementation of Queues. Circular queue representation.	SL6 Recursion - Merge Sort - Binary Search SL 5 - Data structures (Prentice Hall) SL4 Circular Queue (bad implementation) SL6 Stacks - Queues (Array + Pointer Implementation) - Circular Queues	SL6 Recursion - Merge Sort - Binary Search (only the binary search part) SL 5 - Data structures (Prentice Hall) SL6 Stacks - Queues (Array + Pointer Implementation) - Circular Queues	Stacks and Queues Notes
	Review
	Midterm Exams
	Trees. Binary Tree Representations. Binary search trees.	SL5 Trees - Binary Trees - Binary Search Trees SL6 Binary Search Trees	SL5 Trees - Binary Trees - Binary Search Trees
	Binary Tree Traversals (inorder, preorder, postorder). Binary Search Trees. Searching a Binary Search Tree. Inserting into a Binary Search Tree. Deleting from a Binary Search Tree.	SL1 Searching - Trees SL1 Searching - Tree traversals - Red Black trees SL1 AVL Trees - B Trees - B+ Trees SL4 Trees - Binary Trees - Tree traversals - Threaded Binary Trees - Heaps - Binary Search Tree SL4 Tree - General - Binary - Threaded - AVL - Balanced SL5 AVL Trees 1 SL5 AVL Trees 2 SL5 Trees - Binary Trees - Binary Search Trees SL 5 - Data structures (Prentice Hall) SL5 B+TREES SL6 Binary trees - Huffman Encoding - Traversals SL6 Threaded Binary Trees	SL5 Trees - Binary Trees - Binary Search Trees SL6 Binary Search Trees 'C' implementation of BST (home grown) Sample run of BST Midterm Exam Solution: MT1 MT2 MT3 MT4 MT5 MT6 MT7 MT8	Trees Notes
	Algorithmic complexity. Sorting. Bubble sort, insertion sort, quick sort, merge sort	SL6 Algorithmic Complexity I SL3 Asymptotic Analysis SL2 Complexity (i) SL2 Complexity (ii) SL6 Algorithmic Complexity II SL3 Algorithm Analysis SL1 Complexity SL1 Sorting SL4 Algorithm Def - Asymptotic Notations SL4 Sorting - Bubble - Insertion - Selection - Shell - Quick - Merge SL5 - Quicksort (nice) SL6 Recursion - Merge Sort - Binary Search SL3 Quicksort	SL6 Algorithmic Complexity I SL6 Recursion - Merge Sort - Binary Search SL1 Sorting SL5 - Quicksort (nice)	Trees Notes
	Heaps. Heap operations. Heap sort.	SL5 Heaps - Heap Sort - Priority Queues SL6 Heap - Heapsort - Priority queues	SL6 Heap - Heapsort - Priority queues
	Hashing. Graphs. Application of graphs. Representation of Graphs.	SL1 Hash Tables SL5 Hashing SL1 Graphs SL4 Graphs - Def - Implementation - Graph search SL6 Graphs - Operations - Traversals (Also tree traversals breadth/depth first) SL6 Minimum Spanning Tree SL6 Shortest Path Problems	SL5 Hashing SL4 Graphs - Def - Implementation - Graph search SL6 Graphs - Operations - Traversals (Also tree traversals breadth/depth first)	Graphs Notes 1 Graphs Notes 2
	Final Exams

Prof. Dr. Zeki Bayram