Data Structures - Fall 1998
Lab Exercises and Programming Assignments
 
*Updated on 9/15/98
Your programming assignments can be obtained by coming to this web page and click on the assignment in the table.
If a program is late, you will need to schedule an appointment with me asap to discuss your programming and make a schedule for finishing your work.
So, Don't be late!

Your programming grades will be combined with exam grades to determine your course grade



 
Week Work To Do This Week Due day before  midnight 11:59pm 
 
Aug 25-29 Using elm or pine for email/news (elm header -csci15b89f - Hello Thinking Cap) 
Exercise 1: Gnu emacs and g++ (No, due day! Try it on your own and have fun!)   
Program 1: The Thinking cap program (From our textbook publishes lecture #1.) 
Point worth 25 points 
Due Sept 5, 98 
5 point deduction/day for 5 day late for upto 35 points deduction. 
 
Sep 1-19 
 
Exercise 2: The xdb debugger & make facility (No,due day) 
                 Add Chapter 2 Feature Components into your modified ThinkingCap 
Program 2: Tac-Tic-Toe & Container class
You can turn in earlier on Sept 17,18 Final Due on: Sept 19 11:59pm 
Item to turn in: ( Total worth 45 points ) 
* Your modified ThinkingCap.h & cpp 
* Thinker2.h ,  e2main.cpp , Thinker2.cpp 
* Tac-Tic-Toe Design (Class design & PseudoCode
* P2Design 
------------------------------------------------------------------------ 
* Tac-Tic-Toe Implementation Due Oct 1,2 Final Due Oct 5 11:59am  
Note: 10 Points deduction/day for maximum of 60points after Due date. 
* tatito.h tatito.cpp p2main.cpp
Oct 1st EXAM #1
Oct 1 Chapter 4:  Pointers and Dynamic Arrays 
Program 3: Spelling Checker Program
Program 3: Preliminary Pseudo Code  will be Due in Next Lab Meeting. (Oct 8,9) 
                   Final Pseudo Code  will be Due in Next Lab Meeting. (Oct 15,16) 
                   Final Deliverable due: Oct 18  (Sunday 11:59pm) 
                   Final Deliverable Extended to Oct 25 (Sunday 11:59pm) 
 Item to turn in: (Total worth 45 points) 
 Your makefile, cpp,h files and the main program. 
 Plus a sample run of the output on spelling check.  
You will modified your BagClass on P. 168 of your textbook for: 
* Read in a default dictionary file and Inserting string (as dictionary) into this container class. 
* Read in a user defined dictionary file if there is one. 
* Modify the member function in occurences(...) for doing string search. 
   Notice: You should be able to reuse the  == operator overload from ThinkingCap. 
* Read you sample input text file and scan it will your container's dictionaries. 
* Features: Add new words to user defined dictionary file and updates for spelling 
   check next time with the same input file. 
* You may use X-windows display ASCII character set to display the mis-spelled word. 
   or simply a text character pointer to indicate the mis-spelled word for processing. 
* Scan in one sentence at a time. 
e.g 
//Input file: 
IBM marked the first birthday of DB2 Universal 
Database (UDB) today with sweeping announcements, including version 5.2 
of the year-old database; plans for Linux and OS/390 mainframe editions; 
a new knowledge management product; datamart bundles, third-party 
partnerships; and the acquisition of IW Manager from Tanning Technology 
Corp. 
Suggested word to replace: 1.double 2. dbase 3. debug 4... 5 ..  6 .. 7 .. 8..  9 ... 10  
11. User Input  12. Skip   13. Add to dictionary. 
>11 
>suggested input to replace DB2?DataBase2 
Tips:  You will need to use more string.h function for string manipulation. 
      such as: strstr, strcmp, strcpy etc...
Oct 24 Program 4: Linked List (perhaps a Simulation proj) Program 4: Preliminary Pseudo Code  will be Due in Next Lab Meeting. (Oct 29,30) 
Final Due Date: (Nov 7 11:59pm)  , ( Change to Nov 14  11:59pm ) 
Item to turn in: (Total worth 45 points) 
you must compile ( or re-compile ) with our ect-unix platform with makefile. 
Submit files: makefile , main.cpp, linkedlist.cpp, phonebook.cpp and their header files. 
========================================================== 
PhoneBook Implementation using Double Linked List class. 

Spec: 
1. Command Line PhoneBook will use command line argument: 
       main(int argn, char* argc[]);    //I gave this information in the lab already. 

2. Your phonebook will maintain information for the following 5 fields. 
    * firstName(15)     //15 chars  Column 0-14 
    * lastName(15)      //15 chars  Column 15-29 
    * address(30)         //30 chars  Column 30-59 
    * phoneNumber(with Area Code)  format: (530-898-8888)   //12 Chars.  60-71 
    * Memo (50)         //additional description   72-121 

3. Features such as: add, delete, modify,list and search will be implemented. 
    You will read in input database file (it's just a flat text file) with column specific. 
    for example: Column=0 to Column 14 is first name. 
Extra credit: 2 pair of links. (One for 1st name, and one for last name) 
*This assignment will require you to implement in ect-unix platform. 
Command Line syntax: 
$phonebook -h    /help 
Command Insert sample: 
    $phonebook -i  
    $FirstName: Washington C 
    $LastName: Armstrong 
    $Address: 911 Nord Ave, #911, Chico  ca 95926 
    $Phone: 530-343-9111 
    $Memo: A guy's trying to give you hard time for your own good future. 
Command delete: 
    $phonebook -df  
    $Enter FirstName:Wash*   //This should give me options on which Washington to  
    delete. Your output will navigate to the one I want to delete and quit with successfull  
    message. 
Command Search: 
    $phonebook -sf  
    $Enter FirstName: Anthony  //will list all the Anthony with difference last name. 
    $phonebook -sf  
    $a*            //will list all the first name start with character 'a' and delete the one you choose! 
 
options summary: 
-h     //on-line help menu, should display all options and how to run the program.  
-i      //insert or add (alphabetically with firstname as criteria, first & last name must be 
           unique in your database. If there is already. You shuold modify your input name.) 
-l      //list all the information you have. (alphabetical order on first/last name) 
-m    //modify existence information. (using firstname and last name.) 
-d     //delete a record in the information database. 
-sf     //search by firstname options. (One for first name, one for last name) 
-sl     //serch by lastname options.

Nov  Program 5:Templates Final Due Date: (Sat Nov 21, 11:59pm, Optional 30 points) 
I'd made this pogram to be Optional because of our booksrc code has some mis match with our  
g++ compiler. It seems all template sample can be compiled except the one with Sting class. 
However, student had implemented StringBag & IntBag should find little difficult to do this!) 
Template class for StringBag and IntBag: (30 points) 
Please use P288 main program to test your StringBag and IntBag fo your template class. 
submit your program with readme.txt and makefile in your assigned  project subdirectory. Since the design of this code is taken straight from the textbook. You only require to sumit your documentation for your program assignment, readme file and makefile. 
Extra Credit: (10pts) P 305 #5 Implementation for external iterator.
Nov 9 EXAM #2
Nov 12 Program 6: Stacks, Queue & Recursion Final Due Date: ( Dec 10 & 11 Lab Time, 60 points, you requre to demo your output in the lab!) 
Reuse Stacks & Queue class as a tools, write a recursive MAZE program to solve the shortest path. 
Problem statement: A given MAZE in 16 X 16 (or N X N) 2-dimensional array. 
You will write a program to solve the shortest path to the MAZE pattern.  
Theory:  
You  will alway start the maze run from Left/Top corner where the S symbol located. 
The goal of this program is to find the all the possible final ending point marked by E symbol and print out all path visitED and summerized with the shortest path. 
One simple approach to this problem  is to write a recursive program to navigate 
all possible path (start from RIGHT direction, then BOTTOM, LEFT, TOP ( LHR left hand rule)  and store & save all the possible final (E symbol) path into stack and pop all the other path out.
Algorithm: 
Step 1: sketch the maze recursive visit algorithm.  
Step 2: Discover the termination criteria for recursive call. 
Step 3: Add the output steatement for current x-y coord while visiting. 
Step 4: Test (Revise) the code. 
Step 5: Add stack/queue feature to store all possible path. 
Step 6: Check all the your stacks and find the shortest path.
Nov 23 November 23-27  Thanksgiving vacation -- no classes held.  
All late assignment will not be accept anymore after the Thank's day,  (29th 11:59pm) 
Please put all your assignment into the /n/projects/ashiu/csci15b/your subdirectory. (p3,p4,p5,p6) 
And notify me in email  for any turn in! 
Your subdirectory should came with a readme file to tell me what work , what doesn't and  
how to run your program.  
Reminder: please change all your turn-in file permission to access  by me only. 
e.g   $/n/projects/ashiu/csci15b/david/p3/chmod 770 *
Dec 14 FINAL EXAM:
Dec  Program 7: Binary Tree & Binary Search Jost need to learned it for your final!
 
 



 
 


 

Anthony Shiu (ashiu@ecst.csuchico.edu) 

Since Sept 15, 1998