Algorithms and Data Structures: Aims and Objectives Algorithms and Data Structures: Aims and Objectives The role of algorithms and data structures in Computer Science Programming forms the core of Computer Science. Algorithms and data structures move the focus of programming away from the constructs found in programming languages to considering how we can program the computer to do useful things. You will find a course in algorithms and data structures comes early on in most computer science curricula, generally following on from the introductory programming course. An algorithm is a way of doing something - a set of instructions which if obeyed gives the desired result. But the instructions aren't specified in a programming language, rather they are specified in more general terms, and the programmer must find ways of translating the general idea given as an algorithm into the more specific instructions of whichever programming language he or she is using. Data structures are ways of storing data in computers so we can make best use of it. Again, these ways will be expressed in general terms and programmers have to fill in the details for whatever programming language they are using. Algorithms and data structures go together because most algorithms work on manipulating collections of data. Only in the very simple programs, of the sort you would only write when just learning to program, would what you have to do be so simple that you don't think of it except in terms of the actual programming language. In any realistic program which handles data, the question of how that data is going to be stored, and how it is to be manipulated to gain the desired outcome, is one of the main things the programmer will need to think about. A program may be technically right in the sense that it gives the right results, but so poorly designed in terms of the algorithms and data structures that it takes hours to deliver a result which could have been returned in seconds had it been better designed. Computer scientists over the years have thought long and hard about the main sort of problems that are likely to be encountered in building programs, and designed suitable algorithms and data structures which are efficient and which are proven to do the job correctly. This course will start you off becoming aware of these issues. Aims The aim of this course is to give you a feel for algorithms and data structures as a central part of what it is to be a computer scientist. You should end it appreciating that understanding the algorithm and data structures used for some problem is much more important than knowing the exact code for it in some programming language. You should be aware of the fact that there are often several algorithms for some problem, and one algorithm may be better than another, or one algorithm better in some circumstances and another better in others. You should have some idea of how to work out the efficiency of an algorithm, though we won't cover detailed formal analysis. You should be confident with algorithms expressed using both iteration and recursion, and have some idea of how to convert algorithms expressed using recursion into iteration. You will be able to use and design linked data structures, but appreciate why it is good programming style to hide the details of a data structure within an abstract data type. You will appreciate how the inheritance mechanism of object-oriented languages enables you to write generalised code expressing an algorithm or data structure in a way that may be used in a variety of real-world situations. Objectives The topics covered will be similar to those found in introductory algorithms and data structures courses in computer science departments across the world: sorting and searching algorithms, categorising efficiency in time and memory use, linked list and tree data structures, hash tables, stacks and queues. The objectives are that you should know something of all of these by the end of the course. As well as knowing about them, you should be familiar enough with the concepts that should you need to take any of them further and make use of them, you will be able to do so. I will not be taking the encyclopaedic approach of covering every aspect of every algorithm and data structure in detail, just enough of each to get a feel for it. Although this is not primarily a course on Java programming, Java will be the language used for it, and it is inevitable that there will be aspects of Java which you will come across first in this course. The computer science educational world is still getting to grips with the object-oriented revolution which produced the Java language, and this is reflected by conflicting claims over whether the object-oriented nature of Java is a help or a hindrance in teaching algorithms and data structures. I will be approaching data structures in an object-oriented style, which involves some updating of the "traditional" approach, though in an evolutionary rather than a revolutionary way. Because this is not a course on Java, I won't be covering the extensive set of data structures provided as part of Java's library in its collections framework, instead we will consider how to program such data structures using the building blocks of arrays and our own classes. The course will not assume the existence of any specialised development environment, or any input/output code beyond that provided as part of the Java standard library. You may find this "plain" approach an interesting and useful contrast with the use of the BlueJ Java interactive development environment in the Object-Oriented Programming course you are taking alongside this course. How to pass this course I made some notes on "how to pass the course" when I taught the introductory programming course at Queen Mary, and what I wrote then is mostly relevant to this course as well. The main thing is to be aware that learning is an active thing, not a passive thing, particularly in university education, and particularly in a subject like computer science. If your attitude is that you don't have to do very much yourself, and it is the job of academic staff to "fill you up" with knowledge, you won't get far. Academic staff can point you in the right direction, give you an indication of the things it is most profitable to study, set you exercises and assess you in them, but it's up to you to do the actual studying. You should not confuse learning with memorising. If at any point in this course you find yourself trying to memorise things, you have completely the wrong approach. If "last minute revision" forms a major part of your exam-passing strategy, then you need to rethink that strategy. In fact, you shouldn't be thinking in terms of "exam-passing stratgey" at all - you should be thinking in terms of understanding and appreciating an important aspect of a subject you are doing because you enjoy it. Then passing the exam will come naturally as a by-product. The best way to learn is by doing. Try to understand the algorithms and data structures, and then program them yourself in your own style. Please remember that being a university student is meant to be a full-time job, The fact that your scheduled lecture and lab hours do not make up a full working week means you should be devising your own schedule of extra work to make up the full 35-40 hours a week a paid employee would consider to be the norm. I have produced some notes of my own which explain my own view of the topics of this course, and my own attempts to write programs that demonstrate them. But you will also find it useful to see how others explain the same topics, and program them. This will help you understand that it's the principles that are important, not the exact form of the program. It would be useful for you to own and work through at least one of the recommended textbooks. I have also put together a comprehensive site of algorithms and data structures links specialising in particular on course notes provided in public web space for similar academic courses in universities across the world. Please make use of all these resources. The lectures should be regarded as the "pacemaker" of the course. They will give you an idea of the speed at which the topics in the course should be covered, and the relative importance of the different topics. "Chalk and talk" sessions which show how structures change as an algorithm is executed are an important part of the course. So please do not make the mistake of either feeling you don't need to attend lectures (because I have made a full set of notes available in advance) or that all you need to do is attend the lectures. Lab exercises will be set weekly exploring and testing some of the material covered in class. The best way to learn this material is by having practical experience with it. Lab exercises will be a mixture of problems similar to those you will encounter in tests and exams for the course, and more challenging examples which will take some time to think through and program. Although you are allocated a one hour slot a week, this is not meant to be the only time you spend on the lab exercises, you should expect to be spending several more hours a week outside the set lab hour on them if you are to tackle this course in the way intended. Book There is a recommended book for this course, Data Structures and Other Objects Using Java by Michael Main. There are actually many books on algorithms and data structures using Java to program the examples. This one covers the right mix of material at about the right level. So it makes good supplementary reading for this course. However, I am not going to follow the book closely, or much at all. It is there to read if you want an alternative approach to mine, and it is always good when learning some topic to look at how different people tackle describing it. One of the problems of the Michael Main book, so far as you are concerned, is that it assumes you have been taught an "objects first" approach to introductory programming - that is where the idea of objects and classes is one of the first thing covered in the introductory programming course. However, your introductory programming course did not take that approach, rather it was deliberately decided to leave these aspects of programming to your second programming course. Therefore, the way through the book which most closely corresponds with the order I will tackle the subjects is what Main calls the "early recursion / early sorting" route. This means starting with chapter 1, but then moving on to chapter 8 on recursion, followed by chapter 12 on sorting. As you cover more about objects and classes in your second programming course, I will move onto those data structures topics which rely on them. Chapter 2 covers the basic idea of classes, and it may be useful to read this to back up what you do in your programming course. Chapter 3 covers the idea of a collection class implemented as an Abstract Data Type, which we shall cover in detail in our course. We shall then cover topics in roughly the same order as the book. Matthew Huntbach Last modified: 8 December 2004
