Ämnesdisposition

  • Allmänt

    Fäll ihop allt Expandera allt

    Teaching


    Marc Hellmuth     is head teacher (some lectures are shared with Anna Lindeberg)

    TAs (click in their names to see email-addresses):
    Anna Lindeberg
    (more TBA)


    Course literature
    • primary course book: Introduction to Algorithms, Cormen et al.,  MIT Press, 2022
    • secondary literature: The Algorithm Design Manual, Skiena, Springer, 2012
                                           Data Structures and Algorithms Made Easy, Karumanchi, CareerMonk Publications (5th Edition). 2017

    Lecture-Script, Slides and further course material is available below: "Resources" -> "Lecture Slides and Notes"

    Solutions to exercises will not be provided online BUT they will be revealed in the "Laboration", i.e., in the exercise sessions before the lectures!
    In addition, many examples to theoretical results in the lecture and implementations of certain algorithms in different languages are provided.
    Moreover, potential exam questions will be discussed.
    It is, therefore, strongly recommended to participate in the exercise sessions!

    A course survey is distributed electronically at the end of the course, to get feedback for a course evaluation.

    Schedule online here: LINK


    Topics (The script for the lecture can be found here lecture-script):
      
    • Part 1 Fundamentals
      For a nice overview about topics in computer science follow the link: https://www.youtube.com/watch?v=SzJ46YA_RaA
      • Lecture 1: What is an algorithm? Correctness of algorithms - Example Insertion Sort.
                           Additional reading Course-book "Introduction to Algorithms" Chp 1 and 2.1
                           Content: Part1_Slides 1-14 
      • Lecture 2: Runtime of algorithms (Big-O. Omega, Theta)
                           Additional reading Course-book "Introduction to Algorithms" Chp 2.2 and 3
                           Content: Part1_Slides 15-26
      • Lecture 3: Runtime of algorithms (Recursion and Mastertheorem). Space-Complexity. Intro Elementary Data Structures.
                           Additional reading Course-book "Introduction to Algorithms" Chp 4.3 - 4.6
                           Content: Part1_Slides 15-47
      • Lecture 4: Elementary Data Structures (Arrays, Linked Lists, Stacks, Queues, Trees (incl some Graph Theory)). Recap Insertion Sort and Sorting Problems.
                           Additional reading Course-book "Introduction to Algorithms" Chp 10 / B4 and B5
                           Content: Part1_Slides 44-end and Part2_Slides 1-8

    • Part 2 Sorting 
      • Lecture 5: Merge Sort. More to trees (complete, binary, full, ordered, height, depth .. )
                           Additional reading Course-book "Introduction to Algorithms" Chp 2.3 / B5
                           Content: Part2_Slides 8-17
      • Lecture 6: Heapsort and Quicksort
                           Additional reading Course-book "Introduction to Algorithms" 6 / 7
                           Content: Part2_Slides 18-30
      • Lecture 7 (1st half): Lower Bound Comparison Sorts and Counting Sort
                           Additional reading Course-book "Introduction to Algorithms" Chp  8.1 and 8.2
                           Content: Part2_Slides 31-end

    • Part 3 Searching and Search Trees
      • Lecture 7 (2nd half): Searching in Array (linear, binary. jump, exponential Search)
                                   Additional reading Secondary Course-book "Data Structures and Algorithms Made Easy"" Chp  11
                           Content: Part3_Slides 1-13
      • Lecture 8:  Binary Search Trees (BST), 1st-part-of AVL trees
                           Additional reading Course-book "Introduction to Algorithms" Chp 12
                                                              Secondary Course-book "Data Structures and Algorithms Made Easy,"" Chp 6.11-6.14
                           Content: Part3_Slides 14-30
      • Lecture 9: 2nd-part-of AVL trees and Red-Black trees
                           Additional reading Course-book "Introduction to Algorithms" Chp 13
                           Content: Part3_Slides 31-end
                               
    • Part 4 Hashing and Hashtables 
      • Lecture 10: Course-book "Introduction to Algorithms" Chp  11
                              Content: Part4_Slides

    • Part 5 Graph algorithms
      • Lecture 11: BFS (connectedness, trees, distances)
                              Course-book "Introduction to Algorithms" Chp  20
                              Content: Part5_Slides         1-21
      • Lecture 12: DFS and Min-Spanning-Tree, Kruskal
                              Course-book "Introduction to Algorithms" Chp  20/21
                              Content: Part5_Slides         21-end
      • Lecture 13   Let's see how far we get (TBA)
      • Lecture 14   Recap + Discussion Exam Structure

    Examination


    Examiner:     Marc Hellmuth

    Examination Form:

    • Home assignments = Exercises below ("LABO" on course documentation)  worth 3.0 HP, graded A-F.
    • A written exam ("THEO" on course documentation), worth 4.5 HP, graded A-F.

    All assignments (exercises below) are individual and independent. No cooperative hand-ins are allowed. You need a passing grade on both, LABO and THEO to pass the course.

    • ALWAYS hand-in a SINGLE PDF-file (it can be scanned handwritten or latex-compiled or something else .. ).
    • NEVER provide your personal identity number within the hand-in files

    Futher important information:

    • When you have questions regarding the course or exercises, please write your question into the discussion forum at the homepage or ask within the tutorials or lectures. We are not answering individual emails!
    • Students with medical diagnoses that may impair their concentration or reading ability, or anything else that hinders them from providing exercises on time, are requested to inform me before the first exercise hand-in
    • For the exercises, the use of AI tools is prohibited. This includes but is not limited to AI-based text generators, content summarizers, and plagiarism detection tools. The purpose of theoretical assignments is to assess your understanding, critical thinking skills, and ability to express ideas in your own words.

    Course Grade:  0.4*(grade LABO) + 0.6*(grade THEO) = final grade

    Written exam: Will be offline for 4 hours (see schedule). This is NOT an open-book exam (no smartphones, tablets, notebooks etc allowed).The Exam from 2024 can be found under the header "Resources" (LINK)

    Grading criteria:
    LABO are collectively graded (total number of achieved points). For both, LABO  and THEO, thus usual grading scale  applies:

    100.00 % to 90.00 % = A
     89.99 % to 80.00 % = B
     79.99 % to 70.00 % = C
     69.99 % to 60.00 % = D
     59.99 % to 50.00 % = E


    Q & A

    • What do I need to know and learn to pass the course?
      See slides 0-Orgastuff.pdf for the hard-coded details. Moreover, if you can follow the content of the course (i.e., you understand the slides as well as all the proofs) and if you are able to solve the exercises below then you are possibly well-prepared for the exam. Exam questions will be "similar in flavor" to those exercises [not identical of course!]. Moreover, for the exam I give from time to time  some hints within in the lecture, to give you an idea of what is expected.

    • What means "understanding something"?
      Understanding something typically refers to the ability to comprehend, grasp, or make sense of a particular concept and idea,. It involves more than just knowing facts! However, it is hard to define. Take the term "understand" as something like "I am able to explain it to some other students".
      By way of example: Are you able to explain when an algorithm is said to solve a problem? Can you prove that n^2\in O(n^2.5) and explain it to some other student? Do you know what it means to change the base of a logarithm? Can you prove the correctness of insertion-sort and explain this proof to some other student?
      A good practice here is to explain the content and to discuss it with other students.
      Judging if you understood the content is  completely up to you: The teacher can explain it to you but not understand it for you!

    • What if I dont understand certain parts of the content?
      If you cannot follow the content of the course, then be self-organized based on my hints on the course page. Hints which chapters you can read are given at the kurser homepage: explicit for each lecture.
      Discuss the content with other students. Go to the tutorials and ask the TAs to recap some parts of the lectures.

    • How can I deepen my knowledge?
      If you want to deepen your knowledge, be self-organized based on my hints on the course page. Hints which chapters you can read are given at the kurser homepage. Moreover, feel free to attack additional problems stated in the course book w.r.t. each of the sessions.

    • What is the difference between the courses DA4005 and DA4006?
      DA4006 is a foundational course concerned with fundamental content aimed at understanding how algorithms work, their applications, methods to prove their correctness, and analyzing their time and space complexity. While we primarily cover problems that can be solved by algorithms in polynomial time in DA4006, the course DA4005 also delves into the complexity of algorithms for problems that may not necessarily be solved in polynomial time. This includes an exploration of NP-completeness, as well as heuristics to solve such problems.

    • How are the "laboration"-sessions structured?
      The "laboration"-sessions are structured based on the current topics being discussed and the individual tutor's approach. They typically involve a combination of individual work by students during the sessions, supplemented with additional examples, explanations, and theory provided by the tutor. Practical aspects, like implementing algorithms and data structures in different programming languages, may also be covered. Furthermore, these sessions offer opportunities for students to ask questions and receive assistance when facing challenges with exercises.

    • What are "bonus exercises" in the Exercises (Home Assignments "LABO")
      Bonus exercises can be used to earn extra points. While all "non-bonus" exercises are mandatory, the "bonus" exercises are voluntary. The total points you can earn by completing the exercises are based on the non-bonus exercises. Therefore, completing the additional bonus exercises gives you the opportunity to receive more than 100% of the points. Note that there are no second submissions allowed, so you may use bonus exercises to also achieve the minimum passing grade of 50% for the LABO part.

    News

    updates and news will be provided here.





     

    Resources

  • Exercises (Home Assignments "LABO")

    Markerad