Notes on Algorithms

https://rafal.io/posts/assorted-notes.html

https://sites.google.com/site/indy256/algo contains Source code implementation of common algorithms

Hash Tables

http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx

Set Union / Find

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure

Dynamic Programming

http://www.seas.gwu.edu/~ayoussef/cs212/dynamicprog.html

http://marknelson.us/2007/08/01/memoization/

http://20bits.com/articles/introduction-to-dynamic-programming/

http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

http://www.ics.uci.edu/~eppstein/161/960229.html – Longest common subsequence

Book Chapter : http://www.sce.carleton.ca/faculty/chinneck/po/Chapter15.pdf

More on Dynamic Programming

Dynamic Programming is a technique that trades space for time. It stores the results computed (which might be needed in future) in memory, thus avoiding the need to compute the result everytime.

See [Dynamic Programming] page for more info

Thanks Bikram Ballav for compiling these

#Data_Structure_Algorithm_What_To_Read Data Structure and Algorithms

Syllabus:

Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs.

Searching, sorting, hashing. Asymptotic worst case time and space complexity. Algorithm design techniques: greedy, dynamic programming and divide-and-conquer. Graph search,

minimum spanning trees, shortest paths.

1. What Books to read :

Book Name :

1 Data Structures Using C – Aaron M. Tenenbaum [ Chapter 1 to 8, 9.3 ] ch 1 , ch 2 completely

from chapter 3 – 3.1, 3.2, 3.3 recursion

chapter 4 – 4.1 to 4.5 queue and stacks

chapter 5- 5.1 to 5.5 tree

chapter 6 completely sorting 6.1 to 6.5

chapter 7 completely – 7.1 to 7.4 searching

chapter 8 completely – 8.1 to 8.4 graph and their applications

and from chapter 9-9.3 only to read dynamic memory management

2 Data Structures and Algorithm Analysis in C by Mark Allen Weiss [ Chapter – 2, 3 , 4, 5, 6, 7, 9, 10 ]

3 Fundamentals of Data Structures by Ellis Horowitz and Sartaj Sahni [ Chapter – 1 , 2, 3 , 4, 5, 6, 7, 9 ]

4 Thomas H Cormen et.al ( covers both Data Structure and Algorithms ) – Chapter 1,2,3,4[excluding 4.4],6,7[excluding 7.3],8,10,11[excluding

11.5],12[excluding 12.4], 15.1, 15.2,15.4 , 16.1, 16.2, 16.3 , 18, 22,23, 24[excluding 24.4 and 24.5] , 25 .

Nptel web course by IIT G : http://nptel.ac.in/courses/106103069/32

2. From where to read ? Topics for that subject to read along with Chapter Subparts :

Data Structure

1 Array : Accessing Array using Pointers , Representation: 1 D Array and 2D Array

Mark Allen Weiss chapter 3.2.1 / Horowitz chapter 2

2 Stacks : Operations and Applications

Mark Allen Weiss chapter 3 – 3.3 / CLRS 10.1 / Horowitz chapter 3 / Tenenbaum Chapter 2

3 Queues : Operations and Applications , Priority queue, Circular Queues: Operations and Applications

Mark Allen Weiss chapter 3 – 3.4 / CLRS 10.1 / Horowitz chapter 3 / Tenenbaum – 4.1 to 4.5

4 Linked lists : Singly Linked List , Doubly Linked List, Circular Linked List

Operation – Creations, insertion and Deletion of Nodes from a List

Linked Implemented of —–> Stacks , Queues , Priority queue

Circular Lists

Doubly Linked List

Mark Allen Weiss chapter 3- 3.2 / CLRS 10.2 / Horowitz chapter 4

5 Trees – Binary Trees : 1 Representation: Array & Linked Representation of Binary Tree , 2 Operations: Insert, Delete , 3 Traversal: Preorder, Inorder, Postorder

Mark Allen Weiss chapter 4 / CLRS 10.4 / Horowitz chapter 5 / Tenenbaum 5.1 to 5.5

