About Course

Advanced Data Structures and algorithms is a course for an engineering graduate to improve the problem solving skills with the help of different Data Structures and algorithmic approaches. These methods can be used in decision making and optimization problems. Advanced Data Structures and algorithms course covers concepts to find strategies to win games, finding best paths and cost, searching and matching of words . The course also includes fundamental terminology of non-linear data structures like Trees and Graphs which are especially used to handle large amount of data. The course will also enable the use of appropriate searching methods in handling collection of elements.

Course Syllabus

Mixed Bag Problems:

• Rotate an array of size n in clockwise direction k times.
• Prime Generator.
• Given a sorted array of n distinct integers where each integer is in the range from 0 to m-1 and m > n. Find the smallest number that is missing from the array.
• Calculate the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
• The birthday bar problem.
• Given a string text, you want to use the characters of text to form as many instances of the word “balloon” as possible.
• Partition the line of filing cabinets into K sections so as to minimize the maximum number of files a partition contains. E.g.: 10 20 30 40 50| 60 70 | 80 90 [N = 9, K = 3].
• Find Longest common prefix string amongst an array of strings.

Online Resources

• Rotate Array
• Count Primes
• Missing Element in Sorted Array
• Range Sum
• The Birthday bar
• Maximum number of ballons
• The Painters Partition Problem
• Longest Common Prefix

Problems on Game Theory:

• Bulb Switcher problem.
• Game of N stones where each player can remove 1, 3 or 4.
• Game of Nim.
• Find the winner in Nim game where a player fails if XOR of remaining elements is 0

Online Resources

• Bulb Switcher
• Game of Stones
• Nim-game-1
• Variation in nim game
• Pots of Gold

Greedy Method

Introduction, general method.

Problems on Greedy Method:

• Activity Selection Problem.
• Connect N ropes with minimum cost.
• Fractional Knapsack.
• Dijkstra’s Shortest path

Online Resources

• Activity Selection
• Minimum Cost of Ropes
• Maximum units on a truck
• Minimun Cost Path

Dynamic Programming

Introduction, Memoization and Tabular Methods to store the results.

Problems on Dynamic Programming:

• n-stair problems.
• Domino/Tiling problem.
• Compute nCr.
• Longest increasing sub sequence.
• Maximum contiguous sub array/non- contiguous sub sequence sum.
• Maze with blockers.
• Maximum collected apples in a 2D maze.

Online Resouces

• Climbing Stars
• Domino and Tromino Tiling
• NCR1019
• Longest Increasing Subsequence
• Maximum Sum Increasing Subsequence
• Unique Paths
• Gold Mine Problem

Graph Theory

Graph terminology, Graph representation, Graph traversal techniques.

Problems on Graph Theory :

• Check if there exists a path between 2 given nodes A and B of a graph.
• Detect Cycle in a Directed/Undirected Graph.
• Given an undirected graph, check if it’s a tree.
• Find the number of islands considering neighborhood.
• Given an unweighted, undirected tree, find the length of the longest path in that tree. The length of a path is the number of edges in that path.
• Given a snake and ladder board, find the minimum number of dice throws required to reach the destination or last cell from source or I cell.

Online Resources

• Find if path exists
• Detect cycle in a diected graph
• Detect cycle in an undirected graph
• Is it a tree
• Number of Islands
• Snake and Ladder

Priority Queues/Heaps

Introduction to Priority Queues, Heap, Implementation of Heaps.

Problems on Priority Queues/Heaps:

• Given an array of integers, find k smallest elements in the array.
• Given an array of n integers, devise an algorithm to get median of the sub-array 0 to i for ∀ i from 0 to n-1. *Given an array of n elements, where each element is at most k away from its actual position in the sorted version of the array (k-sorted array), devise an algorithm that sorts the given k-sorted array in O(n x log2(k)) time.
• Given a row and column wise sorted matrix of size n x n, print all elements in sorted order

Online Resources

• Top K numbers
• Find Median in a stream
• Nearly Sorted
• Sorted Matrix

Tries

Introduction to trie and its implementation.

Problems on Tries :

• Design a spell-checker
• Build auto-complete word suggestion.
• Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another.
• Given an array of integers, we have to find two elements whose XOR is maximum.

Online Resources

• Trie-insert-and-search
• Search Query Auto Complete
• Maximum xorof two numbers
• Minimum xor value pair
• Prefix match with other strings

References

• Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed. Fundamentals of Data Structure in C. 2nd Edition. University Press, India, 2008.
• Reema Thareja. Data Structures Using C. 2nd Edition. Oxford University Press, New Delhi India, 2014

Syllabus

• Click here to view