Difference between revisions of "Algorithms for Scientific Computing - Summer 17"

From Sccswiki
Jump to navigation Jump to search
 
(30 intermediate revisions by 3 users not shown)
Line 7: Line 7:
 
| audience = see [https://campus.tum.de/tumonline/WBMODHB.wbShowMHBReadOnly?pKnotenNr=456346&pOrgNr=14189 module description (IN2001)] in TUMonline  
 
| audience = see [https://campus.tum.de/tumonline/WBMODHB.wbShowMHBReadOnly?pKnotenNr=456346&pOrgNr=14189 module description (IN2001)] in TUMonline  
 
| tutorials = [[Emily Mo-Hellenbrand, M.Sc.]], [[Jean-Matthieu Gallard, M.Sc.]]
 
| tutorials = [[Emily Mo-Hellenbrand, M.Sc.]], [[Jean-Matthieu Gallard, M.Sc.]]
| exam = Mon, Aug 7, 10.30 in lecture hall MI HS 1 (F.L. Bauer Hörsaal)
+
| exam = Mon, Aug 7, 10.30 in lecture hall MI HS 1 (F.L. Bauer Hörsaal) <br/> Thu, Oct 5, 16.00 in lecture hall Interim 2
 
| tumonline = https://campus.tum.de/tumonline/wbLv.wbShowLVDetail?pStpSpNr=950290914
 
| tumonline = https://campus.tum.de/tumonline/wbLv.wbShowLVDetail?pStpSpNr=950290914
 
}}
 
}}
  
 
== News & Announcements ==
 
== News & Announcements ==
* '''Worksheet 9 code template is updated (fixed compatibility issues with Python 3). Please re-download the template zip. NOTE: you need the files supplied in the template zip to run the Worksheet 9 code solution.'''
+
* '''Review for the repetition exam will be held on 26.10.17 Thursday from 11:00 to 12:00 in room MI 02.05.051 (printer room). Please bring your student ID.'''
 +
* Exam review will be held on 24.08.17 at 11AM in room MI 02.05.057. Please bring your Student-ID.
 +
* As pointed out by some, there are confusions regarding WS6 ex1. Therefore, I reformulated the question and WS6 is updated. Please check.
 +
* The tutorial on Wednesday 12.07 will include the beginning of the lecture on space-filling curve.
 +
* The Mock Exam and its solution is now posted in the "Worksheets and Solutions" table. Please note:
 +
** Disclaimer: this mock exam merely serves the purpose of giving you some ideas/hints on what to expect in the actual exam (e.g., exam format, possible questions, difficulty levels). Please do NOT assume that you will get the same (or very similar) questions in the actual exam, as there are many ways to ask a question on the same subject!
 +
** Exam coverage: You should prepare for all 4 topics, i.e., FFT, Hier. methods, Sparse grids, SFC. And you should expect questions from all lecture slides (except for Red parts) and worksheet exercises. Pseudo code questions are possible to appear.
 +
** Preparation hint: Try to solve & understand all the exercises in the worksheets and the mock exam.
 +
* The supplement material of transforming the regularization formula into a linear system (Lecture July 10, slide 18) is uploaded.
 +
* Worksheet 9 code template is updated (fixed compatibility issues with Python 3). Please re-download the template zip. NOTE: you need the files supplied in the template zip to run the Worksheet 9 code solution.
 
* Worksheet 7 solution is updated (mistake in ex4 corrected). Please re-check the solution!
 
* Worksheet 7 solution is updated (mistake in ex4 corrected). Please re-check the solution!
 
* please re-check the solution of exercise 1 on worksheet 4; this has been corrected!
 
* please re-check the solution of exercise 1 on worksheet 4; this has been corrected!
* as an exception, the '''lecture on Fri, May 19, will start at 10.30''' (until 12.00)
+
* as an exception, the lecture on Fri, May 19, will start at 10.30 (until 12.00)
  
 
== What's ASC about? ==
 
== What's ASC about? ==
Line 72: Line 81:
 
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/hierarch_dDim.pdf Hierarchical Basis in d Dimensions] - Jun 26 (intro and part I), 30 (parts II and III)
 
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/hierarch_dDim.pdf Hierarchical Basis in d Dimensions] - Jun 26 (intro and part I), 30 (parts II and III)
 
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss13/hierarch_integral_representation.pdf "separate proof"] for estimating surpluses (outlook)
 
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss13/hierarch_integral_representation.pdf "separate proof"] for estimating surpluses (outlook)
 +
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/fem_asc.pdf Finite Element Methods (part III and slight outlook on part IV)] - July 3, 7
 
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sparsegrids_algo.pdf Data Structures for Sparse Grids] - July 10
 
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sparsegrids_algo.pdf Data Structures for Sparse Grids] - July 10
 
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sparsegrids_algo_slide18_sup.pdf Slide 18 supplement: transform to matrix form] - July 10
 
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sparsegrids_algo_slide18_sup.pdf Slide 18 supplement: transform to matrix form] - July 10
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/fem_asc.pdf Finite Element Methods (part III and slight outlook on part IV)] - July 3, 7
 
  
 
