This course covers data structures such as dynamic array, dynamic string, long numbers, lists, heap, hash, trees and graphs. You will learn to create objects from scratch using object-oriented Java programming concepts, and then build bigger objects using the objects that have already been built and tested. You will write algorithms on these objects using techniques such as recursion, greedy, divide and conquer, back tracking and dynamic programming. The course discusses algorithms such as searching and sorting, union find problems, knapsack problems and NP complete problems. You will also learn to compute the worst case complexity of the algorithms in terms of time and space in order to choose the best techniques, and to ensure that the objects scale with arbitrarily sized inputs.
The course emphasizes common problems and implementation details in Java and does not cover advanced Java features. It provides ample examples and testing of codes.
- Introduction to data structures and algorithms
- Review of Java used for this course
- Need for algorithms
- Complexity of algorithms in terms of time and space
- Tools for computing complexity in terms of problem size rather than hardware used
- Data structures for building extremely large objects like array, stack, heap, hash, trees and graphs
- Algorithm techniques for solving problems like greedy, divide and conquer, back tracking and dynamic programming
- Implementing objects and algorithms that scale for arbitrary large size problems
- Proving the worst case complexity of each algorithms in terms of time and space
Skills Needed: Working knowledge of Java or C/C++.