Data Structures and algorithms I
Simo Juvaste, School of Computing, University of Eastern Finland, Joensuu campus.
(Tietorakenteet ja algoritmit I, 5 op)
Finnish language version of this page (and course) can be found here
Suomenkielinen versio tästä sivusta ja kurssista löytyy täältä
Contents
Course description from Study Plan
Data Structures and algorithms I (5 op) 3621313
- Lectures 32 h, Exercises 16 h
- Learning outcomes:
The student understands the purpose of algorithms and is able to analyse the time complexity of simple algorithms. The student is able to select a correct data structure (abstract data type) for each purpose and use it efficiently. The student is able to implement most common data structures and design and implement an algorithm for a simple problem.
- Contents: Introduction to algorithm time complexity and O-notation. Properties, correct usage, and implementation of most common data structures.
Course status
- obligatory part of BSc studies (intermediate studies)
- one of the key parts of intermediate studies
- a required prerequisite for MSc studies
Course contents
Prerequisites
- Reasonable Java programming skill
- Ability to simplify simple mathematical equations
Course contents
- Introduction to time complexity 6
* asymptototic analysis
* best-case, average, and worst-case analysis
* O, o, Omega, theta
* time vs. space
* analysis of simple recursive algorithms
- Elementary data structures 13
* Principle of encapsulation 2
* List and derivatives 3
* Trees 4
* Graph (concepts only) 1
* Sets 3
* Choosing correct data structure 2
- Implementing elementary data structures 6
- Elementary algorithms 7
* Sorting algorithms (bubblesort, quicksort, mergesort, heapsort, radix sort)
* hashing 2
* balanced binary search trees 2
Programming languages used
- Lecture examples are given in Java-based pseudocode.
- Most of the exercises are made in Java (using Java API and custom libraries).
Goal
- Raise the abstraction level of programs and programmers.
- Remember efficiency.
Schedule at Spring 2017
Lectures 32 h Simo Juvaste
Exercises 16 h Simo Juvaste
Tutoring
- For problems occuring in solving the exercises.
- Starting Wed Feb 1st 09-11 T/B247.
Course exam
- Fri 24.03.17 12:00-16:00, class E100 (Educa)
Registration through Oodi.
- Exam retake Fri 5.05.17 12:00-16:00 OTS100 (Otsola)
Registration through Oodi.
Results (PNG) (only uef.fi)
General exams
- Fri 05.05.17 12:00-16:00 OTS100 (Otsola)
- Fri 09.06.17 12.00-16.00 OTS100 (Otsola)
- ...
Time budjet
For an average student, for an average grade:
|
|
8 |
|
Weeksly |
Total |
| Lectures |
4 |
32 |
| Own weekly study |
2 |
16 |
|
|
|
| Exercises |
2 |
16 |
| Solving exercisis |
7 |
56 |
|
|
|
| Exam |
|
4 |
| Preparing |
|
9 |
|
|
|
| Total (h) |
16,63 |
133 |
| Total (cr) |
|
4,99 |
| 26,67 |
|
|
Time usage varies weekly and individually. For an excellent grade, you might need more work.
Grading on Spring 2017
- Student voted on the first lecture:
- 30-40% of grade based on obligatory practical exercises (3-4 such exercises/course).
- The rest based on course exam.
- If you make more than 1/3 of ordinary exercises, max 10% bonus. If you make less using the same formula negative bonus (at most -5%). Bonus = 10% * (n-N/3)/(2N/3), where n = # of exercises you did and N = total # of ordinary exercises (40-42, depending on the number of obligatory exercises).
- If you participate a general exam, then grading is based on the exam only.
Material/literature
Literature
- Liang: Introduction to Java Programming, comprehensive 7th edition (or later).
- Weiss: Data Structures and Algorithm Analysis [in C | Pascal | C++ | Java | etc]
- Cormen, Leiserson, Rivest: Introduction to Algorithms
- Knuth: The Art of Computer Programming
- Lecture material in A4: (to appear)
- PDF material (only uef.fi) (PDF, extended and updated during the course). From outside uef.fi -network, retrieve from password-protected folder of lecture recordings, link below.
- Lecture recordings.
- Lectures will be recorded. Recordings will be available after lectures (few hours)
here. Username is first four letters of the course name, password is first four letters of the second word of the course name. All lower case.
- Originals are 1920x616 resolution, ~1.7GB/lecture.
- _small are 1024x330 resolution, ~130MB/lecture.
- You can watch these, e.g., using mplayer:
mplayer http://user:pass@cs.uef.fi/pages/sjuva/dsaI_vid/dsaI_2017_lecture01.mp4
-
- Using UEF account, you can also see these at media.uef.fi (playlist).
- Lecture contents 2017:
- 1. 16.1. Course practical organization, introduction to abstraction, motivation for data structures, stepwise refinement
- 2. 17.1. Introduction to time complexity, asymptotic growth classes (O, Omega, Theta, o)
- 3. 23.1. Classification to function growth rate, calculating time complexity of an algorithm
- 4. 25.1. List as an abstract data type, java.util.LinkedList, ListIterator
- 5. 30.1. Recap of LinkedList, Linked list using ListNodes (TraLinkedList), Stack, Queue, Deque
- 6. 31.1. Recap of lists, replacing recursion using stack/queue, array structures
- 7. 6.2. Elementary tree concepts, binary tree, search and insert to binary tree
- 8. 8.2. Balanced search trees, successor, predessor and remove in in-ordered binary tree
- 9. 13.2. General tree, set
- 10. 14.2. Recap of Java Sets, Map, multilist, priority queue, bag. Very short intro to graphs
- 11. 20.2. Sorting as a problem, simple sorting algorithms, quicksort
- 12. 21.2. Quickselection, mergesort, radix sort. Introduction to ADT implementation, encapsulation and parametrization
- 13. 27.2. Java Collection Framework, array-based implementations of list
- 14. 28.2. Dynamic implementation of list; implementing stack, queue, deque, ring; dynamic implementation of tree
- 15. 6.3. Array implemention of tree, implementation of priority queue, heapsort, closed hashing
- 16. 7.3. Open (chained) hashing, hash functions, implementing iterations
Lecture examples, exercise skeletons, etc.
WWW-links to DSA material
Compilers
Data structure library
- We use a library having tree, binary tree, set, priority queue, and graph implementations.
- At cs you can use:
Compile trajc Program.java
- Run: traj Program
- In general (java = java6 or later, ja path/tra.jar is where you have tra.jar)
- Compile: javac -cp path/tra.jar:. Program.java
- Run: java -cp path/tra.jar:. Program
- In windows replace : with ;
- Using Eclipse:
- In project, use 2nd mouse button for Build Path -> Configure Build Path -> (Java Build Path ->) Libraries -> Add External JARs -> choose downloaded file tra_j6.jar (or tra.jar if Java5), Order and Export, select tra_j6.jar.
- Using IntelliJ IDEA:
- For project: File -> Project Structure -> Libraries -> + -> choose downloaded file tra_j6.jar.
- Using Netbeans (not checked, instructions are approximate!)
- For project: File -> Project Properties -> Libraries -> Add jar/directory -> choose downloaded file tra_j6.jar.
- Dokumentation online
- Download jar here:
Exercises
Execercises given here and at exercise class a week before.
Last modified
Wed Apr 12 12:00:33 EEST 2017
Simo Juvaste
