Data Structures and Algorithms: An introduction
[DSA introduction] [Hello. This is Rachel Cardell-Oliver from the University of Western Australia]
Over the next few weeks we will be studying the topic of data structures and algorithms.
This talk asks What are data structures? and What are algorithms?
An algorithm is a clearly specified set of instructions a computer will follow to solve a problem.
Many algorithms require the use of a proper representation of data to achieve efficiency. This representation, and the operations that are allowed for it, are known as a data structure.
Let's consider an example. When a friend visits your city, you show them a map for getting around. Here is a map of my city, Perth. I have marked some places I would like to show my friends: the airport and the city, the national park, the University of WA, Cottesloe beach, Rottnest island, and Fremantle for an evening out by the harbour. Next, I show the connections between those places, using buses, trains, and a ferry. Now I have abstracted from the "real world" and represented the sight-seeing problem by a data structure. This particular data structure is know as a graph. Now we can start solving problems. The set of instructions I follow to solve a problem is called an algorithm.
Using the graph data structure, I can use algorithms to program solutions to problems such as, is there a way to see all the sights in one day? What are the best routes to use? and how long will that take? To make the problem more realistic, imagine a graph with all possible roads and bus routes included, as is managed by your favourite route-finding app on your phone.
Computer programs are written to solve many, many different applications. But the same fundamental data structures (such as graphs) and the same algorithms are used again and again. This data structures and algorithms course will introduce you to some of the most useful and widely used ones. You will learn a toolkit of problem solving methods that you can apply in any problem domain: from designing a circuit board or a computer network, to writing a simulator or method to compress your data.
In many cases, you will not need to write programs for the data structures and algorithms yourself. This is because most modern languages now come with libraries that provide efficient implementations of the fundamental data structures and algorithms for you. Java, for example, provides the Collections API which we will study later. But in order to use the libraries effectively, it is necessary to understand the fundamental data structures and algorithms they provide. This understanding is sometimes called "computational thinking".
I'll conclude with a short story from the history of Computer Science.
In 1976 the Swiss Computer Scientist and Electrical Engineer, Niklaus Wirth, wrote a book called Algorithms + Data Structures = Programs. This book was very influential, laying foundations for the discipline of computer science. I still have a copy of the 1976 version on my book shelf! Every CS major still take a course in data structures and algorithms. In recent years, DSA courses are being taught to students across all disciplines from architecture to chemistry to marketing. This is because knowledge of computer programming is now necessary in almost every field, a bit like mathematics. The cs50 course from Harvard University is a famous example of this new style of course. Many of the videos I will present are based on material from cs50, with grateful thanks.
Niklaus Wirth Bio:
Wirth was born in Winterthur, Switzerland, in 1934. In 1959 he earned a degree in Electronics Engineering from the Swiss Federal Institute of Technology Zürich (ETH Zürich). In 1960 he earned an M.Sc. from Université Laval, Canada. Then in 1963 he was awarded a Ph.D. in Electrical Engineering and Computer Science (EECS) from the University of California, Berkeley, supervised by the computer designer pioneer Harry Huskey.
From 1963 to 1967 he served as assistant professor of Computer Science at Stanford University and again at the University of Zurich. Then in 1968 he became Professor of Informatics at ETH Zürich, taking two one-year sabbaticals at Xerox PARC in California (1976–1977 and 1984–1985). Wirth retired in 1999. ETH Zürich today is (still) one of the leading schools in the world for engineering, science and technology.
[Source:
[ Presentation by Rachel Cardell-Oliver ]