Description
Question 1 [16 marks] (submit question1.c)
Recall the Quicksort algorithm where items are sorted by picking a “pivot” and rearranged by comparing
their values with the pivot.
Implement the Quicksort algorithm by writing a function that takes in a C string array, its size, and a bool
variable indicating whether it is sorted according to length or alphabetical order. Use this function header:
void quicksort_cstrings(char* stringArray[], int size, bool byLength)
Hint: You are likely going to implement a few helper functions like swap and partition to make the code
more manageable. For the implementation of the partition function, choose the last item as the pivot.
You can also use functions from string.h which is already included for you in question1.h.
You can assume that each word contains no space and has 1 to 63 characters. The user will input a nonnegative number for number of words and if it is 0 the program will print “No words to be sorted.”.
For example, here is the output generated by the provided test1.c file when the user inputs 0:
As another example, if the user inputs 5 words: of, cute, A, lot, birds, then the order sorted by length
(byLength variable is true) is: A, of, lot, cute, birds; whereas the order sorted by alphabetical order
(byLength variable is false) is: A, birds, cute, lot, of:
Assignment 3 CMPT 125 Intro. To Computing Science & Programming II Spring 2021
Page 2 of 6 © Victor Cheung, 2021
As shown in the test1.c file, since the number of words is unknown, malloc is used to create enough
memory for the inputs. If malloc fails, the program terminates by calling the function: exit(0)
Only include the function definition(s) in your answer and name the source file containing it as question1.c.
You must implement the sorting algorithm without using predefined sorting functions.
Question 2 [20 marks] (submit question2.c)
Recall in Assignment 2 Question 3 you were asked to define the enum Suit, struct Card, and struct Deck,
along with the NUM_OF_CARDS_IN_DECK token defined as 52:
• The enum Suit has 4 values: Spades, Hearts, Clubs, Diamonds
• The struct Card has 2 fields: Suit called suit, char called value
• The struct Deck has 2 fields: char* pointing to a C string called brand, Card array of size 52 called
cards
First, write a function that initializes all the fields in a Deck variable by taking in the address of the variable
and a C string as the brand name. For each Card variable, it has a suit (of type Suit) and a value (of type
Char) that are ‘A’, ‘2’, ‘3’, …, ‘9’, ‘T’, ‘J’, ‘Q’, ‘K’. Use this function header:
void initializeDeck(Deck* theDeck, char* brandName);
Next, write another function that shuffles the cards in the cards field. This shuffling can be achieved by
the Fisher-Yates shuffle algorithm that can be found here (refer to the answer by John Leehey):
https://stackoverflow.com/questions/6127503/shuffle-array-in-c
Use this function header:
void shuffleDeck(Deck* theDeck);
Assignment 3 CMPT 125 Intro. To Computing Science & Programming II Spring 2021
Page 3 of 6 © Victor Cheung, 2021
Note that in the provide test2.c file there is a call to the “srand(0)” function, which starts the random
number generator properly. Do not modify or call this “srand(0)” in your answer as this will make the
numbers generated unpredictable and thus difficult to mark. You will only need to call “rand()” everytime
you want a random number generated for you.
Lastly, write a function that prints the cards of a Deck 13 cards per row. Use this function header:
void printDeck(const Deck* theDeck);
Read carefully at the sample output. In particular, there is no space in the front and the back of each row,
but a space between each card. To print the suits, refer to the following sample printf calls:
printf(“\u2660\u2663”); //prints the spades symbol followed by the clubs symbol
printf(“\u2661\u2662”); //prints the hearts symbol followed by the diamonds symbol
You will notice that some operating systems, for example, Windows, do not print the symbols properly. If
that happens, run your code in a CSIL workstation or some online coding IDEs.
Above: suit symbols properly printed in a CSIL workstation. Second group is shuffled.
Above: suit symbols not being properly printed in a Windows 10 machine. Second group is shuffled.
Only include the function definitions in your answer and name the source file containing them as
question2.c. Use the definitions of the structs and enum provided in question2.h for your answer.
Assignment 3 CMPT 125 Intro. To Computing Science & Programming II Spring 2021
Page 4 of 6 © Victor Cheung, 2021
Question 3 [12 marks] (submit question3.c)
Implement the following functions of a stack that stores C strings as its items(read the .h file for full details
on how each function should behave):
cStringStack* cStringStack_create();
void cStringStack_push(cStringStack* csStack, char* cStr);
char* cStringStack_pop(cStringStack* csStack);
bool cStringStack_isEmpty(cStringStack* csStack);
void cStringStack_free(cStringStack* csStack);
void cStringStack_reverse(cStringStack* csStack);
cStringStack* cStringStack_duplicate(cStringStack* csStack);
Note that since the number of C strings to be stored is unknown, your implementation should dynamically
grow/shrink by requesting/releasing memory to add/remove items. It must not use any size in advance.
The provided test3.c file implements a simple program that reads in user inputs and stores them into the
stack structure. It will only be fully working if you have correctly implemented all the functions above. See
the sample outputs as examples:
undo as the first command
Left: a sequence of inputs. Right: ended with the command “quit”.
Only include the function definitions in your answer and name the source file containing them as
question3.c.
Assignment 3 CMPT 125 Intro. To Computing Science & Programming II Spring 2021
Page 5 of 6 © Victor Cheung, 2021
Question 4 [8 marks] (submit question4.txt)
In our lecture we mentioned the Binary Search algorithm can be implemented using recursion.
First, write the recursive formula of its time complexity, as well as the time complexity of the base cases
(when the array size is 0 or 1).
Next, derive the time complexity of the recursive Binary Search algorithm. Show your steps. To show
exponential terms, use ^ to denote the power, e.g., 2^3 means 2 to the power 3; to show bases, use _ to
denote the subscript, e.g., log_2(8) means log of 8 base 2.
Include the top comments as in the other files along with your answer, and name the file containing them
as question4.txt. Use a text editor to create this file (the same IDE you use for the assignment would work,
just make sure it has a .txt extension instead of .c or .h).
Coding Style [4 marks]
Your program should be correctly indented, have clear variable names and enough white space and
comments to make it easy to read. Named constants should be used where appropriate. Each line of code
should not exceed 80 characters. White space should be used in a consistent manner.
To help you to get into the habit of good coding style, we will read your code and marks will be deducted
if your code is not styled properly.
Using the Makefile and Other Supplied Files
The Makefile provided in this assignment is used by a command in the CSIL machines called “make” to
quickly compile your code. It is especially useful if you have multiple source files. To use it, type the
following command in the prompt (make sure you are in the directory with all the files of this assignment):
$ make test1
The example above illustrates how Question 1 is compiled into an executable called “test1” when using
the Makefile. Replace the “test1” with “test2”, …etc. for other questions. You can then run the executable
by typing “./test1” to test your code for Question 1. If you make changes to your code, use the make
command again. You can also use “make all” if you want to compile all files at once.
The test files (test1.c, test2.c, …etc.) are provided in this assignment for you to test your code. Each
typically contains a main function along with other tester functions and/or calls. You can modify them to
further test your code, but do not submit these test files because we will be using our test files that are
similar but not identical to grade your assignment. This makes sure that your code is not written to
produce hard-coded output.
The header files (question1.h, question2.h, …etc.) are there to make the compilation work. Ignore them,
do not modify them, and do not submit them.
Submission
Submit only the files indicated above by compressing them into a zip file (do not put them into a folder
and zip them) and upload it to Canvas by 11:59p Mar 19. Name the zip file in this format:
Assignment 3 CMPT 125 Intro. To Computing Science & Programming II Spring 2021
Page 6 of 6 © Victor Cheung, 2021
For example, John_Smith_012345678_Assignment3.zip
Assignment late penalty: 10% per calendar day (each 0 to 24 hour period past due), max 2 days late.
Academic Honesty
It is expected that within this course, the highest standards of academic integrity will be maintained, in
keeping with SFU’s Policy S10.01, “Code of Academic Integrity and Good Conduct.” In this class,
collaboration is encouraged for in-class exercises and the team components of the assignments, as well
as task preparation for group discussions. However, individual work should be completed by the person
who submits it. Any work that is independent work of the submitter should be clearly cited to make its
source clear. All referenced work in reports and presentations must be appropriately cited, to include
websites, as well as figures and graphs in presentations. If there are any questions whatsoever, feel free
to contact the course instructor about any possible grey areas.
Some examples of unacceptable behavior:
• Handing in assignments/exercises that are not 100% your own work (in design, implementation,
wording, etc.), without a clear/visible citation of the source.
• Using another student’s work as a template or reference for completing your own work.
• Using any unpermitted resources during an exam.
• Looking at, or attempting to look at, another student’s answer during an exam.
• Submitting work that has been submitted before, for any course at any institution.
All instances of academic dishonesty will be dealt with severely and according to SFU policy. This means
that Student Services will be notified, and they will record the dishonesty in the student’s file. Students
are strongly encouraged to review SFU’s Code of Academic Integrity and Good Conduct (S10.01) available
online at: http://www.sfu.ca/policies/gazette/student/s10-01.html.
