Question 1a: Advanced Linked Lists

[bonus 10% for Q1 doubly linked lists]

typedef struct NODE { typedef struct NODE { value_typekey_type key value; ; or value_typekey_type key; value;

struct NODE * next; struct NODE * next; struct NODE * sort; struct NODE * sort;

} Node; struct NODE * prev; struct NODE * prev_sorted;

} Node;

In this linked list:

• The datatype for the value being stored is called value_type
• The datatype for the key being stored is called key_type
• As in lab 4, next links to the node in the order it was added to the list (either at the head or the tail) o This will be referred to as insertion order
• Similar to lab 4, sort links to the node where the key is greater or equal to its key o e. the list is kept in ascending order by key o This will be referred to as key sort order o Note: unlike lab 4, there is only one key

Create a Sorted List abstract data type

• Has two heads (head for insertion order, head_sort for key sort order)
• Has two tails (tail for insertion order, tail_sort for key sort order)
• Has an int field called size that stored the node count (the number of elements in the list)
• The datatype should be called Sorted_List

Note: technically you will be implementing only be a subset of the Sorted List ADT as you will not be asked to implement all functions of the full ADT

Functions to be implemented

All functions, except where noted, return SUCCESS if the function can complete or FAIL if not

• int size (Sorted_List *)
  • returns the number of nodes in the list (not SUCCESS/FAIL as the function cannot fail)
• int push ( Sorted_List *, value_type , key_type )
  • add the node to the head of the list
  • the node must also be inserted in ascending sort order by key, using the sort link
• int append ( Sorted_List * , value_type , key_type ) o similar to push, except the node gets added to tail
• int remove_first ( Sorted_List * , value_type * , key_type *) o removes the node from the head of the list
  • returns the value and key of the removed node through the parameter values

(and frees the node) o returns SUCCESS (alternatively you can change the signature to return void) o remember to update the sort order links

• if not using doubly linked lists, you will need to find the previous sorted node to change its sort order link

• int remove_last ( Sorted_List * , value_type * , key_type * )
  • similar to remove_first, except it removes the node from the tail
• int remove_smallest_key ( Sorted_List * , value_type * , key_type * ) o removes the node with the smallest key
  • returns the value and key of the removed node (and frees the node) o remember to update the insertion order links
    • if not using doubly linked lists, you will need to find the previous insert order node to change its insertion order link
  • int remove_largest_key ( Sorted_List * , value_type * , key_type * )
    • similar to remove_smallest_key, except it removes the node with the largest key
  • void empty_list ( Sorted_List *)
    • empties the contents of the list
    • remember to free the memory of the contents
  • void destroy_list ( Sorted_List *)
    • empties the contents of the list, as well as freeing the list itself

To test the Sorted List ADT

Write two programs called a4q1a_char.c and a4q1a_int.c

• Data types used o c
  • has its value_type datatype set equal to int
  • has it key_type datatype set equal to double o c
  • has its value_type datatype set equal to char[80]
• e. it can take strings up to 79 characters in length
• has its key_type datatype set equal to int
• its value is set equal to the length of the string
• Both programs read in a text file that contains a series of commands, one per line

(i.e each ending with a newline) o The name of the text file should be entered as a command line argument

• If there is no file name, read from stdin
• this can use IO redirect, i.e. a4q1a_int < filename.txt
• If using keyboard input, exit using ^d
• All commands are echoed to stdout, followed by a colon :, o After that the results of the command follows,
• usually on the same line following 11 strlen(cmd name) spaces or on the next line when noted

Note: Silent commands do not have the colon : after the command, but rather after the command name

• Remember to free the sorted list at the end of the program (use destroy_list)

General Note: The two programs should be almost identical, with the following differences o The file input will be slightly different depending on the data type and nature of the input data o Your will have to write similar, but not identical void print_list_all ( Sorted_List * ) and void print_list_sort ( Sorted_List * ) functions

• These functions print out the lists according to their respective sort orders
• See the report commands section below for details

(the print_all and print_sort commands)

o You will have to have your make file recompile all files that mention or use value_type and key_type variables or Sort_List structs when compiling the two programs

• To do this you will need to use condition compilation (see Week1 lecture notes)
• In specific, use #ifdef CHAR to compile using the char[80] typedef definition of value_type

and #ifdef INT to compile using the int typedef definition of value_type

• g. if you stored all your Sort_List ADT functions in a single file called sort_list.c Then for a4q1a_char.c you could have in your make file a command like

gcc -Wall -ansi -DCHAR -c sort_list.c

List of Commands

Silent Commands (modifies the list but does not print anything other than the command itself)

• a = append

o a4q1a_int.c

