2301520 Fundamentals of AMCS

  1. Definition of algorithm, Expressing algorithm, Problem specifications, Correctness, Loop invariants, Counter example
  2. Algorithm performance, Worst-case, Best-case and Average-case analysis, RAM model, Asymptotic notation
  3. Asymptotic notations and their relationships, Basic algorithm analysis, Recursive algorithm
  4. Relationship between algorithm and data structure, Abstract Data Type, Dictionaries
  5. Sorting algorithms, Simple quadratic sorts, O(n log n) sort, Comparison-based sorting algorithm

Box - Page - Convex - Zoom - Linear - Fade - None - Default

Syllabus

  • 2301520 Fundamentals of AMCS
  • Course Description
  • Behavioral Objectives
  • Learning Contents
  • Course Assessment
  • Required Text
  • Course Plan
  • References

Course Description

Mathematical reasoning; computer programming and algorithms; mathematical software systems.

Behavioral Objectives

  1. Describe and write a mathematical proof related to upper/lower bound of real number, limit of a real-value function and sequences of real numbers
  2. Analyze algorithms on various data structures
  3. Design data structure and algorithm to solve a given problem
  4. Prove algorithm correctness
  5. Perform asymptotic analysis of a given algorithm
  6. Analyze the Worst-case analysis, Best-case analysis and Average-case analysis
  7. Utilize mathematical software to solve problems in applied mathematics and computational science

Learning Contents

  • Mathematical software system
  • Computer programming and algorithms
  • Mathematical Reasoning

Down arrow

Mathematical software system

  1. Power Series and Numerical Approximation
  2. Data Manipulation and Statistics
  3. Differential Equations
  4. Computer Simulation

Down arrow

Computer programming and algorithms

  1. Definition of algorithm and its correctness
  2. Algorithm analysis:Worst-case, Best-case and Average-case
  3. Asymptotic notations and their relationships
  4. Relationship between algorithm and data structure
  5. Sorting algorithms

Down arrow

Mathematical Reasoning

  1. Logic
  2. Methods of proof
  3. Supremum and Infimum of sets of real numbers
  4. Sequences of real number
  5. Limits of real valued functions
  6. Continuous functions

    7. Up arrow

Course Assessment

  1. Part I:Mathematical software system (30%)
  2. Part II:Computer Programming and Algorithms (30%)
  3. Part III:Mathematical Reasoning (40%)

Required Texts

  • พัฒนี อุดมกะวานิช, หลักคณิตศาสตร์, สำนักพิมพ์แห่งจุฬาลงกรณ์มหาวิทยาลัย, 2555
  • Corman, T. H., Leiserson, C. E. and Rivest, R. L., Introduction to algorithms, MIT Press, 1990

Supplementary Texts

  • Aho, A.V., Hopcroft, J.E., and Ullman, J.D., The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
  • Brassard, G. and Bratley P., Fundamentals of Algorithmics, Prentice-Hall, 1996.
  • Even, S., Graph Algorithms, Computer Science Press, 1979.
  • Heileman, G. L., Data structures, algorithms, and object-oriented programming, McGraw-Hill Companies, 1996.
  • Horowitz, E. and Sahni, S., Fundamentals of Computer Algorithms, Computer Science Press, 1978.
  • Kurtz, D. C., Foundations of Abstract Mathematics, McGraw-Hill, 1992.
  • Manber, U., Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.

Course Plan

  • 1 - 10 July 2014:Mathematical software system
  • 15 - 22 July 2014:Computer Programming and Algorithms
  • 23 - 30 July 2014:Mathematical Reasoning

Mathematical software system

No.Date/TimeContents
11 กรกฎาคม 2557 9:00 – 12:00 น. Introduction to Mathematical Software
22 กรกฎาคม 2557 9:00 – 12:00 น. Power Series and Numerical Approximation
33 กรกฎาคม 2557 9:00 – 12:00 น. Data Manipulation and Statistics
44 กรกฎาคม 2557 9:00 – 12:00 น. Differential Equation
57 กรกฎาคม 2557 9:00 – 12:00 น. Computer Simulation
68 กรกฎาคม 2557 9:00 – 12:00 น. Orientation: No class
79 กรกฎาคม 2557 9:00 – 12:00 น. Review
810 กรกฎาคม 2557 9:00 – 12:00 น. Part I exam

Computer Programming and Algorithms

No.Date/TimeContents
115 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 – 14:00 น.		 Definition of algorithm, Expressing algorithm, Problem specifications, Correctness, Loop invariants, Counter example
Lab 1: Introduction to Python on the web, http://www.sagemath.org
216 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 – 14:00 น.		 Algorithm performance, Worst-case, Best-case and Average-case analysis, RAM model, Asymptotic notation
Lab 2: Python data structure and programming
317 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 – 14:00 น.		 Asymptotic notations and their relationships, Basic algorithm analysis, Recursive algorithm
Lab 3: Function and Class in Python
418 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 – 14:00 น.		 Relationship between algorithm and data structure, Abstract Data Type, Dictionaries
Lab 4: Advanced data structure in Python
521 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 – 14:00 น.		 Sorting algorithms, Simple quadratic sorts, O($n \log n$) sort, Comparison-based sorting algorithm
Lab 5: Sorting algorithm in Python
622 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 – 14:00 น.		 Part II exam

Mathematical Reasoning

No.Date/TimeContents
123 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 - 14:00 น.		 Logic and methods of proof
224 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 - 14:00 น.		 Boundednes, Supremum, Infimum
325 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 - 14:00 น.		 Sequences of real numbers
428 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 - 14:00 น.		 Limits and Continuity
529 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 - 14:00 น.		 Review
630 กรกฎาคม 2557 8:30 – 11:30 น.
13:00 - 14:00 น.		 Part III exam

Links

Computer Programming and Algorithm lectures

  1. Definition of algorithm, Expressing algorithm, Problem specifications, Correctness, Loop invariants, Counter example
  2. Algorithm performance, Worst-case, Best-case and Average-case analysis, RAM model, Asymptotic notation
  3. Asymptotic notations and their relationships, Basic algorithm analysis, Recursive algorithm
  4. Relationship between algorithm and data structure, Abstract Data Type, Dictionaries
  5. Sorting algorithms, Simple quadratic sorts, O(n log n) sort, Comparison-based sorting algorithm