Selection Sort Exercise

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:

§  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)

w  Logical Level (Abstract): Abstract view of the data values and the operations that manipulate them.
(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**

§  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)

§  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)

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)

·       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)

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)

§  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)

§  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)

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". 

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!