Data Structures for IT/CS 2

Answer

2009-05-11T19:32:00.000-07:00

(A + B) * (A – C)
INPUT A
STORE A
INPUT B
STORE B
INPUT C
STORE C
LOAD A
ADD B
STORE SUM
LOAD A
SUBT C
STORE DIFF
STORE DIFF2
LOAD DIFF
SUBT ONE
SKIPCOND 100
JUMP HERE
CLEAR
STORE ANS
JUMP SHOW
HERE, LOAD SUM
STORE ANS
LOOP, LOAD DIFF
SUBT ONE
STORE DIFF
SKIPCOND 800
JUMP SHOW
LOAD ANS
ADD SUM
STORE ANS
JUMP LOOP
SHOW, LOAD A
OUTPUT
LOAD B
OUTPUT
LOAD C
OUTPUT
LOAD SUM
OUTPUT
LOAD DIFF2
OUTPUT
LOAD ANS
OUTPUT
HALT
A, DEC 0
B, DEC 0
C, DEC 0
SUM, DEC 0
DIFF, DEC 0
DIFF2, DEC 0
ONE, DEC 1
ANS, DEC 0

Schedule for Project Presentation

2009-03-12T19:57:00.000-07:00

8:00 - 10:00 IT2A
10:00 - 12:00 CS2
1:00 - 3:00 IT2B
3:00 - 4:00 IT2C

*I would not entertain late comers.

Final Project Group Topics

2009-02-17T10:17:00.000-08:00

Group	Project
1	Trees Root, Siblings, External Node, Ancestors, Descendant, Depth, Height, Degree Operations: Insert, Remove, Search, Display
2	Traversal - Trees PreOrder Operations: Insert, Remove, Search, Display
3	Traversal - Trees InOrder Operations: Insert, Remove, Search, Display
4	Traversal - Trees PostOrder Operations: Insert, Remove, Search, Display
5	Tree Application Arithmetic Expression Tree Operations: Display
6	Binary Tree – Number of nodes, number of external nodes, number of internal nodes, height Operations: Insert, Remove, Search, Display
7	Directed Graph Operations make-graph(): graph Create a new graph, initially with no nodes or edges. make-vertex(graph G, element value): vertex Create a new vertex, with the given value. make-edge(vertex u, vertex v): edge Create an edge between u and v. In a directed graph, the edge will flow from u to v. get-edges(vertex v): edge-set Returns the set of edges flowing from v get-neighbors(vertex v): vertex-set Returns the set of vertexes connected to v
8	Undirected Graph Operations make-graph(): graph Create a new graph, initially with no nodes or edges. make-vertex(graph G, element value): vertex Create a new vertex, with the given value. make-edge(vertex u, vertex v): edge Create an edge between u and v. In a directed graph, the edge will flow from u to v. get-edges(vertex v): edge-set Returns the set of edges flowing from v get-neighbors(vertex v): vertex-set Returns the set of vertexes connected to v
9	Weighted Graph Operations (an extension of undirected/directed graph operations) make-edge(vertex u, vertex v, weight w): edge Create an edge between u and v with weight w. In a directed graph, the edge will flow from u to v.
10	Graph Traversal Depth – First Traversal
11	Graph Traversal Breadth-First Search
12	Weighted graphs: Dijkstra’s algorithm
13	Travelling Salesman Problem

Reporting Update

2009-02-13T23:20:00.000-08:00

Report Schedule
IT2A - Thursday/February 19, 2009
IT2B - Thursday/February 19, 2009
IT2C - Wednesday/February 18, 2009
CS2 - Friday/February 20, 2009

The presentation of your topics will start according to the date specified above for your respective classes.

Lab Exam

2009-01-31T09:14:00.000-08:00

Visit this site - http://www.coders2020.com/what-is-infix-prefix-postfix-how-can-you-convert-from-one-representation-to-another-how-do-you-evaluate-these-expressions. This will serve as your guide for your upcoming midterm lab exam this monday.

Stack and Queue

2009-01-24T14:20:00.000-08:00

The codes for stack and queue are already available under Course Materials-> Handouts/ Learning Modules in elms.

Top Students for Prelim

2009-01-12T20:37:00.000-08:00

