comp-intro-midterm.md

Computer :

• A programmable electronic device that can store, retrieve, and process data
• A "black box" that will accept input and produce output
  • the output depends on the current program in the block box

The Von Neumann Model : Such computers have input and output devices, a main memory (RAM), and a CPU (The central processing unit)

Stored-program idea : Main memory contains both the program and the data with which the program is working

The Turing machine

• An abstract artifact
• To analyze the logical foundations of computer systems

The von Neumann Architecture

• A practical Architecture
• The conceptual blueprint of almost all computer platforms today
• Central Processing Unit (CPU) + Memory + Input/Output(I/O) devices

Memory

• Holds data items + programming instructions
• In some computers program and data are stored in separate memory units
  • Data memory and Instruction memory
• CPU
  • ALU + set of registers + control units
• I/O devices
  • LCD monitors, keyboards, printers, mice, network interface cards, CD-ROMs, and so forth

Computer Program

• A set of instructions telling the computer what to do with the input in order to produce the output

Machine code

• The representation of a computer program which is actually read and interpreted by the computer
• A program in machine code consists of a sequence of machine instructions
• Instructions are binary strings

Programming Language

• A formal language in which commputer programs are written
• The definition of a particular language consists of both syntax and semantics
  • Syntax - how the various symbols of the language may be combined
  • Semantics - the meaning of the language constructs

File

• A complete collection of data treated by a computer as a unit especially for purposes of input and output

Operating System

• Software that controls the operation of a computer and directs the processing of programs (as by assigning storage space in memory and controlling input and output functions)

Virtual Machine

• Software implementation of a machine that executes programs like a physical machine

Cloud Computing:

• 한 기계를 여러 사람이 나눠서 사용
• 넓은 의미에서의 버츄얼 머신

Compiler

• A program that converts another program from some source language (or programming language) to machine language (object code)

Algorithm

• A precise and unambiguous specification of a sequence of steps that can be carried out mechanically

Moore's Law

Andy Grove's 10x rule

Operator Precedence

• a++, a--
• ++a, --a
• • / %

• < <= >=

• == !=
• &&
• ||

Some code:

public static void bubblesort(int A[])  {
  for (i = 1; i < n; i++) {
    for (j = 0; j < n-i; j++) {
      if (A[j] > A[j+1]) {
        int temp = A[j];
        A[j] = A[j+1];
        A[j+1] = temp;
      }
    }
  }
}

public static void mergesort(int A[]) {
  mergesort(A, 0, A.length - 1);
}
public static void mergesort(int A[], int left, int right) {
  if (left < right) {
    int mid = (left + right) / 2;
    mergesort(A, left, mid);
    mergesort(A, mid+1, right);
    merge(A, left, mid, right);
  }
}
public static void merge(int A[], int left, int mid, int right) {
  int temp[] = new int[right - left + 1];
  for (int k = 0; k < right - left + 1; k++) {
    temp[k] = A[left + k];
  }
  int i = 0;
  int j = mid - left + 1
  int k;
  for (k = left; k <= right; k++) {
    if (temp[i] < temp[j]) {
      A[k] = temp[i];
      i++;
    }
    else if (temp[i] > temp[j]) {
      A[k] = temp[j];
      j++;
    }
    if (i >= mid - left + 1 || j >= right - left + 1) break;
  }

  while(i < mid - left + 1) {
    k++;
    A[k] = temp[i];
    i++;
  }
  while (j < right - left + 1) {
    k++;
    A[k] = temp[j];
    j++;
  }
}

public static void binarysearch(int ab[]) {
  int low, mid, high;
  low = 0; ; high = n-1;  //n means the size of array
  while (low <= high) {
  	mid = (low + high) / 2;
    if (x < ab[mid]) high = mid - 1;
    else if (x > ab[mid]) low = mid + 1;
    else return mid;
  }
  return -1;
}