Xingni Zhou - Data Structures Based on Linear Relations

Information and Computer Engineering

Volume

Data structures and algorithms analysis New perspectives

Edited by

Volume

ISBN 9783110595574

e-ISBN (PDF) 9783110595581

e-ISBN (EPUB) 9783110593181

Bibliographic information published by the Deutsche Nationalbibliothek

The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available on the Internet at http://dnb.dnb.de.

2020 China Science Publishing & Media Ltd. and Walter de Gruyter GmbH, Berlin/Boston

Looking at old problems with new perspectives, requires creative thinking Einstein

When I was teaching the course on data structures six or seven years ago, I advanced with the methods Ive always used in this course. After a few lectures, I received an email from a student in which he said: I myself like programming a lot. On one hand I am familiar with the computer, both software and hardware, thus I never lack an understanding of the foundational knowledge (for example, I know memory, address, circuits etc. very well); on the other hand, I seem to find your way of lecturing easy to adapt to and likable But it seems that many of my classmates are still having difficulties in studying data structures

I have taught data structures for more than ten years. From my experience, students always treat data structures as a hard course to take. Among many discipline courses of computer science, data structures is deemed by many students as a very difficult course []. Although I didnt learn data structures when I was an undergraduate, and only learned data structures by myself later because of the need to teach, I have never thought of it as something difficult. Why?

Reflecting upon my study and work experience carefully, maybe its indeed like what the email says it was because I already had a strong grasp of programming and some understanding of the applications of data structures. For example, the first software development project I undertook already involved applications of concepts such as multithreading, linked list, queue and hash. Although I didnt learn them at school, I was able to easily understand the corresponding data structures and algorithms via dealing with concrete problems first. Therefore, when I started to learn the theoretical knowledge on the textbooks later, I was able to get up to speed pretty soon. Another reason is that I learned software testing methods during the project development. By tracing the programs, it is easy to see their execution paths and results, and thus helping to understand the design and implementation of algorithms.

I think of the textbooks available to students nowadays: they introduce the concepts in a highly abstract way. However, there isnt enough perspective on the relationship between the theoretical abstraction and the real-world application. If there isnt enough hands-on knowledge, it would be hard to understand or accept the abstraction. There is a bad tendency nowadays: textbooks and lectures focus too much on abstract knowledge and ignore actual applications. Textbooks on data structures typify this tendency. Such a situation is harmful for entry-level students, as they cant walk into the abstract world, and thus eventually dont get what the courses are talking about [].

] that the concepts on data structures are actually not hard, the real difficulties are:

1. How to make the leap from data structure concepts to program implementations (how to implement a data structure):

2. How to make the leap from actual application to data structure abstractions (how to make use of data structures to solve actual problems).

I myself only learned a little bit of programming as an undergraduate (no more than 20 h of lab in total), and I didnt have any knowledge on data structures. But as soon as I graduated, I took part in a large-scale software development project that eventually won the third prize of the National Award for Science and Technology Progress. Subsequently, I also participated in the software installation, testing and maintenance of multiple telecommunication companies, and thus experienced first-hand the most vivid cases that actuated the above two leaps. Although the development process was very demanding working late into the night every day for more than half a year at the clients office, dealing with the enormous pressure of memory leak on a 24-h online system, finding bugs urgently after a system crash on both the production and backup machine I shall say that I was lucky. Although I didnt learn much programming at school, I was able to learn by myself and from my colleagues many new skills, knowledge and experience in my work. Such tempering by practice was very conducive to my later understanding and teaching of courses related to program design.

Upon reflection and summarization, I believe the reason why the students struggle to make the two leaps mentioned above is because of the disconnection between the teaching method of the traditional textbook and the practical demands.

Nietzsche once wrote: One cant understand what he hasnt experienced. In other words, people only accept information related to something already understood in the past. This is a process of learning via comparison. In this process, the brain seeks to find the connection between each piece of information, leaning on past experiences to understand new things [].

Euler believed, if the instructor is unable to teach the thought process behind the mathematical problems, math education will be meaningless. The de facto inventor of modern computer Leibniz also said: according to me, nothing is more important than exploring the source of the invention; this is much more important than the ].

Traditional textbooks on data structures usually just list the question, and then directly give out the algorithm. But to actually solve problems with the computer, one has to consider: how to analyze the known information in the question, how to mine the connection among data (the logic structure of data), how to choose the appropriate storage method (the storage structure of data) to save the logical structure into the computer and then arrive at the algorithm top-down, from the storage structure. This is the real thought processes and steps for solving actual problems, and also the methods employed in software development. The problem of traditional textbooks is the lack of guidance and analysis on the thought process, which causes a surplus in concept illustration and implementation details, yet a lack of description on the process of design and implementation. This leads the students to only see the detailed solution of one problem after another, yet unable to grasp the general method and principles of algorithm design.

This book attempts to give the knowledge background and the application background of the questions and algorithms from the perspective of apply what one has learned, adding in examples from actual software development. It focuses on the methods of analysis and thought flows of design, and illustrates the testing and analysis process of important algorithms, making up for the shortcomings of traditional textbooks. It teaches the students to solve problems with methods of software development. This allows the students to comprehend and grasp them easily and to flexibly choose the appropriate logic structure, storage structure and the corresponding algorithms, design programs that have high performance and efficiency, and that are easy to read and maintain, thus fulfilling the aim of the data structures course.