Lesson 1 class introduction, DSA introduction

class introduction

• class website: csie.ntu.edu.tw/~htlin/course/dsa20spring
• textbook: Data Structures and Algorithms in C++, 2nd Edition by Goodrich, Tamassia and Mount

DSA introduction

Five Criteria of Algorithm

• input
• output
• definiteness: for programmer
• finiteness: terminate
• effectiveness: computer

Example: getMinIndex with Sequential Search Algorithm

int getMinIndex(int* arr, int len){  //input
int minpos = 0;
int i;
//effective(compiler)
for(i=1;i<len;i++){   //finiteness & definiteness
if(arr[i]<arr)
  minpos=i;
}
return minpos;//output 
}

• Correctness Proof of Algorithm

loop invariance by mathematical introduction — discrete math helps

claim: “algorithm” returns m such that arr[m] <= arr[j] for all j
claim2: at (end of) loop of i=k
arr[minpos]<=arr[j] for j=0,1,…,k
proof: i=1: trivial
i=k ==> i=k+1

• Efficiency of Algorithm
  knockout tournament for getMinIndex: not much faster overall, but possibly faster if done in parallel

Expressing Algorithms with Pseudo Code

Pseudo Code for getMinIndex

pseudo code: “spoken launguage” of programming

getMinIndex
  (integer array arr, integer len)
  minpos <-0
  for i<- 1 to len do
    if arr[i]<arr[minpos] then
      minpos<-1
  return minpos

Bad Pseudo Code

• Too detailed
• Too Mysterious: goals of pseudo code: communicate correctly
• Too Abstract

Good Pseudo Code of SelSort

no “formal definition” and depends on the speaker/listener

selSort
(integer array arr, integer len)
for i<-0 to len-1 do
 //find minIndex from arr[i .. len-1]
 min <- get MinIndex(arr[i .. len-1])
 //put arr[min] at arr[i]
 swap(arr[min],arr[i])

What is Data Structure

scheme of organizing data within computer

• How to Organize 200 Exam Sheets?
  • casual
  • highest score -> lowest
  • Student ID
  • End of the Student ID
• Good Algorithm Needs Proper Data Structure
  If having data structure such that getMinIndex faster,
  ===> SelSort also faster

algorithm::data structure ~ recipe::kitchen structure

• Good Data Structure Needs Proper Accessing Algorithms: get, insert

rule of thumb for speed: often-get <==> “nearby”

• Good Data Structure Needs Proper Maintenance Algorithms: construct,update, remove

hidden “cost” of data structure: maintenance effort

Why Data Structures and Algorithms

Data Structure ——> Storage
Algorithms ——> computation resources

use storage/computation resources properly ====> good program

• Proper Use: Tradeoff of Different Factors
  • time
  • space
  • power
  • bandwidth
  • manhour

understand tradeoff ====> good program

• Different Tradeoff on Different Platforms

parallel transmission/computation

• Programming Coding
  • requirement
  • analysis
  • design
  • refinement & coding
  • verification: proof/test/debug

programming :: buildinghouse ~ coding :: construction work