CMPE231 Schedule

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:

 

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