Data Structures and algorithms II

(Tietorakenteet ja algoritmit II, 3 op)

Course will be given in English at Joensuu and in Finnish in Kuopio. This page is common for both. Most of page is in English, but there are links to Finnish material as well. All the Finnish language text on this page is links to Finnish version of the material, and/or relevant for Kuopio students only.

There is no Moodle page for this course. All information should be found here and/or sent by email.

Finnish language version of this page (and 2018 course) can be found here
Suomenkielinen versio tästä sivusta ja 2018 kurssista löytyy täältä

Contents

• Official course description
• Course contents
• Schedule
• Grading
• Material/literature
• Lecture recordings
• WWW-links
• Software tools
• Data structure library
• Exercises
• Tutoring

• Lectures 20 h, Exercises 12 h
• Learning outcomes: The student can analyse recursive algorithms and is able to measure and extrapolate time complexity of programs. Student understands the elementary concepts of graphs, properties of different graphs, and graphs as abstract data type. Student knows the principle of most common graphs algorithms and is able to desing and implement simple graph algorithms. Student know most important algorithm strategies and is able to apply those. Student is able to use mass storage efficiently and is able to analyse time complexity of an algorithm that uses mass storage.
• Contents: More complex time complexity analyis, graphs as data structure, using graphs, algorithm strategies, mass storage data structures.

Course status

• obligatory part of BSc studies (CS major intermediate studies)
• second part of one of the key parts of intermediate studies

• Elementary time complexity analysis.
• Elementary data structures (lists, arrays, tree, hash tables)
• Reasonable Java programming skill, including generics
• Ability to simplify simple mathematical equations

• Time complexity analysis (recap, contine from DSA I)kertausta, jatkoa): 5 h
  • Recap of asymptotical analysis
  • Emprirical time measurements
  • Recursion recurrencies in time complexity analysis
  • Amortized time complexity
  • Proof of lower bounds
• Strategies: 5 h
  • Breadth/depth first
  • greedy
  • divide-and-conquer
  • back-tracking
  • branch and bound
  • heuristics
  • dynamic programming
  • string algorithm
• Advanced data strucutres 3 h
  • Graphs
  • B-tree
• Elementary algorithms: 5 h
  • Breadth/depth first searh
  • shortest path (Dijkstra and Floyd)
  • minimum spanning tree (Prim and Kruskal)
  • topological sort
  • matching
  • maximum flow
• External graph algorithms: 2 h

• Lecture examples are given in Java-based pseudocode.
• Most of the exercises are made in Java (using Java API and custom libraries).

• Raise the abstraction level of programs and programmers.
• Remember efficiency.

Lectures 20 h

• 28.3. -- 3.5.2017

• 28.03.17  TUE  12-14  TD106  
  29.03.17  WED  12-14  TD106  
  03.04.17  MON  14-16  TD106  
  04.04.17  TUE  12-14  TD106  
  10.04.17  MON  12-14  TD106  
  11.04.17  TUE  12-14  TD106  
  25.04.17  TUE  12-14  TD106  
  26.04.17  WED  12-14  TD106  
  02.05.17  TUE  12-14  TD106  
  03.05.17  WED  12-14  TD106
  

• 31.3. -- 11.5.2017
• Group 1

  31.03.17  FRI  08-10  TD106B  
  07.04.17  FRI  08-10  TD106B  
  21.04.17  FRI  08-10  TD106B  
  28.04.17  FRI  08-10  TD106B  
  05.05.17  FRI  08-10  TD106B  
  11.05.17  THU  08-10  TD106B
  

• Group 2

  31.03.17  FRI  10-12  TD106B  
  07.04.17  FRI  10-12  TD106B  
  21.04.17  FRI  10-12  TD106B  
  28.04.17  FRI  10-12  TD106B  
  05.05.17  FRI  10-12  TD106B  
  11.05.17  THU  10-12  TD106B
  

• For problems occuring in solving the exercises.
• If needed
• Thu 30.3. 10-11 T/B247.
• Wed 5.4. 13-15 T/B247.
• Wed 19.4. 13-15 T/B247.
• Wed 26.4. 14-15 T/B247.
• Tue 2.5. 14-15 T/B247.

• Luennot 20.3. -- ~3.5.2017
• 20.03.17 ma 14-16 TTA
  21.03.17 ti 14-16 E16+17
  27.03.17 ma 14-16 E16+17
  03.04.17 ma 14-16 E16+17
  04.04.17 ti 14-16 E16+17
  10.04.17 ma 14-16 E16+17
  24.04.17 ma 14-16 E16+17
  25.04.17 ti 14-16 E16+17
  02.05.17 ti 14-16 E16+17
  04.05.17 to 08-10 E16+17 (huom: muuttunut päivä)

Harjoitukset 30.3. -- 11.5.2017

• Ryhmä 1
  30.03.17 to 12-14 F211
  06.04.17 to 08-10 E26
  20.04.17 to 08-10 E26
  27.04.17 to 12-14 F211
  04.05.17 to 12-14 F211
  11.05.17 to 12-14 F211

• Ryhmä 2
  30.03.17 to 14-16 F211
  05.04.17 ke 08-10 E26
  20.04.17 to 10-12 E26
  27.04.17 to 14-16 F211
  04.05.17 to 14-16 F211
  11.05.17 to 14-16 F211

Harjoitustehtäväohjausta järjestetään tarvittaessa.

• Fri 12.05.17 12:00-16:00, class OTS100 (Joensuu) / SN100 (Kuopio)
  Registration through Oodi.
• Exam retake Fri 16.6.2017 12:00-16:00 OTS100 (Joensuu) / CA101
  Registration through Oodi.

• Starting Fri 16.6.2017

For an average student, for an average grade:

Data structures and algorithms II, time budjet
Weeks (h/l)	6	5
	Weekly	Total
Lectures	4	20
Recap	1.2	6
Exercises	2	12
Making	6	36
Course exam		2
Preparation		4
Total (h)	14.2	80
Total (cp)		3.00
26.67

Time usage varies weekly and individually. For an excellent grade, you might need more work.

Grading 2017:
• 30-40% of grade based on obligatory practical exercises (2-3 such exercises/course). Submitted before exercise class. Web address and instructions for submission will be given later.
• 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).
• Ordinary exercises are discussed and checked at exercise classes only, no need to submit beforehand.