UD513_Intro_to_DS_and_Algo

Note and reference material to UD 513 Intro to Data structure and Algorithm

Course website: https://www.udacity.com/course/data-structures-and-algorithms-in-python--ud513

Table of content:

Lesson 1: Introduction and efficiency

Concept of time and space complexity

Big O notation

Evaluate complexity of an algorithm

Lesson 2: List based collection

Concept of container

Python built-in type - list

Python class usage

Abstract Data Type - Stack, and implementation

Abstract Data Type - Queue, and implementation

Abstract Data Type - Linked List, and implementation

Lesson 3: Searching and Sorting

Concept of efficienct algorithm

Binary Search implementation

Concept of sorting

Concept of divide-and-conquer

Concept of recursion

Entry level sorting - Bubble sort

Advanced sorting - Merge sort, and tracing

Advanced sorting - Quick sort, and implementation

Recursion example - Fibonacci sequence

Lesson 4: Maps and Hashing

Concept of key-value pair

Python built-in type - dictionary

Nested dictionary, and implementation

Concept of Hashing

Concept of load factor and collision

Abstract Data Type - Hash, and implementation

Lesson 5: Trees

Concept of tree, and terminology

Definition of tree traversal - pre-order, in-order, post-order

Tree traversal with recursion, and implementation

Concept of Binary Tree

Concept of Binary Search Tree, and implementation

Concept of Balanced Search Tree

Concept of Red-black Tree

Lesson 6: Graph

Concept of grpah, and terminology

Definition of graph traversal - Topological, Depth First Search (DFS), Breadth First Search (BFS)

Abstract of graph presentation - Adjacency List, Adjacency Matrix, Edge List

Implementation of DFS as well as BFS

Implementation of graph presentation