Syllabus + Introduction Data Struct. - 2019.01.14

Page 1

ADT: Abstract Data Type

Sorting Algorithms 0(n^2):

Selection Sort

Bubble Sort

Insertion Sort

More Efficient Sorting Algorithms 0(nlogn):

Merge Sort

Quick Sort

Divide - and - Conquer Algorithm

Website Recommendations for Job Interviews:

GeeksForGeeks

Leetcode.com (very good).

For the first mini project: Refresh your mind about:

Template in C++

Generic Programing

Inheritance

Polymorphism

Operation Overloading Functions

Vectors (we will review in our class)

For one of the mini projects: We will Implement Auto-complete features using Trie

Week 1-2:

Array

Pointer : Linked list (like carts on a train and pointers to connect each nose), template class.

Class: Array Bag (we will learn to define an Array Bag class), inheritance, polymorphism.

Introduction:

Data Structure: A particular way of organizing data in a computer so that it can be used efficiently

We will learn various data structures:

Array

Singled linked list

Stack (to develop a basic calculator)

Queue and Priority Queue (to simulate the bank driven data system)

Tree (hierarchical data structures)

Heap

Hash table

Graph

Problem solving technique: Recursion (important for tree data structures)

Different Sorting algorithms and their efficiency

Efficiency: To solve a problem

Array: A linear data structure consisting of a collection of elements, each identified by at least one array index

Used to implement many other data structures, such as lists, heaps, hash tables, queues, stacks and strings

Disadvantage:

Cannot be easily extended or reduced to fit the data set.

Expensive to maintain new insertions and deletions.

Singly Linked List: A linear data structure where each element is a separate object

Each object (node) contains two items:

The data

The reference to the next node

Linked List:

Advantage:

A dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand.

Can use more memory than an array

Disadvantage:

Does not allow direct access to individual elements

Uses more memory compared with

Stack: A linear data structure which follows a LIFO order in which the operations are performed

Real life example:

Plates stacked over one another in canteen

Implemented by:

Array, Linked list or Queue

Application

Basic calculators employing a reverse polish notation can use a stack to hold values.

Example: 1+4x5+2

Queue: A linear data structure: FIFO (First in First out) structure.

The element is inserted from one end called REAR

The deletion of existing elements takes place from the other end called FRONT.

Can be implemented:

Array

Linked list

Stack

Tree: A hierarchical (or non-linear) data structure:

Advantage:

Trees reflect structural relationships in the data

Trees are used to represent hierarchies

Trees provide an efficient insertion and searching

Trees are very flexible data, allowing to move subtrees around with minimum effort

Binary Tree:

Complete tree

Full tree

Binary Search Tree: All of the left children are less than the top level node value. All the right children will be greater than the value of the top level node.

Traversals:

(Can be implemented using Stack)

Preorder

Postorder

Inorder

Level order

Advanced topic:

AVL tree, Red-black Tree

Heap and Priority Queue:

Heap: is a complete binary treee

Min Heap

Max Heap

Use Heap to implement Priority Queue

Hash Table: A data structure used to store key/value pairs

Use an array as a storage medium

Use a hash function to compute an index into an array in which an element will be inserted or searched

Insertion and search operations are irrespective of the size of the data.

Key -> *box* -> array from 0 to 5

Sorting Algorithm:

Selection Sort

Bubble Sort

Insertion Sort

Merge Sort

Quick Sort

Radix Sort

Efficiency of different sort algorithms.