=== Space-Filling Curves ===
 
=== Space-Filling Curves ===
Line 82: Line 91:
 
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sfc_mapping.pdf Hilbert Curve (Construction, Definition, and Arithmetisation)] - July 14, 17
 
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sfc_mapping.pdf Hilbert Curve (Construction, Definition, and Arithmetisation)] - July 14, 17
 
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss14/sfc_hilbert_arith.ipynb Python Notebook script for Hilbert curve arithmetization]
 
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss14/sfc_hilbert_arith.ipynb Python Notebook script for Hilbert curve arithmetization]
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/sfc_parallel.pdf Space-filling curves and parallelisation] - Jul 21
+
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sfc_3Dcurves.pdf 2D and 3D Space-filling Curves] - Jul 17, 21
 +
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/sfc_parallel.pdf Space-filling curves and parallelisation] - Jul 24
 
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss14/sfc_hilbert_plotter_adp.ipynb Python Notebook script Hilbert curve on a quadtree]
 
** [http://www5.in.tum.de/lehre/vorlesungen/asc/ss14/sfc_hilbert_plotter_adp.ipynb Python Notebook script Hilbert curve on a quadtree]
* [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/sfc_3Dcurves.pdf 2D and 3D Space-filling Curves] - t.b.a. <!-- Jul 4 (intro and part I), Jul 8 (part III) -->
 
  
 
== Worksheets and Solutions ==
 
== Worksheets and Solutions ==
Line 94: Line 103:
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt1/ws1_solution.pdf Ws1 solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt1/ws1_solution.ipynb Ws1 solution Notebook]
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt1/ws1_solution.pdf Ws1 solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt1/ws1_solution.ipynb Ws1 solution Notebook]
 
|-
 
|-
| 2 || Discrete Fourier Transform II || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt2/ws2.pdf Worksheet 2] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt2/ws2_template.ipynb Worksheet 2 Notebook template] || May 3 ||  
+
| 2 || Discrete Fourier Transform II || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt2/ws2.pdf Worksheet 2] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt2/ws2_template.ipynb Worksheet 2 Notebook template] || May 3 ||  
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt2/ws2_solution.pdf Ws2 solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt2/ws2_solution.ipynb Ws2 solution Notebook] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt2/ws2_solution_ex2.py Ws2 Ex2 solution code]
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt2/ws2_solution.pdf Ws2 solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt2/ws2_solution.ipynb Ws2 solution Notebook] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt2/ws2_solution_ex2.py Ws2 Ex2 solution code]
 
|-
 
|-
Line 101: Line 110:
 
| 3 || Discrete Cosine Transform || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt3/ws3.pdf Worksheet 3] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt3/ws3_template.ipynb Worksheet 3 Notebook template] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt3/ws3_template_ex1.py Template Exercise 1] || May 17 ||   
 
| 3 || Discrete Cosine Transform || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt3/ws3.pdf Worksheet 3] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt3/ws3_template.ipynb Worksheet 3 Notebook template] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt3/ws3_template_ex1.py Template Exercise 1] || May 17 ||   
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt3/ws3_solution.pdf Ws3 solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt3/ws3_solution.ipynb Ws3 solution code]  
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt3/ws3_solution.pdf Ws3 solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt3/ws3_solution.ipynb Ws3 solution code]  
 
 
|-
 
|-
 
| 4 || Discrete Fourier Transform III || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt4/ws4v2.pdf Worksheet 4] || May 24 ||  
 
| 4 || Discrete Fourier Transform III || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt4/ws4v2.pdf Worksheet 4] || May 24 ||  
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt4/ws4_solution.pdf Ws4 solution]
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt4/ws4_solution.pdf Ws4 solution]
 
|-
 
|-
| 5 || Numerical Quadrature 1D || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt5/ws5.pdf Worksheet 5] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt5/ws5.ipynb Worksheet 5 Notebook template] || May 31 ||  
+
| 5 || Numerical Quadrature 1D || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt5/ws5.pdf Worksheet 5] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt5/ws5.ipynb Worksheet 5 Notebook template] || May 31 ||  
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt5/ws5_solution.ipynb Ws5 solution Notebook]  
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt5/ws5_solution.ipynb Ws5 solution Notebook]  
 
