Due: Wednesday, April 9, 2025 11:59 pm

Part I: C Semantics

The purpose of this part is to understand the function handler in C, how to implement polymorphism in non-object-oriented languages such as C.

Tasks

1. Given an array of random integers, sort the array in a way that the even numbers appear first and the odd numbers appear later. The even numbers should be sorted in descending order and the odd numbers should be sorted in ascending order. For example, given [3, 8, 2, 9, 1, 6], the output of your program should be [8, 6, 2, 1, 3, 9].

   Download the template of the program. Read and understand the program. Implement your comparator function. Compile and run the program. The output of the program should be as follows. Include a screenshot of your output in the README file and explain how you implement the comparator function.

   	The sorted array is: 12 10 8 6 4 2 0 1 3 5 7 9 11 13 
   

2. Create a new file for this task. Write a function that takes in an integer argument and returns its factorial value as an integer.

   In your main function declare a variable calc as

   	int (*calc)(const int)
   

   Assign your factorial function to calc, then use calc to execute the function. Print out its return value. What does this demonstrate with respect to types and functions in C? Include your answer in your report.

   Update your function so that it can take in an integer command-line argument. Pass it in as N to the factorial function. Then experiment and in your report include a screenshot of the output and explain what is happening when you go from 12! to 13! to 14! to 15!.

3. This task is to create a generic linked list class in C. First, create a Node struct that can hold an arbitrary pointer points at the data to be stored in the Node and a next pointer. Then, create a LinkedList struct that has a head pointer. You are free to use single- or doubly-linked lists. Then implement the following functions.

   • LinkedList *ll_create() creates a new LinkedList struct, initializes it, and returns it.
   • void ll_push(LinkedList *l, void *data) adds a node to the front of the list, storing the given data in the node.
   • void *ll_pop(Linked List *l) removes the node at the front of the list and returns the associated data.
   • void ll_append(LinkedList *l, void *data) adds a node to the end of the list, storing the given data in the node.
   • void *ll_remove(LinkedList *l, void *target, int (*compfunc)(void *, void *)) removes the first node in the list whose data matches target given the comparison function. The function returns the pointer to the data in the removed node.
   • void *ll_find(LinkedList *l, void *target, int (*compfunc)(void *, void *)) finds the first node in the list whose data matches target given the comparison function. The function returns the pointer to the data in the node. If the target is not in the list, then the function returns NULL.
   • int ll_size(LinkedList *l) returns the size of the list.
   • void ll_clear(LinkedList *l, void (*freefunc)(void *)) removes all of the nodes from the list, freeing the associated data using the given function.
   • void ll_map(LinkedList *l, void (*mapfunc)(void *)) traverses the list and applies the given function to the data at each node.

   Please create the LinkedList described above following the requirements below.

   1. You are expected to have a header file including the Node struct, the LinkedList struct, and all the above function prototypes. Besides, a C file is needed to implement all the above functions.

   2. You can then test your linked list functions using this test file. Compile using:

      gcc -o clltest clltest.c yourLinkedList.c
   3. Extend the above test file so it uses a linked list with a second data type.
   4. In your report, include a screenshot of the output of clltest for both the original and second data types.
   5. In your report, explain why freefunc is a necessary parameter for the ll_clear function. Invent an eample in which there would be a memory leak if the freefunc were incorrectly supplied by the caller or not used by ll_clear.

Part II: Semantics of Selected Languages

In this part you'll explore both the syntax and semantics of certain types of statements in your chosen language.

Tasks

