Courses/Computer Science/CPSC 203/CPSC 203 Template/Lecture Template/Lecture 3

Required Reading

"Behind the Scenes: The Internet: How it Works". Pg. 112-139. The Prentice Hall Custom Program for CIS (white coloured bound soft-cover).

Introduction

We are building up a critical vocabulary that allows us to explore aspects of problem-solving.

In the first two lectures we began introducing a small set of terms that help us frame our discussion of problem solving:

• Algorithm (a mechanical process for solving a problem in a step-by-step manner)
• Heuristic (a rule of thumb for solving a problem)
• Hypothesis (a provisional idea whose merit requires evaluation)
• Error (the difference between an expected value, and the value actually observed).

In this lecture we introduce three more terms that are common in problem solving, and usually associated with "more complex" problems:

• System
• Design
• Evolution

The plan for this lecture is:

• Introduce our new vocabulary for more complex problems.
• Introduce Polya's 4 High Level Principles for problem solving (and a couple of suggestions on each point)
• Go through a problem solving exercise focussed on "Designing A Solution" to a realistic complex problem (Designing an alternate Internet Tier Structure that could be resistant to attacks).
• Evaluate some of our solutions.

At the end of this lecture you should:

• have an initial understanding of the role of System, Design, Evolution in terms of complex (real world)problems .
• Understand Polya's 4 High Level Principles for problem solving
• Have attempted (in a small group) to design your own solution to a complex problem.

Glossary

Internet Tier Structure Glossary

• Routers -- devices that send data packets between networks
• Internet Backbone -- the several dozen Tier 1 Internet Service Providers
• T lines -- high speed fiber-optic lines used by Internet Service Providers
• ISP -- Internet Service Providers
• Network Access Points -- Points of connection between ISPs that contain groups of routers designed to quickly move large amounts of data

In addition to today's glossary, familiarize yourself with the "jargon" in the required reading above. Eg. terms such as,

• "packet-switching",
• "points of presence",
• "TCP/IP", "DNS/Servers",
• "FTP",
• The main Internet protocols (Figure 7, page 119),
• "HTTP, HTML, and Other Web jargon".

Concepts

System, Design, Evolution

These three terms often come up in the discussion of complex problems. In a nutshell, complex problems are often about Systems, and we attempt to Design a solution, but the systems themselves, due to their complexity undergo a process of Evolution, which leads to new problems.

Consider, for example our last discussion about how the Internet was originally designed to protect information in the event of a nuclear holocoust, and subsequently evolved into the complex Scale-Free system we observe today, which both provides new opportunities, and a host of new problems.

System -- "Anything we choose to regard (a) as a whole and (b) as comprising a set of related components" -- Oxford Disctionary of Computing. In general, a system is a group of elements that work together to accomplish some goal or objective. For example, in a computer system, the elements could be logic circuits and the goal could be computation.

Design -- "Design stripped to its esssnce can be defined as the human capacity to share and make our environment in ways without precedent in nature, to serve our needs and give meaning to our lives" -- John Heskett, in "Toothpicks and Logos: Design in Everyday Life". Design could be said to be the act of trying to define a harmonious assemblage of the components of a system, so that the whole works as it should.

Evolution is the tendency of complex systems to undergo irreversible change with time. Thus we speak of "cosmological evolution", for the irreversible large scale patterns of change in physical systems; "biological evolution" for the irreversible patterns of change in biological systems; "technological evolution" for the patterns of change caused by technologies we initially designed, which subsequently continued to evolve.

Polya's 4 Principles for Problem Solving

From, "How to Solve It", By George Polya. 1957.

• First, Understand The Problem
  • What is Known, Unknown
  • Draw a Figure

• Second, Devise a plan.
  • Find the connection between the data and the unknown (i.e. what is missing).
  • Have you seen this problem before? Is there a related problem you know how to solve?

• Third, Carry out the plan.
  • Check each step. Is it correct? Can you "prove" it is correct?

• Fourth, Review/Extend the plan.
  • Is this the best solution?
• Could you solve this differently? More simply?

Recap Scale Free Network Core Ideas

Core ideas from last lecture recapped on overhead.

Internet Tier Structure

While last lecture we studied the structure the Internet has "grown into", a scale free network, the Internet also has some basic design rules. Recall, the original design of the Arpnet was to survive a nuclear war, and this affected design considerations.

• Tier One Internet Service Providers are required to connect to all other Tier One Internet Service Providers.
  • They form the Internet "Backbone", and include many of the original Arpnet sites.
• Tier Two Internet Service Providers are required to connect to at least one Tier One Internet Service Provider
  • These constitute large organizations usually with regional or national focus.
• Tier 3 Internet Service Providers must connect to at least one Tier 2 Internet Service Provider.
• "Tier 4" -- the rest of us who connect to the Internet via a Tier 3 service provider.

Internet Tier Structure Exercise

(30 minutes design; 15 minutes presentation)

The purpose of this exercise is:

• To introduce you to working in teams (as per the Term Project)
• To introduce you to a time-limited exercise (as in the Time boxed assignments)
• To have you practice "sketching" a prospective solution to a problem (such a sketch might be part of a mid-term or final), and justifying it.

Class is arranged into groups (3 persons/group) for this exercise. Use 1 page per group.

1. Appoint 1 person in your group to be the "Sketcher". Everybody contributes to ideas.
2. Problem 1: What happens if the Internet Backbone were to 'be taken out' -- could the Internet still function? Give reasons for your answer. (5 minutes)
3. Problem 2: Can you design an alternate Tier structure for the Internet that you think would be more stable. Sketch this answer. (25 minutes)
4. For your alternate Internet design, list: its strong points, its weak points.
5. I'll ask for 3 (random) groups to volunteer to discuss their design.
6. Hand Designs up to front. I'll post a half-dozen of the most interesting designs to Blackboard.

Summary

We introduced three new terms, that particularly apply to complex systems: System, Design, and Evolution.

• • We Looked at the Tier Structure of the Internet, from it's original design.
  • We participated in an exercise to design an alternate Tier model of the Internet, and used Polya's 4 Principles as a guide in the Design.

Text Readings

see "Required Reading" at top of page.

Questions

• /Lecture 3 Questions