|-
 
|-
| 6 || Hierarchical Basis || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt6/ws6.pdf Worksheet 6] || Jun. 07 ||  
+
| 6 || Hierarchical Basis || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt6/ws6-updated.pdf Worksheet 6] || Jun. 07 ||  
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt6/ws6_solution_ex1-2.ipynb Ws6 Ex1-2 solution Notebook] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt6/ws6_solution_ex3.pdf Ws6 Ex3 solution]  
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt6/ws6_solution_ex1-2.ipynb Ws6 Ex1-2 solution Notebook] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt6/ws6_solution_ex3.pdf Ws6 Ex3 solution]  
 
|-
 
|-
Line 122: Line 130:
 
| 9 || Multi-dimensional hierarchization and adaptive sparse grids || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt9/ws9.pdf Worksheet 9] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt9/ws9_template.zip Worksheet 9 code template] || Jul. 05 ||
 
| 9 || Multi-dimensional hierarchization and adaptive sparse grids || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt9/ws9.pdf Worksheet 9] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt9/ws9_template.zip Worksheet 9 code template] || Jul. 05 ||
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt9/ws9_solution.ipynb Ws9 code solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt9/ws9_ex2_solution.pdf Ws9 Ex2 solution]
 
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt9/ws9_solution.ipynb Ws9 code solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt9/ws9_ex2_solution.pdf Ws9 Ex2 solution]
<!--
 
| 10 || Grammars for space-filling curves || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt10/ws10.pdf Worksheet 10] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt10/ws10_code_template.zip Worksheet 10 code template] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt10/ws10_template.ipynb Notebook template] || Jun. 22 || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt10/ws10_solution.pdf Ws10 solution ] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt10/ws10_code_solution.zip Ws10 solution code] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt10/ws10_solution.ipynb Ws10 solution Notebook]
 
 
|-
 
|-
| 11 || Arithmetization of space-filling curves || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt11/ws11.pdf Worksheet 11] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt11/ws11_code_template.zip code template] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt11/ws11.ipynb Notebook template] || Jun. 29 || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt11/ws11_solution.pdf Ws11 solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt11/ws11_code_solution.zip Ws11 solution code] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt11/ws11_solution.ipynb Ws11 solution Notebook]
+
| 10 || Grammars for space-filling curves || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt10/ws10.pdf Worksheet 10] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt10/ws10_code_template.zip Worksheet 10 code template] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt10/ws10_template.ipynb Notebook template] || Jul. 12 ||
 +
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt10/ws10_solution.pdf Ws10 solution ] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt10/ws10_code_solution.zip Ws10 solution code] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt10/ws10_solution.ipynb Ws10 solution Notebook]
 +
|-
 +
| 11 || Arithmetization of space-filling curves || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt11/ws11.pdf Worksheet 11] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt11/ws11_code_template.zip code template] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt11/ws11.ipynb Notebook template] || Jul. 19 ||  
 +
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt11/ws11_solution.pdf Ws11 solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt11/ws11_code_solution.zip Ws11 solution code] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt11/ws11_solution.ipynb Ws11 solution Notebook]
 
|-
 
|-
| 12 || Refinement trees and space-filling curves || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt12/ws12.pdf Worksheet 12], [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt12/ws12.ipynb Worksheet 12 Notebook template] || Jul. 6 || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt12/ws12_solution.pdf Ws12 solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss16/blatt12/ws12_solution.ipynb Ws12 solution Notebook]
+
 
 +
| 12 || Refinement trees and space-filling curves || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt12/ws12.pdf Worksheet 12], [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt12/ws12.ipynb Worksheet 12 Notebook template] || Jul. 26 ||  
 +
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt12/ws12_solution.pdf Ws12 solution] [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/blatt12/ws12_solution.ipynb Ws12 solution Notebook]
 
|-
 
|-
| 13 || Q&A session (exercises) ||  || Jul. 13 ||
+
| 13 || Q&A session (exercises) ||  || Aug. 02 ||
 
|-
 
|-
 +
<!--
 
| 14 || Q&A session (lecture) ||  || Jul. 20 ||
 
| 14 || Q&A session (lecture) ||  || Jul. 20 ||
 
-->
 
-->
 +
| - || Mock Exam || [http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/exam0_mock/ASC_SS17_Mock_Exam.pdf Mock exam] || - ||
 +
