Course Details

Introduction to Algorithms (IALG) course is designed to introduce the algorithmic approach to programming. Data-structures and algorithms together form a solid base on which one can easily build programming expertise. Each algorithm is explained in detail, its usage and data-structure requirements. Implementations are discussed in C++ and STL implementation (if available) is discussed.

Design and analysis techniques such as greedy algorithms, amortized analysis and dynamic programming are discussed. Exponential complexity algorithms are introduced and approximate solutions touched upon. The course has various exercises around algorithms. The course can be completed in around two weeks time. We also suggest you to go through our blog on Art of Programming: Data Structures to gain an insight into why it makes sense to learn more about data structures and algorithms.

Highlights

1. Strong focus on hands-on programming experience
2. Gain insight into how to choose the right algorithm for your programming problem
3. Familiarity with C++ algorithm libraries
4. Discuss with the instructors on the forums as much as you want

Instructors and Forum Moderators

This course is taught by Anup Gangwar and Basant Dwivedi. They will be moderating the course forums as well as lead the contact sessions.

Pre-requisites

This course assumes a sufficient background in the 'C++' programming language, familiarity with Linux and good exposure to data-structures. If you have experience in working with any other UNIX system, then it is fine too. We recommend that you take up the courses User Level Linux, Programming With C++ and Data Structures to gain sufficient background before taking up this course.

Who should take the course

• Students who want to learn algorithms used on a day-to-day basis in the industry
• Job seekers or fresh hires who are looking forward to or starting a career in Embedded Systems, Electronic Design Automation, Networking, Databases or any other high-tech area having little or no programming experience of algorithms

Depth

This course is at beginners level. Most of the topics are treated with programming point of view. Focus is to expose you with the common algorithms, their complexity, basic idea behind these algorithms and popular algorithm design techniques. However, detailed theory behind individual algorihtms are not discussed. There are excellent text books such as "Introduction to Algorithms by Thomas H. Cormen et al." for detailed theory and proofs.

Detailed Description

The first few sections provide the background which is necessary for further sections. Subsequent sections pick up one algorithm and delve deeper providing C++ as well as STL implementations wherever available. Table of content for this course is as follows.

1. Introduction
   • What is a data structure
   • Why learn data structures
   • Integrating data structures in the program design
2. Standard Notations
   • Counting example
   • Asymptotic growth of functions
   • Commonly used functions and notations
   • Pseudo code conventions
3. Analysis of Data Structures
   • What should be analyzed
   • Performance analysis
   • Memory usage analysis
   • Memory access analysis
4. Solving Recurrences
5. Sorting
   • What is sorting
   • Where is sorting used
   • Why is it important to have efficient sorting
6. Sorting - Merge Sort
• Description
• Pseudo code
• Complexity analysis
• Implementations
7. Sorting - Quick Sort
• Description
• Pseudo code
• Complexity analysis
• Implementations
8. Sorting - Heap Sort
• Description
• Pseudo code
• Complexity analysis
• Implementations
9. Searching
   • What is search
   • Where is search used
   • Why is it important to have efficient search
10. Searching - Binary Search
    • Description
    • Pseudo code - array implementation
    • Pseudo code - BST implementation
    • Complexity analysis
    • Implementations
11. Graph Algorithms
    • What are graph algorithms
    • Where are graph algorithms used
    • Why is it important to have efficient graph algorithms
12. Graph Algorithms - Topological sorting
• Description
• Pseudo code
• Complexity analysis
• Implementations
13. Graph Algorithms - Connected components
• Description
• Pseudo code
• Complexity analysis
• Implementations
14. Graph Algorithms - Dijkstra Algorithm
• Description
• Pseudo code
• Sample run
• Complexity analysis
• Implementations
15. String Matching Algorithms
    • Brute force
    • Rabin Karp
16. Greedy Algorithms
• Description
• When will greedy strategy work
17. Dynamic Programming
• Description
• When to apply dynamic programming
18. Amortized Analysis
• Description
• STL vector analysis
19. Exponential Complexity Algorithms
• Introduction
• Graph coloring
• Graph scheduling
• Heuristics
• Approximation algorithms
20. References

The objective of this course as outlined above is to help you understand common algorithms and how to write programs around them. After finishing this course, you will be able to pick the right algorithm or design new ones for your programming problems. You will also be able to perform analysis and make appropriate trade-offs.