ESC190 Midterm, March 11.

Unless you have prior approval from Accessibility Services, you will write the midterm 
between 9:10am and 10:40am, and you MUST submit the midterm by 11am. Late submissions
without prior approval will not be accepted.

You may ask questions on the course Piazza. Please make the questions public if they may
apply to other people. Do not disclose parts of the solution when asking 
public questions. You may ask private questions, but we cannot help you debug your 
code during the test.


For all the questions, you may import stdio.h and stdlib.h, but not other libraries.

You must monitor announcements made by me on Piazza.

Aids allowed: you are allowed to consult the course website and the course textbooks.


1. (15 pts)
   Note that the number 523.12 can be written as
   5x10^2 + 2x10^1 + 3x10^0 + 1x10^-1 + 2x10^-2

   Write the function double my_atof(char *str) which takes in a string 
   that contains a number in decimal notation str, and returns its value as a
   double.
   You can assume that the input is valid. You can assume there will be digits both
   before and after the decimal point.

   You may *not* use any C library functions. You may write your own helper functions.

   Signature:
   double my_atof(char *str);
   
   Sample call:
   my_atof("523.12") # returns the double 523.12

   Double may not always be able to store the exact number. When testing, we will accept 
   answers that are accurate to within 0.0001. You do not need to worry about overflow.

   Submit the file Q1.c that contains the implementation of my_atof, and 
   *DOES NOT CONTAIN A MAIN FUNCTION*.


2. (15 pts)
   Write a recursive version of the function strncmp. A description of strncmp 
   is below:
   Compares up to num characters of the C string str1 to those of the C string str2.
   This function starts comparing the first character of each string. If they are
   equal to each other, it continues with the following pairs until the characters
   differ, until a terminating null-character is reached, or until num characters 
   match in both strings, whichever happens first.

   Return values:
   <0	the first character that does not match has a lower value in str1 than in str2
    0 	the contents of both strings are equal
   >0	the first character that does not match has a greater value in str1 than in str2

   "<0" means any negative number and ">0" means any positive number -- which numbers
   exactly you return is up to you.

   You may *not* use any C library functions. You may not use helper functions.

   Signature:
   int my_strncmp (char *str1, char *str2, int num );

   Sample call:
   my_strncmp("ESC180", "ESC190", 3); # returns 0
   my_strncmp("ESC180", "ESC190", 5); # returns a negative number


   Submit the file Q2.c that contains the implementation of my_strncmp, and 
   *DOES NOT CONTAIN A MAIN FUNCTION*.


3(a). (10 pts)
   Consider the following graph:

   A--B--C
      |
      |
      D-F-G  
   
   Write *two* possible depth-first traversals of the graph, starting from node A.

   Write two possible breadth-first traversals of the graph, starting from node G.

3(b). (5 pts)

   Explain why there can be more than one depth-first traversals.

   Submit the file Q3.c which only contain the answers to Q3(a) and Q3(b), as comments.
   Recall that you can make multi-line comments using
   /*
       
        your text here
   */ 
   

4. (35 pts)

   In this problem, you will implement a data structure that stores a set of integers, along with 
   operations for adding and removing elements and computing the union between sets.
   A set is a collection of distinct elements. For example, {3, 10, 2} is a set (note: we
   are using math notation, not C notation here). The union of the sets S1 and S2
   is the set that contains the elements present in either S1 or S2, or both.

   You must use a linked-list structure to implement set, and you must use intset.h.

   Your program will be compiled using gcc main.c intset.c.

   We may use a different main.c that uses the functions declared in intset.h

   Submit the file intset.c that contains the implementation of the functions
   declared in intset.h (along with any helper functions). The file intset.c MUST NOT CONTAIN
   A main function.