Course Details

Data Structures (DSTR) course is designed to teach you data-structures from a users perspective. It focuses on standard data-structures and how they can be used to write efficient code. It also gives C++ implementations as well as discusses STL implementations and how to use them. The course has toy exercises as well as a project to design and implement a large representative data structure. This 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 master data structures.

Highlights

1. Strong focus on hands-on experience
2. Master data structures which are used on a day-to-day basis in big software projects
3. Gain insight into how to make trade-offs between data structures for your programming problems
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 and familiarity with Linux as the online laboratory is based on it. 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 as well as Programming With C++ to gain sufficient background before taking up this course in case you are not very comfortable with the pre-requisites.

Who should take the course

• Students who want to learn data structures 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 with data structures

Depth

This course is at beginners level. Most of the topics are treated with programming point of view. Focus is to provide an insight into how to choose the right data structure for your programming problems. Complexity of data structures are discussed in sufficient detail and examples are provided to help you make trade-offs. However, detailed theory behind individual data structures is not discussed. There are excellent text books available which deal with detailed theory and proofs such as "Introduction to Algorithms by Thomas H. Cormen et al.".

Detailed Description

The first section introduces data-structures, what is meant by them, what are the common operations, how algorithms can be designed around them and how to choose a data-structure for a particular algorithm. The next section focuses on some introductory math, which is needed to understand data-structures and analyze them.

Subsequent sections pick up one data-structure and delve deeper around this. We take the following approach to introduce various data structures: introduction, efficient operations on it, implementation in C++, STL implementation if any and common pitfalls. Specific issues/choices if any for a particular data-structure are also dealt with. Shown below is a detailed table of content for this course.

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. Linked list
   • Description and operations
   • Implementation in C++
   • STL implementation
   • Gotchas and usage scenarios
5. Dynamic Arrays
   • Description and operations
   • STL implementation
   • Gotchas and usage scenarios
6. Stack
• Description and operations
• STL implementation
• Gotchas and usage scenarios
7. Queue
• Description and operations
• STL implementation
• Gotchas and usage scenarios
• Priority queues
8. Hash Map
   • Description and operations
   • Hasing functions and collision
   • STL implementation
   • Gotchas and usage scenarios
9. Tree
   • Description and operations
   • Implementation in C++
   • Efficient operations and traversals
   • Traversal implementations
   • Gotchas and usage scenarios
10. Special Tree Structures
    • Binary search trees (BST)
    • Balanced and un-balanced BSTs
    • Self balancing BSTs
    • Gotchas and usage scenarios
11. Graphs
    • Description and operations
    • Depth first walk
    • Breadth first walk
    • Implementation in C++
    • Boost implementation
    • Gotchas and usage scenarios
12. Introduction to Graph Algorithms
    • Connected component detection
    • Topological sorting
    • Network flow
    • Spanning tree
13. Heap
    • Description and operations
    • STL implementation
    • Gotchas and usage scenarios
14. Some Usage Examples
    • Parsee trees
    • Circuit representation in VLSI systems
    • Simple web-page rank
    • Student database
15. Project
16. References

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