Department of Information Technology

Algorithms and data structures

Programkonstruktion II in ITP

Find, store and modify data in efficient ways.

A data structure is a container for data. The stored data can be input, or output produced by a program, or any intermediate data created by the program. Operations can add data to a data structure, find data in a data structure, modify data in a data structure, remove data from a data structure, or list all the data in a data structure in some order.Not all containers are equally good for a given combination of these operations. For instance, it takes some time to pack things into a backpack with many pockets, but finding and removing a dry pair of socks should then go quickly. Conversely, if the objective is to take clothes to the laundromat, then putting them into a simple shopping ag is sufficient as the effort of orderly packing them into a backpack will not pay off. So, when choosing a data structure, one has to consider which operations will have to be performed on it, and how often.
An algorithm is an instruction set that one can follow in order to solve a given problem. Cooking recipes can thus be seen as algorithms. Also, the operations of adding, finding, modifying, removing, and listing data in a data structure need algorithms.A program is an implementation of some algorithm in a particular programming language. In order to evaluate algorithms, data structures and programs, we measure the amount of resources, such as time or memory, that are consumed. We can do so without implementing the algorithm into a program and running it, just like engineers, who can compute the strength of a bridge before building it. With such measurements, we can recommend when to use a particular algorithm or data structure. We can also compare two algorithms that have the same specification. Prerequisites: Functional programming, algebra. Goal: To provide methods to understand, analyse and compare data structures, algorithms, and programs. Required for: Further courses in algorithms and data structures. Courses that require that you can program well.

Updated  2012-04-24 17:08:49 by Anneli Svensson.