Homeworks

HW1 (2/07/2006): Write a program to remove all comments and string constants from a C program. Your program accepts a file as input, and outputs that same file with no strings or comments. For example, it turns: printf("I like \"hello world\" programs!"); into printf(); and also removes /* something */ comments and // something coments. You can use any language you wish (C language recommended) as long as you don't use any regular expression packages (this sort of exludes the use of Perl, etc.). You can use lex however (but that's only 'cause you'll learn it while trying to use it - search the web for usage info).

HW2 (2/21/2006): Write a simple assembler. Your assembler only has to deal with fixed units called INTEGERS (DWORD, 32bit INTs). Each instruction is 4 DWORDS long. Instructions are of the form:

loop1: mov [cntr],12
     write [cntr]
     inc [cntr]
     cmp [cntr],0
     jg loop1
     halt
cntr: int

Basically every instruction can have a "label: " in front of it. Most instructions are modeleted after x86 instruction set (except read/write---which simply prompt a user to enter a number, and output an number---one per line).

A variable is just a memory location with an `int' keywords; in example above, "inc [cntr]" will increment the memory location pointed to by "cntr".

There are no registers. All operations work on 32bit integers (major oversimplification).

Each `line' of assembly is translated to 4 INTs, [opcode,op1,op2,blank], opcode is the instruction code, op1 and op2 are 32bit integers representing either values or memory locations.

Opcode is 4 BYTES, [opno,op1ref,op2ref,blank]. opno is a number of the instruction. op1ref indicates if op1 is a reference, etc. ie: "mov [23],123" would move value 123 to memory location 23. op1ref would be "1" to indicate that 23 is a reference (memory location).

