Category Archives for Web Science

C.4.1 Online Interaction

C.4.1 Discuss how the web has supported new methods of online interaction

Google Maps is it free ? 

If your business is missing can you add it 

Can this information be monetized ? How 

Should Google have a monopoly on location information?

Are there Alternatives to Google Maps?

Watch Video below and then create an account on open street map and add a building your condo/house Wells school etc. Read this post and describe in your own word how Open Street Maps is Different from Google Maps. Post your response to google classroom

C.4.1 Online Interaction Continued


KEYWORDS PHRASES Web1.0 & Web 2.0

WEB 1.0

Semantic Web

Web 2.0 

Web 3.0

ubiquitous

Berners-Lee

open protocols HTML HTTP

decentralization

successful companies that emerge at each stage of its evolution become monopolies

market economics don’t apply.

hypertext systems

Read Only

Read Write

Hyperlinks

Web of linked documents

social networking phenomenon took hold

Web wasn’t about linking documents, it was about connecting people.

Social Networks

KEYWORDS Semantic Web Return of The Link

The aim of the Semantic Web is to shift the emphasis of associative linking from documents to data

Abundantly available information can be placed in new contexts and reused in unanticipated ways. This is the dynamic that enabled the WWW to spread, as the value of Web documents was seen to be greater in information rich contexts (O’Hara & Hall, 2009).

WEB of Data

Relational databases

Excel Speadsheets

Web 3.0

ubiquitous

Berners-Lee

URI

Linked to Other Data

Web of Linked Data

market economics don’t apply.

RDF (resource description network)

Democracy rules: open and free

Missing links – search engines fill the gap

Hyperlinks

Web of linked documents

Governments are making data available see https://data.gov.uk/

Web wasn’t about linking documents, it was about connecting people.

datasets

The beginnings of the web (Web 1.0 , Web of content)

The world wide web started around 1990/91 as a system of servers connected over the internet that deliver static documents, which are formatted as hypertext markup language (HTML) files, which support links to other documents, but also multimedia as graphics, video or audio. In the beginnings of the web, these documents consisted mainly of static information and text, where multimedia were added later. Some experts describe this as a “read-only web”, because users mostly searched and read information, while there was little user interaction or content contribution.

Web 2.0 – “Web of the Users”

However, the web started to evolve into the delivery of more dynamic documents, enabling user interaction or even allowing content contribution. The appearance of blogging platforms as Blogger in 1999 gives a time mark for the birth of the Web 2.0. Continuing the model from before, this would be the evolution to a “read-write” web. This opened new possibilities and lead to new concept as blogs, social networks or video-streaming platforms. Web 2.0 might also be looked at from the perspective of the websites themselves evolving in more dynamic and feature-rich. For instance, improved design, JavaScript and dynamic content loading could be considered Web 2.0 features.

Web 3.0 – “Semantic Web”

The internet and thus the world wide web is constantly developing and evolving into new directions and while the changes described for the Web 2.0 are clear to us today, the definition for the Web 3.0 is not definitive yet. Continuing the read to read-write description form earlier, it might be argued that the Web 3.0 would be the “read-write-execute” web. One interpretation of this, is that the web enables software agents to work with documents by using semantic markup. This allows for smarter searches and the presentation of relevant data fitting into context. This is why Web 3.0 is sometimes called the semantic executive web.

But what does this mean?

It’s about user input becoming more meaningful, more semantic, by users giving tags or other kinds of data to their document, that allow software agents to work with the input, e.g. to make it more searchable. The idea is to be able to better connect information that is semantically connected.

Later developments

However, it might also be argued that the Web 3.0 is what some people call the Internet of Things, which is basically connecting every day devices to the internet to make them smarter. In some way, this also fits the read-write-execute model, as it allows the user to control a real life action on a device over the internet. Either way, the web keeps evolving and the following image provides a good overview and an idea where the web is heading to.

he Web Expansion (TrendOne, 2008)

Further Reading 

http://www.ftsm.ukm.my/ss/Book/EVOLUTION%20OF%20WWW.pdf

https://eprints.soton.ac.uk/272374/1/evolvingwebfinal.pdf

http://dig.csail.mit.edu/2007/Papers/AIMagazine/fractal-paper.pdf

C.2.9 Describe the different metrics used by search engines.

