Introduction to Algorithms

CharliePark·2020년 8월 25일
0

TIL

목록 보기
11/67

Abdul Bari의 Algorithms 강의를 듣고 공부한 내용입니다. 링크

 

What is Algorithms?

Algoritm is step by step procedure for solving a computational problem

Then, what is program?

Program is a procedure for solving a computational problem

OK, then what is the difference between program and algorithms?

 

By comparing program and algorithm, we can understand the importance and meaning of algorithm

 

Software development lifecycle : there are two important phases in developing

Design phase and Implementation phase

 

first you design, and then you write a program

Before you write a program, you write on a paper, MS Word, notepad etc. about how program should work, what's the function program have etc. this is nothing but algorithm.

So, algorithms are written in design time

Program is written in implementation time.

Algorithm

  • written in Design Time
  • written by someone who has domain knowledge (can also be a programmer with domain knowledge)
  • Any language can be used
  • HW/SW & OS independent
  • Analyze - achieving the goals right, efficient in time and space

Program

  • written in Implementation Time
  • written by programmer
  • programming language is used
  • HW/SW & OS dependent
  • Test - Running and checking errors

gonna use C language in this lecture

 

1.1 A priori analysis and A posteriori testing

※ A priori : (Latin) 선험적인; 연역적인 // A posteriori : (Latin) 경험에 의거하여, 귀납적인

 

A priori analysis

  • analysis of algorithm by studying it into a greater detail knowing how it is working
  • find out the time and space consumed by an algorithm
    • time function and space function
  • hardware independent
  • language independent

A posteriori testing

  • run and execute program, and check
  • watch-time, and the amount of memory consuming in terms of bytes
  • hardware specific
  • language specific
  • OS & environment specific

 

1.2 Characteristics of Algorithm

  1. Input - can take 0 or more input
  2. Output - at least 1 output
  3. Definiteness - should be obvious, should have single, exact meaning. cannot write any statement which can't be understood and can't be solved. Every statement should be clear and definite
  4. *Finiteness - must terminate at some point, must have finite set of statements, duration must be finite (on the other hand, there are some programs which runs continuously until the user stops them, for example, database server)
  5. *Effectiveness - whatever the statement in algorithm is, it must work in the steps of algorithm. None of statements in algorithms is unnecessary.

0개의 댓글