The instruction set follows (feel free to add any instructions you feel are important---I've tried to keep it simple, etc.)

nop', op=0 # nop ; no operation
'add', op=1 # add a,b ; a = a + b
'and', op=2 # and a,b ; a = a & b
'cmp', op=3 # cmp a,b ; compare a and b.
'dec', op=4 # dec a ; decrement a
'div', op=5 # div a,b ; a = a / b
'halt', op=6 # halt the machine (exit)
'inc', op=7 # inc a ; a = a + 1
'je', op=8 # je a ; jump to a if eq flag
'jne', op=9
'jg', op=10
'jge', op=11
'jl', op=12
'jle', op=13
'jmp', op=14 # jmp a ; jump to a.
'mov', op=15 # mov a,b ; a = b
'mod', op=16 # mod a,b ; a = a % b
'mul', op=17 # mulb a,b ; a = a * b
'neg', op=18 # neg a ; a = -a
'not', op=19 # not a ; a = !a
'or', op=20 # or a,b ; a = a | b
'pop', op=21 # pop a ; a = pop from stack.
'push', op=22 # pushb a ; push a onto stack.
'sub', op=23 # sub a,b ; a = a - b
'xor', op=24 # xor a,b ; a = a ^ b
'read', op=25 # read a ; value into a
'write', op=26 # write a ; display a

Tips: Use any language of your choice. Most modern languages have easy ways of `tokenizing' a string. Work with 1 line of input at a time. You might have to loop through the input twice (since you won't know the values of labels on the first run). This is a simple program of: loop through all lines of input, break each line into "label: instruction op1,op2" turn that into an `instruction', and output it. That's it. We'll write the virtual machine for this a bit later.

HW3 (3/7/2006): Write a virtual machine for your assembled code (from hw2). It will work this way: Assume memory is blocks of 4 dwords. Allocate an array of instruction structures. Load the binary code (from hw2) into ram. (now, you have instructions from hw2 in ram, in neat structures you can just loop through). Initialize a variable called "ip" (instruction pointer) to 0. Jump to instruction under this "ip" in your loaded array of structures. For each instruction, do what the instruction specifies (ie: for 'add', do the actual addition). For instructions like jmp, adjust the "ip", etc. You will also need to have another variabled called "flags" (for cmp instructions, etc.). When you encounter 'halt' instruction, just exit.

HW4 (3/14/2006): Write a recursive descent compiler. Your compiler can take in any high level language (that you invent) and output your assebly code (that you should be able to run via your assembler). Bits of grammar and code examples showing tricky parts can be found in comp.pdf class notes---that should give you enough background to code your own version. More on this in class.

HW5 (3/21/2006): Write a C program to sort an integer array using the qsort() library routine. (defined in stdlib). Define a person_t structure, like: typedef struct { char name[100]; int age; } person_t;, declare an array of such person structures, and sort the array by name, and then by age; by calling stdlib's qsort() function. Then, use the bsearch() function to lookup some name. Basically write the code to show me you've played around with qsort() function and know how to work with function pointers in C language. Do not write your own sort function---the whole purpose is for you to use a library function.

(HW5 contuned): Write a C++ `List' library that (in worst case) has these properties:
Insert in front/back takes O(1) time.
Remove from front/back takes O(1) time.
Lookup into middle takes O(1) time.
Replace in middle takes O(1) time.
Remove from middle takes O(n) time.
The list should grow as more elements are inserted. The user shouldn't care how things are implemented, and should only care about having a list and being able to insert/remove values from it. (Note that you cannot achieve these performance numbers with linked lists; also note that this is generally faster than any publically available library out there, including most things in STL).

HW6 (3/28/2006): Write a program, in any language, to generate a valid Sudoku game. Every time you run the program, it should output a -random- sudoku game to standard output. Note that the game has to be solvable (you cannot just have random numbers). Tip: This is very similar to 8-Queens problem, and you can use similar techniques to write it. Tip2: Google is your friend.

HW7 (4/11/2006): Write a program in any language to display all permutations of any string. The program gets the string as input from the user, then proceeds to display all permutations for that string of symbols. For example, if the user enters: "ab", the set of permutations would be {"ab","ba"}, if the user entered "bac", the set of permutations would be: {"abc","bac","bca", "acb","cab","cba"}, and so on and so on... Note that you can have repeating symbols, like "aba", would produce the appropriate permutations of 3 symbols, etc. Also note that the user may enter any number of these things (they can enter 20 symbols if they feel like it). Try to pick the easiest programming language to do this in.

HW8 (5/2/2006): Write code in LISP to do the following:

A function to be called remove-one. It takes two parameters, the first an item, the second a list. It returns a list, like the list that was used as the second parameter, but with all occurrences of the first parameter item removed. For example: (remove-one 'a '(b a c a d)) should return the list (b c d).

A function to be called remove-all. It takes two parameters, both lists. It returns a list like its second parameter, but with all occurrences of anything from the first parameter list removed. For example: (remove-all '(a b) '(c a d b e a f)) should return the list (c d e f).

A function, apply-one, that takes two arguments, an item --- call it A --- and a list --- call it L. It returns a list of the same length as L. If B is a member of L, the two-element list (A B) should be a member of the output list. For example, if sam and (x y z) are used as input, the output should be ((sam x) (sam y) (sam z)). [I don't care about the order of the pairs in the output.]

A function combine, that takes two lists as arguments, call them List1 and List2. It returns the `Cartesian product'. That is, the output list contains (x y) for each x in List1 and each y in List2. For example, if (a b) and (x y z) are the inputs, the output should be ((a x) (a y) (a z) (b x) (b y) (b z)). [Again, I don't care about the order of the members in the output list.]

HW9 (5/9/2006): Write a C# program to find all solutions to the 8-Queens problem. Comment every line of the program with a description of what that line does. (8-Queens problem: given 8 queens, place them on a chess board such that no queens attacks another). Make it as simple, or as complicated as you want... (ie: make it graphical?)

HW10 (5/16/2006): Program the following in Prolog: A three-place relation to be called removeOne. When queried with an item as the first argument, a list as the second, and a variable as the third, the variable should be bound to the second argument with all occurances of the first argument removed. for example, the query: removeOne(a,[b,a,c,a,d],X) should yield X=[b,c,d].

A three-place relation to be called removeAll. When queried with lists as first and second parameters, and a variable for the third, it should bind the variable to a list consisting of the memebers of the second argument, but with all occurances of anything from the first argument removed. For example removeAll([a,b],[c,a,d,b,e,a,f],X) should yield X=[c,d,e,f].

Good luck!