C.2.8 Suggest how web developers can create pages that appear more prominently in search engine results


      C.1.6 Describe how a domain name server functions.


        Domain Name Servers (DNS) are the Internet's equivalent of a phone book. They maintain a directory of domain names and translate them to Internet Protocol (IP) addresses.

        This is necessary because, although domain names are easy for people to remember, computers or machines, access websites based on IP addresses.

        Information from all the domain name servers across the Internet are gathered together and housed at the Central Registry. Host companies and Internet Service Providers interact with the Central Registry on a regular schedule to get updated DNS information.

        When you type in a web address, e.g., ibcomputerscience.xyz your Internet Service Provider views the DNS associated with the domain name, translates it into a machine friendly IP address ( and directs your Internet connection to the correct website.)

        After you register a new domain name or when you update the DNS servers on your domain name, it usually takes about 12-36 hours for the domain name servers world-wide to be updated and able to access the information. This 36-hour period is referred to as propagation.

        Find the IP address (32 bits )for this domain and covert the 4 bit parts into 4 Binary octets

          C.2.8 SEO Methods

          C.2.8 Suggest how web developers can create pages that appear more prominently in search engine results


            On Page

            • Bullet Point 1
            • Bullet Point 1
            • Bullet Point 1
            • Bullet Point 1
            • Bullet Point 1
            • Bullet Point 1

            Off  Page

            • Bullet Point 1
            • Bullet Point 1
            • Bullet Point 1

              C.1.6 Outline the different components of a web page.

              C.1.8 Outline the different components of a web page.


                A web page can contain a variety of components. The basics structure of a HTML document is:

                head

                This is not visible on the page itself, but contains important information about it in form of metadata.

                title

                The title goes inside the head and is usually displayed in the window top of the web browser.

                meta tags

                There are various types of meta tags, which can give search engines information about the page, but are also used for other purposes, such as to specify the charset used.

                body

                The main part of the page document. This is where all the (visible) content goes in.

                Some other typical components:

                Navigation bar

                Usually a collection of links that helps to navigate the website.

                Hyperlinks

                A hyperlink is a reference to another web page.

                Table Of Contents

                Might be contained in a sidebar and is used for navigation and orientation within the website.

                Banner

                Area at the top of a web page linking to other big topic areas.

                Sidebar

                Usually used for a table of contents or navigation bar.

                  C.1.4 – C.1.5 URL and Named Servers

                  C.1.5 Describe the purpose of a URL.


                  An URL defines a pathway to a specific resource. It allows to link different resources, which creates the basis for navigating the WWW (it is the links that make it a web). Normally a web page or file.

                  https://ibcomputerscience.xyz/c-1-4-c-1-5-url-and-named-servers/

                  1. http:// – the URL prefix, which specifies the protocol used to access the location
                  2. ibcomputerscience.xyz – the server name or IP address of the server
                  3. c-1-4-c-1-5-url-and-named-servers/ – the path to the directory or file

                      C.1.6 Describe how a domain name server functions.


                        Domain Name Servers (DNS) are the Internet's equivalent of a phone book. They maintain a directory of domain names and translate them to Internet Protocol (IP) addresses.

                        This is necessary because, although domain names are easy for people to remember, computers or machines, access websites based on IP addresses.

                        Information from all the domain name servers across the Internet are gathered together and housed at the Central Registry. Host companies and Internet Service Providers interact with the Central Registry on a regular schedule to get updated DNS information.

                        When you type in a web address, e.g., ibcomputerscience.xyz your Internet Service Provider views the DNS associated with the domain name, translates it into a machine friendly IP address ( and directs your Internet connection to the correct website.)

                        After you register a new domain name or when you update the DNS servers on your domain name, it usually takes about 12-36 hours for the domain name servers world-wide to be updated and able to access the information. This 36-hour period is referred to as propagation.

                        Find the IP address (32 bits )for this domain and covert the 4 bit parts into 4 Binary octets

                          Web Science Resources

                          More Resources to Questions


                          LinkDescriptionOther comments
                          linkInformation about the surface webContent on answers.com
                          linkInformation about the deep webContent on answers.com
                          linkThe invisible web
                          linkWhat Is the 'Invisible Web'?90% of all pages are not locatable by search engines
                          linkSearch engines and SpamPart of a research paper from Stanford University
                          linkPage rank explained by linksand law.comThere is a large amount of information related to the calculations that are beyond the scope of the course
                          linkGoogle's PageRank Explained
                          linkSearch engine optimisation tips
                          linkWhitehatworks.comAn opinion of how the Google Page Rank algorithm has been recalculated fro 2010-11
                          linkSearch engines, crawlers and pagerankThe Anatomy of a Large-Scale Hypertextual Web Search Engine
                          linkVideo - How search worksGoogle Video on Search engines - good starting point
                          LinkGoogle - how search worksGoogle's description of how search works
                          LinkInfographic from Google on SearchHow Search works Infographic

                          C3 Distributed approaches to the web (6 hours)

                          Computing methods such as Grid, Ubiquitous, P2P, Mobile. Open standards. Compression techniques.


                          LinkDescriptionOther comments
                          linkWhat is Grid Computing?An outline of Grid Computing
                          linkWhat is Ubiquitous ComputingAn introduction to Ubiquitous Computing (needs a better example)

                          C4 The evolving web (10 hours)

                          Evolution of the web, cloud computing, copyright / IP, democratisation of the web?


                          LinkDescriptionOther comments
                          linkDemocratisation of the webHas Web 2.0 led to an inequality in participation? - link to power laws
                          linkThe Web as a driver of democracyArticle by Eric Schmidt
                          linkHow Web 2.0 WorksPeople can determine the content and appearance of the wb
                          linkTypes of cloud computingA discussion of public and private cloud computing
                          linkEthernet switches won't support the cloud5 reasons why the traditional network may not migrate to being a cloud based one

                          HL extension - 15 hours


                          C5 Analysing the web (5 hours)


                          Web graphs


                          Note that these articles are for a level beyond the requirements of this topic, so teachers should look at the assessment statements in the Guide, the depth of coverage in the Specimen Paper and the time allocated for the teaching of the topic.


                          There is no need to study the mathematical equations in the algorithms.


                          An understanding of the bowtie structure of the web and the link to power laws is also required.


                          LinkDescriptionOther comments
                          webgraph lecture notes.pdfwebgraph lecture notes.pdf
                          Lecture notes used by Les Carr (Southampton University)Reproduced with permission of the author
                          Web as a graph.pdfWeb as a graph.pdf
                          The Web as a graphInformation on the bowtie structure
                          Overviewpowerpoint presentation - theory of web graphs, edges and vertices, bowtie structure, deep web, power laws
                          article
                          or PDF: Here
                          Graph structure of the web as a bowtie including information on the strongly connected components (SCC), relevance of power laws by Andrei Broder1, Ravi Kumar2, Farzin Maghoul1, Prabhakar Raghavan2, Sridhar Rajagopalan2, Raymie Stata3, Andrew Tomkins2, Janet Wiener3.As 1: AltaVista Company, San Mateo, CA.2: IBM Almaden Research Center, San Jose, CA.3: Compaq Systems Research Center, Palo Alto, CA.
                          linkGraph Theory and the web map
                          linkGoogle's PageRank Explained
                          linkPage rank explained by linksand law.comThere is a large amount of information related to the calculations that are beyond the scope of the course

                          C6 The intelligent web (10 hours)

                          The Semantic web, ontologies and folksonomies, ambient and collective intelligence.


                          LinkDescriptionOther comments
                          linkWeb ScienceAn article written by Professor Nigel Shadbolt, Professor Dame Wendy Hall FRS, Professor James Hendler and Professor William Dutton
                          linkCollective IntelligenceArticle from MIT based on harnessing collective intelligence to research climate change
                          linkDefinitions of Collective Information
                          linkCollective inteliigenceArticle based on the work of Thomas W Malone at MIT

                            5 Abstract Data

                            https://sites.fas.harvard.edu/~cscie119/lectures/coursepack.pdf

                            https://www.youtube.com/watch?v=h28AybaAjQ4

                            Quick Navigation

                            Stacks and Queues

                            Trees

                            Topic 5 - Abstract data structures- Student Booklet

                            Topic 5—Abstract data structures

                            By M Brooke

                            5.1 Abstract data structures (23 hours)

                            Thinking recursively

                            Key Terms

                            • Recursion
                            • Base Case

                            5.1.1 Identify a situation that requires the use of recursive thinking.

                            Factorial program

                            Factorial (http://www.wolframalpha.com/input/?i=factorial)

                            Let us consider factorials as a basis for investigating recursion. Factorials are represented by an exclamation mark "!". These can be seen below.

                            3! = 3 * 2 * 1 = 6

                            4! = 4 * 3 * 2 * 1 = 24

                            Factorial - iterative solution

                            In order to solve this we could use iteration to do this. Here is an iterative approach to calculating 4!. In this solution we simply loop four times multiplying by one less each time.

                            ANSWER =1
                            loop J from 1 to 4
                            ANSWER = ANSWER * J
                            J = J + 1
                            end loop

                            Factorial - Recursive solution

                            In order to solve this with a recursive method there are two elements that must be in place for a recursive algorithm to work. There has to be a base case at which the recursion will stop and there must be a recursive call that moves towards the base case. In the case of a factorial. The two elements are as follows.

                            Step 1 - Identify the recursive call

                            In this case it can be noted that 4! = 4 * 3! and 3! = 3* 2! etc. The general case can be expressed as:

                            n! = n * (n –1)!

                            Step 2 - Identify the base case

                            In this case the base case at which we want the iteration to stop is when n = = 1. This can be expressed as follows:

                            FACTORIAL (N) {
                            if (N=1) then
                            output 1
                            endif
                            else
                            output N * FACTORIAL (N-1)
                            end else
                            }

                            Towers of Hanoi

                            Towers of Hanoi (http://www.superkids.com/aweb/tools/logic/towers/)

                            The towers of Hanoi is a mathematical puzzle. It consists of three rods and a number of different sized disks that can be slid on and off the poles. The idea of the game is to move the entire stack of disks from one rod to another following these simple rules:

                            1. Only one disk can be moved at a time

                            2. Each move involves moving one disk from one stack to the top of another stack (or empty pole).

                            3. You can only move disks on top of a smaller disk.

                            There are several example of this game online for you to play out the scenario. [1] The more disks you have the more turns it will take and in fact there is legend that surround the game in which some monks in a monastery play the game with 64 golden disks. They can only move one disk a day and when the puzzle is complete that time will end.[2]

                            In order to write the recursive method we will ne to find the base case and the recursive call. It is a little more complex than the factorial example above but let us summarise the code. [3]


                            Towers of Hanoi - Recursive solution

                            Step 1 - Identify the recursive call

                            1. To move all but one disk to the spare peg. This can be done recursively.

                            2. Then move the bottom disk to the destination peg.

                            3. Move all the other disks onto the destination peg. (This can be done recursively)

                            Step 2 - Identify the base case

                            The base case is when the base disk has nothing.

                            So in pseudocode this would look like this:

                            HANOI ( N , BEGINNINGPEG, SPAREPEG, ENDPEG) {
                            if N=1 then
                            move BEGINNINGPEG to ENDPEG
                            end if
                            else
                            HANOI (N-1, BEGINNINGPEG, ENDPEG, SPAREPEG)
                            HANOI (1, BEGINNINGPEG, SPAREPEG, ENDPEG)
                            HANOI (N-1, SPAREPEG, BEGINNINGPEG, ENDPEG)
                            end else
                            }

                            Fibonnaci number

                            Fibonnaci number (http://en.wikipedia.org/wiki/Fibonacci_number)

                            In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence[4]:

                            ,1,2,3,5,8,13,21,34,55,89


                            Fibonnaci - Iterative solution

                            FibonacciIterative (N)

                            if (n == 0)

                            Output 0

                            end if

                            if (n == 1)

                            output 1

                            else

                            PREVPREV = 0;

                            PREV = 1;

                            RESULT = 0;

                            LOOP I from 2 to <=N

                            RESULT = PREV + PREVPREV

                            PREVPREV = PREV

                            PREV = RESULT

                            I = I+1

                            End loop

                            output RESULT

                            end else

                            Fibonnaci - Recursive solution.

                            Step 1 - Identify the recursive call

                            fibonacci(n) = fibonacci(n - 1) + fibonacci(n -2)

                            Step 2 - Identify the base case

                            fibonacci(0) = 0

                            fibonacci(1) = 1

                            So in pseudocode this would look like this:

                            fib(N) {
                            if (n = 0) then
                            output 0
                            endif
                            else if(n = 1)
                            output 1
                            end elseif
                            else
                            output fib(n – 1) + fib(n – 2)
                            end else
                            }

                            5.1.2 Identify recursive thinking in a specified problem solution.

                            Towers of Hanoi (http://www.cs.cmu.edu/~cburch/survey/recurse/hanoi.html)

                            5.1.3 Trace a recursive algorithm to express a solution to a problem.

                            Exercise 40 in Blue Pelican.

                            Key Terms

                            • Abstract Data Structure
                            • Array
                            • 2D array
                            • Stack
                            • Queue
                            • FIFO
                            • LIFO

                            Abstract data structures

                            5.1.4 Describe the characteristics of a two-dimensional array.

                            Consider the following array/matrix of numbers

                            31 42 33

                            21 35 79

                            22 86 69

                            75 30 15

                            In mathematics and in computer science the convention is to declare this array/matrix in terms of rows x columns. ie the above is a 4x3 array. This can be declared in JAVA as

                            int array [ ] [ ] = new int [4] [3]

                            5.1.5 Construct algorithms using two-dimensional arrays.

                            Many methods that operate on two dimensional arrays tend rely on nested “for” loops as you need to methodically go through all rows and columns. For example in order to print out each item above example array the following steps would need to be followed.

                            Note that two dimensional arrays are built from an “array of arrays” approach. In practice this means that each row is an object and in fact each row can be given a different length (though this is rarely used).

                            int array [ ] [ ] = new int [4] [3];

                            for (int r = 0, i<array.length, r++)

                            {

                            for (int c = 0, i<array[r].length, c++)

                            {

                            System.out.print(" " + array[r][c]);

                            {

                            System.out.println("");

                            }

                            5.1.6 Describe the characteristics and applications of a stack.

                            Think of a pile of plates or coins – you start off on the empty table top and add (push) the first coin onto the pile (stack). The next coin goes on top of the first and so on. When you remove (pop) a coin off the stack, the top one comes off first, then the next and so on until the stack is empty. In a computer program, data (rather than coins) are pushed onto and popped off stacks as needed. Each item of data is known as an element. Therefore a stack is a LIFO (Last In First Out) structure, because the last element pushed onto the stack is always the first element popped off. See http://www.ece.cmu.edu/~koopman/stack_computers/sec1_2.html#121 for more details of the overall concept of stacks.

                            Parameter storage and subprogram return addresses

                            When a program calls another program or function, the called function can also call another function. When the first program is called, the current program needs to be temporarily suspended and its return address and the values of the parameters it is using kept so they can be used when the called function returns.

                            To do this the return address and the contents of the parameters are placed in a stack in memory. As subsequent calls are made, the next return address and set of parameters are PUSHed onto the stack. When a function stops executing, the return address is POPped off the stack, and the program continues.

                            Interrupt handling

                            Interrupts work in the same way as above. When the CPU detects interrupt operations, the current state of the computer must be saved. The contents of variables and return addresses are placed on the stack. When the interrupt has been handled, the computer returns to where it was by POPping the data from the stack.

                            Evaluation of arithmetic expressions

                            To see why stacks are well suited to expression evaluation, consider how the following arithmetic expression would be computed:

                            X = (A + B) * (C + D)

                            First, A and B would be added together. Then, this intermediate result is pushed onto the expression evaluation stack. Next, C and D are added and the result is also pushed onto the expression evaluation stack. Finally, the top two stack elements (A+B and C+D) are multiplied and the result is stored in the variable X. The expression evaluation stack provides automatic management of intermediate results of expressions, and allows as many levels of precedence in the expression as there are available stack elements.

                            5.1.7 Construct algorithms using the access methods of a stack.

                            See 5.1.10

                            5.1.8 Describe the characteristics and applications of a queue.

                            The primary use of a queue is to ensure the service that is being queued for is given first to those that joined the queue first. This is known as a First In First Out structure (FIFO). Some examples of how queues are used in computer science are as follows:

                            Keyboard queue

                            The keyboard buffer into which characters are stored as they are pressed operates as a queue. The first letter typed is the first letter sent. Subsequent letters are added at the tail of the buffer.

                            Printer queues

                            Requests for printing are sent and the fist sent is the first printed. A printer queue stores the requests as they arrive.

                            Customer queue simulations

                            Check-outs and traffic lights are good examples of queues. The aim is to minimize the wait time on queues and to minimize the number of queues to keep the costs down. For more complex systems computer programs are written to simulate these queues and to predict the behavior of queues under certain conditions in order to maximize efficiency and cost.

                            5.1.9 Construct algorithms using the access methods of a queue.

                            See 5.1.10

                            5.1.10 Explain the use of arrays as static stacks and queues.

                            Arrays as stacks

                            Linear arrays provide a good way of implementing a stack. You already know that a linear array consists of a collection of elements, each one of which has an index number (starting at zero)

                            01234

                            To make it easier to visualise a stack we will represent the array vertically:

                            4
                            3
                            2
                            1
                            0

                            To get the array to act as a stack we need to have some way of keeping track of which element contains the topmost item. This can be easily achieved using an int variable (“top” in the diagrams). An empty stack could be represented by -1 (zero would be a stack with one item). Attempting to pop an item off an empty stack would result in a stack underflow. Similarly, attempting to push an item onto a full stack results in stack overflow.

                            Empty stack top ==-1
                            4
                            3
                            2
                            1
                            0
                            Threeitems pushed top ==2
                            4
                            3
                            2D
                            1E
                            0A
                            Full stack top ==4
                            4T
                            3F
                            2D
                            1E
                            0A
                            One itempopped top ==3
                            4T
                            3F
                            2D
                            1E
                            0A

                            Notice that when an item is popped off the stack, it is not actually deleted from the array element, it will simple be over-written by a new item being pushed onto the stack.

                            Thus to push an item onto the stack, the logical steps would be:

                            · Test for a full stack (don’t allow elements to be pushed onto a full stack)

                            If stack is not full..

                            · Get the value to be stored.

                            · Increment top

                            · store value in stack[top].

                            To pop an item off stack

                            · Test for an empty stack (don’t allow elements to be popped off an empty stack)

                            If stack is not empty..

                            · Retrieve value at stack[top]

                            · Decrement top

                            Arrays as linear queues

                            There are two ways of implementing a queue using an array – a linear queue and a circular queue.

                            Linear queues are slightly easier to visualize and code, but circular queues are more efficient as they avoid the need to move data long the array as items are dequeued from the head.

                            There are a number of possible strategies for implementing an array as a linear queue; the example shown is merely one such possibility.

                            The head of the queue is always element zero (which may be effectively empty if there are no items in the queue). The tail of the queue grows from zero as the queue is filled – thus a full queue is signaled by tail being the last element in the queue. In this example, that is element 4 – more generically the index of the last element in a Java array is always the size of the array -1. In a similar way to the stack top variable, we can store the position of the tail of the queue in an int variable. One way of flagging an empty queue would be to set the tail marker to -1 (zero would show that there was one item in the queue):

                            tailMarker == -1
                            01234

                            As items are enqueued, they are inserted into the array at tailMarker +1 and tailMarker is then updated to reflect the new position of the tail (or you could increment tailMarker first and then enqueue the data).

                            tailMarker == 2ADF
                            01234

                            Once tailMarker reaches the index of the last element in the array, the queue is full. Any further enqueuing operation would result in an overflow error.

                            tailMarker == 4ADFGT
                            01234

                            Items are always dequeued from array element zero (the head of the queue). Once an item has been dequeued, two things must happen. Firstly, all the other items in the queue must be shuffled “forward” by one element (i.e. moved into the element with the next lower element number). Secondly, tailMarker must be decremented to reflect the new position of the tail of the queue.

                            If decrementing tailMarker results in it having a value of -1, the queue is empty. Any further dequeueing operation will result in an underflow error.

                            Arrays as circular queues

                            Circular queues are more efficient as they avoid the need to shuffle the data along the array as items are dequeued from the head (the exception to this might be when promoting an item already in the queue to the head). The coding is a little fiddly, but not difficult once you get the logical steps clear – which after all is the secret of all programming…

                            To visualise an array as a circular queue it might be helpful to imagine an array bent round into a circle:

                            To operate an array as a circular queue (queue[] might be a good identifier) we will need to have two int variables as markers, in this example we will name them head and tail.

                            Operations on a circular queue

                            Below is a summary of the methods needed to operate a circular queue. It is assumed that a char queue of order size has been instantiated (i.e. char queue = new char[size];). The terms inputChar and outputChar will be used to refer to items queued and dequeued.

                            The methods are presented as pseudocode to clarify the logical steps needed.

                            New and empty queues:

                            Void method to initialise a queue as “empty” (applied to new queues or queues where the last item has just been dequeued). A good strategy is to flag an empty queue by setting head and tail to -1.

                            initialiseQueue: head gets -1 ; tail gets -1;

                            Boolean method that returns true if the queue is empty

                            isEmptyQueue: If head == -1 and tail == -1 then return true

                            else return false;

                            Enqueueing and dequeueing items:

                            A new queue should be initialized by setting head and tail to -1.

                            Testing that head and tail are equal to -1 is also a good way of verifying that an existing queue is empty.

                            The first item enqueued should go into element 0. This item becomes both the head and the tail of the queue.

                            0Aheadtail
                            1
                            2
                            3
                            4
                            5
                            6
                            7
                            8
                            9

                            We can then carry on enqueueing items until the queue is full.

                            If the queue is full, we can’t enqueue any more items.

                            Therefore we need a method to test for a full queue:

                            If head == 0 and tail == size-1 then return true;

                            0Ahead
                            1B
                            2C
                            3D
                            4E
                            5F
                            6G
                            7H
                            8I
                            9Jtail

                            As items are dequeued from the head, the head marker is incremented to reflect this.

                            The diagram shows the queue with three items dequeued (A, B , C).

                            We now have 3 elements available for use...

                            0A
                            1B
                            2C
                            3Dhead
                            4E
                            5F
                            6G
                            7H
                            8I
                            9Jtail

                            ...so tail needs to “wrap around” to store the next item at queue[0]

                            (remember that this is a circular queue)

                            If tail == size-1 and queue is not full then tail gets 0;

                            queue[tail] gets inputChar;

                            0Ktail
                            1B
                            2C
                            3Dhead
                            4E
                            5F
                            6G
                            7H
                            8I
                            9J

                            Tail then increments as before, until we get to a full queue again.

                            When this happens, tail == head-1 so we need to add that condition to our test for a full queue.

                            0K
                            1L
                            2Mtail
                            3Dhead
                            4E
                            5F
                            6G
                            7H
                            8I
                            9J

                            One other particular condition that needs to be catered for is what happens to the queue when the last remaining item is dequeued.

                            If the queue contains one item only, both the head and the tail of the queue will be referencing the same element of the array (it could be any element in the array).

                            Once the last item has been dequeued, the queue is empty and should be initialized by setting the head and tail reference variables to -1

                            0K
                            1B
                            2C
                            3Dtail and head
                            4E
                            5F
                            6G
                            7H
                            8I
                            9J

                            Summary:

                            To operate a circular queue, in addition to methods to enqueue and dequeue items you will also need to have Boolean methods to test for a full queue, an empty queue and to detect the last item in the queue.

                            Linked lists

                            Linked lists will be examined at the level of diagrams and descriptions. Students are not expected to construct linked list algorithms using pseudocode.

                            5.1.11 Describe the features and characteristics of a dynamic data structure.

                            Dynamic data structures are able to increase and decrease in size as the need arises. This is done by allocating and deallocating memory space. The table below illustrates the features of a dynamic data structure comparing it with a static data structure such as an array.

                            Dynamic data structureStatic data structure
                            Memory is allocated to the data structure dynamically as the program runs.Memory size is fixed and set at the time of compiling.
                            Disadvantage. There may be overflow or underflow during runtime if allocations are exceeded.Advantage.Memory size is fixed and so there will be no problems during run time with memory allocations
                            Advantage. Makes the most efficient use of memory as it is using only as much as it needsDisadvantage. As memory size is fixed there may be a lot of wasted memory space during the running of the program.
                            Disadvantage. Harder to program as the program needs to keep track of data size and locations during the running of the programAdvantage. Easier to program as there is no need to check on memory size or make use of algorithms that require links to new data.

                            5.1.12 Describe how linked lists operate logically.

                            A list is a data structure that allows data items to be stored. They can be of a fixed size such as arrays that are static or can be of a dynamic size. Linked lists are an example of a dynamic list data structure. In a linked list each item of data points to the next item of data. This is best illustrated diagrammatically. lol

                            Singly Linked list basics

                            A number of pointers are required in the singly linked list. The start or head pointer points to the first element in the list. The last node has a null pointer which is an empty pointer. Each other node has a pointer pointing to the next node in the list. In order to access the list we need to always start at the head. To move through the list we follow the pointers to the end until we encounter the null pointer. In a singly linked list we can only move one way through the list.

                            Typical operations on a list are as follows:

                            Add/Insert node

                            Delete/remove node

                            Identify head

                            Identify next

                            Locate/search node

                            Test for empty

                            Add/Insert node

                            Imagine the example where we want to add the following of names into an alphabetically ordered list.

                            Rogério

                            William

                            Tomás

                            Miguel

                            António

                            The steps below highlight where the node needs to be inserted and gives a decription of the rearrangements of pointers that need to take place in the programming.

                            In order to find the correct position for each node the list is accessed at the head and the data compared to the node if necessary move to the next node and compare again. Repeat this until the correct position for insertion is found or until the end of the list is reached.

                            1. List is empty Rogério is inserted at the head. Head points to Rogério and Rogério points to null.

                            2. William is alphabetically after Rogério so is appended to the end of the list. .Rogério points to William and William points to null

                            3. Tomás is inserted between Rogério and William. Rogério points to Tomas and Tomas points to William .

                            4. António is inserted at the head of the list. Head points to António and António points to Rogério.

                            These steps can be represented by a flow diagram:

                            Deleting a node

                            The methods for deleting a node will vary depending on where that node is in a list.

                            Case 1: Deleting head node

                            Move to Head

                            Adjust Head pointer to point to next node

                            Case 2: The node to be removed is an intermediate one

                            Move to node before node to be deleted.

                            Adjust Current node pointer to point to next.next node

                            Case 3: It is the last node to be removed

                            Move to node before the last one.

                            Adjust Current node to point to null

                            5.1.13 Sketch linked lists (single, double and circular).

                            Trees

                            Binary trees will be examined at the level of diagrams and descriptions. Students are not expected to construct tree algorithms using pseudocode. Tracing and constructing algorithms are not expected.

                            5.1.14 Describe how trees operate logically (both binary and non-binary).

                            Tree structures are very common in computing, the most familiar perhaps being the organisation of files and folders (or directories if you prefer) on a storage device.

                            The diagram shows a simplified folder structure – each folder contains one sub-folder and three files, except the lowest level folder, which only contains files. If we wanted to carry out an operation on all the files in all the folders (e.g. setting them all to read-only), the most efficient approach would be to use a recursive technique.

                            The following is a Java-ish pseudocode of the recursive algorithm that might be used. It assumes the existence of a Boolean method hasSubFolder and a method called setFiles which will set the attributes of all the files in a given folder to ro (read only) mode:

                            Root folder

                            public void setAttrib (Folder thisFolder)

                            {

                            if(hasSubFolder(thisFolder))

                            {

                            setAttrib(thisFolder.subFolder);

                            }

                            setFiles(thisFolder,ro);

                            }

                            • The method would initially be called with the root (top level) folder passed as a parameter. Since hasSubFolder would evaluate to true, the recursive call on line 5 to setAttrib will execute, passing the subfolder as a parameter. The first call will be pushed onto a stack.
                            • Since the second level folder also has a sub-folder, line 5 will execute again and make another call to setAttrib, passing the third level folder as a parameter. The second call will be pushed onto a stack.
                            • The third level folder has no subfolder, so this call will jump to line 7, set the attributes of all files in the third level folder to read-only and then complete.
                            • The second call will be popped of the stack and the algorithm continued from where it was interrupted by the recursive call (at the end of line 5). Line 7 will execute and this call will complete.
                            • Finally, the original call will be popped off the stack and resumed, executing line 7 and completing.
                            • So we now have all the files in all the folders processed, all calls completed and an empty stack.

                            In practice, folder tree structures are inevitably more complex than the very formalised example given here. A folder may have one or more subfolders or none; folders may have files or be empty. However, the recursive principles remain the same.

                            For the purposes of the Computer Science course, you need to be able to trace and construct recursive algorithms related to one particular tree structure, the Binary Tree.

                            Binary trees are a particular type of tree structure where every node in the tree has exactly two branches (hence binary). A representation of a single binary tree node is shown below. However large they are, binary trees are constructed simply by repeating this node:

                            Just like a doubly linked list node, a binary tree node consists of some data (or a reference to an object that contains data – more on that later) and two references to other nodes. These references are to the “left sub-tree” and “right sub-tree” respectively:

                            The best way to understand the anatomy of a binary tree is to build one, so the following section will briefly run through the logical process of constructing a binary tree of nodes that simply contain an integer as their data member.

                            Like all dynamic date structures, the first thing we need is an externally accessible reference. In trees, this is a reference to the tree’s root. Intially, treeRoot will reference NULL (no tree).

                            Adding the first node to the tree (known as the root node):

                            Binary trees use a simple rule – “less than” goes to the left, “more than” goes to the right. So if we add another node with the data value of 2, it will become the left sub-tree of 4.

                            Now add a node with the value of 3. This is less than 4, so we traverse left, but more than 2, so we traverse right...

                            Repeating that simple rule, < goes left, > goes right, if we then add 6, 1, 5, 7 in that order, we end up with a complete tree:

                            5.1.15 Define the terms: parent, left-child, right-child, subtree, root and leaf.

                            The vocabulary of binary trees borrows terminology from both natural trees (those big things with leaves and branches etc.) and family trees (the organisation of parents, children etc.). In the sample tree below, the node containing the value 4 is the Root of the whole tree.

                            If we take the node highlighted in red (containing the value 2), we can explore the rest of the vocabulary associated with trees.

                            • Node 2 is the child node of 4, but the parent node of 1 and 3.
                            • 2 is in 4’s left subtree.
                            • It is the root node of two subtrees, a left subtree containing 1 and a right subtree containing 3.
                            • It is a sibling node to 6 (sibling nodes are at the same level in the tree).
                            • 2’s two child nodes (1 and 3) are both leaf nodes as they have no subtrees.

                            Removing nodes from a tree can be a little more complex and is covered well here:

                            http://www.algolist.net/Data_structures/Binary_search_tree/Removal

                            5.1.16 State the result of inorder, postorder and preorder tree traversal.

                            Consider the following expression tree:

                            The expression can be seen as follows:

                            In order traversal would result in infix. Rule: A node is visited in-between its left subtree and right subtree (Left visited first).

                            a/b+c*d

                            Preorder traversal would result in prefix. Rule: A node is visited before its descendants.

                            +/ab*cd

                            Postorder traversal would result in postfix. Rule: A node is visited after its descendants.

                            ab/cd*+

                            5.1.17 Sketch binary trees. structure.

                            Binary tree as a decision tree

                            Here is a binary decision tree for fault diagnosis for a washing machine.

                            The non-leaf nodes are the questions and the leaf nodes are the advice - even if this is "no further advice is available".

                            Here is a binary decision tree for interpretation of an aerial photograph.

                            Tree as a directory structure

                            Trees can also be used to store folders and subfolders. This is common to all operating systems. Here is an example of the UNIX directory structure

                            All the files are grouped together in the directory structure. The file-system is arranged in a hierarchical structure, like an inverted tree. The top of the hierarchy is traditionally called root (written as a slash / )

                            Applications

                            5.1.18 Define the term dynamic data

                            Dynamic data is data that changes when further updates to the data become available.

                            5.1.19 Compare the use of static and dynamic data structures.

                            Dynamic data structureStatic data structure
                            Memory is allocated to the data structure dynamically as the program runs.Memory size is fixed and set at the time of compiling.
                            Disadvantage. There may be overflow or underflow during runtime if allocations are exceeded.Advantage.Memory size is fixed and so there will be no problems during run time with memory allocations
                            Advantage. Makes the most efficient use of memory as it is using only as much as it needsDisadvantage. As memory size is fixed there may be a lot of wasted memory space during the running of the program.
                            Disadvantage. Harder to program as the program needs to keep track of data size and locations during the running of the programAdvantage. Easier to program as there is no need to check on memory size or make use of algorithms that require links to new data.

                            5.1.20 Suggest a suitable structure for a given situation.

                            There are many situations where the size of the structure is not known beforehand. These cases lend themselves to dynamic data structures. An example of this is the programming of a printer spooler where the number of print jobs will vary and is not known beforehand.

                            Other situations may occur where the size of the data structure can be determined beforehand in this case a static data structure would be used.

                            Now test yourself

                            https://quizlet.com/122628585/test/embed

                            Michael Brooke emjbe.net

                            Published by

                            Google Drive

                            Report Abuse

                            –Updated automatically every 5 minutes

                            2.1​ Computer org- Binary 2.1.9 – 2.1.13

                            2.1​ Computer org- Binary 2.1.9 - 2.1.13

                            Use this resource click here

                            Computers are machines that do stuff with information. They let you view, listen, create, and edit information in documents, images, videos, sound, spreadsheets and databases. They let you play games in simulated worlds that don’t really exist except as information inside the computer’s memory and displayed on the screen. They let you compute and calculate with numerical information; they let you send and receive information over networks. Fundamental to all of this is that the computer has to represent that information in some way inside the computer’s memory, as well as storing it on disk or sending it over a network.

                            To make computers easier to build and keep them reliable, everything is represented using just two values. You may have seen these two values represented as 0 and 1, but on a computer they are represented by anything that can be in two states. For example, in memory a low or high voltage is used to store each 0 or 1. On a magnetic disk it's stored with magnetism (whether a tiny spot on the disk is magnetised north or south).

                            The idea that everything stored and transmitted in our digital world is stored using just two values might seem somewhat fantastic, but here's an exercise that will give you a little experience using just black and white cards to represent numbers. In the following interactive, click on the last card (on the right) to reveal that it has one dot on it. Now click on the previous card, which should have two dots on it. Before clicking on the next one, how many dots do you predict it will have? Carry on clicking on each card moving left, trying to guess how many dots each has.

                            Click to load Binary Cards

                            The challenge for you now is to find a way to have exactly 22 dots showing (the answer is in the spoiler below). Now try making up other numbers of dots, such as 11, 29 and 19. Is there any number that can't be represented? To test this, try counting up from 0.

                            Spoiler: Solution to card puzzles

                            You should have found that any number from 0 to 31 can be represented with 5 cards. Each of the numbers could be communicated using just two words: black and white. For example, 22 dots is "white, black, white, white, black". Or you could decode "black, black, white, white, white" to the number 7. This is the basis of data representation - anything that can have two different states can represent anything on a digital device.

                            When we write what is stored in a computer on paper, we normally use “0” for one of the states, and “1” for the other state. For example, a piece of computer memory could have the following voltages:

                            low low high low high high high high low high low low
                            

                            We could allocate “0” to “low”, and “1” to “high” and write this sequence down as:

                            0 0 1 0 1 1 1 1 0 1 0 0
                            

                            While this notation is used extensively, and you may often hear the data being referred to as being “0’s and 1’s”, it is important to remember that a computer does not store 0’s and 1’s; it has no way of doing this. They are just using physical mechanisms such as high and low voltage, north or south polarity, and light or dark materials.

                            Jargon Buster Bits

                            Every file you save, every picture you make, every download, every digital recording, every web page is just a whole lot of bits. These binary digits are what make digital technology digital! And the nature of these digits unlock a powerful world of storing and sharing a wealth of information and entertainment.

                            Computer scientists don't spend a lot of time reading bits themselves, but knowing how they are stored is really important because it affects the amount of space that data will use, the amount of time it takes to send the data to a friend (as data that takes more space takes longer to send!) and the quality of what is being stored. You may have come across things like "24-bit colour", "128-bit encryption", "32-bit IPv4 addresses" or "8-bit ASCII". Understanding what the bits are doing enables you to work out how much space will be required to get high-quality colour, hard-to-crack secret codes, a unique ID for every device in the world, or text that uses more characters than the usual English alphabet.

                            This chapter is about some of the different methods that computers use to code different kinds of information in patterns of these bits, and how this affects the cost and quality of what we do on the computer, or even if something is feasible at all.

                            C.2.1 Define the term search engine

                            C.2.1 Define the term search engine


                            A search engine is a  program that allows a user to search for information normally on the web.

                                C.2.11 Discuss the use of white hat and black hat search engine optimisation

                                C.2.11 Discuss the use of white hat and black hat search engine optimisation


                                  BLACK HAT

                                  Definition: Black hat SEO is a technique, in simple words, to get the top positions or higher rankings in the major search engines like Google, Yahoo and Bing that breaks the rule and regulations of search engine’s guidelines. See example of guidelines for google click here.

                                  Keyword stuffing

                                  This worked at one time, now you still need the key words / search terms in your title and page content you need to ensure that you do not overuse the keywords / phrases as that will trip a search engine filter.   

                                  PBN

                                  Google ( currently ) favors older sites, sites with history. In this approach you buy an expired domain with good metrics , build it up and add links to your sites giving a boost in ranking.  This works, but it is costly to set set up and you need to use alias etc.

                                  Paid For Links

                                  Similar to PBN the aim is to get good quality links from high authority sites. Have a look at Fiverr where yo can buy such links. This is difficult for google to detect and it is also very effective.  

                                  Syndicated / Copied Content

                                  Rather than creating good quality content use content copied from other sites, the content may be  changed using automated techniques.   Google is much better at detecting please refer to PANDA Update

                                  Over Use of Key Words in Anchor Text

                                  The anchor text tells google what your site is about example "fleet insurance" , but if you overuse or your backlinks look unnatural you will be penalized please refer to Penguin. Before Penguin this was very effective in getting ranked 

                                   Web 2.0 Links

                                  Build a web site on Tumbler for example for the sole purpose of sending links to your money site

                                  WHITE HAT

                                  Guest Blogging

                                  The process of writing a blog post for someone else’s blog is called guest blogging

                                  Link Baiting

                                  Create an amazing article info graphic that other sites may use, if you include a link to your site in the article you get more back inks as a result ( natural acquisition of back links as opposed to paid )

                                  Quality Content

                                  Search engines evaluate the content of a web page, thus a web page might get higher ranking with more information. This will make it more valuable on the index and other web pages might link to your web page if it has a high standard in content.

                                  Site optimization Design 

                                  Good menu navigation. Proper use of title tags and header tags, adding images with keyword alt tags, interlinking again with keyword anchor text. Create a, sitemap to get site crawled plus inform the spiders how often to visit site. 

                                  A good User Experience (UX)

                                  This a broad term and overlaps some other areas mentioned example page load speed. The purpose to ensure that if a use click to go to your site they stay without clicking back to the serps  immediately. Google is happy as this a quality signal as its main purpose to provide the user with relevant results.    

                                  Page Site Load Speed

                                  Fast loading pages gives the user a good experience aim for under 3 seconds

                                  Freshness

                                  Provide fresh content on a regular basis.

                                  Google is continually ( as are other search engines ) fighting black hat techniques that web masters employ to rank high in the serps. Investigate these 2 major algorithm updates Panda and Penguin. A good example of a current black hat practice is the use of PBN's.

                                  Students to investigate PBN's Panda and Penguin Quick discussion on these and what Google was targeting and how PBN's are currently being used effectively to rank sites higher ( if caught you will wake up one morning and you web site(s) have been de-indexed from Google.

                                    1 2 3