[http://www5.in.tum.de/lehre/vorlesungen/asc/ss17/exam0_mock/ASC_SS17_Mock_Exam_Solution.pdf Mock exam solution]
 +
|-
 
|}
 
|}
  
Line 139: Line 155:
 
* If you want to use a local installation of Jupyter Notebook on your laptop or home computer, just refer to [http://jupyter.org/ the Jupyter Notebook website] on how to [http://jupyter.org/install.html install Jupyter Notebook] on Linux, Windows or MAC platforms.
 
* If you want to use a local installation of Jupyter Notebook on your laptop or home computer, just refer to [http://jupyter.org/ the Jupyter Notebook website] on how to [http://jupyter.org/install.html install Jupyter Notebook] on Linux, Windows or MAC platforms.
  
== Exam ==
+
== Repeat Exam ==
 
<!--
 
<!--
 
* '''Exam review''' (opportunity to take a look at your graded exam): Wednesday, Aug 24, 10-12
 
* '''Exam review''' (opportunity to take a look at your graded exam): Wednesday, Aug 24, 10-12
 
-->
 
-->
 
* type: written exam, duration: 100 min
 
* type: written exam, duration: 100 min
* time, date, room: '''Mon, Aug 7''', 2017, '''10.30-12.10''' ('''MI HS 1''', Friedrich L. Bauer Hörsaal)
+
* time, date, room: '''Thu, Oct 5''', 2017, '''16.00-17.40''' ('''Interim 2''')
** note that the exam will start precisely on 10.30; please be in the exam room '''by 10.15''', at the latest!
+
** note that the exam will start precisely on 16.00; please be in the exam room '''by 15.45''', at the latest!
 
<!--
 
<!--
 
* '''please make sure that you register in TUMonline'''
 
* '''please make sure that you register in TUMonline'''
Line 152: Line 168:
 
** you may use one '''hand-written''' sheet of paper (size A4, front and back may be used)
 
** you may use one '''hand-written''' sheet of paper (size A4, front and back may be used)
 
** no other helping material of any kind is allowed
 
** no other helping material of any kind is allowed
* '''extra session for questions''': t.b.a.
+
<!--* '''extra session for questions''': t.b.a. -->
  
 
== Literature and Additional Material ==
 
== Literature and Additional Material ==

Latest revision as of 08:06, 23 October 2017

Term
Summer 2017
Lecturer
Univ.-Prof. Dr. Michael Bader
Time and Place
Lecture: Mon 8:30-10:00, Fri 10:15-11:45, MI Hörsaal 2 (1st lecture: Mon, Apr 24)
Tutorial: Wed 10:15-11:45, MI 00.13.09A
Audience
see module description (IN2001) in TUMonline
Tutorials
Emily Mo-Hellenbrand, M.Sc., Jean-Matthieu Gallard, M.Sc.
Exam
Mon, Aug 7, 10.30 in lecture hall MI HS 1 (F.L. Bauer Hörsaal)
Thu, Oct 5, 16.00 in lecture hall Interim 2
Semesterwochenstunden / ECTS Credits
6 SWS (4V + 2Ü) / 8 Credits
TUMonline
https://campus.tum.de/tumonline/wbLv.wbShowLVDetail?pStpSpNr=950290914



News & Announcements

  • Review for the repetition exam will be held on 26.10.17 Thursday from 11:00 to 12:00 in room MI 02.05.051 (printer room). Please bring your student ID.
  • Exam review will be held on 24.08.17 at 11AM in room MI 02.05.057. Please bring your Student-ID.
  • As pointed out by some, there are confusions regarding WS6 ex1. Therefore, I reformulated the question and WS6 is updated. Please check.
  • The tutorial on Wednesday 12.07 will include the beginning of the lecture on space-filling curve.
  • The Mock Exam and its solution is now posted in the "Worksheets and Solutions" table. Please note:
    • Disclaimer: this mock exam merely serves the purpose of giving you some ideas/hints on what to expect in the actual exam (e.g., exam format, possible questions, difficulty levels). Please do NOT assume that you will get the same (or very similar) questions in the actual exam, as there are many ways to ask a question on the same subject!
    • Exam coverage: You should prepare for all 4 topics, i.e., FFT, Hier. methods, Sparse grids, SFC. And you should expect questions from all lecture slides (except for Red parts) and worksheet exercises. Pseudo code questions are possible to appear.
    • Preparation hint: Try to solve & understand all the exercises in the worksheets and the mock exam.
  • The supplement material of transforming the regularization formula into a linear system (Lecture July 10, slide 18) is uploaded.
  • Worksheet 9 code template is updated (fixed compatibility issues with Python 3). Please re-download the template zip. NOTE: you need the files supplied in the template zip to run the Worksheet 9 code solution.
  • Worksheet 7 solution is updated (mistake in ex4 corrected). Please re-check the solution!
  • please re-check the solution of exercise 1 on worksheet 4; this has been corrected!
  • as an exception, the lecture on Fri, May 19, will start at 10.30 (until 12.00)

What's ASC about?

Many applications in computer science require methods of (numerical) mathematics - especially in science and engineering, of course, but also in surprisingly many areas that one might suspect to be directly at the heart of computer science:

Consider, for example, Fourier and wavelet transformations, which are indispensable in image processing and image compression. Similar, numerical methods for approximation have become essential techniques for high-dimensional classification problems in data science. Essentially, these methods come down to the question of how to represent and process information or data as (multi-dimensional) continuous functions. "Algorithms for Scientific Computing" thus provides an algorithmically oriented introduction to the foundations of such mathematical methods.

Topics include:

  • The fast Fourier transformation (FFT) and some of its variants:
    • FCT (Fast Cosine Transform), real FFT, Application for compression of video and audio data
  • Hierarchical and recursive methods in scientific computing
    • From Archimedes' quadrature to the hierarchical basis
    • Classification problems
    • From the hierarchical basis to wavelets
  • High-demonsional problems
    • Sparse grids and the sparse-grid combination technique
  • Octrees and Space filling curves (SFCs):
    • Tree-structured (hierarchical) adaptivity
    • Construction and properies of SFCs
    • Application for parallelization and to linearize multidimensional data spaces in data bases

Lecture Slides and Supplementary Materials

Lecture slides are published here successively. For future lectures, the respective slides from summer 2016 will be linked.

Fast Fourier Transform

Hierarchical Methods

Sparse Grids

Space-Filling Curves

Worksheets and Solutions

Number Topic Worksheet Tutorial Solution
1 Discrete Fourier Transform I Worksheet 1Python Introduction Apr. 26

Ws1 solution Ws1 solution Notebook

2 Discrete Fourier Transform II Worksheet 2 Worksheet 2 Notebook template May 3

Ws2 solution Ws2 solution Notebook Ws2 Ex2 solution code

- - - May 10 tutorial cancelled due to student assembly
3 Discrete Cosine Transform Worksheet 3 Worksheet 3 Notebook template Template Exercise 1 May 17

Ws3 solution Ws3 solution code

4 Discrete Fourier Transform III Worksheet 4 May 24

Ws4 solution

5 Numerical Quadrature 1D Worksheet 5 Worksheet 5 Notebook template May 31

Ws5 solution Notebook

6 Hierarchical Basis Worksheet 6 Jun. 07

Ws6 Ex1-2 solution Notebook Ws6 Ex3 solution

7-Part1 Function Approximation and Wavelet Ex1-3: Worksheet 7 Worksheet 7 Notebook template Jun. 14

Ws7 solution

7-Part2 Function Approximation and Wavelet Ex4-5: See above Jun. 21 See above
8 Multi-dimensional Quadrature Worksheet 8 Worksheet 8 template Jun. 28

Ws8 solution

9 Multi-dimensional hierarchization and adaptive sparse grids Worksheet 9 Worksheet 9 code template Jul. 05

Ws9 code solution Ws9 Ex2 solution

10 Grammars for space-filling curves Worksheet 10 Worksheet 10 code template Notebook template Jul. 12

Ws10 solution Ws10 solution code Ws10 solution Notebook

11 Arithmetization of space-filling curves Worksheet 11 code template Notebook template Jul. 19

Ws11 solution Ws11 solution code Ws11 solution Notebook

12 Refinement trees and space-filling curves Worksheet 12, Worksheet 12 Notebook template Jul. 26

Ws12 solution Ws12 solution Notebook

13 Q&A session (exercises) Aug. 02
- Mock Exam Mock exam -

Mock exam solution


Jupyter Notebook

Repeat Exam

  • type: written exam, duration: 100 min
  • time, date, room: Thu, Oct 5, 2017, 16.00-17.40 (Interim 2)
    • note that the exam will start precisely on 16.00; please be in the exam room by 15.45, at the latest!
  • helping material:
    • you may use one hand-written sheet of paper (size A4, front and back may be used)
    • no other helping material of any kind is allowed

Literature and Additional Material

Books that are labeled as "available as e-book" can be accessed as e-book via the TUM library - see the ebooks website of the library for details on how to access the books.

Fast Fourier Transform:

The lecture is oriented on:

Hierarchical Methods and Sparse Grids

Wavelets

Space-filling Curves:

Background Material Concerning Scientific and High Performance Computing