Data Structures: Enero 2012

Lunes, Enero 30, 2012

PSITS NIGHT

For me, I enjoy the PSITS NITE last sunday.because many schools are attending and they have a representative per schools.the most I've enjoyed was the MTV spoof because all the schools are participating . and i don't forget the boy was standing right beside me....i saw my schoolmates in STI..

Shell sort

Description

Shellsort, also known as Shell sort or Shell's method is an in-place comparison sort. It generalizes an exchanging sort, such as insertion or bubble sort, by allowing the comparison and exchange of elements that lie far apart. Its first version was published by Donald Shell in 1959. The running time of Shellsort is heavily dependent on the gap sequence it uses. For many practical variants, determining their time complexity remains an open problem.It is a multi-pass algorithm. Each pass is an insertion sort of the sequences consisting of every h-th element for a fixed gap h (also known as the increment). This is referred to as h-sorting. It is an unstable: it may change the relative order of elements with equal values. It has "natural" behavior, in that it executes faster when the input is partially sorted.

Gap sequences

Every gap sequence that contains 1 yields a correct sort; however, the properties of thus obtained versions of Shellsort may be very different.
The table below compares most proposed gap sequences published so far. Some of them have decreasing elements that depend on the size of the sorted array (N). Others are increasing infinite sequences, whose elements less than N should be used in reverse order.

General term (k ≥ 1)	Concrete gaps	Worst-case time complexity	Author and year of publication
$\lfloor N / 2^k \rfloor$	$\left\lfloor\frac{N}{2}\right\rfloor, \left\lfloor\frac{N}{4}\right\rfloor, \ldots, 1$	$Θ(N 2)$ [when N=2^p]	Shell, 1959^[1]
$2 \lfloor N / 2^{k+1} \rfloor + 1$	$2 \left\lfloor\frac{N}{4}\right\rfloor + 1, \ldots, 3, 1$	$Θ(N 3 / 2)$	Frank & Lazarus, 1960^[3]
$2 k - 1$	$1, 3, 7, 15, 31, 63, \ldots$	$Θ(N 3 / 2)$	Hibbard, 1963^[4]
$2 k + 1$ , with 1 prepended	$1, 3, 5, 9, 17, 33, 65, \ldots$	$Θ(N 3 / 2)$	Papernov & Stasevich, 1965^[5]
successive numbers of the form $2 p 3 q$	$1, 2, 3, 4, 6, 8, 9, 12, \ldots$	$Θ(N log 2 N)$	Pratt, 1971^[6]
$(3 k - 1) / 2$ , not greater than $\lceil N / 3 \rceil$	$1, 4, 13, 40, 121, \ldots$	$Θ(N 3 / 2)$	Knuth, 1973^[7]
$\prod \limits_{\scriptscriptstyle 0\le q<r\atop \scriptscriptstyle q\neq(r^2+r)/2-k}a_q, \hbox{where}$ $r = \left\lfloor \sqrt{2k+\sqrt{2k}} \right\rfloor,$ $a_q=\min\{n\in\mathbb{N}\colon n\ge(5/2)^{q+1},$ $\forall p\colon0\le p<q\Rightarrow\gcd(a_p,n)=1\}$	$1, 3, 7, 21, 48, 112, \ldots$	$O(N e^\sqrt{8\ln(5/2)\ln N})$	Incerpi & Sedgewick, 1985^[8]
$4^k + 3\cdot2^{k-1} + 1$ , with 1 prepended	$1, 8, 23, 77, 281, \ldots$	$O (N 4 / 3)$	Sedgewick, 1986^[9]
$9(4^{k-1}-2^{k-1})+1, 4^{k+1}-6\cdot2^k+1$	$1, 5, 19, 41, 109, \ldots$	$O (N 4 / 3)$	Sedgewick, 1986^[9]
$h_k = \max\left\{\left\lfloor 5h_{k-1}/11 \right\rfloor, 1\right\}, h_0 = N$	$\left\lfloor \frac{5N}{11} \right\rfloor, \left\lfloor \frac{5}{11}\left\lfloor \frac{5N}{11} \right\rfloor\right\rfloor, \ldots, 1$	?	Gonnet & Baeza-Yates, 1991^[10]
$\left\lceil \frac{9^k-4^k}{5\cdot4^{k-1}} \right\rceil$	$1, 4, 9, 20, 46, 103, \ldots$	?	Tokuda, 1992^[11]
unknown	$1,4,10,23,57,132,301,701$	?	Ciura, 2001^[12]

When the binary representation of N contains many consecutive zeroes, Shellsort using Shell's original gap sequence makes Θ(N²) comparisons in the worst case. For instance, this case occurs for N equal to a power of two when elements greater and smaller than the median occupy odd and even positions respectively, since they are compared only in the last pass.
Although it has higher complexity than the O(NlogN) that is optimal for comparison sorts, Pratt's version lends itself to sorting networks and has the same asymptotic gate complexity as Batcher's bitonic sorter.
Gonnet and Baeza-Yates observed that Shellsort makes the fewest comparisons on average when the ratios of successive gaps are roughly equal to 2.2.^[10] This is why their sequence with ratio 2.2 and Tokuda's sequence with ratio 2.25 prove efficient. However, it is not known why this is so. Sedgewick recommends to use gaps that have low greatest common divisors or are pairwise coprime.^[13]
With respect to the average number of comparisons, the best known gap sequences are 1, 4, 10, 23, 57, 132, 301, 701 and similar, with gaps found experimentally. Optimal gaps beyond 701 remain unknown, but good results can be obtained by extending the above sequence according to the recursive formula $h_k = \lfloor 2.25 h_{k-1} \rfloor$ .
Tokuda's sequence, defined by the simple formula $h_k = \lceil h'_k \rceil$ , where

