이 시리즈의 모든 자료와 내용의 출처는 2021-2 고려대학교 COSE213 정원기 교수님의 자료구조 수업임을 밝힙니다.

Introduction to Data Structure

Software System Life Cycle

총 5단계로 구성
: Requirements - Analysis - Design - Refinement & Coding - Verification

Requirements

• Input, Output의 Specification
• Function의 Specification
• Error Handling

Analysis

• 문제 상황을 manageable한 수준으로 break-down
• Strategies : Bottom-up / Top-down
  Bottom-up : small / specific한 function들에서 시작 -> connect (structured programming)
  Top-down : high-level to low-level, complex system (OOP)

Design

• Language-independent (No coding!)
• Data objects and operations
  : Defining ADTs(Abstract Data Type)
  Specifying Algorithms (Operations / Functions)

Refinement & Coding

• Choosing representations and writing algorithms
• Programming Paradigms : Structured Programming, Modular Programming, OOP...

Verification

• Correctness proofs
• Testing : All possible scenarios / Measure running time
• Error removal

Data Abstraction & Encapsulation

What is Data Abstraction & Encapsulation?

• Data Encapsulation
  : Concealing of the implementation details of a data object from the outside
  ex) class - public / private (cannot be accessed from outside)
• Data Abstraction
  : Separation between the specification (what) of a data object and its implementation (how) - methods & variables

ADT (Abstract Data Type)

• Data type : Collection of objects and a set of operations
  ex) int
  Objects : 0, 1, -1, 2, -2, ... , MININT, MAXINT
  Operations : +, -, *, /, ...

• Abstract Data Type
  : A data type that the specification of objects and operations is separated from the representation and implementation
  (구체적 구현 방법을 포함하지 않는 추상적인 데이터 타입)

• Example of ADT

  ADT NaturalNumber
  Objects : an ordered range of the integers from 0 to MAXINT
  Functions :
  +, -, <, ==, = ...
  Zero():NaturalNumber
  IsZero(x):Boolean
  Add(x, y):NaturalNumber
  Equal(x, y):NaturalNumber
  Successor(x):NaturalNumber
  Subtract(x, y):NaturalNumber

Benefits of Abstraction & Encapsulation

• Simplification of development
• Easier Testing and Debugging
• Reusability
• Modification of data type without changing interfaces

Algorithm

What is Algorithm?

• Finite set of instructions that accomplishes a particular task
• Criteria :
  Input >= 0 / Output >= 1
  Definiteness : Instructions should be clear and umambigous
  Finiteness : Algorithm terminates after a finite number of steps
  Effectiveness : Every instruction must be basic enough to be carried out ( Pseudo-codes )

Recursive Algorithm

• A function calls itself (direct)
• Or A function calls another function that invokes the calling function (indirect)
• Related to mathematical induction
• Terminating condition is essential for every recursive algorithm