Computing Science 360 Lab Assignments

R. Sutcliffe Spring 2017


Read this document carefully before starting any labs. Students are expected to do ALL lab assignments.  Some examination questions may cover material covered in the labs and not in the assigned text readings, or vice-versa.


WARNING:  Some students may be tempted to submit work prepared by others.  Such copying IS possible to detect, and will result in a failing grade. There will also be a report to university authorities who will take further action. If you use any code written by another person, whether from the text, the net, or another student, you must fully attribute it.


Each assignment must be bound with your name, student number, the course number, and the assignment number and title all clearly PRINTED on the cover.  It must include, in order, the bold items in all cases, plus all other items for those for which a complete solution is requested (i.e. after assignment #2). In the latter case, make sure there is a clear description of the algorithms used (if necessary) including any mathematical background needed (don't copy formulas without explaining.) Some problems are NOT completely specified; you must do this yourself.


• A statement of what course goals the assignment fulfills. 

(* Example:

     This assignment fulfills the following goals:

      -  a group I language (Python)

      -  implemented on the iPhone platform.

*)

• A brief restatement of the problem in your own words

• Sample I/O to illustrate how it is supposed to work

   (* note that this is a prediction of what is supposed to happen, not a copy of what actually did. *)

• Documentation for a USER to operate the program

• Explanations of error handling and messages

• A statement of the steps required to solve the problem

• A refinement of the solution into pseudocode, clearly showing any algorithms in particular.

        (Provide references where applicable.)

• A data table, listing all variables and noting all imports

• The final program listing, including

• comment header for identification

(* Name: Daniella Christian *)

(* Student Number: 052011 *)

(* CMPT 360 Spring 2017 *)

(* Assignment #1 *)

(* Solving third order differential equations *)

• appropriate comments for internal documentation

• Actual printouts of trial runs with real data [formatted nicely]

   (Printouts must have your name and assignment number via print statements in the code.)

• Actual printouts of data files used to obtain the submitted results (except where excessive)


Assignments and the project are to be handed in to the Professor by the indicated date.  LATE ASSIGNMENTS AND PROJECTS WILL NOT BE ACCEPTED without a physician's note. Hand in what you've done, because two zeros in assignments zeros the entire course regardless of anything else you do.


Assignment # Date Due

1 Jan 25

2 Feb 8

3 Feb 22

4 Mar 10 

5 Mar 24

6 Apr 5

7 Apr 12

GOALS

As a whole, your assignments must meet the following goals. Each one must clearly show which goals) are satisfied.  Do this by stating goals fulfilled at the top of the first page so they can be checked off. If  this is not present, the paper may  be returned unmarked. Some languages may have to be downloaded and installed.


1. One program on each of three of the following platforms: (a) Mac, (b) UNIX/Linux, and (c) Windows (d) iPhone (e) Android (f) other (must be approved first by instructor).

     Note: XCode is installed on the Mac; documentation is available online. iPhone developer materials are readily available, as is a Swift manual. Linux is available from a number of sources, including KNOPPIX (bootable: http://knopper.net/knoppix/index-en.html) and KALI (bootable: http://docs.kali.org/downloading/kali-linux-live-usb-install) and BSD UNIX is available from the Mac command line--all these would have the GNU suite of languages available) and we expect students to be able to compile from the command line. Assorted compilers are available on all boxes, including ISO Modula-2 (Stonybrook on Windows--look for Start-other-M). You may of course install programming environments and languages from the Internet on your own machine, but should of course be cautious and take a backup before doing any install. Always back up your files, especially if stored on the TWU machines, which can be wiped at any time in an update or when you sign off.

2. Two programs (different languages) of each of group I & II, one from each of group III, IV

     I Modula-2, Java, C, C++, Objective C, C # , Pascal, or Python (one must be unfamiliar to you)

    II Fortran, Cobol, Oberon, Modula-3, Future or Visual Basic (NOT VBA!!), Delphi, Turing, Swift, or similar pre-approved language

    III  Perl, php/mysql, TCL/TK, AWK, JavaScript, Frontier, Applescript, Ruby, or other scripting/macro language other than Python

    IV Smalltalk, Objective C, Scheme, Ada, APL, J, Forth, Prolog, LISP, Eiffel, or other pre-approved language

Note: There are hundreds of languages, of which the above are only samples. Most of the ones you may come up with to try will be in categories II or III.


Marking of Assignments (out of 50):

45 - 50  Excellent.  Everything complete, explanations and all planning evidence and documentation clear AND IN PROPER ENGLISH, efficient and readable (prettyprinted) code.

35 - 44 Good. Some things overlooked, but reasonable explanations.

27 - 34  Just satisfactory.  Some important omissions or errors in the submitted package

  < 27   Unsatisfactory

NOTE: Planning documents not required for the first two assignments or for any  papers you submit.

Again, don't  forget to say in every case clearly at the top of the first page which goals are being satisfied.

DO NOT START A DAY OR TWO BEFORE A PROBLEM IS DUE OR YOU WILL NOT GET IT DONE. THESE ASSIGNMENTS REQUIRE THOUGHT, RESEARCH, AND SOME EXPERIMENTATION TO GET RIGHT. NOTE: When you are required to produce an implementation of an algorithm or a data structure, you must do so from scratch, without using any pre-existing libraries or templates. These problems may take many hours to solve.


Assignment #1

(Do this one using any Group I and any Group II language--two+ goals satisfied.)  With the documentation, include a summary of the differences between the two languages that are relevant to the assignment (not an exhaustive catalogue). Essentially, this exercise is to create a short program in a familiar language, translate it into an unfamiliar one of a similar kind, and compare the two.

Write a program that will accept the coordinates of points Z1, Z2, and Z3 the vertices of a triangle on the plane, and determine the side lengths and the angles of the triangle.  Of course,  this is the complex plane and each point is in the form a + bi  where i has the usual meaning. Of course the problem must be researched first, and the code must check input for validity!!! Please research this before starting.

NOTE: Should you decide to use Modula-2 as the new language, I suggest you examine the materials stored at modula-2.com, specifically the text on ISO Modula-2. You can also start at http://www.arjay.bc.ca/Modula-2/Text/  This is for beginners, so you can skim, but the Stonybrook Modula-2 compiler on the Windows machines or the p1 compiler we hope to install on the Macs should do. A GNU compiler can also be downloaded for Linux, but it isn't very stable.


Assignment #2 

(Do this one using any Group I and any Group II language. Two+ more goals satisfied.) Write and test an efficient (check the meaning of this before going ahead) sorting routine and use it to sort 100, 1000, and 10000 items.  Submit the first two data files and outputs (not the larger one!), and verify that the third is correct but do not submit the whole input/output (a line or two will do). Comment on the ease or difficulty of implementing various kinds of sorting routines in these two languages. At least one of the languages in assignment II must be different than either of those in assignment 1. 

NOTE: This allows you to write in a familiar language and translate into an unfamiliar one. You can use the same starting language as in assignment 1 with a different target language , or the same target language and a different starting one.


Assignment #3

Implement an ADT "double linked list", "queue", "dqueue", or "stack" or other data structure in a language new to you and then use it in an application.  OR Implement a binary sort/search tree or a b-tree or ab-tree, and  use it in an application. Comment on the difference between your methodology and a Modula-2, Python, C++ or Java methodology (whatever language you know best) for the same thing.

Assignment #4

Implement the Sieve of Eratosthenes in both a modular language such as C++, Modula-2, Modula-3, Oberon, Ada, or Java, AND in any other language (group II-IV) for the same physical machine; surround the program to compute the primes below 10000 with a loop to allow for some time testing, and determine which compiler produces the best code. Explicate your reasoning--there should be no other variables than the compiler.

OR Implement both Whetstone and Dhrystone in any one language, comment on the nature and purpose of the test and provide a run for the machine you are using. 

OR  Implement some other benchmark program in the same manner.

Your conclusions should inform me what the test results mean.

Assignment #5

 Using a language/environment you download from the Internet and install (not a group one language, and this is the chance to write in some language not even mentioned above or in the text), write and test a program to display a static (ie non-interactive) one player game (tic tac toe is too easy, but sudoku may be a possibility) that a user can play. Your program has to be able to tell if the person wins, but it need not be "intelligent" enough to play the game against the human player. You may make this a more interesting project by (a) proposing an alternative assignment, and/or (b) teaming up with another persons and doubling+ the size of the project, but in the latter case, pre-approval is required

 

Assignment #6

Do one of 

a) a nifty script or macro 

b) something nifty in the Swift playground

