VG101 | Introduction to
Computer and Programming
Assignment 6
Manuel | UM-JI (Fall 2017)
a136 MATLAB: write each exercise in a di erent le
a136 C/C++: use the provided assignment template
a136 Include simple comments in the code
a136 If applicable, split the code over several functions
a136 Extensively test your code and impove it
a136 Write a single README le per assignment
a136 Zip all the les and upload the archive on Canvas
Ex. 1 | Structure, pointers, and functions
A point P in the complex plan can be de ned using either Cartesian or Polar coordinates.
1. Write two structures to represent a point in the complex plan. In the README le explain and
argue on your choices, including data types.
2. Write two functions to convert from Cartesian to Polar and from Polar to Cartesian. The functions
should use pointers such that more than one set of coordinates can be converted at a time. That
is the pointer could contain more than one complex number such that the function would returns
the conversion of all the complex numbers at once.
3. In the main function de ne the following complex numbers and convert them between Cartesian
and Polar coordinates: 3 + 45i, log(4)i, 45.245 + 0.235i, 3e i 17 , 4(cos 9 + i sin 9 ), e i 12 .
Speci cations.
a136 Organise the complex numbers into two arrays: Cartesian and Polar
a136 Prints the numbers by pair, one pair per line, the original number rst and the converted one second
Ex. 2 | Pointers, loops, and conditional statements
Write a C program that reads through an array of integers using pointers, and scan through it to nd all
the values larger than a randomly generated number r. The element r must be smaller than the max of
the array.
Speci cations.
a136 Start by reading the number of integers n
a136 Then read the n space separated integers
a136 On a new line display the output as space separated elements
Ex. 3 | Strings and le I/O
Write a program to nd the number of times a given string occurs in a sentence. The program should
read the sentence from a le called sentence.txt and the word from a le called word.txt. The output
should be printed in a le count.txt.
Speci cations.
a136 The binary, input, and output les are expected to be in the same directory
a136 Do not use absolute paths
a136 Do not prompt the user
Ex. 4 | File I/O, arrays, and loops
Read two matrices A and B from a text le called matrices.txt. Compute A + B, A B and AT BT .
Output the result into a text le named result.txt. Each row of a matrix is represented as a list of
integers separated by a space. When the end of a row is reached a new one starts on the next line. Two
matrices a separated by a blank line.
Speci cations.
a136 The binary, input, and output les are expected to be in the same directory
a136 Do not use absolute paths
a136 Do not prompt the user
a136 Output the resulting matrices in the order \addition, multiplication, transpose"
Partial sample output (ex. 4)
a36 ./h6 -ex4
1 2 3
2 3 4
5 6 7
9 8 7
4 3 2
5 7 2
Ex. 5 | Basic object oriented programming in C
A mathematical set is a collection of distinct objects, such as f1, 3, 9g, fr, g, bg, and f5, 11, 11g=
f5, 11g. Based on the multi-set header le below write in a corresponding set.c le the necessary
functions to handle a set (creation, deletion as well as adding and removing elements). Assume a set
can contain elements of type either char, int or double.
Hint: to resize a memory block use the function realloc.
Universal set header le (ex. 5)
1 #define INITSETSIZE 64 // Initial memory allocated for the set
2 #define CHAR 1
3 #define INT sizeof(int)
4 #define DOUBLE sizeof(double)
5 /* elem: list of elments; card: cardinal of teh set; type: data type (CHAR INT or DOUBLE) */
6 typedef struct universalSet { void *elem; int card; int type; } uset;
7 /* Initialize an empty set of given type and allocate the initial memory: INITSETSIZE*type */
8 void newSet(uset *set, int type);
9 void deletSet(uset *set); // Free the memory allocated by newSet
10 /* add elem to the set: check whether it is already in the set;
11 resize memory if card = allocated memory; new memory = previous+64
12 e.g. before: mem=128, card=128, after: men=192, card=129 */
13 void addElem(void *elem, uset *set);
14 /* remove elem from the set; do nothing if the set does not contain this elem;
15 resize memory if "too much memory" is used; new = previous-64
16 e.g. before: mem=192, card=129, after: card=128, mem=128 */
17 void remElem(void *elem, uset *set);
Ex. 6 | Coding quality
Review the previous assignment comparing your code to the samples provided by the TAs. Precisely and
clearly list all the aspects where you need to improve. The list can be in the form. of bullet points and
must be written in a separate text format le.
Note: common needed improvements relate to the README le, the quality of the algorithm, the
presentation of the code (spacing, indentation etc.), use and naming of the variables, etc.
Details each aspect that needs improvements and provide clear guidelines for leading to higher coding
quality.
Group Exercise
The goal of this exercise is to get a better understanding of pointers, while helping each others.
For a better result please apply the following suggestions.
a136 Start thinking of the problem as early as possible;
a136 Relate linked lists to arrays and think of the di erences;
a136 Think of the di erence between inserting/deleting the rst element and the last element;
a136 For a total of nine functions, each student is expected to write three. The workload
distribution should be detailed in the README le;
Remark: linked lists are a very common data structure, and many implementations are available
online. Do not reuse any code from others; Honor Code will be strictly applied.
Ex. 7 | Linked lists
1. Online research questions.
a) Explain what a linked list is?
b) List some applications of linked lists.
c) Search what kinds of linked list exist.
2. Programming questions.
a) The code provided below has been \compacted" in order to t over a single page. Reorganise
it writing no more than one instruction per line while respecting indentation.
b) Based on the header le below complete the implementation of the linked list.
Linked list header le (ex. 6)
1 #ifndef LIST_H
2 #define LIST_H
3 typedef struct node{ char ch; struct node *next; } node_t;
4 typedef enum{false, true} bool;
5 node_t *Initialize(char ch);
6 void PrintList(node_t *head);
7 void FreeList(node_t **head);
8 bool IsEmptyList(node_t *head); // Return true if the list is empty, false otherwise
9 void InsertFirstList(node_t **head,char insert_char); // Prepend a node
10 void InsertLastList(node_t **head,char insert_char); // Append a node
11 void DeleteFirstList(node_t **head); // Delete the first element in the list
12 void DeleteLastList(node_t **head); // Delete the last element in the list
13 int SizeList(node_t *head); // Return the size of the list
14 int SearchList(node_t **head, char target); // Count how many times target appears
15 void SplitList(node_t **head, node_t **tail, int pos); // Split into [0;pos-1] and [pos,end]
16 void MergeList(node_t **head1, node_t **head2); // Merge two lists
17 #endif
Linked list implementation (ex. 6)
1 #include
2 #include
3 #include
4 #include "list.h"
5 int ex6() {
6 node_t *a=Initialize(a391a39); node_t *b=NULL; PrintList(a);
7 InsertFirstList(a, a39Va39); InsertFirstList(a, a39Ma39);
8 PrintList(a); InsertLastList(a, a39Ca39); PrintList(a);
9 SplitList(a, b, 2); PrintList(a); PrintList(b);
10 DeleteFirstList(a); PrintList(a); InsertLastList(a, a39Ga39);
11 DeleteLastList(b); PrintList(b); InsertLastList(b,a390a39);
12 PrintList(b); InsertLastList(b, a391a39); PrintList(b);
13 MergeList(a,b); PrintList(a);
14 char target=a39Ga39;
15 printf("Count a39%ca39: %d\n",target, SearchList(a,target));
16 target=a391a39;
17 printf("Count a39%ca39: %d\n",target, SearchList(a,target));
18 FreeList(a);
19 return 0;
20 }
21 node_t *Initialize(char ch) {
22 node_t *head;
23 head=(node_t*)calloc(1,sizeof(node_t));
24 if(head==NULL){ fprintf(stderr,"Failed to assign memory!\n"); exit(-1); }
25 head->next=NULL; head->ch=ch;
26 return head;
27 }
28 void PrintList(node_t *head) {
29 node_t *temp=head;
30 printf("***Print Linked List***\n");
31 while(temp!=NULL) { printf("%c ",temp->ch); temp=temp->next; }
32 printf("\n****Print Finished****\n\n");
33 }
34 void FreeList(node_t **head) {
35 node_t *tmp=NULL; node_t *pHead=*head;
36 while(pHead->next!=NULL) { tmp=pHead; pHead=pHead->next; free(tmp); }
37 free(pHead);
38 }
Expected output (ex. 6)
a36 ./h6 -ex6
**Print Linked List***
1
***Print Finished****
***Print Linked List***
M V 1
***Print Finished****
***Print Linked List***
M V 1 C
***Print Finished****
***Print Linked List***
M V
***Print Finished****
***Print Linked List***
1 C
***Print Finished****
***Print Linked List***
V
***Print Finished****
***Print Linked List***
1
***Print Finished****
***Print Linked List***
1 0
***Print Finished****
***Print Linked List***
1 0 1
***Print Finished****
***Print Linked List***
V G 1 0 1
***Print Finished****
Count a39Ga39: 1
Count a391a39: 2
Groups