Tuesday, February 25, 2014
Sunday, February 16, 2014
Chapter 8 Outline
8.1 What is Abstract Data Type?
·
Abstract data
type (ADT):
o ADT is a
container whose properties (data & operations) are specified independently
of any particular implementation.
o We know their properties and operations and we
understand which types of values they can contain, but we have no information
about their internal structure or implementation.
(u know what it Is, what it means, but don’t need to see the implementation of it [no need to know how]) Example:
(u know what it Is, what it means, but don’t need to see the implementation of it [no need to know how]) Example:
§ Gmail (object)
§ Sign In/Create account (Operations)
§ User no need to look at the details, just do it.
o The basic idea is that the implementation of these
operations is written ONCE in the program, and any other part of the program
that needs to perform an operation on the ADT can do so by calling the
appropriate function.
o The goal in design is to reduce complexity thru
abstraction.
o To put concept of ADT into context, we need to look at
how we view data.
§ 3 Perspectives of viewing data in computing: (How much level u want the user to see it)
w Application Level (user): The view of data w/thin a particular problem.
(Don’t have to look at anything else, just look at particular problem)
(Don’t have to look at anything else, just look at particular problem)
w Logical Level
(Abstract): Abstract view of the data values and the operations that manipulate
them.
(Object has behavior) **work w/ differ classes**
(Object has behavior) **work w/ differ classes**
w Implementation Level: The specific representation of the structure that holds the data
items and coding of the operations in a programming language.
(You see codes) **Fixing messy codes etc**
(You see codes) **Fixing messy codes etc**
§ These 3 views concerned with Data Structures
– the implementation of a composite data field in an abstract data type.
w It is the way of storing the data in a manner so that we can access
those data easily at later time.
(Stack, Queue, List, Tree)
(Stack, Queue, List, Tree)
§ The ADT are containers which data items are
stored and each exhibits specific behaviors these are Containers because
their sole purpose is to hold other objects.
w Containers – Objects whose role is to
hold and manipulate others.
(variable, data[], SUM)
(variable, data[], SUM)
o
Logical Implementations:
o
2 logical implementations of containers:
§ Array-Based Implementation – Objects in
the container are kept in an array.
§ Link-Based Implementation – Objects in
the container are not kept physically together, but each item tells you where
to go to get the next one in structure.
(Don’t have to put them together, not need to be together can jump and come back)
(Don’t have to put them together, not need to be together can jump and come back)
· 8.2 Stacks
o
Stack is an abstract composite structure in which accesses
are made at only one end.
§ LIFO – Last
In First Out eg: Carts in the Mall
§ Insert – Push
§ Delete – Pop
· 8.3 Queues
o
Queues are an abstract structure in which items are entered
at one and removed from the other end.
§ FIFO – First In First Out eg:
Drinks sell @7-11
§ Insert – Enqueue/Enq/Enter/Insert
§ Delete – Dequeue/Deque/Deq/Delete/Remove
· 8.4 Lists
o
List is like a container of items.
o
The items are:
§ Homogeneous, Linear, Have vary lengths
o
Logical operations be applied:
§ Add item
§ Remove item
§ Get next item
§ More items
o
Array
– Built-In Structure & List – Abstract Structure.
o
A list may be
visualized as a Link Structure, this is based on the concept of node
o
Node consist 2 pieces of info: User’s data & a
link/pointer that indicates where to find the next node.
§ Link Structure – An
implementation of a container where the items are stored together with
information on where the next item can be found.
(Stack and Queue)
(Stack and Queue)
o
If the list is an
unsorted list, the items will be printed in the order in which they are
inserted.
o
If the list is
sorted, the items will be printed in sorted order.
o Stacks, Queues and Lists are LINEAR in
nature (items are next to each other) only
one relationship is being modeled.
· 8.5 Trees
o
Hierarchical
structures, each node in the tree can have more than two children.
o
Binary Trees :
§ An abstract structure in which each node is capable of
having 2 successor nodes called children, and so on (tree its branching
structure)
§ Beginning of the tree is a unique starting node called
root.
w Binary Trees – An abstract
composite structure OR A linked container w/ a unique starting node called the root, in
which each node is capable of having two child nodes and in which a
unique path exists from the root to every other node.
w Root
– The unique starting node in a tree.
(1 is the root)
§
A tree node that
has no children is Leaf. (7,8,9,10 are
leaf nodes)
§
Every node has a
unique (single) parent.
(2 = left subtree & 3 = right subtree of 1)
(2 = left subtree & 3 = right subtree of 1)
§
Any node in the
tree can considered the root node of a subtree. (subtree whose root node 2 also
includes the node 4 & 7)
o
Binary Search
Tree :
§ It is like a sorted
list in that there is a semantic ordering in the nodes.
§ A binary tree (shape
property) that has the (semantic) property that characterizes the values in a
node of a tree:
w (bigger go right,
lesser go left)
o
Build Binary Tree :
Bigger go right, lesser go left
o
Other
Operations
§ Binary search tree is an object with the
same functionality as a LIST.
· 8.6 Graphs
o
A graph is made up of sets of nodes
called vertices and sets of lines called edges (arcs) that
connect the nodes.
o
The vertices
(dots) in the graph represent objects; the edges (lines) describe relationships
among the vertices (dots).
§ Graph –
A data structure that consists of a set of nodes and a set of edges that relate
the nodes to each other.
§ Vertex
– A node in a graph
§ Edge (arc)
– A pair of vertices representing a connection between two nodes in a graph.
o
Undirected
graph – A graph in which the
edges have no direction. (可來回)
§
Two vertices that are connected by one edge – Adjacent Vertices
o
Directed
graph (digraph) – A graph in
which each edge is directed from one vertex to another (or the same) vertex.
§ Path – A sequence of vertices that connects
two nodes in a graph.
o
LISTS, STACKS, QUEUES, TREES –
All just holding containers.
§ Stacks return the item that has been in the stack the least amount of
time.
§ Queue returns the item that has been in the queue the longest amount of
time.
§ List & Trees return the info that is requested.
§
Graph has algorithm defined upon
it that actually solve classic problems.
o Graph Algorithms
§ Depth-First Search – Given a starting vertex and
an ending vertex, we can develop an algorithm that finds a path from startVertex
to endVertex.
w
It is
called Depth First search because we start at a given vertex and go to the
deepest branch and explore as far down one path before taking alternative
choices earlier branches.
§ Breadth-First Search
§ Single-Source Shortest-Path
Search
· 8.7 Subprograms
o
How we pass info back and forth btw
algorithms and sub-algorithms.
o
We call them subprograms rather than sub-algorithms.
o
Subprograms are available as part of
high-level language.
o Parameter Passing
o A parameter list is a list of the identifiers or values with which
the subprograms is to work.
§ Parameter List – A mechanism for communicating between
two parts of a program.
§ Parameters – The identifiers listed in parentheses beside
the subprogram name; sometimes called formal parameters.
§ Arguments – The identifiers listed in parentheses on
the subprogram call; sometimes called actual parameters.
o Value and Reference Parameters
o
2 ways of passing parameters:
§ Value Parameter – A parameter that expects a copy of its
argument to be passed by the calling unit (put on msg board).
(The calling unit gives a copy of the argument to subprogram)
(The calling unit gives a copy of the argument to subprogram)
§ Reference Parameter – A parameter
that expects the address of its argument to be passed by the calling unit (put
on msg board).
(The calling unit gives the address of the argument to subprogram)
(The calling unit gives the address of the argument to subprogram)
Tuesday, February 04, 2014
Ethical Issue: Open-Source Softwares
Thoughtful Questions:
1) There are several common examples of open-source software that many people use in their everyday lives. Can you name any?
- Linux : Operating System
- Google Chrome OS : Lightweight operating system based around the web browser.
- Android smart-phone operating system.
These are all familiar names that we ever heard. They are pretty common.
2) Do you believe that the quality of an open-source software product is likely to be higher or lower than the quality of software produced by a large corporation? How do you think technical support for open-source software compares to that for proprietary software?
-I believed that, the quality of an open-source software product is likely to be lower than than the quality of software produced by a large corporation. Because, the reason why the "original" product is being sell out on the market with some expensive price (software such Microsoft Office) it might cost something thousands; is because that, programmer actually spent a lot of time writing the codes and making this product up. And it is not just one person, its a large professional corporation that made it together. And because it is professional and it is good enough to sell it with price, that software and its quality must be good enough and worth to buy. So by looking at this we can imagine the quality of the open-source software product, it wouldn't be too good. First of all, people could edit it and make changes with the coding from the original, but how do you know that the person that is giving you this free software that he or she just made changes is just a good programmer or not? And since they know that it is not as good as the original that's made by a large corporation, they then feel ok to give out people for free.
3) Daniel Bricklin, biography appears in Chapter 12, did not patent (or copyright) his software, believing that software should not be proprietary. As a result, he lost a great deal of money in the form of possible royalties. Do you consider his actions to be visionary or naive?
-I think is naive, because he didn't copyright his software and didn't think of the consequences of believing that the software should not be proprietary which is losing a great deal of money. He could have at least have an idea of believing that the software should not be proprietary BUT it is ok for others to have only IF they copyright the software to the owner.
4) The Free Software Foundation is a tax-exempt charity that raises funds for work on the GNU Project. GNU software is free. Go to the Web and read about its philosophy. Compare GNU products with those of manufacturers such as Microsoft and Sun.
-Obviously it is different already when you see the name. GNU is a free software foundation that raises funds for work on the GNU project but Microsoft software needed to be paid in order to have the software and they are not made for funds like GNU software.
5) If you were to continue with computing and become a programmer, which side of the argument would you take: Should software be copy-righted or should it be free?
- I would take soft wear be copy-righted. Because the reason why a software is sell it with price is because it worth that price. Imagine an engineer sitting in font of the computer, typing codes again and again, input as many possible values as possible (basically testing) and they ended up giving out the codings for nothing. In the person who actually "write the codes"'s view, I would just say no, they need to copyright my softwares and my work that I've done for long time. But in a general people's point of view. Sometimes when a software is not free, I wouldn't want to go actually buy them, I will just download it. But in this question is talking about "become a programmer" so my answer is "it should be copy-right".
Monday, February 03, 2014
Blog Post: My Winter Holiday
This is a Prezi about my Winter Holiday! It contains the things that I'd done during the holiday. It was nothing much, mostly I just stayed home or go to my aunty's house. But of course, I did something fun at home such as watching dramas, animes with myself or with my family together! My sister and I always watch movies, chit chat, or eat the whole night; night time is our world! we watched many movies at night together. And so we sleep in the morning till early in the afternoon mostly (which is not good). Anyways, other than having fun at night and spend time at aunty's house, my family and I also went for a 3 days trip at HuaHin for welcoming the Year of 2014 ! (for more information,have a look at my Prezi below).After I've done my Prezi about my new year, I realized that, Time flies so quickly!
Subscribe to:
Posts (Atom)