(better give me a proposal on either a or b, but if you need the word "nifty" defined, you are taking the wrong course.)

c) a 1.5K+ word paper comparing      

 - two or more scripting languages

- a group I or II OO language to a group IV OO language,

- two AI languages

- two languages used for robotics

d) Compare C++ to Objective C or C # to Java or Objective C to Swift. Provide some small examples to illustrate.

e) Compare templates in any three of ISO Modula-2, R10 Modula-2, Modula-3, C++, or Java Provide some small examples to illustrate. You need to produce your own templates, not just use ones in a library. Note that there is as yet no compiler for R10 Modula-2, so in that case the comparison is paper only.

If you do part (d or e) you must include a comparison of the object models (arity, garbage, other issues.)

f) Compare ISO Modula-2 with R10 Modula-2 by constructing a detailed chart comparing the reserved words, standard identifiers, Wirthian macros, symbols, and library rules (not the internal templating/blueprinting syntax in detail, but state the difference between templates and blueprints).


Assignment #7 (Use a language you have not previously used for this course, Objective C, Smalltalk, Scheme, Lisp, Prolog, APL, J, Perl, php, Swift, or????  Do one of theseexamples  or an alternate proposal and submit complete documents.)

a) Write and test a random number generator (No, you cannot just call one in an existing library routine someone else wrote, and yes you must disourse on what makes a correct/efficient random number generator. P.S There is an introduction to these topics in the online Modula-2 text mentioned above. The material there can be adapted to any language.).

b) Write and test an efficient routine for finding a substring inside a larger target string. (research necessary; this is non-trivial and takes considerable time.)

c) Write and test a routine for solving a system of three equations in three variables. Don't forget about the special cases!!!!

d) Write a program of your choice that makes use of files and records (php/mysql combo??) to achieve its goals.  Get it approved first.

e) Write something really nifty (get it approved first) [How about a few Internet tools like a multiple domain whois or a FAQ handling machine.]

f) Obtain and improve some Ajax code. The instructor has some functional but ill-documented code for web-site design that implements frames properly that could use a user interface.

g) Write a parser for Modula-2 programs(in Modula-2) that creates a table of all value entities and their types, then goes through the original program and does the Wirthian macro substitutions for I/O routinesthat are documented in the R10 dialect  and creates and saves a new file with the changes for running through an ISO compiler.

These examples are given to illustrate the level of difficulty of the assignment. You may make this a more interesting project by (a) proposing an alternative assignment, and/or (b) teaming up with one or more other persons. However, all alternative assignments must be pre-approved.