Algorithms

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 —-

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s