1. EMAN, ROÑARD C. (BSIT2B) 96
2. PAASA, PATRICK ANGELO P. (BSIT2C) 93
3. LASAY, NORRIS LEMUEL C. (BSCS2) 90
4. ZABATE, MARVIN JOHN B. (BSCS2) 88
5. LUI, ADRIAN E.(BSCS2) 88
6. JAMIO, PAUL JOHN I. (BSIT2B) 88
7. MEDILLO, DARWIN I. (BSIT2A) 88
8. REANCHO, LIRALYN S.(BSIT2A) 88
9. AMARANTO, MAYLYN T. (BSIT2C) 88
10. BERNARDINO, JAMES CARL H. (BSIT2C) 88
11. CARILLO, RAFFY D. (BSCS2) 88

Templates

2009-01-03T00:47:00.000-08:00

Function templates
Function templates are special functions that can operate with generic types. This allows us to create a function template whose functionality can be adapted to more than one type or class without repeating the entire code for each type.

In C++ this can be achieved using template parameters. A template parameter is a special kind of parameter that can be used to pass a type as argument: just like regular function parameters can be used to pass values to a function, template parameters allow to pass also types to a function. These function templates can use these parameters as if they were any other regular type.

The format for declaring function templates with type parameters is:

template function_declaration;
template function_declaration;

The only difference between both prototypes is the use of either the keyword class or the keyword typename. Its use is indistinct, since both expressions have exactly the same meaning and behave exactly the same way.

For example, to create a template function that returns the greater one of two objects we could use:

template <class myType>
myType GetMax (myType a, myType b) {
return (a>b?a:b);
}

Example

// function template
#include 
using namespace std;

template <class T>
T GetMax (T a, T b) {
 T result;
 result = (a>b)? a : b;
 return (result);
}

int main () {
 int i=5, j=6, k;
 long l=10, m=5, n;
 k=GetMax<int>(i,j);
 n=GetMax<long>(l,m);
 cout <<>return 0;
}

Class templates
We also have the possibility to write class templates, so that a class can have members that use template parameters as types. For example:

template <class T>
class mypair {
 T values [2];
public:
 mypair (T first, T second)
 {
   values[0]=first; values[1]=second;
 }
};

Example:

// class templates
#include 
using namespace std;

template <class T>
class mypair {
   T a, b;
 public:
   mypair (T first, T second)
     {a=first; b=second;}
   T getmax ();
};

template <class T>
T mypair::getmax ()
{
 T retval;
 retval = a>b? a : b;
 return retval;
}

int main () {
 mypair <int> myobject (100, 75);
 cout <<>return 0;
}

Template Specialization

// template specialization
#include 
using namespace std;

// class template:
template <class T>
class mycontainer {
   T element;
 public:
   mycontainer (T arg) {element=arg;}
   T increase () {return ++element;}
};

// class template specialization:
template <>
class mycontainer <char> {
   char element;
 public:
   mycontainer (char arg) {element=arg;}
   char uppercase ()
   {
     if ((element>='a')&&(element<='z'))
     element+='A'-'a';
     return element;
   }
};

int main () {
 mycontainer<int> myint (7);
 mycontainer<char> mychar ('j');
 cout <<>return 0;
}

Observe the results of the codes above. A short quiz will be given about this during lecture.

U.S. Capitals Lab

2008-12-09T08:12:00.000-08:00

Objective: to maintain an ordered linked list

Write a program that maintains a linked list of U.S. capitals in alphabetical order. First of all, create a text file containing a few names of state capitals. Your program should get the names from the file, inserting them in the linked list and then call the sorting function and finally display the results.

Create a text file and name it as “stateCapital.txt”

Here is the content of your text file: State Capitals

Montgomery
Juneau
Phoenix
Little Rock
Sacramento
Denver
Hartford
Dover
Tallahassee
Atlanta
Honolulu
Boise
Springfield
Indianapolis
Des Moines
Topeka
Frankfort
Baton Rouge
Augusta
Annapolis
Boston
Lansing
St. Paul
Jackson
Jefferson City
Helena
Lincoln
Carson City
Concord
Trenton
Santa Fe
Albany
Raleigh
Bismarck
Columbus
Oklahoma City
Salem
Harrisburg
Providence
Columbia
Pierre
Nashville
Austin
Salt Lake City
Montpelier
Richmond
Olympia
Charleston
Madison
Cheyenne

