Brief Recap of Lab 5

Brief recap of Lab 5

Review of HTML

· HTML tags come in pairs

· The page consists of two sections: HEAD and BODY. The overall template is:

· < HTML >

· < HEAD >

· < TITLE >

· title goes here, will display in title bar

· < /TITLE >

· < /HEAD >

· < BODY >

· the text for the actual web page goes here

· < /BODY >

· < /HTML >

· "good style" to include a title. It is used to refer to the page, for example in a list of bookmarks (favorites) or in the results of a search engine

· , , , , tags (not good style to underline on Web pages because it can be confused with links).

· ordered and unordered lists < OL & gt; and < UL >

· < center > , headings

Preparation for Lab

The lab will cover adding links, color and images to Web pages.

Links

The < A > tag is used to specify a hyperlink. There are two things that you must specify in order to create a link:

· the words that anchor the link, i.e., the words on the web page that should come out underlined in blue

· the location of the file that should be jumped to when the link is clicked.

The < A > tag is used to bracket the words that should come out underlined in blue. The information about the file being linked to is embedded inside the < A > tag .

Give an example:

< A HREF= "http://www.yahoo.com" > link to Yahoo! < /A >

produces

link to Yahoo!

Point out that the http:// is necessary.
Common errors - leaving out or misspelling the URL; leaving out the text for the anchor.

Adding Color to Web pages

There are 5 color elements of a Web page: the background color, the color of the text, and three colors for links: the unvisited link color (the default color is blue), the visited link color (been there, done that) (the default color is purple), and the active link color (sometimes visible while you hold down the mouse button before you release)(default color is red).

Any or all of these can be changed in the BODY tag.
Example: < BODY BGCOLOR="yellow" TEXT="red" LINK="green" VLINK="pink" ALINK="white" >

Images

In order to include a picture on a Web page, you first have to have a file containing a picture. The picture should be in .GIF or .JPG (or .JPEG) format only. Other formats will not work with all browsers. (AOL supports .BMP and .ART formats, but they will NOT work with all other browsers. Just because it works in AOL doesn't mean it's OK to use.) There are two ways of including pictures on a web page:

as a background picture - like wallpaper. The picture will be tiled, like laying tile on a floor. Works best with patterns, doesn't work well with well-defined pictures.
Use < BODY BACKGROUND="picture.gif" >

Do not use both BACKGROUND and BGCOLOR - one is like wallpaper, the other is like painting with a flat color - you either wallpaper or paint, you don't paint over wallpaper!

as an inline image. Use < IMG SRC="filename.gif" >

Lecture 5: Algorithmic Thinking

Program - series of instructions that specify exactly what the computer is supposed to do.

In order to use a program to solve a problem, we go through a series of steps, (software life-cycle).

1. Determine how to solve the problem and come up with an algorithm.

2. Formulate the algorithm in a way that a computer can carry out the steps.

o very specific, detailed instructions

o instructions specified in a manner that computer can understand, not in English

Inside a computer, everything is binary. In the computer's machine language different patterns of binary bits correspond to different instructions. It is tedious to program like that. We use high-level programming languages which use a syntax which is closer to English. The programming languages are not English - they have very rigid rules of syntax, but it is still easier to use than to use machine language.

3. use compiler to "translate" the program written in the high-level programming language to machine language.

Possibly, the compiler will find syntax errors - mistakes in the way the program was formulated - and will not be able to complete the translation process. Fix the errors and repeat the process until the program is compiled successfully.

4. Run (or execute) the program. At this point, we may find other errors and we may have to correct the program again.

5. Debug the program. Test it and see if there are any mistakes. Fix errors and test again.

6. Maintenance.

Algorithm: step by step sequence of instructions for carrying out some task.

