Linköpings universitet's sign

IDA Department of Computer and Information Science

TTIT33 Algorithms and Optimization

Lectures in Algorithms


The lectures provide an introduction and guidance to self studies. The tentative schedule below indicates suggested literature and exercises. Please use slides as indication what you have to know. For better understanding of lectures it is desirable to study the  material before the lecture.
The suggested exercises give an idea what kind of problems may appear at the written exam. Similar problems appear in all textbooks on algorithms, but here we refer only to JM and GT.

The shorthands used below:
GT: Goodrich and Tamassia, Data Structures and Algorithms in Java (4th edition)
LD: Lewis and Denenberg, Data Structures & Their Algorithms (does not cover some of the topics )
CL: Cormen et al., Introduction to Algorithms (2nd edition)
JM: On-line collection of problems for TDDB57


Lecture 1:  Organization, General Introduction. (slides)
                 Algorithm Analysis (slides)
   Literature: GT 4.1-4.2, LD Chapter 1, 2.1-2.2, CL Chapter 1-3
   Exercises: JM Le1: exercises 1, 2, 8, 9, 10, Le2 exercises 1, 2, 3
                    GT  R-4.11, R-4.12, R-4.13, R-4.15-4.19, R-4.24, R-4.26

Lecture 2:  Sorting, Selection (slides)
    Literature: GT 3.1.2, Chapter 11; LD 11.1-11.2, 11.4-11.8 ; CL  2.1, 7.1-7.4, 8.1, 8.3, 8.4
    Exercises: JM Le5: exercises 1, 2, 3, 4, 7, 8;
                     GT R-11.9, R-11.10, R-11.17, R-11.24. R-11.25

Lecture 3:  Basic ADTs: Stacks, Queues, Lists , Trees. (slides)
     Literature: GT p.60, p.162, 5.1-5.3, 6.1-6.2, 7.1-7.3 ; LD p.7, p.15-17, Chapter 3, 4.1-4.4,  ( CL  10.1-10.2, 10.4 not all topics covered)
     Exercises: JM Le2 exercises 5-9, Le3 exercises 4-6, 8, 10;
                      GT R-5.1-5.3, R-5.6-5.9,  C-5.1, C-5.4, C-5.8, R-6.1, R-6.2, R-7.23, R-7.24, R-7.26

Lecture 4:  Graphs (slides)
     Literature: GT 13.1-4;  LD 12.1-2 ; CL  22.1-4
     Exercises: JM Le6 exercises 1-2, 4-5, 10
                      GT R-13.3, R-13.6-13.10, R-13.12.

Lecture 5:  ADT Map/Dictionary, Hash Tables, Binary Search Trees. (slides)
     Literature: GT 9.1-9.3, 10.1.1-10.1.2; LD p.181-182, 6.4, 8.3 ; (CL 11.2-11.4, 12.1-12.3 not all topics covered)
     Exercises: JM Le3 exercises 1-3, 10,
                      GT R-9.1-9.6, R-9.8, R-9.14, R-10.1-10.4, R-10.6, C-10.1, C-10.2

Lecture 6:  Balanced Search Trees: AVL,  (m,n)-search trees, Heaps, Heap Sort (slides)
     Literature: GT 10.2, 10.4, 14.3, 8.1, 8.3; LD 7.1-7.2, 9.1 ; (CL 18.1-2, 6.1-5 not all topics covered)
     Exercises: JM Le4 exercises 1-2, 3a,b, 6-8,
                      GT R-10.8-13., R-10.23 (AVL Trees only), R-8.1-3, R-8.8, R-8.10-22

Lecture 7:  Union-Find Structures (slides)
              Examination Requirements (slides)