Description
COMP 2401 — Assignment #1
GoalYou will write a program in C, in the Ubuntu Linux shell environment, to translate an encrypted message into ASCII characters and print out the decrypted message to the screen. The encrypted bytes, set up as array of unsigned chars, can be found here: ciphertext.txtLearning Objectives• familiarize yourself with the Linux programming environment• write a small program in C that is modular, correctly designed and documented• manipulate values at the bit levelInstructions:1. Support Functions:• get/set/clear bitYou will implement the following bit manipulation functions, just as we saw in class:unsigned char getBit(unsigned char c, int n) returns the value of the nth bit of character cunsigned char setBit(unsigned char c, int n) returns the value of character c, with bit n set to 1unsigned char clearBit(unsigned char c, int n) returns the value of character c, with bit n set to 0• rotateYou will implement two functions that perform a circular rotation of the bits in a byte. One function is a rotation to the left, and the other is a rotation to the right. The function prototypes are the following:unsigned char rotl(unsigned char c) returns the value of c with its bits shifted left in a circular fashionunsigned char rotr(unsigned char c) returns the value of c with its bits shifted right in a circular fashion• swap two bitsYou will implement a function that swaps two bits in a byte. The function prototype is the following:unsigned char swapBits(unsigned char c, int pos1, int pos2)The function returns the value of c with its bits in positions pos1 and pos2 switched with each other.• encryptThe heart of the decryption algorithm (depicted in Figure 1) is the encrypt function, which is a permutation cipher that takes one byte and changes some of its bits depending on the value of a key. The result is the changed byte. You will implement this function, using the following prototype:unsigned char encrypt (unsigned char c, unsigned char key)The overall logic of the encrypt function is the following: start with the value of the c as the basis for the resulting byte examine each bit of the key, starting at the most significant bit if the current bit of the key has value 0, swap the following two bits of the resulting byte: the bit in the current bit position, and the bit two positions to the left (circling back to the least significant bits, if necessary) if the current bit of the key has value 1, perform a circular right shift on the resulting byteCOMP 2401 — Assignment #1 Fall 2013 2/32. Decryption algorithmThe decryption algorithm has the following structure:Figure 1 — Decryption AlgorithmThe encrypted message, known as ciphertext, is processed one byte at a time. It is shown in Figure 1 as C0 through Cn, where n is the length of the ciphertext. The plaintext is the corresponding readable, decrypted byte. It is shown as P0 through Pn. The Key and the initialization vector (IV) are initial values that are known beforehand. You can find these values in a header file located here: a1Defs.hYou will implement the decryption algorithm, as depicted in Figure 1. Your program will process the ciphertext one byte at a time, and print out the corresponding plaintext bytes.The algorithm works as follows. At every iteration i:• encrypt the value of IVi using the key• exclusive-or (XOR) the value of Ci with the encrypted IVi to compute the value of Pi• perform a circular left shift on the value of the encrypted IVi to compute the value of IVi+1Notes: You may use the XOR bitwise operator in C. The sizeof function can compute the length of the ciphertext.Constraints• you must include the given header file in your program and use the function prototypes exactly as stated• do not use any global variables• you must use all the support functions that you implemented in Part 1, and reuse functions everywhere possible• your program must be thoroughly commented• programs that do not compile, do not execute, or violate any constraint are subject to severe deductions• late assignments are never acceptedCOMP 2401 — Assignment #1 Fall 2013 3/3SubmissionYou will submit in cuLearn, before the due date and time, one tar file that includes all the following:• all source code• all data files required for your program to execute• a readme file, which must include:o a preamble (program author(s), purpose, list of source/header/data files)o exact compilation commando launching and operating instructionsGrading• Marking breakdown:ComponentMarksget/set/clear bit functions6rotate functions20swap two bits function10encrypt function35decryption algorithm24printing result5• Assignment grade: Your grade will be computed based on two criteria:o completeness of the program functionality and its executiono quality of the implementation You must familiarize yourself with the grading rules• Bonus marks: Up to 5 extra marks are available for fun and creative additional features
COMP 2401 — Assignment #2
Goal
You will write a program in C, in the Ubuntu Linux shell environment, to simulate the use and operation of a function call stack. Every time a function is called, a new stack frame is created to contain information about that function, and the stack frame is added to the function call stack in LIFO (last-in-first-out) order. When the function returns, the corresponding frame is removed from the call stack.In this assignment, you will:• define the data types and structures required to represent the function call stack; you will use arrays to represent all collections of data• write a main function that prompts the user for a collection of integers and calls one of two given sum functions (one iterative and one recursive) to add the integers together• modify the given sum functions to call instrumentation functions upon entry and return• write two instrumentation functions: one that initializes and adds a frame to the function call stack when a sum function is entered, and one that removes a frame from the call stack when a sum function returns; both instrumentation functions output the contents of the call stackLearning Objectives• understand and modify existing code• work with arrays and perform simple pointer manipulations• get familiar with the basic operation of the function call stack mechanism• compare the operation of the call stack using iterative and recursive function calls• practice pass-by-value and pass-by-reference parameter passing• use standard I/O function calls to interact with a user• integrate basic error checking with user I/OInstructions1. Main and supporting functionsWrite a main function and supporting functions that do the following:• define the function call stack variableo there must be only one instance of the function call stack in the entire program; do not make copies!o this is not a global variable• prompt the user to input the values of an integer array; you can start by prompting for the number of integers• prompt the user to select which sum function to call (iterative or recursive)• call the appropriate sum function; you will use the code for the sum functions found here: a2Loop.c• display the resulting sum to the userYour program must use the definitions in the header file found here: a2Defs.hCOMP 2401 — Assignment #2 Fall 2013 2/32. Data typesModify the given header file to define the following data types required to simulate the function call stack:• StackType corresponds to the function call stack and holds the frames currently on the stack• FrameType holds the data for a frame corresponding to a specific function; this includes the function name and information about its parameters• VarType holds the information for a specific parameterThe data types that you define must work with the stack utility functions found here: a2Stack.c3. Instrumenting the sum functionsModify both sumIterative and sumRecursive functions (found in a2Loop.c) to call the instrumentation functions on entry and return. The sum functions must call enterSumFunc immediately upon entry to initialize a stack frame corresponding to the sum function. They must call leaveSumFunc when the sum function returns.4. Instrumentation functionsImplement the two instrumentation functions:void enterSumFunc(StackType *stkPtr, char *fname, int num, int *arr, int *sum)void leaveSumFunc(StackType *stkPtr)• enterSumFunc creates a new stack frame to store information about one of the sum functions, including its name (sumIterative or sumRecursive) and the parameters passed to it; enterSumFunc must:o initialize a new stack frameo set the frame’s function name to the value in fnameo initialize the frame’s parameter data with information about the parameters passed to the sum function num represents the number of elements to be added together by the sum function arr is the array of integers to be added together sum points to the result of the sum functiono add the new frame as the next frame in LIFO sequence on the call stack pointed to by stkPtro output the contents of the function call stack, using the given dumpStack function• leaveSumFunc prints out the contents of the function call stack when one of the sum functions returns, using the given dumpStack functionConstraints• Design:o you must separate your code into modular, reusable functionso never use global variableso compound data types must be passed by reference, not by value• Reuse:o you must include the given header file in your program and use its function prototypes exactly as definedo you must use the sum functions found here: a2Loop.co you must use, without modification, the stack utility functions found here: a2Stack.c• Implementation:o your program must perform all basic error checkingo it must be thoroughly commented• Executiono programs that do not compile, do not execute, or violate any constraint are subject to severe deductionsCOMP 2401 — Assignment #2 Fall 2013 3/3SubmissionYou will submit in cuLearn, before the due date and time, one tar file that includes all the following:• all source and header files• a readme file, which must include:o a preamble (program author(s), purpose, list of source/header/data files)o exact compilation command(s)o launching and operating instructionsGrading• Marking breakdown:ComponentMarksmain and support functions25data types20instrumenting sum functions20instrumentation functions35• Assignment grade: Your grade will be computed based on two criteria:o completeness of the program functionality and its executiono quality of the implementation You must familiarize yourself with the grading rules• Bonus marks: Up to 5 extra marks are available for fun and creative additional features
COMP 2401 — Assignment #3
Goal
You will modify your program from Assignment #2 to simulate a function call stack, implemented as a linked list of frames, using C in the Ubuntu Linux environment.In this assignment, you will:• define the data types and structures required to represent the function call stack as a linked list of frames• write supporting functions to manage the function call stack• modify the instrumentation functions to work with the call stack implemented as a linked list• change the existing call stack output functions to print to a file instead of standard outputLearning Objectives• perform more complex pointer manipulations by implementing a linked list• work with dynamically allocated memory• practice using double pointers in pass-by-reference parameter passing• use file I/O function calls to output to a file• Note: Of course, linked lists are not the best underlying data structure for representing a stack. The use of linked lists in this assignment is for exclusively pedagogical purposes.Instructions1. Data typesModify the function call stack data type, so that the call stack is implemented as a singly linked list of frames, exactly as we saw in the “Advanced Linked Lists” section of the course notes:• StackType corresponds to the function call stack and contains a pointer to the head of the linked list of frames• FrameNodeType represents a node in the linked list• your main function must define the function call stack as dynamically allocated memoryo there must be only one instance of the function call stack in the entire program; do not make copies!o this is not a global variableNotes:• your program must use the definitions in the header file found here: a3Defs.h• the header file declares a frame number in each frame; your program must initialize this value2. Supporting stack functionsImplement the following support functions for the function call stack:• initStack allocates and initializes the stack• push adds a frame in LIFO order to the call stack• pop removes from the stack the frame that was last added• cleanupStack deallocates all the memory for the stackNote: remember to manage your memory! do not leave any memory leaksCOMP 2401 — Assignment #3 Fall 2013 2/33. Instrumentation functionsModify both enterSumFunc and leaveSumFunc functions to manipulate the function call stack as a linked list:• enterSumFunc is called when a sum function begins; it must:o create a new dynamically allocated stack frame to store information about one of the sum functionso initialize all the frame data, as you did in Assignment #2o add the new frame to the function call stacko output the contents of the call stack, using the modified dumpStack function• leaveSumFunc is called when a sum function returns; it must:o output the contents of the call stack, using the modified dumpStack functiono remove the corresponding frame from the stackNotes:• your sum functions must call the instrumentation functions defined above• the instrumentation functions must use the supporting push and pop functions4. Stack output to fileDefine, as a global variable, a pointer to the output file that will contain the contents of the call stack• remember! global variables are to be used very rarely, this is a one-time exception!Modify the call stack output functions to work with the linked list and output the contents of the stack to a file:• dumpStack traverses the linked list of frames and outputs the contents to the output fileo you must use the same output format as in Assignment #2• dumpVar and dumpBytes must be modified to print to file as wellNotes:• think about where you must open and close the output file!• you must use the stack utility functions found here: a3Stack.c• you can find some helpful sample code here: testUtil.cConstraints• Design:o you must separate your code into modular, reusable functionso never use global variables, unless otherwise instructedo compound data types must be passed by reference, not by valueo you must manage your memory! use valgrind to find memory leaks• Reuse:o you must include the given header file in your program and use its function prototypes exactly as defined• Implementation:o your program must perform all basic error checkingo it must be thoroughly commented• Executiono programs that do not compile, do not execute, or violate any constraint are subject to severe deductionsCOMP 2401 — Assignment #3 Fall 2013 3/3SubmissionYou will submit in cuLearn, before the due date and time, one tar file that includes all the following:• all source and header files• a readme file, which must include:o a preamble (program author(s), purpose, list of source/header/data files)o exact compilation command(s)o launching and operating instructionsGrading• Marking breakdown:ComponentMarksdata types15supporting stack functions50instrumentation functions25stack output to file10• Assignment grade: Your grade will be computed based on the completeness of your implementation, plus bonus marks, minus deductions.• Deductions: 100 marks if:o any files are missing from your submission, or if they are corrupt or in the wrong format 50 marks if:o the code does not compile using gcc in the Ubuntu Linux shell environmento unauthorized changes have been made to the header and/or source files provided for youo code cannot be tested because it doesn’t run 25 marks if:o your submission consists of anything other than exactly one tar fileo your program is not broken down into multiple reusable, modular functionso your code is not correctly separated into header and source fileso your program uses global variables (unless otherwise explicitly permitted)o the readme file is missing or incomplete 10 marks for missing comments or other bad style (non-standard indentation, improper identifier names, etc)• Bonus marks: Up to 5 extra marks are available for fun and creative additional features
COMP 2401 — Assignment #4
Goal
You will write a program in C, in the Ubuntu Linux environment, to manage a movie database.In this assignment, you will:• define the data types and structures required to represent a movie collection as a doubly linked list• write code to interact with the user for the purpose of managing movie data• implement functions to manipulate the doubly linked list• create a set of input files to test a programLearning Objectives• get familiar with more complex dynamic memory operations by managing a doubly linked list• practice a wider variety of user I/O interactions using standard library functions• use redirection of standard input to test a programInstructions1. Data typesDefine the data types required for the movie database:• MovieType represents one movie; it includes the movie title, the year it was made, and the genre• MovieNodeType corresponds to a node in the doubly linked list of movies, implemented as we saw in the “Advanced Linked Lists” section of the course notes• your main function must define the movie list as a pointer to the head of the doubly linked listo there must be only one instance of the movie list in the entire program; do not make copies!o this is not a global variableNote:• your program must use the definitions in the header file found here: a4Defs.h2. Movie management user interface (UI)Write a main and a main menu function to interact with the user and provide these four options (with 0 to exit):• add movieso getMovieData prompts the user for the number of movies to be entered, then prompts for the movie data• delete a movieo the user enters the title of a movie to be removed from the list• list all movieso a list of all movies is printed to the standard output• list movies by genreo the user enters the genre of movies to be listedo a list of all movies of that genre is printed to the standard outputNote:• you can find some helpful sample code for user I/O here: testUtil.cCOMP 2401 — Assignment #4 Fall 2013 2/43. List management functionsImplement the following list management functions:• addToMovieListo adds a given movie to the movie list, alphabetically by title, then chronologically by year if titles are identical• deleteMovieo removes the given movie from the movie list• printMovieDatao prints out a list of all movies to the standard output• printMoviesByGenreo prints out a list of all movies of the given genre to the standard output you must create a new temporary list containing movies of only that genre – do not copy the movie data! you must reuse the addToMovieList and printMovieData functionsNotes:• the print functions must display all the data for each movie• remember to manage your memory! do not leave any memory leaks4. Instrumentation functionDefine, as a global variable, a pointer to an output file that will contain the contents of the movie list• the file can be opened at the beginning of the main function and closed at the end of the programWrite a dumpList function that prints to the output file the detailed contents of the movie list, including:• the value of the head, as an address• for each node:o the value of the node, as an addresso the address of the data, as well as its contentso the value of the previous node, as an addresso the value of the next node, as an addressNotes:• your program must call dumpList at the beginning and end of these functions: getMovieData, addMovieToList, deleteMovie• your output must be formatted as in Figure 1• you can reuse the convertToBytes and dumpBytes functions from previous assignments5. Test input filesDesign a suite of test cases that thoroughly exercise your program’s functionality and possible error conditions.In your readme file, list and number all the cases that must be tested. At minimum, these will include, for each feature of the program, one test case for every normal case and every error case; for the add movies feature, for example, the following must be tested:o adding a movie to an empty listo adding a movie to the beginning of the listo adding a movie to the end of the list… and many more …Create a set of test input files; each input file:• corresponds to one test case• contains the standard input data to be redirected into your program for that test caseCOMP 2401 — Assignment #4 Fall 2013 3/4Figure 1 – Sample output of instrumentation functionConstraints• Design:o you must separate your code into modular, reusable functionso never use global variables, unless otherwise instructedo compound data types must be passed by reference, not by valueo you must manage your memory! use valgrind to find memory leaks• Reuse:o you must include the given header file in your program and use its function prototypes exactly as defined• Implementation:o your program must perform all basic error checkingo it must be thoroughly commented• Executiono programs that do not compile, do not execute, or violate any constraint are subject to severe deductions• Testingo submissions that do not include a list of test cases and a suite of test input files are subject to severe deductionsCOMP 2401 — Assignment #4 Fall 2013 4/4SubmissionYou will submit in cuLearn, before the due date and time, one tar file that includes all the following:• all source and header files• a Makefile• a readme file, which must include:o a preamble (program author(s), purpose, list of source/header/data files)o exact compilation command(s)o launching and operating instructionso a list of test cases that test your program• a set of test input filesGrading• Marking breakdown:ComponentMarksdata types10movie management UI16list management functions62instrumentation function12• Assignment grade: Your grade will be computed based on the completeness of your implementation, plus bonus marks, minus deductions.• Deductions: 100 marks if:o any files are missing from your submission, or if they are corrupt or in the wrong format 50 marks if:o the Makefile is missingo the code does not compile using gcc in the Ubuntu Linux shell environmento unauthorized changes have been made to the header and/or source files provided for youo code cannot be tested because it doesn’t run 25 marks if:o your submission consists of anything other than exactly one tar fileo your program is not broken down into multiple reusable, modular functionso your code is not correctly separated into header and source fileso your program uses global variables (unless otherwise explicitly permitted)o the readme file is missing or incomplete 10 marks for missing comments or other bad style (non-standard indentation, improper identifier names, etc)• Bonus marks: Up to 5 extra marks are available for fun and creative additional features
COMP 2401 — Assignment #5
Goal
You will write a program in C, in the Ubuntu Linux environment, to simulate a two-player game of Twenty Questions, as a distributed system over the School of Computer Science network. One player (the oracle) chooses an object that the other player (the guesser) tries to guess by asking the oracle one question at a time. At every turn, the guesser asks a yes/no question, or tries to guess the object. The oracle responds by signalling one of three responses: yes, no, or win. If the guesser correctly guesses the object within 20 questions, s/he wins, otherwise the oracle wins. The winning player is given a choice of quitting the game, or playing another round. If s/he opts to play again, s/he becomes the oracle for the next round.In this assignment, you will:• implement a game between two users on different computers, communicating over TCP/IP sockets• modify client-server code so that a single executable program can switch between client mode and server modeInstructions1. Process startupYou are writing code for a single executable program. Both guesser and oracle players will be running their own copy of the same program, but executing on different computers that are networked together.Your program initiates a connection to another game process as follows:• the user may specify an IP address on the command line or not• if an IP address is specified, then the game process initiates a connection using TCP/IP sockets to the other game process running at the specified IP address• if no IP address is specified, then the game process waits for another game process to initiate a connection2. Game logicThe Twenty Questions game logic works as follows:• setting up a roundo the player on the game process that initiated the connection takes on the role of guessero the other player becomes the oracle• during the roundo at each turn, the guesser is prompted for a yes/no question (questions should be numbered)o the question is sent to the oracle’s game processo the oracle user enters a response using signals; do not prompt the oracle for input! the SIGINT (Ctrl-C) signal indicates a yes answer to the question the SIGTSTP (Ctrl-Z) signal indicates a no answer to the question the SIGQUIT (Ctrl-\) signal is a win answer, meaning that the guesser has correctly guessed the objecto both players see all the questions asked so far, along with the answero if the guesser correctly guesses the object, s/he winso if the number of questions reaches 20 without a correct guess, the oracle wins• ending a roundo when a player wins, s/he is prompted to either play another round or quito the losing player does not get a choice and must play again if the winner chooses to do soo if the winner decides to play again, s/he becomes the oracle, and a new round starts upo if the winner decides to quit: the winner’s game process closes the connection, cleans up all its resources, and terminates the loser’s game process waits for a new connection to be initiatedCOMP 2401 — Assignment #5 Fall 2013 2/2Constraints• Design:o you must separate your code into modular, reusable functionso never use global variables, unless otherwise instructed• Implementation:o your program must perform all basic error checking and clean up resources upon terminationo it must be thoroughly commented• Executiono programs that do not compile, do not execute, or violate any constraint are subject to severe deductionsSubmissionYou will submit in cuLearn, before the due date and time, one tar file that includes all the following:• all source and header files• a Makefile• a readme file, which must include:o a preamble (program author(s), purpose, list of source/header/data files)o exact compilation command(s)o launching and operating instructionsGrading• Marking breakdown:ComponentMarksprocess startup40game logic60• Assignment grade: Your grade will be computed based on the completeness of your implementation, plus bonus marks, minus deductions.• Deductions: 100 marks if:o any files are missing from your submission, or if they are corrupt or in the wrong format 50 marks if:o the Makefile is missingo the code does not compile using gcc in the Ubuntu Linux shell environmento code cannot be tested because it doesn’t run 25 marks if:o your submission consists of anything other than exactly one tar fileo your program is not broken down into multiple reusable, modular functionso your code is not correctly separated into header and source fileso your program uses global variables (unless otherwise explicitly permitted)o the readme file is missing or incomplete 10 marks for missing comments or other bad style (non-standard indentation, improper identifier names, etc)• Bonus marks: Up to 5 extra marks are available for fun and creative additional features
