CS 300 • Midterm I • Data Structures

Motivation

Big-O Notation

Big-Omega Notation

Big-Theta Notation

Fundamental Rules

Analyzing Complexity

Example 1

Example 2

Example 3

Recurrences

Example 4

Solving Recurrences

Example 5

Our First Data Structure

Code for Amateurs

Linkedlist.h

ListNode

ListItr

List

Example 1

Example 2

Example 3

What is a Stack?

Stack.h

Implementation

Example 1

Example 2

Example 3

What is a Queue?

Queue.h

Implementation

Example 1

Example 2

Example 3

Tree as a Data Structure

Terminology

How do we implement Trees?

Binary Trees / Binary Search Trees

Example 1

BST.h

Implementation - Constructors/Copying

Implementation - Destructors

Implementation - Find

Implementation - FindMin/FindMax

Implementation - Insert/Remove

Implementation - Printing

Example 2

Example 3

Example 4

Example 5

Example 6

Why AVL Trees?

Height

AvlTree.h

Insertion - Part 1

Insertion - Part 2

Insertion - Part 3

Remove

Example 1

Example 2

Patron çıldırdı, O(1) istiyor!

Handling Collusions

Example 1

Hashtable.h (Seperate Chaining version)

Seperate Chaining Implementation

Example 2

Hashtable.h (Open Addressing version)

Open Addressing Implementation

Example 3

Introduction

Fundamental Properties

BinaryHeap.h

Implementation - Part 1

Implementation - Part 2

Example 1

Example 2

Example 3

What is the point?

How does it work?

Implementation

Example 1

Optimizing Union

Optimizing Find

Algorithm Analysis 1

Algorithm Analysis 2

Algorithm Analysis 3

Algorithm Analysis 4

Algorithm Analysis 5

Algorithm Analysis 6

Algorithm Analysis 7

Algorithm Analysis 8

Algorithm Analysis 9

Linked List 1

Linked List 2

Linked List 3

Linked List 4

Stack 1

Stack 2

Stack 3

Queue

Trees 1

Trees 2

Trees 3

Trees 4

Trees 5

Trees 6

AVL Trees 1

AVL Trees 2

AVL Trees 3

AVL Trees 4

Hash Tables 1

Hash Tables 2

Hash Tables 3

Hash Tables 4

Heaps 1

Heaps 2

Heaps 3

Heaps 4

Algorithm Analysis

Linkedlists

True/False Question 1

True/False Question 2

AVL Trees

Hashtables