Course syllabus

Dear students in the course TIN093/DIT602 spring 2019:

2019-09-13: The re-exam is marked and results are reported in ladok. Exams can be picked up at the student office on floor 4.  Exam review will be on Thursday 19/9 at 12.00-13.00.

August 2019: Very unfortunately, the page has been removed by the system and the IT support has not been able restore it after it was discovered in mid June. It seems the page will be up again towards the end of August, hopefully before the re-exam. Until then: The page was similar to the autumn´s course home page  where you can find Peter Damaschke´s lecture notes that also were used in the spring 2019 course including the reading recommendations in the course book. On this Canvas page under "Files" you can find slides from guest teachers, assignments, most recent exam etc). I am very sorry for the inconvenience and I have really tried to get help to restore the page, but without success. I am back from my holiday on August 26.

Exam aids for the re-exam in August: same as last time (can be found in the pdf from the most recent exam, see "Files").

 

Regards Birgit Grohe (Examiner of spring course including re-exam in August)

----------------------------------------------------------------------------------------------

Course-PM

TIN093 / DIT602 Algorithms lp3 vt19 (7.5 hp)

Course is offered by the department of Computer Science and Engineering

Contact details

List of...

  • examiner
  • lecturer
  • teachers
  • supervisors

...along with their contact details. If the course have external guest lecturers or such, give a brief description of their role and the company or similar they represent.

If needed, list administrative staff, along with their contact details.

Course purpose

Short description of the course purpose and content: can be copied from syllabus in Studieportalen. Additional information can be added.

Schedule

TimeEdit

Course literature

List all mandatory literature, including descriptions of how to access the texts (e.g. Cremona, Chalmers Library, links).

Also list reference literature, further reading, and other non-mandatory texts.

Course design

Description of the course's learning activities; how they are implemented and how they are connected. This is the student's guide to navigating the course. Do not forget to give the student advice on how to learn as much as possible based on the pedagogy you have chosen. Often, you may need to emphasize concrete things like how often they should enter the learning space on the learning platform, how different issues are shared between supervisors, etc.

Provide a plan for

  • lectures
  • exervises
  • laboratory work
  • projects
  • supervision
  • feedback
  • seminars

Should contain a description of how the digital tools (Canvas and others) should be used and how they are organized, as well as how communication between teachers and students takes place (Canvas, e-mail, other).

Do not forget to describe any resources that students need to use, such as lab equipment, studios, workshops, physical or digital materials.

You should be clear how missed deadlines and revisions are handled.

Changes made since the last occasion

A summary of changes made since the last occasion.

Learning objectives and syllabus

Learning objectives:

 

  1. Knowledge and understanding
  • describe your algorithms and their qualities: explain algorithms in writing, so that others can understand how they work, why they are correct and fast, and where they are useful.
  • recognize that non-trivial computational problems, which need to be solved by algorithms, appear in various real-world computer applications and to formalize them.
  • intractability: recognize intractable problems and other classes of problems like P, NP, NPC.
  • prove the correctness of algorithms.

 

  • Skills and abilities
  • design: apply the main design techniques for efficient algorithms (for instance greedy, dynamic programming, divide-and-conquer, backtracking, heuristics) to problems which are similar to the textbook examples but new.
  • perform the whole development cycle of algorithms: problem analysis, choosing, modifying and combining suitable techniques and data structures, analysis of correctness and complexity, filling in implementation details, looking for possible improvements, etc.
  • perform simple reductions between problems, explain NP completeness, recognize various computationally hard problems which tend to appear over and over again in different applications, cope, at least in principle, with computationally hard problems, using heuristics, refinements of exhaustive search, approximative solutions, etc.
  • implement algorithms properly and evaluate them in theory and experiment.

 

  • Judgement and approach
  • critically assess algorithmic ideas and demonstrate the ability to resist the temptation to create obvious and seemingly plausible algorithms (which often turn out to be incorrect).
  • analyse: explain why the time efficiency of algorithms is crucial, express the time complexity in a rigorous and scientifically sound manner, analyze the time complexity of algorithms (sum up operations in nested loops, solve standard recurrences, etc.) i.e. perform an objective evaluation of the performance and be able to compare it to other algorithms performance.

However, be aware that this is not a course in programming! The main focus is on the design of algorithms from a given problem specification and the analysis of efficiency of these algorithms. This is, so to speak, the analytical work that has to be done before writing any line of code, if one wants to solve a new problem with the help of computers.

Link to the syllabus on Studieportalen.

Study plan

If the course is a joint course (Chalmers and Göteborgs Universitet) you should link to both syllabus (Chalmers and Göteborgs Universitet).

Examination form

Description of how the examination – written examinations and other – is executed and assessed.

Include:

  • what components are included, the purpose of these, and how they contribute to the learning objectives
  • how compulsory and/or voluntary components contribute to the final grade
  • grading limits and any other requirements for all forms of examination in order to pass the course (compulsory components)
  • examination form, e.g. if the examination is conducted as a digital examination
  • time and place of examination, both written exams and other exams such as project presentations
  • aids permitted during examinations, as well as which markings, indexes and notes in aids are permitted

Do not forget to be extra clear with project assignments; what is the problem, what should be done, what is the expected result, and how should this result be reported. Details such as templates for project reports, what happens at missed deadlines etc. are extra important to include.

Course summary:

Date Details Due