H omework Assignment 1 Solution

Assignment







1. Consider the following C program program with multiple errors(most indicated) as indicated:










#include <stdio.h




int xy,x, char c; float f; //error




float arr[10] //error




int i#rate = 10; //error




int chg(int flag) {




int struct = 8;




int i = 3;




xy=4;




if (flag = 0) { //error?




arr[i] = 1.79766E+308; //error




} else {




arr[10] = 1.9; //error




}




return flag;




}




int main (void){




if (xy = 10) {




printf("Begin:: ");




}




chg(flag=0); //error




return 0;




}













Label each error as either: lexical, syntactical, static semantic, dynamic semantic, uncheckable error or logical error. To compile type: gcc -Wall -std=c11 YOU NEED TO JUSTIFY YOUR ANSWER IN 1 OR 2 SENTENCES.







Download and compile gcd.c to assembly code on your machine: Use the command gcc -S gcd.c



Although C is considered a high-level language it really is only a few steps up from assembly. You should be able to recognize a simple correspondence between the C code and the compiled assembly code. Annotate the generated assembly code (you may copy and paste it in this file and annotate by line): Look for the key points, there is no need to label each instruction.




In particular, you should recognize and label the following:




The creation of the stack frame.
Argument storage and updates.



Local variable storage and updates.



Translation of the loop.



Some form of return result, and an exit from the function.



You can use gcd.h .




3. Do exercise 1.4 pg 38 Below is a modification of the code given in the textbook.







int gcdM(int i, int j) {




while ( i != j) {




if (i j) {




i = i % j;




} else {




j = j % i;




}




}




return i;




}




Does this program always compute the same result as problem 2 above? If gcdM() does not give the same results as gcdI(), can you fix it? Under what circumstances would you expect one or the other to be faster?




Download and compile gcd_full.c: Use the command gcc -Wall gcd_full.c -o gcd (it's always a good idea to compile with -Wall). You may run it with any integer input ./gcd 56 14



The function gcdI is obviously an iterative implementation of a gcd function.




Add a new function, gcdR, that gcd function using a functional style: You should recursively call gcdR and use no loops. Adjust the main function to call gcdR instead.



Briefly discuss the computation complexity of both implementations of power (big-oh notation); one sentence will do.



In a language where you have the flexibility to implement an algorithm iteratively and recursively why would you choose one over the other?






Statically typed languages have their advantages, but sometimes it really is simpler to use a dynamic language.



The following is a simple implementation of factorial in Python: fact.py




#! /usr/bin/env python




import sys




def fact(n):




if n == 0:




return 1




else:




return n * fact(n-1)if len(sys.argv) != 2:




print("%s usage: [NUMBER]" % sys.argv[0])




exit()




print(fact(int(sys.argv[1])))




The following is a simple implementation of factorial in Ruby: fact.rb













def fact(n)




return 1 if n == 0




return n * fact(n-1)




end




if ARGV.length != 1




puts "fact.rb usage: [NUMBER]"




exit




end




puts fact(ARGV[0].to_i)




Rewrite gcdI and gcdR from gcd_full.c in Python and Ruby (they will syntactically and semantically be very similar).




In particular:




Create a file named gcd_full.py that contains an implementation of gcdI and gcdR in Python.
Create a file named gcd_full.rb that contains an implementation of gcdI and gcdR in Ruby.



Make sure to place the code in this file as well.




Page 38 problem 1.1 a-e.



True or False. Some programming languages are more "powerful" then others. Explain your answer.



[Rosen,Discrete Mathematics and Its Applications 5th ed., pg 273 #48] "Consider the following inductive definition of a version of Ackermann's function. This function was named after Wilhelm Ackermann, a German mathematician who was a student of the great mathematician David Hilbert. Ackermann's function plays an important role in the theory of recursive functions and in the study of complexity of certain algorithms involving set unions." In the early days of imperative languages, Ackermann's function was used to measure the recursion capability of a compiler.



The Ackermann Number N of the compiler as the largest N for which ack (3,N)




gives an answer without a stack overflow. In earlier decades a variation had been used as one of the benchmarking algorithms. (There are several different variants of this function. All are called Ackermann's functions and their values do NOT have to agree!)










ack( m,n ) =
n + 1
if m = 0
ack( m,n ) =
ack(m - 1, 1)
if n = 0 and m 0
ack( m,n ) =
ack( m-1, ack( m, n-1 ) )
if n 0 and m 0
What is the value of ack(1,0) ? ______



What is the value of ack(0,3) ? ______



Create a file named ack.c and implement ack in C. Try and find the largest Ackermann number for your program.



Create a file named ack.py and implement ack in Python. Try and find the largest Ackermann number for your program.



Create a file named ack.rb and implement ack in Ruby. Try and find the largest Ackermann number for your program