Learning Data Structures & Programming
Programming and data structure are two critical elements in building a career as a software techie. India boasts many software companies like TCS, Infosys, HCL Technologies, Mindtree, Tech Mahinda, L&T infotech, ITC infotech, and First source. Every company has an in-house training unit. They induct graduate trainees and put them through rigorous coding training before induction. Many trainees cannot cope with the rigor and leave in the middle. The problem lies in background and preparation. There is a gap in demand and supply as far as the availability of the coders is concerned. Most placements happen based on the intrinsic capabilities of the students rather than their abilities to code. The companies would like to recruit only graduates from known institutions rather than graduates with coding capabilities. If the students have a good attitude, they can learn quickly and become productive quite soon. Yet, the companies would still prefer the graduates who can be effective from day 1. In-job training is only possible for short durations like a week or two or three weeks. With this in mind, most companies will prefer undergraduates with good aptitude and who have received enough programming and data structures training. So, in this blog, I address the issue of training in programming and data structures. Let me address these issues one at a time. The first is the choice of programming language.
I remember that a few of our colleagues in the department were excited about Java and ignored the saner voices to introduce Java for teaching programming to the first- year students. They argued that Java could enable students to learn network programming. The students may use embedded graphics and multimedia in programs and create useful utilities that excite them. Unfortunately, it turned out to be a disastrous experiment, as three of the other faculty members, including me, predicted. The student counselor told us that some students could not comprehend the lectures in the class, which focused mainly on teaching objects, inheritance, polymorphism, and object manipulation to students who never had any previous coding experience. It is impossible to teach any topics like network programming or embedding graphics, audio, or video in a one-semester course. It was wishful thinking of the colleagues who insisted on the experiment of introducing Java as the first programming language course. I still remember that our opinions were treated in a patronizing manner “oh, you don’t know” or “I can’t believe you don’t understand.” The result was that many students sought help from city coaching centers to complete programming assignments. Since the first programming course is compulsory for all engineering students across disciplines, professors from other departments were very upset with the dept of CSE for carrying out such a disastrous experiment on the students. Finally, after six semesters, we reverted to C. C with all its peculiarities, still the most preferred language for teaching programming if we carefully avoid the tricks.
Of late, some university depts have started using Python. Python is catching up quickly as the preferred choice for teaching programming courses. However, if my memory serves me correctly, we taught PASCAL until 2000 to the students at IIT Kanpur. It is pedagogically the best programming language, as it is the closest implementation of algorithms into code. As far as Python is concerned, the three significant advantages are:
- Creating Python programs takes significantly less time than programming either in Java in C++ or C.
- Python programs are shorter than the equivalent programs in Java or C++ because of dynamic typing and built-in types.
- Many useful libraries are available that support Python programs’ easy use.
Most leading universities in the US, including MIT, CMU, Berkeley, UIUC teach Python as the first programming language course ( Esther Shein , Python for Beginners, CACM, vol 58, no. 3).
IIT Bhilai is carrying out an exciting experiment. It has started to teach web programming using Python and Flask at an introductory level. I am not sure about the students’ responses. However, the idea is entirely novel. It can achieve two things. First, the students will be excited to see that their programs can be helpful and available. After all, one learns to create software that others will use, and most users will use it over the internet through a public server. So, I believe the approach is likely to have greater acceptance among the students. Pedagogically, it will not be a significant shift from teaching Python. However, it has an added advantage of students learning HTML, CSS, Flask, and Python. Teaching Python through a web programming approach came from Rajat Moona, the incumbent director of IIT Bhilai. Since the faculty at IIT Bhilai is young, they enthusiastically supported it.
I believe data structure is taught to all computer science undergraduate students. There are many variations in teaching data structures. Some view the course as a gentle introduction to algorithms, and theoretical underpinning is more critical than implementation issues. Perhaps, the thinking behind it is that the students have learned introductory programming. So, students know how to code. They can manage to write programs without being told to implement data structures. The theory is more important as knowing how to analyze code would make them realize efficient coding is more important than just coding. The argument seems to be very strong and elementary to understand. However, the vital point it misses is that the introductory programming course emphasizes learning syntax and the meaning of the programming constructs. However, efficiency issues are touched on but not discussed in depth. Building and learning clean programming skills are more important than understanding the programmatic manipulation of complex data structures.
Furthermore, an introductory programming course is a requirement across disciplines. Apart from Computer Science and Engineering students, it includes other streams such as Electrical, Mechanical, Chemical, Material Science and Engineering, Maths, Physics, Chemistry, and Biological Sciences. So the course is not designed for programming as we expect from CSE students in the future. Therefore, without programming practice in the data structure course, I believe students of CSE tend to develop code phobia. The theory is required, but a proper balance is needed.
Graphs
- Depth-First Search of a Graph
- C Implementation of Graph Data Structure
- Graph Properties & Representation
- Graph Terminology
- Introduction to graphs
Hashing
- Universal Hashing
- Analysis of Open Address Hashing
- Hashing With Open Addressing
- Hashing By Chaining
- Well-Known Hash Functions
- Introduction to Hashing
Sorting Algorithm
- Quick Sort Analysis
- Quick Sort Algorithm
- Heap Sort Algorithm
- Shell Sort Algorithm
- Radix Sort Algorithm
- Merge Sort Algorithm
- Insertion Sort Algorithm
- Bubble Sort Algorithm
- Selection Sort Algorithm
- Introduction to Sorting Algorithms
Animation of Sorting Algorithms
Search Trees and Height Balanced Trees
- Search, Insert, Delete and Splay on Splay Trees
- Amortized Time Complexity of Splay Trees
- Splay Trees
- Deletion of Keys from B-Trees
- B-Trees and Insertions into B-Trees
- Examples of Deletions in Red-Black Trees
- Deletions in Red-Black Trees
- Examples of Insertions in Red-Black Trees
- Fixing color of Red-Black Trees After Insertions
- Introduction to Red-Black Trees
- Fixing Height Violations in AVL Trees
- Maintaining Balanced Binary Search Tree
- Average Case Analysis of BST
- Introduction to Binary Search Tree
Heaps and Priority Queues
Binary Trees and Their Applications
- Converting an Infix Expression to its Equivalent Postfix
- Huffman Encoding Algorithm and its Implementation
- Prefix code and text compression
- Basic Properties of Binary Trees (Contd)
- Basic Properties of Binary Trees
- Implementation of Binary Trees (contd)
- Implementation of Binary Trees
- Traversal of Trees
- Introduction to Binary Trees
- Introduction to Trees
Linked Lists, Stacks and Queues
- Circular Queue Implementation
- Queues as ADT
- Infix Expression Evaluation Using Stacks
- Stack of Multiple Data Types
- Stack Implementation
- Stacks as ADT
- Sparse Matrix Using Linked List
- Implementation of List in C