November 19, 2019

Complexity Classes

The following list contains common time complexities of algorithms: O(1) The running time of a constant-time algorithm does not depend on the input size. A typical constant-time algorithm is a direct formula that calculates the answer. O($\log n$) A logarithmic algorithm often halves the input size at each step. The running time of such an algorithm is logarithmic, because $\log n$ equals the number of times n must be divided by 2 to get 1. Read more

November 4, 2019

Dining Philosophers

Bữa tối của các triết gia (dining philosophers problem) là một ví dụ nổi tiếng khi nhắc đến các vấn đề trong bài toán xử lý concurrent. Vấn đề được phát biểu như sau: Cho 5 triết gia ngồi chung một bàn tròn với 5 chiếc đũa xếp xem kẽ giữa 2 người ngồi cạnh nhau như hình img: sphof.readthedocs.io Mỗi triết gia tìm cách để ăn được thức ăn từ đĩa của mình với điều kiện: “chỉ ai có 2 chiếc đũa cạnh mình mới được phép ăn”, do đó họ lần lượt đổi trạng thái giữa ăn (eating) và đợi (thinking) :)) Mỗi người sau khi giữa đôi đũa để ăn sau 1 khoảng thời gian phải bỏ lại 2 chiếc đũa về vị trí cũ để tiếp tục quá trình này. Read more

September 30, 2019

Immutable Go Object

Every Go programmer knows about the receiver in go, which be declared as: type X struct {} func (receiver X) doThing() {...} We have two types of receiver in golang, which is Value receiver and Pointer receiver. Basically, the receiver in golang could be map to self in other programming languages and the function which uses the receiver will be pointed from struct type of the receiver. So, what does this means, anyway? Read more

September 17, 2019

Imperative vs Functional

Difference between Imperative languages and Functional languages: Imperative languages are based on assignment sequences whereas functional languages are based on nested function calls. In imperative languages, the same name may be associated with several values, whereas in functional languages a name is only associated with one value. Imperative languages have fixed evaluation orders whereas functional languages need not.(1) In imperative languages, new values may be associated with the same name through command repetition whereas in functional languages new names are associated with new values through recursive function call nesting. Read more

August 15, 2019

Boundaries for algorithm analysis

Some boundaries you should know to approximate time and space complexity of your algorithm. $2^{10} = 1,024 \approx 10^{3}, 2^{20} = 1,048,576 \approx 10^{6}$ 32-bit signed integers (int) and 64-bit signed integers (long long) have upper limits of $2^{31} − 1 \approx 2 \times 10^{9}$ (safe for up to $\approx 9$ decimal digits) and $2^{63} − 1 \approx 9 \times 10^{18}$ (safe for up to $\approx 18$ decimal digits) respectively. Read more

© khanhtc 2019