General Information

Resources

• Liem-Algoritma_dan_Pemrograman
• http://www.tutorialspoint.com/
• http://tour.golang.org/
• http://www.hackerrank.com/
• http://www.spoj.com/
• https://uva.onlinejudge.org/
• http://www.taipangame.com/
• https://en.wikipedia.org/wiki/Taipan!

Course Objectives

• Ability to analyze a computational problem and to propose an algorithmic solution
• Understanding and ability to apply basics components of an algorithm
• Understanding simple data structures; array data type and composite data type
• Mastering basic algorithms; finding extremes, common statistical formulas, …
• Mastering basic data searching and sorting methods

Grading System

• 30% Midterm exam
• 35% Final exam
• 15% Final project
• 10% Lab works
• 10% Quizes and homeworks
• A > 80, D < 50, E < 40

Reading list

There will be quizes from the reading material

• wk 2. pg 8-45
• wk 3. pg 46-54 and 84-90
• wk 4. pg 55-62
• wk 5. pg 91-117
• wk 6. pg 63-83

• wk 8. pg 118-123 and 131-134
• wk 9. pg 124-130
• wk 10. pg 135-149
• wk 11. pg 150-157 and 160-188
• wk 12. pg 189-205

Why This Course is Hard

Quote from Prof. Michio Kaku

Let me give some advise to you if you are a young physicist, perhaps just getting out of high school You have dreams of being Einstein, you have dreams of working on string theory and things like that and then you hit freshman phyisics.

Let me be blunt: We physicists flunk most students taking elementary physics. And we’re more or less encouraged to do so by the engineering department. We don’t want to train engineers who make bridges that fall down. We don’t want to create engineers that create skyscrapers that fall over.

There’s a bottom line: you have to know the laws of mechanics.

So before you can work with the laws of Einstein, you have to work with the laws of friction, levers, pulleys, and gears.

As a consequence we have a very high flunk-out rate in elementary physics. So if you’re a young physicist graduating from high school with stars in your eyes, and you encounter freshman physics for the first time, watch out!

If you have a rough time, that’s the way it is.

Computer Science analogy for Prof Michio Kaku advice

You have dreams to be a computer scientist, you have dreams of building the ultimate games and things like that and then you hit basics of computer algorithms,

Let me be blunt: We computer scientists flunk most students taking basics of algorithms and data structures. And we’re more or less encouraged to do so by the college. We don’t want to train engineers who make system softwares crash. We don’t want to create engineers that create applications that are useless.

There’s a bottom line: you have to know the basics of algorithms.

So before you can work with machine learning, image processing, and stuff, you have to work with iterations, conditions, arrays, and simple data types.

As a consequence we have a very high flunk-out rate in basics of algorithms. So if you’re a young computer scientist graduating from high school with stars in your eyes, and you encounter basic algorithms for the first time, watch out!

If you have rough time, that’s the way it is.

What is Algorithm?

Algorithm

A named sequence of actions to achieve an expected result

The actions must be clearly understood by the actors (machines, people, …)

Its execution starts at one designated first action and finishes at a final action

It must terminate after a reasonable number of executed actions

Given an initial state, execution of the algorithm always gives the same final state

The expected result is the difference between the initial and the final state

Actions :

• Primitive actions (which are already clearly understood by actors), or
• Previously defined named algorithms

Computational Problem and Algorithmic Thinking

An algorithm is a recipe, when followed, will always give you a correct answer

Solving computational problems means finding/devising an algorithm

• Break down problem into smaller, easier to understand sub-problems
• Solution (aka the algorithm) to the sub-problems should be obvious
• Compose the solutions of the sub-problems to solve the whole problem
• Always plan the correct sequence of the composition of the sub-solutions

Algorithmic thinking is applicable and is very useful in many areas But surely is the most important basic knowledge in Computer Science

Computer Model

Computer Architecture

Model of Computation vs. Real Computers

Input

• keyboard, mouse, touchpad, touchscreen, scanner
• sensors: camera, gyro, gps, accelometer, lidar, …

Output

• display screen, printer, audio, vibration
• actuators: robot arms, pan-tilt device, autonomous vehicles, 3d-printer, …

Memory

• main memory (shortterm memory) byte addressable 8GB, …
• data accessed thru their addresses, commonly in words (4 byte size)

Processor

• Intel, AMD, Arm: #cores, caches, #bit instrs, general/special, #processors

(Computer) Algorithm vs. Computer Program

Primitive actions are computer executable instructions

Algorithm is used to express the ideas of the programming solution

• Algorithms solely for human readers

Program is the actual codes that will be used to drive a computer

• Source programs intended for both computers and (mainly) humans
• Rigid rules (syntax) how they are written
• Contain details may not pertinent to the solution main ideas
• Contain description of data to be processed
• Protocols to access particular device interfaces
• User interface design (GUI)
• Language style and philosophy

Algorithm Notation vs. Programming Languages

Algorithm notation is designed to be as simple as possible And easily implemented in many programming languages

Each programming language has its own design philosophy

• Procedural (C), Object oriented (Java), or Functional language (Lisp)

• General purpose language vs. Catering special needs (Game, Math, Web, Industry)

• Quick development vs. Efficient execution (interpreting vs. compiling)

What benefits in interpreting? And what about in compiling?

Samples of “hello world!”

// C
#include <stdio.h>
int main( int argc, char *argv[] ) {
    printf( "hello world!\n" );
    return 0;
}

;;; ANSI Common Lisp
(format t "hello world!~%")

/* Java */
public class HelloWorld {
    public static void main( String[] args) {
        System.out.println( "hello world!" );
    }
}

(* Pascal *)
program HelloWorld
begin
    writeln( 'hello world!' )
end.

0100 0101 = 0x2^7+1x2^6+..+0x2^3+1x2^2+0x2^1+1x2^0 = 69
2018 = 1024+512+256+128+64+32+2 = 2^10 +2^9 +2^8 +2^7 +2^6 +2^5 +2^11 = 0000 0111 1110 0010
0000 0111 1110 0010 = 07E2h

a <- 10
sum := a + b
ave = total / n

We can copy the value to somewhere else, but we don't move its value.
We can check what value stored in that variable
We can replace the value stored in that variable with a new value

e.g. i, j, temp1, tmax, average, arr, sum, SID, sName, StudentInfo, student_info, pcur

0 100000000 000000 = +0.5
0 101000000 111111 = +0.3125
S     M       E

100 0001 (65) - 101 1010 (90)  = 'A'-'Z'
110 0001 (97) - 111 1010 (122) = 'a'-'z'
011 0000 (48) - 011 1001 (57)  = '0'-'9'

input sname, sgpa, year

output 2018, sname, (total*2), (grade > 3)

sqrt(), sqr(), cos(), sin(), abs(), random(), crypt(), ...

output(), setTime(), Register(), Lock(), Unlock(), Exec(), Mount(), Mkdir(), ...

input(), json.Compact(), Unmarshal(), ...