• input line: a key value

note: there can be any number of spaces in the input been the command and args, or between args

• example

• commands, as stored in the input file

a 3.27 1427 a 0.94 984

a 7.21 346

• output(11 1 spaces after the colon)

a: 3.27 1427 a: 0.94 984 a: 7.21 346

• c
  • input line: a value
  • example
  • commands, as stored in the input file

a The sun did not shine. a It was too wet to play. a So we sat in the house a All that cold, cold, wet day.

Note: skip the white space between the command a and the input string

• The key values for the above are 22, 23, 22, 29

• g. strlen(The sun did not shine.) == 22
  • output (11 1 spaces after the colon)

a: The sun did not shine. a: It was too wet to play. a: So we sat in the house a: All that cold, cold, wet day.

• p = push o same as a except it pushes instead of appends the key/value pair onto the list

Verbose Commands (modifies the list and then reports to stdout)

• rem_first = remove first node of the list by insertion order o also prints the elements key-value pair, with two spaces between the key and the value

• Example for c assuming the first list element key is 2.465 and value is 212 rem_first: 2.465 212
• Note the two spaces after rem_first: rem_first is 9 characters in length, so the number of spaces following should be 11 9 = 2
• If the list is empty, remove will fail. It should print then print the following rem_first: Nothing to remove
• rem_last = remove last node of the list by insertion order and print the elements key-value pair
• rem_small = remove the node with the smallest key and print the elements key-value pair rem_large = remove the node with the largest key and print the elements key-value pair
• empty = empty the list o the output of this command should be

empty: size = 0

Report Commands (prints information, but does not modify the list)

• size = size of sorted linked list

o if there are 21 nodes in the list it prints size: List size = 21

• print_all = print list in insertion order o The type of order is printed on the same line as the command o The list starts printing on the next line, one element per line

o Each element is prefaced by 5 spaces, then the key, then 2 spaces, then the value o Example using the input from the append examples

• a4q1a_int.c print_all: Insertion Order

3.27 1427

0.94 984

7.21 346

• a4q1a_char.c print_all: Insertion Order
  • The sun did not shine.
  • It was too wet to play.

22 So we sat in the house 29 All that cold, cold, wet day.

• print_sort = print list in key sort order o The output is the same as with print_all except the order of the lines are in key sort order and the command line will read Key Sort Order

o Example using the input from the append examples

• a4q1a_int.c print_sort: Key Sort Order

0.94 984

3.27 1427

7.21 346

• a4q1a_char.c

print_sort: Key Sort Order

22 The sun did not shine.

• So we sat in the house
• It was too wet to play.

29 All that cold, cold, wet day.

The assignment continues with Question 1b Function Pointers to be released by March 26

the relevant lecture notes for Q1b, presented the last week of face-to-face classes, have now been posted

Question 1b: List ADT and Function Pointers

Using the same data type Sorted_List as in q1a,

Implement

• Sorted_List * map ( Sorted_List *, fn ptr) o map only applies to the values, not the sort keys

o however, make sure that the new list produced has the same key values and links (both next and sort)

• value_type reduce ( Sorted_List *, reduce fn ptr, value_type init, int order ) o like map, reduce only applies to values, not keys

o however, reduce also takes an extra parameter, int order

• order is either INSERTED_ORDER or SORTED_ORDER and determines which set of links to follow while reducing: next or sort respectively
• note: while the order of the reduction does not matter when using add or mult as the reducing function, it could with other reduction functions

• value_type map_reduce (Sorted_List *list, map fn ptr, reduce fn ptr, value_type init, int order ) o Conceptually, you are first applying map, and then reduce

o However, both map_fn and reduce_fn should be applied together, node-by-node

• e. do not create a full map list and then apply reduce to it
• instead apply the map function to lists node, then store the result in the reduce accumulator

o This allows you to avoid creating and freeing the memory that would be used if an intermediate map list were to have been created and only then reduced

• value_type * map_2_array ( Sorted_List *list1, List_Sort *list2, fn ptr, int order) o map_2_array takes two lists and applies a function, passed in as a function pointer, that takes two values (from the nodes at the same position in their respective lists) and returns a value of type value_type
  • The values are collected in an array with element type value_type in the same order as traversed along the links chosen (i.e. next if INSERTED_ORDER was chosen or sort if SORTED_ORDER was)
  • the function then returns the above array

note: unlike map, order of traversal matters with map_2_array as different nodes will be paired together depending on the order

• value_type map_2_reduce( Sorted_List *list1, List_Sort *list2, map fptr, reduce fptr, int order) o Similar to map_reduce,

o However, node by node, it should