h' k = 2.25 h' k - 1 + 1

h' 1 = 1

, can be recommended for practical applications.

Martes, Enero 17, 2012

case study 3

For me in this case, the indictment of a programmer for the manslaughter for writing faulty codes that the result in the death of robot operator. they slowly, the course of many articles,are introduced into the several factors within the corporation that were contributed into the accident.For letter A, the responsibility for an accident is rarely defined and able to be traced into one or two individuals or causes. In this case,it is clear that the larger number of people can share the responsibility into the accident.They can identify all the people who involve.like Bart Matthews who was killed in the accident. For Letter B, i can imagine the leader of a task force was assigned into a correct the problems that can uncovered the accident.for letter C, If i am in the position of Ms. Yardley's i can say that i will react when Rays Jonhson told to us about the fake of the test result. i can decide that Mr. is the most who can be nice and they talked me that the test result .

case study 2

Im not agree, for the young Romanian for being charged with hacking into NASA computers and causing it more than 1.5 million dollars or (1.1 million euros) for having damage the US space agency,and the prosecutor was said on Tuesday.because this man was the only teenager who hacking the computer and A community of enthusiast computer programmers and systems designers, originated in the 1960s around the Massachusetts Institute of Technology's (MIT's) Tech Model Railroad Club (TMRC) andMIT Artificial Intelligence Laboratory. This community is notable for launching the free software movement. The World Wide Web and the Internet itself are also hacker artifacts. The Request for Comments RFC 1392 amplifies this meaning as "[a] person who delights in having an intimate understanding of the internal workings of a system, computers and computer networks in particular."

the young Romanian was named Victor Faur it's a 26 years old and from the western town of Arad ,it was accused for breaking computers in the US navy and the Department of Energy between November 2005 and September 2006.

The Romanian police was alerted into NASA in July that the servers had been breached by unknown people based in Romania.

The ensuing probe was jointly by the Romanian police and the FBI to led into the man who hacked the computer in NASA. and then the NASA was need to rebuild the systems into the scientists and engineers to communicate with spacecrafts and the resulting was huge losses for NASA.

Victor Faur's said in the television interviews that his action was aimed to prove that several computers are vulnerable to attack and underlined.but he not tries to make any "material gains".

He said that i had neither modified nor erased the files,nor destroyed the communications systems, who was formally put under the investigation in December and has been barred from leaving the country

An early day the indictment by the US Attorney's office that Faur charges with leading a hacking group called "WhiteHat Team" which they succeed to broke the systems because of their reputation of being among the most secure in the world or they was called a Hacker's deleted team.

Case Study 5

Give at least three scenarios in the real world wherein HASH COLLISION can happen. Include an image.

Password cracking = is the process of recovering passwords from data that has been stored in or transmitted by a computer system.

Certificate authority, or certification authority, (CA) = is an entity that issuesdigital certificates. The digital certificate certifies the ownership of a public key by the named subject of the certificate.

digital signature or digital signature scheme= is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit.

Give at least three specific software/program/application wherein HASHING and HASH COLLISION might occur. Include the name of the software/program/application, description and a screenshot.

Microsoft Word Mac= Microsoft Office for Mac 2011 is the most recent version of the Microsoft Office productivity suite for Mac OS X. It is the successor to Microsoft Office 2008 for Mac and is comparable to Microsoft Office 2010 for Windows.

MySQL= is arelational database management system (RDBMS) that runs as a server providing multi-user access to a number of databases. It is named after developerMichael Widenius' daughter,

Linux- is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds. Linux system distributions may vary in many details of system operation, configuration, and software package selections.

Lunes, Enero 16, 2012

Case Study 4

1. What is hash collision?
-In Computer Science,a Collision or Clash is a situation that occurs when two distinct of data have the same hash value,check sum,fingerprint, or cryptographic digest.

2. What really happens during a hash collision? Include an image
-Collisions are unavoidable whenever members of a very large set (such as all possible person names, or all possible computer files) are mapped to a relatively short bit string. This is merely an instance of the pigeonhole principle.

3. What are the ways and methods to resolve hash collision? Explain Each

Linear probing, in which the interval between probes is fixed (usually 1)
Quadratic probing, in which the interval between probes is increased by adding the successive outputs of a quadratic polynomial to the starting value given by the original hash computation
Double hashing, in which the interval between probes is computed by another hash function

Lunes, Enero 9, 2012

reflection of case study 1

We just have a antivirus in our computers,laptops and in our USB that have detected if we download our files in the computer. It uses flaws in Windows software and dictionary attacks on administrator passwords to propagate while forming a botnet, and has been unusually difficult to counter because of its combined use of many advanced malware techniques. The Conficker had infected an estimated seven million government, business and home computers in over 200 countries, making it the largest known computer worm infection since the 2003.the cause of the infected computers are the computers will shut down,causing the forcing aircraft at several airbasesto be grounded because their flight plans could not be downloaded and leading to its disconnection for three days.The Conficker was first detected in November 2008.To start itself at system boot, the virus saves a copy of its DLL form to a random filename in the Windows system folder, then adds registry keys to have svchost.eve invoke that DLL as an invisible network service.

The symptoms of the Conficker Worm are account lockout policies being reset automatically,certain microsft windows services such as automatic updates,background intelligent transfer service(BITS),windows defender and windows error reporting disabled, domain controllers responding slowly to client requests,congestion on local area networks(ARP flood as consequence of network scan),web sites related to antivirus software or the windows update service becoming inaccessible and user accounts locked out.