Programming can be viewed as the process of designing and implementing algorithms that a computer can carry out. (Algorithms predate computers, e.g. Euclid's algorithm for finding greatest common factor).

A recipe for baking chocolate chip cookies is an algorithm. By following the instructions carefully anyone familiar with cooking should be able to bake it.

Giving directions to your house is an algorithm.

In order for an algorithm to be effective it must be stated in a manner that its intended executor can understand. Expensive cookbook, will probably assume you are experienced in the kitchen.

Instructions on the side of macaroni-and-cheese do not assume much expertise (figure 8.1).

Computers are more demanding with algorithms than humans. Computers require that the steps in an algorithm be stated in an extremely precise form. Any simple mistakes such as spelling in a program or forgetting a comma can confuse the computer and make it unable to execute the program.

Computers are not people. When we speak to people, we can assume that they understand certain basic facts of everyday life. For example, we can tell a person to go and buy a loaf of bread. But if we were instructing a robot, we might have to be much more specific:

If someone has bought bread at this store before the following instructions would be enough:

1. Buy a loaf of bread from the store to serve with a meal

If not the person in mid-operation would become frustrated by the following omissions: What are the directions? How much is it?

Revised instructions:

1. Tell the person how much bread costs

2. Check that they have enough money

3. If not get enough money for them to pay for it

4. Give them store address

5. Send them to purchase the bread

Example of errors: If the instruction giver wrongly assumed that the buyer is familiar with the area the person might become lost getting to the address.
In that case Step 4 above would have to be expanded as follows:

a. Make a right turn at the first corner

b. Make a left after 2 lights….

If the person if from Canada and was sent off here is another possible bug:

Error: Used Canadian currency which was not accepted and the meal did not have bread on time.

A computer is like the person who knows nothing until being told.

Two examples of bugs:

1. A similar assumption to the currency assumption - The Mars Climate Orbiter was lost in space in 1999. In the calculation of its route some programmers used the metric system (centimeter, kilometer, etc) while others used English units e.g., inches, feet and pounds).

(Another example is a patriot missile failing to intercept a scud fired at US troops in 1991. The following is from an article: “Specifically, the time in tenths of second as measured by the system's internal clock was multiplied by 1/10 to produce the time in seconds.” )

Example of an algorithm: finding the oldest person in a room full of people.

1. line up all people along one wall

2. ask the first person to state his or her name and birthday and write it down

3. for each successive person in line:

a. ask his or her name and birthday

b. if the state birthday is earlier than the date written on the paper, cross out the old information and write down the name and birthday of this person

4. When you reached the end of the line, the name and birthday of the oldest person will be written on the paper.

(book)

Another way: Algorithm 2:

1. Line up all the people along one wall.

2. As long as there is more than one person in the line, repeatedly:

a. Have the people pair up (1st and 2nd in line, 3rd and 4th in line, and son on). If there are an odd number of people, the last person will remain without a partner.

b. Ask each pair of people to compare their birthdays

c. Request that the younger of the two leave the line.

3. When there is only one person left in line, that person is the oldest.

Algorithm 2 is more complex than 1, but same end result.

First time each pair compare and younger leave – the number of people in the line is cut roughly in half. Then the older members due this and reduce the line again. Eventually there will be one person left.

Analysis:

Which algorithm is better? If you’re concerned about time, you’ll want to analyze it.

First algorithm requires asking each person for his/her birthday and comparing it to the birthday on the paper. So the amount of time will be proportional to the number of people. If 100 people and it takes 5 seconds to compare birthdays, then talgorithm 1 will require 5 * 100 = 500 seconds. If 200 people, then it will require 5 * 200 = 1000 seconds.

If double the people, time doubles.

Algorithm 2 allows you to perform multiple comparisons simultaneously, which saves time. While the first pair compares their age, all other pairs are doing the same. So you can eliminate half the people in the line in the time it takes to perform one comparison. Total time involved in executing algorithm 2 is proportional the number of rounds needed to shrink the line down to one person.

Figure 8.4 if 8 people – we reduce to the one oldest in 3 rounds

8 -> 4 -> 2 -> 1

If twice as many people only 4 rounds.

16 -> 8 -> 4 -> 2 -> 1

(logarithm captures this halving effect: ceiling of log2N)

If there are 100 people in 5 seconds to compare birtdays(before 500) 5 * log210 = 5 * 7 = 35 seconds. 200 would be 5 * 8 = 40 seconds. If double number of people, time required to execute algorithm 2 will increase by the duration off one additional comparison.

Similar to searching issue – if large database with records etc, and want to search through it. Sequential Search: examine each item until desired item is found.

Binary search: if organized ex. phone book – alphabetized – inspect – middle position, if what looking for done, if not, if the middle entry comes after the item you are seeking (joan smith comes after dave reed), then you know that the desired item appears in the first half of the list. If the middle entry comes before the desired item (Adam Miller before Dave Reed) then the desired item must appear in the second half of the list. Once you have determined the half in which the item must appear, you can search that half via the same technique. Each check cuts the list in half.

core51_5