CS 1MD3 T2 2005
Assignments

All assignments will be handed in using WebCT. Your MUSS userid is your userid for WebCT as well.

It seems that in some of the labs (like those ABB), cygwin is already installed. I definitely recommend learning vim (which I use all the time) or emacs (which I ought to use sometimes) for editing programs. Of course, you can use textpad too, but you will be less efficient if you do that. It takes a bit of time to learn, but the long-term rewards are definitely worth it!

1. Translate some C code to Pascal. The code is also available as text file for easier editing. It appears that "free Pascal" is installed in all the labs, so you can make sure your programs are correct. The marking scheme will definitely deduct marks for syntactically incorrect programs!
2. Write some C code algorithms 2 ways, and compute various space/time properties of the results. Details here.
3. Implement a variety of data-structures in C. Find your student ID from the assignment 3 page, and follow the link to find your own assignment.
4. Hash tables! Find your student ID from the assignment 4 page, and follow the link to find your own assignment.

5. Assignment 5 - This assignment requires you to write a finite state machine in two different ways.

   As usual, find your id, and that page contains the transition table for your finite state machine.

   Interpretation of the transition tables:

   The functions to create should use the following prototype:

   • the states use the 'alphabet' 1,2,3,4,5
   • the symbols of the machine use the 'alphabet' a,b,p,q,t
   • the start state is 1.
   • the set of final states is {5}

   void fsm1(char *s); /* string from symbol alphabet */
   void fsm2(char *s); /* string from symbol alphabet */
   

   You may assume that the input to fsm1 and fsm2 consist of strings that are only from the symbol alphabet

   First, for fsm1, write a state machine machine using if statements to encode the transition function.

   Second, for fsm2, write a state machine machine using the transtion table directly to encode the transition function. In other words, store the table in a 5x5 array and use lookup to determine the next state.

   In both cases, before fsm1 or fsm2 exit, they would print ( using printf) "accept" or "reject" depending on whether the corresponding machine would accept or reject the input string.

   Your program should contain a main() function which has some (hard-coded) test strings sent to both fsm1() and fsm2(). Make sure to have test cases (ie strings) that cause both 'accept' and 'reject' to be printed! In case your machine accepts all strings (or rejects all), write some explanation as to why you believe this is the case.

   Deliverables: one (1) .c file saved as plain text containing the above 2 function and the main program.

Bonus Assignments

Coming soon