Umeå universitet
Teknisk-naturvetenskaplig fakultet
Institutionen för datavetenskap

Datastrukturer och Algoritmer A, 5p

Teaching Staff

Kursansvarige: Jop Sibeyn
Övriga lärare: Tomas Larsson

Announcements

Results of the 15 participants of the combined omtenta/upsammlingstenta are here. This also includes those four who participated on 01.09.13.
The reassignment for the summer is now online. Check it out below in the section "Assignments" you who are interested.
2001.06.11: Some information regarding assignments over the summer has been sent out to your CS mail, make sure to check it.
For the tentamen it is allowed to take a normal pocket calculator with a limited amount of memory (not a pocket computer). In addition you are allowed to take one sheet of A4 (two sides) with notes. You are not allowed to bring the book itself, but of course you can copy parts of the book onto your page of notes.
Hints for learning for the tentamen.
Assignment 1 has been corrected. Those of you who received a 'K' grade, please follow this link.
Assignment 3 is online.
As you should solve the assignments in C compiled under UNIX, with all code in your accounts on CS, an introduction to the computer system has been added at the bottom of this page among with some other useful links. Check out Dataintro, and most important are the chapters 'Introduktion till NT 4.0' and 'Programmering'. If there are any questions to how the system works, programming, compiling etc, do not hesitate to contact Tomas.
Some assisting hours for this week and the beginning of next have been added to the 'handledningschema'-link further down. A more complete schedule will follow shortly. Please remember to read CS mail often as important news is usually sent by mail to quickly reach everyone.

Tentamen

Results

The thresholds are 44 -> 3, 55 -> 4, 66 -> 5. The results are complete. You can come to pick things up. I am quite happy with your work. There were certainly some people who have failed (for many of them it appears that they just did not study enough) but there are also quite some people who show to have intelligence AND knowledge. Particularly those three that will get a 5 should seriously consider whether they should not change to CS. Not necessarily now, you can also do this later. I changed myself to CS after completing my studies in mathematics. Finding academic positions (and other "kul" jobs) inside CS is easy, in physics and math this is very hard and will not become easier. The two questions that required some extra cleverness are worked out.

670418 41

690213 21 22

710330 10 15

721103 47

740826 16

760115 12 41

770131 68

770329 14

770625 47

770707 44

771129 44

780409 43

780412 74

780510 35 43

780511 27 40

780518 19

780619 72

780623 59

780714 27 36

780809 61

780920 19 22

790418 55

790426 39 54

790628 5 28

800406 17

801109 52

801210 39 49

Book

Data Structures and Algorithm Analysis in C, Mark Allan Weiss, Addison Wesley, 1999, ISBN 0-201-49840-5.

Topics Covered

The lecture will more or less stick to the book. However, because of the requirements of the second assignment, some topics will be treated somewhat earlier. Over the whole lecture some topics will be treated from almost all chapters. Rather than going in detail on some topics, an overview is given of what there is and where you can find more if needed. For each of the following topics approximately one week will be used. The schedule is not entirely fixed and will be adapted while running. At the end it will be specified clearly what you are expected to know for the tentamen, but this will be all that has been treated during the lecture. Not more and not less.

Lectures

For the lectures that have been given (with occasionally a look-ahead), the approximate text can be found below.

Monday 19.03.01, 13-17.
Basic Mathematics, Cost Model
Thursday 22.03.01, 13-15.
Recurrence Relations, Some Algorithms, Matrix Multiplication
Monday 26.03.01, 13-15.
ADT, Lists, Stacks, Queues
Thursday 29.03.01, 13-15.
Union-Find: introduction and first algorithms
Monday 02.04.01, 13-15.
Union-Find: further algorithms
Thursday 05.04.01, 13-15.
Table lookup, Union-Find: analysis
Monday 09.04.01, 13-15.
Hashing
Wednesday 11.04.01, 13-17.
Priority Queues: Heaps
Monday 23.04.01, 13-15.
Priority Queues: Binomial Trees
Monday 07.05.01, 13-15.
Search Trees, Search-Tee ADT
Thursday 10.05.01, 13-15.
AVL-Trees, 2-3 Trees
Monday 14.05.01, 13-15.
Sorting
Thursday 17.05.01, 13-15.
Sorting and Selection
Monday 21.05.01, 13-15.
Graphs: Shortest Path and DFS

Exercises

För varje vecka hittar du här öffningerna från boken som du bör göra. You should at least have a look at all the problems and make some thoughts about possible solutions before you come to the exercises. It is better, however, to spend at least two hours on trying to solve the exercises, figuring out the hard spots, and using the time at the exercises to ask clever questions to the assistants, instead of reading and understanding the questions.

12: 2.1, 2.4, 2.9, 2.10, 2.13
14: 3.16 a-d, 3.17, 3.21, 3.26, 8.1
17: 5.1, 5.4, 6.7 (c. only if you like it), 6.13, 6.15
19: 6.30 a. and b., 4.5, 4.6, 4.7, 4.15 (at least b.)
20: 4.28, 4.42, 7.27, 7.31, 7.32, 7.41

Assignments

Handledningsschema

Laborationsresultat

Assignment 1, date due 03.04.01.
Assignment 2, date due 17.04.01.
Assignment 3, dates due 09.05.01 and 23.05.01.

Re-Assignment, date due 20.08.01

Tentamen

Tentamen 01.06.01 9.00 - 15.00 i Skrivsal 3
Omtentamen 31.08.01 9.00 - 15.00 i Skrivsal 2

670418		41
690213	21	22
710330	10	15
721103	47
740826		16
760115	12	41
770131	68
770329	14
770625	47
770707	44
771129	44
780409		43
780412	74
780510	35	43
780511	27	40
780518	19
780619	72
780623	59
780714	27	36
780809	61
780920	19	22
790418	55
790426	39	54
790628	5	28
800406	17
801109		52
801210	39	49