• apply the map function to the value of list1s node as its first argument and the value of list2s node as its second argument
• then store the result in reduces accumulator

Below list1 and list2 only depict the value and next fields

where add and mult are functions that take two int arguments as seen in the reduce example in the lecture notes

Figure 1: Example of map_2array and map_2_reduce using INSERTED_ORDER

list1 and list2 are the same as before,
but now depict the key and sort fields where key was set equal to value

Figure 2: Example of map_2array and map_2_reduce using SORTED_ORDER

To test within, map, reduce, etc.

Write a program called a4q1b.c

• Data types used
  • value_type datatype is equal to int o key_type datatype is equal to double o same as a4q1a_int.c, so compile files containing Sorted_List functions using -DINT
• The program reads in a text file that contains a series of commands, one per line, with the name of the text file entered as a command line argument o Base this code on the code you used in q1a to implement command entries from a file o However, the code will need to be extended to allow for new commands that are detailed below
• Again, all commands are echoed to stdout, followed by a colon : in the same format as used with q1
• Include a void print_array(value_type *, int size) o this prints out values in the array produced by map_2_array
  • the values in the array should be printed one per line, with five spaces preceding the value
• Make sure you have declared an array that can hold up to 10 Sorted_List pointers o Do not confuse this with the array produced by map_2_array, this array holds Sorted_List pointers not value_type values.
• Remember to free all sorted lists and nodes (and arrays that may contain them) at the end of the program

To implement the new commands, write the following functions use either map, reduce, map_reduce, map_2_array, or map_2_reduce when implementing

sum

o sums the values of a list and returns the sum o see lecture notes

• diff o takes two sorted lists of the same size
• returns NULL if the sizes are different o produces an array whose values are the differences of the values in the sorted lists args o you should also take a third argument that can be set to SORTED_ORDER or INSERTED_ORDER in order to follow the appropriate links
• square o takes a sorted list and produces a new sorted list whose value at a node equals the original value (not key) squared

o the keys and links should be copied unchanged

• sum_of_sq_diff o takes two sorted lists of the same size
  • returns NULL if the sizes are different o produces a value computed as follows:
  • at each node position, take the difference between the values
  • square the resulting difference
  • sum across all nodes into a single result o you should also take a third argument that can be set to SORTED_ORDER or INSERTED_ORDER in order to follow the appropriate links

note: these should be 1 or 2 line programs that take function pointers to functions that are also only a few lines long

List of Commands

All commands from q1a should be made available as well as the following

Silent Commands (modifies the list but does not print anything other than the command itself)

• a|n key value
  • append to the nth index of the array of sorted list pointers that you have set up for the program to use (see the 5^th point on how to set up the program two pages back)
  • same as the a command but appends the key/value pair into the array of sorted lists
• p|n key value

o same as a|n except it pushes instead of appends the key/value pair into the array of sorted lists

Report Commands (prints information, but does not modify the list)

For all examples, the sorted list at index 3 holds the values <1, 2, 3> where the key equals the value the sorted list at index 5 holds the values <3, 1, 7> where the key equals the value

• print_all|n
  • print the sorted list at index n in insertion order
  • Using the input from the append examples in q1a that had been stored at index 2

For the command print_all|2, the output should be

print_all: list = 2, Insertion Order

3.27 1427

0.94 984

7.21 346

• print_sort|n

o print the sorted list at index n in key sort order

• sum|n

o sums the values of the sorted list at index n o For the command sum|3, the output should be sum: list = 3, result = 6

• square|n o For the command square|3, the output should be square: list = 3

1.0 1

2.0 4

3.0 9

o remember to free any new list produced, after it has been printing

• diff|n:m order o For the command diff|5:3 INSERTED_ORDER, the output should be diff: list1 = 5, list2 = 3, Insertion Order

2

-1

4 o remember to free any new list produced, after it has been printing

• sum_sq_d|n:m order o For the command sum_sq_d |5:3 INSERTED_ORDER, the output should be sum_sq_d: list = 5, list2 = 3, Insertion Order, result = 21

The assignment continues with Question 2: Recursion

Question 2: Recursion

2a. Recursive functions

• Implement the following functions using recursion (see the next page for examples) o Count up from 0 to n o Count down from 2n to 0 by 2 o nth, nth_sorted
• this applies to Sorted Lists from Q1a o remove_nth, remove_nth_sorted
• this applies to Sorted Lists from Q1a

note: no marks will be awarded if implemented iteratively, even if the answer produced is correct when run

2b. Greatest Common Divisor (GCD)

