Latest Research Trends in Algorithms and Computer Science

Concept of Algorithm Computer Architecture The Concept of Algorithm Complexity and Order NP-complete Problems

Self Introduction Name: Takeaki Uno Affiliation: NII, Sokendai Age, status: 50, professor Research Area: algorithm, data mining, bioinformatics, operations research Recent Studies: efficient practical algorithms for basic operations and basic tasks on huge data in genome science, and data mining, etc.

Goal / Evaluation / Reference Algorithms are efficient especially for processing big data The goal is to learn the skill and sense of developing algorithms, or viewing the problems and issues from algorithmic view points Evaluation: a report, on the end of the semester Reference: any textbook of title Algorithm and/or Data structure , that you feel interesting/understandable e-mail: uno@nii.ac.jp Homepage http://research.nii.ac.jp/~uno/index-j.html (the slides are uploaded)

Contents of the Lecture Architecture of computer, and the program CPU, memory, OS, memory management, instruction, register Data structure (efficient ways of recording/using the data) stack, queue, heap, binary tree, hash Basic Design of Algorithms recursion, divide-and-conquer, enumeration, dynamic programming, sorting, string matching Graph Algorithms matching, shortest paths,

Connection to Latest Researches Algorithms are connected to the many latest researches (algorithms are studied in the areas, in which algorithm are related) Especially, having simple mathematical models and criteria, with huge data or complicated data + Machine Learning (and Other Informatic Areas) There are needs of very fast computation with high accuracy, to deal with massive data + Chemoinformatics Chemical compounds are networks of atoms, so tractable for computers. However, the stereographical structures are difficult

Connection to Latest Researches + Bioinformatics Human genome is of 3 billion letters. They have only 4 kinds of letters ATGC, thus computers have advantages. Genes and variations often have some implicit rules + Astronomy Computer systems of observatories generates huge amount of data, and those data is accumulated to integrated databases + Social science recently, there have been progresses on understanding systems of societies by simulations with including micro activities

Connection to Latest Researches + architecture other than structural calculations to evaluate the strength of the buildings, material optimizations and structure optimizations reduce the costs + literature large amount of literatures allows as to find interesting knowledge by computer operations + other development of simulation science, that is to understand the real world phenomenon and mechanisms by simulations

Latest Researches in Japan Japanese algorithmic researches are of high levels in the world + interior point methods for optimization problems + discrete mathematics and combinatorial optimizations + compression and succinct indexes + database search and database construction + data mining + computational geometry Studies on algorithms are currently on theory, mainly Engineering theorems would be derived in future

Architecture of Computer

Basic Architecture The center of computer is CPU (central processing unit) that basically does basic arithmetic operations CPU is like an engine of a car Having CPU would be a definition of computer Other than CPU, a computer has memory that records several (many) values (mostly 0 or 1) CPU memory

Interfaces Monitor, keyboard, mouse etc. are connected to CPU, and controlled/managed by signals given by CPU From CPU, these signal receive/generation seems like memory; writing some values to a specified memory, signal will be sent So, everything is operated by signals, especially 0/1

Program CPU can do + read value of memory, write to memory + arithmetic operations such as addition and division + compare the values, and branch the operation These are called instructions (values are called operands) The order of instructions are written in a part of memory This is called program Execution is to operate instructions according to the program CPU memory

Execution of Program CPU executes instructions written in the program, sequentially Instructions are written in numbers, and each function is assigned to a number During the execution, the program can change the memory place to read the program (jump) Branching is done by this; jump or not according to the comparison (conditional jump) CPU memory

CPU C JAVA Perl, Basic, CPU

15 0 16 2 15 16 15 17 10 CPU

1 0 CD

0 1 01 01 01 8 2 0-255 2 9 128+32+16+4+1 = 181

16 1 11111111 01 4 24 16 10-15 abcdef 14=d 255=ff

0 1 20 20 20

01 2 32 4 (0-40 ) 2 56 8 256 128+32+16+4+1 = 181 + 4+1 + (16+4+1)/32 = 5.65625

1 256 255 -1 1 1111111 + 1 = 100000000 9 0 -1 +1 -2 254 -5 251 505 256 249 -7 63754 10

10 CPU CPU

CPU CPU HDD

100 0

OS OS Windows UNIX OS

OS

Complexity and Order

Ways to Solve How to solve and The solution are different + Curry and the way to cook curry rice + The way to solve a puzzle ring + The way to stack the tower of Hanoi + The solution to a quadratic equation x2 - 2x + 1 = 0 Ways to solve is more abstract than solution; solution is a solution to just an instance Consider ways to solution

Computer Algorithm Algorithm: set (order) of instructions to do a specified task Usually, algorithm is that for computers Algorithm can be considered as a theory of designing the way of computing, or theory of efficient programs Summation from 1 to 100: 1+2+,...,+100 99 additions (1+100) * (100/2) 3 operations Cut a carrot into slices of star shapes make slices, then cut the edges of each slice make a star shaped stick, then slice it

Algorithms in Your Life how to cook calculation with figures written down on paper car driving skill employment interviews in companies (all are not complete )

Evaluation Criteria How do we evaluate algorithms? How simple simplicity of programs Efficiency (speed, place, cost, ) speed and memory usage (electric power consumption) Simplicity is difficult to evaluate, but speed and memory usage can be measured by values