Refer to http://www.lakesparadise.com/education/elearning/show_tutorial.php?id=25 for C++ file handling.

http://www.yolinux.com/TUTORIALS/LinuxTutorialC++StringClass.html for C++ String class Examples and Tutorial

PRELIM EXAM DETAILS

2008-12-02T23:05:00.000-08:00

Date: December 4, 2008
Time --------------------- Location ----------------- Class
8:00 - 10:00 AM -------- L204 --------------------- IT2A
8:00 - 10:00 AM -------- L203 --------------------- CS2
10:00 - 12:00 AM -------- 302 --------------------- IT2B
10:00 - 12:00 AM -------- 303 --------------------- IT2C

Note:

Irregular students from IT2A/CS2 may take the exam together with the IT2B/IT2C.
Be on time. The exam is good for 90 minutes.
Failure to attend to one of these schedules may cause failure for prelims.

Sorting items in linked list

2008-11-23T06:57:00.000-08:00

Please do not ask regarding the algorithm if your having problem translating it. Learn to read algo. If your sure something is wrong with it, call my attention.

Open your previous devC files and add this algorithm I'm about to give in Node.h.

step 1: Create a function named as Sort (lets assume you want to sort your nodes/items in ascending order) with void as its return type.
step 2: Inside your function, transform this algorithm into a C++ code.

1. Create a pointer (current) of type Node

2. Equate current to head

3. Iterate using while loop until current is null

a. Create another pointer (next) of type Node

b. Equate next to current->link

c. Iterate using a while loop until next is null

i. Test using an if statement whether current’s data value is greater compared to next’s data value (if true, proceed with the bullets list)

Ø Create a pointer (temp) of type Node

Ø Equate temp to a new Node

Ø Assign the values of current (data) to temp (data)

Ø Assign the values of next (data) to current (data)

Ø Assign values of temp (data) to next (data)

Ø Delete temp using the keyword temp

ii. move the next pointer to next->link

d. Move current pointer to current->link

LAB ACTIVITY

2008-11-18T07:35:00.000-08:00

Advantage of Linked Lists.

Linked lists are used to store collections of data. But we've already seen a mechanism for doing this. i.e. A collection of data can be stored in array. However, an array is a sequential structure meaning that it is a group of memory elements located in contiguous locations (located next to one another in a group). You need to know how many elements there will be and you need to allocate a block of memory for them.

When you don't know how many elements there will be, and if elements need to be inserted and deleted frequently, it is better to use a linked list. This is because each element for a linked list is created as needed and can be stored anywhere in the free memory space - the elements in the list do not have to be stored in contiguous locations.

Each element in a linked list is referred to as a node. In a simple singly linked list, each element has two fields:

Data member - contains the data (in our implementation, this is called datum)
Link member - contains the pointer to the next node (in our implementation, this is called next)
Note: we are going to represent the "link" part as "next" variable

In this lab, a node is defined by the following class (called Node):

class Node
{
 private:   
  int data;
  Node* next;
  
 public:
 
  Node();

  void insertItem (int);
  void makeList ();
  void appendItem (int);
  void deleteItem (int);
  void printList ();
};

A couple of notes on linked lists are:

if you were implementing a doubly linked list, the above class would have an additional data member to define a pointer to the previous node.
the last node in any linked list contains a null pointer in the link member.
the null pointer is used to determine the end of the list.
notice that there is a constructor in the above implementation that can be used to set the datum and next members.

The following diagram illustrates a simple singly linked list.

In this lab, we use a class Node to create a linked list.

Operations on Linked Lists.

What follows here, are very rough algorithms on the basic operations that you would perform on a linked list. In actually implementing list operations, you would have to consider conditions such as: Is the list empty? What happens if I get to the null pointer and haven't found a data member that is supposed to be in the list? The algorithms here are just to provide you with an overview of the concepts involved in simple operations.

Creating a List (makeList())

               First, create a node initialized with a data value and a NULL pointer.
              Set the "head" to point to the first node.
              Set up a current-pointer to the first node (or "head").
              Get a data value for the next node.
              While more nodes to add
              {
                 Create a new node initialized with the data value and a NULL pointer.
                 Set the current-pointer link member ("next") to the new node.
                 Set the current-pointer to point to the new node.
                 Get a data value for the next node.
              }