• Read up on the Euclidean Algorithm for solving GCD in Wikipedia o First Section: https://en.wikipedia.org/wiki/Euclidean_algorithm o Procedure: https://en.wikipedia.org/wiki/Euclidean_algorithm#Procedure o Example: https://en.wikipedia.org/wiki/Euclidean_algorithm#Worked_example o Using mod: https://en.wikipedia.org/wiki/Euclidean_algorithm#Euclidean_division o Implementations: https://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations
• Examine the final implementation, which is recursive, and implement it in C o it should have the signature long gcd(long, long)
• This implementation (as yours should be) is naturally tail recursive o explain why it is tail recursive in the readme

o make sure your make file uses the appropriate gcc flag to run tail recursive code efficiently

To test question 2

Write a program called a4q2.c

• The program must read in a text file that contains a series of commands, one per line, with the name of the text file entered as a command line argument o Base this code on the code you used in q1a to implement command entries from a file o However, the code will need to be extended to allow for new commands that are detailed below
• Some of the questions in 2a use the Sorted_List data type with key_type as double and value_type as int, the same as a4q1a_int.c.

o So when compiling files containing Sorted_List functions in your make file, use DINT

• All new commands for entry from the input file are listed on the next page

The assignment concludes with Question 3: Fraction ADT to be released early next week

List of Commands from the Input File

All commands from q1a should be made available as well as the following

• count_up n

o Prints the integers from 0 to n on a single line, comma separated, with 5 spaces before o Using the following commands count_up 4 the output should be

count_up from 0 to 4

0, 1, 2, 3, 4

• count_down n

o Same as count_up, but printing the integers down from 2n to 0 on by 2 o Using the following commands count_down 4 the output should be

count_down from 8 to 0 by 2

8, 6, 4, 2, 0

• nth n order o Displays the nth element in the list according to the order specified (inserted or key sort) on its own line as key value
  • Indented 5 spaces with 2 spaces between the key and the value
  • Firsts prints the command see below for an example o Using the input from the append examples in q1a and the following commands print_all nth 1 INSERTED_ORDER nth 1 SORTED_ORDER nth 5 INSERTED_ORDER the output should be

print_all: Insertion Order

3.27 1427

0.94 984

7.21 346

nth: n = 1, Insertion Order

0.94 984

nth: n = 1, Key Sort Order

3.27 1427

nth: n = 5, FAILED, n >= size where size = 3

• remove_nth n order o removes the nth element in the list according to the order specified (inserted or key sort) and displays the removed element on its own line as key value

o Again using the input from the append examples in q1a For the commands

remove_nth 2 INSERTED_ORDER print_all

remove_nth 1 SORTED_ORDER print_all

the output should be

remove_nth: n = 2, Insertion Order

7.21 346

print_all: Insertion Order

3.27 1427

0.94 984

remove_nth: n = 1, Key Sort Order

3.27 1427

print_all: Insertion Order

0.94 984

Question 3: Interacting Abstract Data Types

New ADT Fraction

You may not use functions from any C library that implements fractions

typedef struct { long num; long denom; /* you may also use unsigned long denom, either approach is fine */

} Fraction;