Evaluation of Time It is easy to evaluate the speed of a program; just get the duration of execution Of course, the quality of the writing of the program affects this and also the performance of the computer But, this is the evaluation of programmer , not that of algorithm Even though the algorithms are the same, the skill of programmers makes the difference We want to have a good model of measuring the efficiency of algorithms

Turing Machine Making model of algorithms means making model of computers We need to have quite basic one The base of computer is CPU and memory The Turing machine is such a model A Turing machine is composed of a tape that records sequence of 01 data, and a head that reads/writes 01 data, and an execution unit managing the movement of tape A Turing machine can read/write data, move the tape, and change the internal state of the execution unit

A Model for Computation Time The time of Turing machine is evaluated by the number of read/write operations Basically, any operation of a computer can be simulated with several operations of Turing machine the number of operations is independent from the time/size of each operation So, both can be evaluated by the same model the number of operations executed by an algorithm will be a good measure

Abstracted Evaluation The idea of the number of basic operations is good. It is much abstracted. However, still the skill of programmer affects We want to have more abstracted one that is independent from that Anyway, what kind of issues do we want to evaluate? For example, measure the efficiency on the execution of a specified task? for a benchmark problem? then, basically the skill of programming still affects

Evaluation for Input Size Computation needs some inputs The size of input increases, then computation time will be long Observe the increase of time against the increase of size we will get a function representing this relation For the input size n (#bits, in exact), we represent the number of the necessary operations such as 10n2+5n+2 This varies among several inputs, use average? to assure the time, we use the maximum

Ignoring the Coefficients We want to know the increase of operations it depends on the largest degree, mainly; 10n2+5n+2 we focus on 10n2 , and ignore other coefficients Programming skills makes simple operations more simpler affects to coefficients such as 10n2+5n+2 we focus only on n2, and ignore all constant factors This way of evaluating the cost of computation is called evaluation by order

Define Mathematically A function f(n) is O(g(n)) is defined by lim f(n) n g(n) < + We say that the order of an algorithm is O(g(n)) if the function bounding the maximum number of basic operations for any input of size n is of O(g(n)) The order of computation time is called time complexity, or simply complexity

Summary of Order Order of computation time: O(f(n)) a (polynomial/exponential) function representing an upper bound of the computation time in the term of input sizes + coefficients are ignored since it represents the programming skill + we focus only on the maximum magnitude (depends only on the maximum degree for larger inputs) Find a word in a dictionary of n items linear search O(n) binary search O(log n) Sorting n numbers insertion, quick sort O(n2) merge sort, heap sort O(n log n) Small order algorithms are so efficient even though the computer and/or programmer is not good

Advantage / Disadvantage When the problem is big, acceleration by algorithmic theory is drastic When the problem is small, practical performance is bad due to sophisticated construction of operations Can not represent the average and practical performance size of million size of 100 2-3 times 10,000 times

Evaluation of Memory Usage The efficiency of memory usage can also be evaluated by the order and complexity + the order represents the worst usage of memory amount for the input size + the complexity is called space complexity We can also ignore the skill of programming For the memory usage, evaluation of the worst case is more acceptable since the algorithm stops if the memory is short

Fundamentals of Complexity Theory

Good Design When we can decrease the order of an algorithm, we could improve the design of the algorithm , then, some question arise; which algorithm is good/bad? Where is the boundary An idea is to compare the most na ve algorithm So, observe the most na ve algorithm

Nave Algorithm We here say non-well designed algorithm na ve algorithm Suppose that here na ve means that to explorer all the possibilities + find all numbers from a1, ,an that are less than b examine all subsets of a1, ,an, and output the one that partitions the set in the way of the statement + sorting examine all possible orders, and output the one which is increasing order + find the longest decreasing subsequence of a1, ,an examine all combinations of a1, ,an, and output the longest among all decreasing sequences

Time of Nave Algorithms + find all numbers from a1, ,an that are less than b + find the longest decreasing subsequence of a1, ,an computation time is O(n2n) + sorting computation time is O(n n!) O(n2n logn) The time spent by these algorithms, that spends time exponential in the input sizes, is called exponential time, and these algorithms are called exponential time algorithms

In Good Ways + find all numbers from a1, ,an that are less than b scan the numbers, and output those less than b computation time is O(n) + find the longest decreasing subsequence of a1, ,an for each ai, find the longest decreasing subsequence ending at ai Find the longest among those of all ai s computation time is O(n2) + sorting scan the sequence and swap the pairs of neighboring numbers with the reverse ordering; repeat this n times computation time is O(n2)

Good Algorithms computation time is O(n) computation time is O(n2) computation time is O(n2) They are not exponential These times that are polynomial in the input sizes are called polynomial time, and the algorithms are called polynomial time algorithms Any polynomial, even with large degrees, is always smaller than exponential, for sufficiently large n, thus essentially different hence, polynomial is good, in some sense

Difficulty of Problems Good algorithms solve problems in short time So, the existence of good algorithm means that the problem is easy to solve (no need of testing all possibilities) the difficulty indicates the cost of developing algorithms polynomial time means that the problem would be easy no polynomial time is found means that the problem would be difficult then, we can compare the difficulties of two problems

Exact Comparison We can compare the difficulties of the problems, by comparing the orders of the algorithms for the problems However, in exact, it is not sufficient faster algorithms would exist So, consider special cases in which we can surely compare, although it is perfectly general