1. Implement a general sort algorithm (e.g., quick sort, merge sort, bubble sort, insert sort, ...) that can be used for any type and can be used to obtain any desired order (or as close as you can get). Write a test program for your implementation, and demonstrate your algorithm works with more than one type. (Note that you must implement your own sorting function - don't use built-in sort function.) Include a screenshot of your testing result in your report.

2. Implement a LinkedList class in your selected language, making use of some form of polymorphism to implement the data structure. Create the same set of functions as above, but adapt the data types, as necessary. If your language enables templates or generics, use them. Create a test file like the C test file that demonstrates you can create linked lists to store two different types of data.

   Your selected language may have a built-in list data type, similar to Python. Can you create similar functions without using it? If not, then write code that models each of the functions listed for the API and note any additional capabilities the built-in type has. See if you can figure out how the internal data structure is implemented by doing some timing tests and looking at the results. For example, if the built-in structure is a linked list, then searching it should take linear (O(N)) time.

   Include a screenshot of your testing result for the LinkedList in your report.

3. Generate a Google Sites page that shows the examples in your language. You can use the code snippets of the general sort and LinkedList class as examples. Explain how the language makes use of polymorphism. If your language has generics or templates, explain how it is implemented. These do not need to be long or detailed explanations, but should identify the benefits and drawbacks of the implementation method.

Extensions

1. A perfectly acceptable extension for any assignment going forward is to do a second language. You are encouraged to pick the second language from List B or C.
2. Explore the precedence and semantics of the C memory operators like & and *, or look at whether your languages have similar capabilities.

3. Make a compilable and runnable haiku in the language that helps to demonstrate the meaning of a statement in the language.

   The haiku Python def shows how the def function adds a new symbol to the computer's state which can subsequently be called.

   You can also choose to make a compilable and runnable haiku in the language that helps to demonstrate the concept of polymorphism. poly.py

4. Make your comparator function for qsort as efficient as possible. For example, make it uses less operations and control flow statements. Use it to sort a large array. Observe the computation time, and compare it with the less-efficient version if possible. Explain why your implementation is efficient in the comments.
5. Implement your own sorting function, say MergeSort or HeapSort, in C.
6. Implement more than one method of creating a generic implementation of a data structure in your selected language. Explain how the methods differ and any benefits/drawbacks.
7. Implement the delete function for your linked list in C that can remove the node at any given position in the list.
8. Improve clltest.c and make the program memory leak free.

Please note that it is your responsibility to explicitly indicate the extensions you have undertaken. If you complete the extension for the C tasks, please indicate that explicitly in the code and report file. If you complete an extension in a selected language, please indicate this explicitly in your Google Sites report. Along with each extension, indicate if you completed it with a partner.

Submission

The submission of this project has two components:

1. Create a folder named Project4_<username> Place the required files into it, zip it, and upload it to the Google Classroom.

   Required Files::

   1. Code: Create a fold for each language, including C and your selected language(s). Place all of your C code and selected language programs to corresponding folders. It should be clear which files correspond to which tasks. All these language folders should be placed into the Project4_<username> folder. Note that the quality of your comments counts toward your grade.
   2. README: We use markdown files for README files. Markdown files are files with the .md filename extension. Each project should have a README file along with all your source codes. The README file will contain:
      • Project identifier, your name, and the submission date.
      • The URL of your Google Sites report.
      • The directory layout for your hand-in folder. You can use the Unix tree command to generate this.
      • Your operating system and C compiler (e.g. use gcc --version).
      • For each task, include how to compile your program, how to run your program, known bugs if there is any, and the program output (a screenshot). The screenshot should include the actual output of running the program if the output is no more than 100 lines. Otherwise, give a brief version of the output.
      • Text and images reporting on the C part of the project.
      • A description of each extension you undertook (for the C part of the project).

      You can follow the instructions for the README file from Project 1.

2. Google Sites Report: The report of this project should have the following elements.
   • Title of the project and your name
   • A section for each task of part II. Every section should contain the snapshot of your sample programs, the outputs, and your explanations.
   • If you complete extensions in your selected language, please include a section for each extension, providing sample programs, outputs, and explanations.

   To check whether you've made your report well organized, please follow the Organization part in the Google Sites section in this writing page. Remember to publish all your changes and include the homepage link of your CS333 Google Sites in the README file.

© 2025 Ying Li. Page last modified: .