• Implement int set_fraction(Fraction * fract, int num, int denom)
  • Sets the numerator and denominator in the Fraction structure o Only the numerator can be negative
    • If the denom parameter is negative, negate the num parameter and store denom in the struct as a positive value
  • The denom parameter cannot be 0
    • If it is zero do not set the num and denom in fract and return FALSE (where FALSE is a #define set to 0)
  • If the num and denom can be successfully set, return TRUE

(where TRUE is a #define set to 1)

• Implement print_fract(Fraction * fract, int mode) o When mode is SIMPLE
  • Print out num/denom
  • If fract has num = 4 and a denom = 3 it should print 4/3 to stdout o When mode is MIXED
  • If fract has num = 3 and a denom = 4, print 3/4 to stdout
  • If fract has num = 4 and a denom = 3, print 1 1/3 to stdout
  • If fract has num = 4 and a denom = 1, print 4 to stdout o SIMPLE and MIXED are two integers of your choice, using #define in a .h
• Implement void simplify(Fraction * fract)
  • This is computed by finding the GCD of the numerator and the denominator and dividing it out from each respectively i.e. for a / b
• find g = gcd(a, b)
• the simplified form of a / b is

(a/g) / (b/g)

• e.g. 6/18
• gcd(9, 12) == 3 (9/3) / (12/3) == 3 / 4

note: when you wrote GCD for Q2, qcd(a,b) should equal gcd(b,a)

• Implement int add_fract(Fraction * result, Fraction * x, Fraction * y)

o To compute a/b + c/d, i.e. to add two fractions, use the following formula

(a d + b c)/b d , simplified o Check to make sure that the result doesnt overflow/underflow

• e the addition produces a result greater than a long can represent
• when the result is positive it is called an overflow
• when negative it is called an underflow o to check for an overflow/underflow, understand and use the solution posted in the most popular reply from the following stackoverflow page
• https://stackoverflow.com/questions/199333/how-do-i-detect-unsigned-integer-multiply-overflow o If the addition overflows/underflows, return FALSE and do not update fract o Otherwise return TRUE

Extend Map/Reduce/etc. with Filter

• Implement Sorted_List * filter (Sorted_List * list, filter_fn pointer)
• the function creates a new sorted list based on the filtered values (added node by node), remember the nodes have to be copied
• the function filters based on the value, not the key o for full marks, implement filter() using recursion
• store filter() in the same .c file where the other map/reduce/ etc. functions are stored
• you do not need to submit two different .c files, just one will do filter will just not be exercised when the Q1b is tested

To test question 3

Write a program called a4q3.c

• The program must read in a text file that contains a series of commands, one per line, with the name of the text file entered as a command line argument o Base this code on the code you used in q1a to implement command entries from a file o However, the code will need to be modified as detailed below
• You will need to store fractions in a sorted list using the Sorted_List data type o value_type should be of type Fraction

o key_type should be a double and hold the decimal equivalent of the value stored in the Node

• e.g. if value stores the fraction 11/4, then key == 2.75
• You will have to have your make file recompile all files that mention or use value_type and key_type variables or Sort_List structs when compiling the program o You will need to add #ifdef FRACT to compile using the Fraction typedef definition of value_type

o E.g. if you stored all your Sort_List ADT functions in a single file called sort_list.c Then for a4q4.c you could have in your make file a command like

gcc -Wall -ansi -DFRACT -c sort_list.c

• All commands for entry from the input file are listed on the next couple of pages

List of Commands from the Input File

You only need a single Sorted List, like in q1a, and q2, not the array of sorted lists as in q1b

Silent Commands (modifies the list but does not print anything other than the command itself)

• a n/d

o appends to a sorted list

• with n stored in the numerator field of the Fraction held in node->value, and d stored in the denominator field of the Fraction
• the decimal value equivalent of the fraction should be stored in the key field

note: when echoing the command, the fraction is output without simplification and the key is displayed with 3 decimal places o example

• commands, as stored in the input file a 5/4 a 3 a 4/6
• output(11 1 spaces after the colon)

a: 1.250 5/4 a: 3.000 3 a: 0.667 4/6

• p n/d

o same as a except it pushes instead of appends the key-value pair onto the sorted list

Report Commands (prints information, but does not modify the list)

• print_all print_mode

o print the sorted list at index n in insertion order o Using the input from the append examples above

For the command print_all SIMPLE, the output should be

print_all: Simple Fractions, Insertion Order

1.250 5/4

3.000 3/1

0.667 2/3

• print_sort print_mode

o print the sorted list at index n in key sort order o Using the input from the append examples above

For the command print_sort MIXED, the output should be print_all: Mixed Fraction, Sorted Order

0.667 2/3

1.250 1 1/4

3.000 3

• sum print_mode o sums the values of the sorted list into a simplified fraction, which is printed (in insertion order) o Using the input from the append examples above For two commands sum SIMPLE sum MIXED

the output should be

sum: result = 4 11/12 sum: result = 59/12

o If the sum enters an overflow situation, the output should be sum: result = OVERFLOW

• This could happen in either the numerator or denominator at any point in the calculation
• If the numerator would be negative, instead of OVERFLOW, it should print UNDERFLOW

• fract print_mode o uses the filter function to only keep fractions and ignore whole numbers when producing the new sorted list; then print the filtered list

o remember to free the new list produced by filter after printing

(hint: you had to do that for various commands in q1b as well) o Using the input from the append examples above

For the command fract MIXED, the output should be fract: Mixed Fractions, Insertion Order

1.250 1 1/4

0.667 2/3

• whole_num print_mode o similar to fract except it uses the filter function to filter out all fractions leaving only the whole numbers in the new list

o Using the input from the append examples above

For the command whole_num MIXED, the output should be

whole_num: Mixed Fractions, Insertion Order 3.000 3

• rem_mixed print_mode o similar to fract except it uses the filter function to keep only the whole numbers and simple fractions (removes the mixed numbers)
• i.e. leaving out the numbers that, when printed as MIXED, have both a whole number and fraction parts, such as 7 2/3

o Using the input from the append examples above

For the command rem_mixed MIXED, the output should be

rem_mixed: Mixed Fractions, Insertion Order

3.000 3

0.667 2/3