Adding a Node (appendItem(int item))

               //Find the end of the list...
              Set a current-pointer to the "head".
              While current-pointer link member ("next") is not NULL
              {
                 Set the current-pointer to the "next" node in the list.
              }
              //Now current-pointer points to the last node...
              Create a new node initialized with the "item" and a NULL pointer.
              Set the current-pointer link member ("next") to this new node.

Printing Nodes (printList())

               Set a current-pointer to the "head".
              While current-pointer is not NULL
              {
                  Print the data member ("datum") of the current node
                  Set the current-pointer to the "next" node in the list.
              }

Inserting Nodes (insertItem(int item))
This algorithm assumes that you want to insert a node into a list of ordered values. Let's say you have two values, 12 and 24. A new value of 14 should be inserted between these existing values so that the final list will contain the values 12, 14, and 24.

               Set a previous-pointer to NULL.
              Set a current-pointer to the "head".
              //Find where your want to insert into the list...
              While the new data member > current-pointer value
              {
                 //Move both pointers along in the list...
                 Set the previous-pointer to the current-pointer
                 Set the current-pointer to the "next" node in the list.
              }
              Create a new node initialized with the "item" and current-pointer.
              Set the link member in the previous_pointer to the new node.

This is much easier to understand if you visualize the nodes and the pointers as they are changed. The following diagram attempts to illustrate this process.

Deleting Nodes (deleteItem(int item))

This routine assumes that the item you are searching for is, in fact, in the list.

               If "item" is in the first node
              {
                  Set a delete-pointer to the first node.
                  Change the "head" pointer to the second node.
              }
              Else
              {
                  Set a current-pointer to the "head".
                  While current-pointer->next->datum is not equal to "item"
                  {
                     Set the current-pointer to the "next" node in the list.
                  }
                  Set a delete-pointer to the node to be deleted (Note: it is
                      the node after current-pointer).
                  Set the link member ("next") of the current-pointer to the
                      "next" node after delete-pointer.
              }
              Delete the node indicated by delete-pointer.

This is much easier to understand if you visualize the nodes and the pointers as they are changed. The following diagram attempts to illustrate this process.

GradeBook Assign

2008-11-06T07:56:00.000-08:00

Notes:

1. Files you need to create: GradeBook.h (where the function prototype are listed), GradeBook.cpp(the implementation of the functions) and Main.cpp (the main file)

2. If scanning for input grade using cin does not work, try
grade = cin.get();
3. 6 functions are included in the class:

GradeBook(string input);
void displayMessage();
void setValue(string input);
string getValue();
void setGrades();
void displayGrades();

4. 7 private variables:

string courseName;
int aCount;
int bCount;
int cCount;
int dCount;
int eCount;
int fCount;

5. If including the header file of GradeBook.h in main.cpp creates a linker error, replace it with GradeBook.cpp (assuming that you saved the functions' implementation file as GradeBook.cpp)

Output sample:

Introduction to the subject

2008-10-26T19:14:00.000-07:00

Welcome to Data Structures. This blog is for IT2 A/B/C and CS2 students.

Quick Syllabus
To become data struct experts, you need to master the following topics:
1. Precondition/Postcondition specifications
2. Self-Referential Classes
3. Dynamic Memory Allocation and Data Structures
4. Linked List
5. Stacks
6. Queues
7. Trees

Grading System
Lec - 70% - Quizzes(40%), Attendance(5%), Class Recitation(5%), Long Tests(20%), Exam(30%)
Lab - 30% - Quizzes(50%), Attendance (5%), Exam(45%)

note: Only 4 absences are allowed for the whole duration of the semester.

Late Homework: Homework will be accepted up to 24 hours after the deadline with a 5% penalty. No homework will be accepted after that point, so please submit your work within 24 hours of the deadline even if the work is only partly completed.
Missed Exams or Quizzes: Makeup exams or quizzes can be arranged only if you inform me at least 24 hours ahead of time or if an unavoidable problem causes you to miss class. Other missed exams or quizzes will be recorded as a zero score. A medical certificate should be submitted to me to validate your reason for absence.

Book References: C++ How to Program, fifth edition by Deitel