6 Binary Search Trees

• AVI-trees : AVL Tree Insertion, Deletion, Rotation — Mark Allen Weiss chapter 4.4

• B-tree CLRS chapter 18 [ 18.1, 18.2, 18.3]

• External Search

Mark Allen Weiss chapter 4 – 4.3 / CLRS chapter 12.1 to 12.3

7 Binary Heaps : Method and Complexity , Priority Queue

Mark Allen Weiss chapter 6 / CLRS 6.1, 6.2, 6.3, 6.5

8 Graphs : Representation and Traversal .

Representation: Matrix, Adjacency list

Traversal: Depth First Search, Breadth First Search

Mark Allen Weiss chapter 9.1.1 / CLRS chapter 22 / Tenenbaum chapter 8.1 to 8.4 / Horowitz chapter 6

Algorithms

1 Searching : Binary Search , Selection

CLRS – Linear Search, binary search. Chapter 12 of CLRS 12.1, 12.2, 12.3 / Tenenbaum 7.1 to 7.4

2 Sorting : Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort, Quick Sort, Radix Sort, Bucket Sort

CLRS – Chapter 1, 2, 6.4 , 7 [excluding 7.3] ,8 / Tenenbaum 6.1 to 6.5

3 Table based data Structure : Hashing : Hashing Techniques

Direct Addressing , Properties of hash function, Universal hashing

Types of hashing — a) Chaining b) Open addressing , Collision resolution schemes – a)Linear Probing b) Quadratic Probing c) Double Hashing

Demerits associated with linear and quadratic probing(Primary and Secondary Clustering Problem )

Mark Allen Weiss chapter 5 / CLRS 11.1 to 11.4

4 Asymptotic worst case time and space complexity CLRS – Chapters 3,4. [excluding 4.4]

5 Algorithm design techniques:

Greedy – CLRS Chapter 16 – 16.1, 16.2, 16.3 . Dynamic programming – CLRS Chapter 15 – 15.1, 15.2, 15.3, 15.4 . Divide-and-conquer – CLRS Covered by merge sort in Chapter 2.

6 Graph search CLRS BFS, DFS – covered in chapter 22- 22.1 to 22.5

7 Minimum spanning trees CLRS Chapter 23. Prim’s and Kruskal’s algorithms 23.1 , 23.2

8 Shortest paths Single Source Shortest Path – CLRS Chapter 24 [excluding 24.4 and 24.5] , All Pairs Shortest Path – CLRS Chapter 25 [ 25.1, 25.2]

3 . Types of problems from where questions came previous years :

Understand Different Problems on Stack, Queue, Link List. Generally they come in a C program, But you can solve them only if you know the logic.

Properties of Heap. Deletion and insertion of items in the heap.

Practice Tree problems like no of leaf nodes, non leaf nodes, total nodes, height of the tree, no of full nodes, mirror image, etc.

AVL tree and balancing them on insertion and Deletion.

Binary tree, Binary Search Tree, Inorder, Preorder, Postorder traversal. Spanning Trees, Minimum Spanning Tree problems.

Finding Complexity : Sometimes direct question comes related to complexity like give complexity of Heap sort. But mostly you are given a code or question. You need to find best average case complexity of that problem. So try to find complexity of every algorithm or program which you practice.

Also understand properties of complexity. Sometimes relation between them is asked.

Searching and Sorting Problems. Difference between Different Techniques and how to apply them on different real life problems.

Questions on approach of dynamic programming, Divide and Conquer [ Merge Sort ] , Greedy [ Huffman code has been asked many times for GATE] and Brute Force.

Practice basic problems like quick sort, merge sort, knapsack problem, matrix chain multiplication, LCS, Job sequencing, Compressing Mechanism.

Questions come from filling of hash tables with

1. linear probing,

2 . quadratic probing,

3. expected no. of empty slots after x insertions (application of probability),

4. load factor.

5 closed hashing

6. property of a hash function

7 Universal Hashing

— Thanks to Bikram Ballav —-