COMP9024 24T0 Data Structures and Algorithms

2024-01-31 Admin 写评论

Week 1 Problem Set
Elementary Data and Control Structures in C

The main purpose of the first problem set is to familiarise yourself with programming in C.

For the remainder of the course it is vital that you understand and are able to solve all of the Exercises 1 – 7 below. In addition, you could gain further, self-guided programming practice by solving small puzzles from this website:

C Puzzles

(Hint: Recommended are L11–L20, L31–L40, D11–D20, DD11–DD17. Pointers and random numbers will be introduced later in COMP9024.)

  1. (Numbers)

    There is a 7-digit number that satisfies 8 · abcdefg = gfedcba + 1, that is, when multiplied by 8 yields the number read backwards plus 1. Write a C-program to find this number.

    Only use arithmetic operations (Hint: integer and modulo division); do not use any string operations.

    [show answer]

  2. (Characters)

    Write a C-program that outputs, in alphabetical order, all strings that use each of the characters 's', 't', 'r', 'i', 'n', 'g' exactly once.

    How many strings does your program generate?

    Hint: Find a simple algorithm to solve this specific problem only. Do not try to solve this problem for other letter combinations. You do not need any library function other than printf().

    [show answer]

  3. (Elementary control structures)

    1. Write a C-function that takes a positive integer n as argument and outputs a series of numbers according to the following process, until 1 is reached:

      • if n is even, then n ← n/2
      • if n is odd, then n ← 3*n+1

    2. The Fibonacci numbers are defined as follows:

      • Fib(1) = 1
      • Fib(2) = 1
      • Fib(n) = Fib(n-1)+Fib(n-2) for n≥3

      Write a C program fibonacci.c that:

      • computes the first 12 Fibonacci numbers
      • applies the process described in Part a. to these 12 numbers.

      The output of the program should begin with 

      Fib(1) = 1
1
Fib(2) = 1
1
Fib(3) = 2
2
1
Fib(4) = 3
3
10
5
16
8
4
2
1

    We have created a script that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this exercise. It expects to find a program named fibonacci.c in the current directory. You can use dryrun as follows: 

    9024 dryrun fibonacci

    Note: Please ensure that your output follows exactly the format shown above.

    [show answer]

  4. (Elementary data structures)

    Define a data structure to store all information of a single ride with the Opal card. Here are two sample records:

    You may assume that individual stops (such as "Circular Quay, No. 4 Wharf") require no more than 31 characters.

    Determine the memory requirements of your data structure, assuming that each integer and floating point number takes 4 bytes.

    If you want to store millions of records, how would you improve your data structure?

    [show answer]


  5. (Stack ADO)

    Modify the Integer Stack ADO from the lecture (stack.h and stack.c) to develop an implementation of a character stack ADO. Below is the header file (charStack.h) that your ADO should use:

    charStack.h 
    // Character Stack ADO header file

#define MAXITEMS 10

void StackInit();      // set up empty stack
int  StackIsEmpty();   // check whether stack is empty
void StackPush(char);  // insert int on top of stack
char StackPop();       // remove char from top of stack

    Your task is to implement these functions in a program called charStack.c.

    Compile your character stack ADO and the test program below (stackTester.c) and run it to test your character stack ADO. The tester

    • initialises the stack,
    • then uses the stack to reverse a given string.
    stackTester.c 
    // Character Stack ADO tester

#include <stdio.h>
#include "charStack.h"

#define STRLEN 7

int main(void) {
   char str[STRLEN] = "string";
   int i = 0;
   
   StackInit();
   while (str[i] != '\0') {
      StackPush(str[i]);
      i++;
   }
   while (!StackIsEmpty()) {
      char c = StackPop();
      putchar(c);
   }
   putchar('\n');
   return 0;
}

    The output of the program schould be 

    gnirts
    Hint:
    • Do not modify  charStack.h  nor  stackTester.c.
    • The standard I/O function  putchar(ch)  can be used to output a single character. It has the same effect as  printf("%c",ch).

    [show answer]


  6. (ADO client)

    A character stack can be used for bracket matching, which means to check if in a sequence of characters all opening brackets such as '(', '[', '{' have matching closing brackets ')', ']', '}'.

    Examples of strings that are correctly bracketed:

    • x = (a+b) * c
    • (a[i]+b[j]*c[k])
    • int f(int a[]) { return 1; }

    Examples of strings that are not correctly bracketed:

    • int f(void) return 1; }   (case 1)
    • x = f(a+b] * c           (case 2)
    • printf("%d", a[3];       (case 3)

    The following algorithm solves the bracket matching problem with the help of a stack: 

    bracketMatching(s):
| Input string s
| Output true if parentheses in s balanced, false otherwise
|
|  initialise empty stack
|  balanced = true
| for each ch in s do |  | if ch is an opening bracket then |  |     push ch onto stack
|  | else if ch is a closing bracket then |  |  | if stack is empty then |  |  |     balanced = false                    // opening bracket missing (case 1)
|  |  | else |  |  |     opening = pop top off stack
|  |  | if opening and ch do not match then |  |  |        balanced = false                 // wrong closing bracket (case 2)
|  |  | end if |  |  | end if |  | end if | end for | if stack is not empty then balanced = false  // some brackets unmatched (case 3)
| return balanced

    1. Trace the algorithm on each of the six example strings from above. For each string, show the stack after each push/pop operation.

    2. Complete the program below (brackets.c) by an implementation of this algorithm using your character stack ADO from Exercise 5. The program

      • initialises the stack
      • asks the user to input a string
      • uses the standard I/O function scanf() to read a line of up to 511 characters (not counting the terminating '\0' character)
      • checks whether all brackets in the string are correctly matched (needs to be implemented)
      brackets.c 
      #include <stdio.h>
#include "charStack.h"

#define INPUT_STRLEN 512

int main(void) {
   char str[INPUT_STRLEN];
   
   printf("Enter a string: ");
   scanf("%[^\n]511s", str);

   StackInit();

   char ch;
   int i = 0;
   while ((ch = str[i]) != '\0') {

   /* NEEDS TO BE IMPLEMENTED */

}

      Examples of the program executing could be 

      ./bracketsEnter a string: x = (a+b) * c correctly balanced./bracketsEnter a string: printf("%d", a[3]; brackets unbalanced

      We have created a script that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this exercise. It expects to find three programs in the current directory:

      • charStack.h – the header file for the character stack from Exercise 5
      • charStack.c – your implementation of the character stack Exercise 5
      • brackets.c

      You can use dryrun as follows: 

      9024 dryrun brackets

    [show answer]


  7. (Queue ADO)

    Modify the Integer Stack ADO from the lecture (stack.h and stack.c) to an integer queue ADO.

    Hint: A queue is a FIFO data structure (first in, first out). The principal operations are to enqueue and to dequeue elements. Elements are dequeued in the same order in which they have been enqueued. Below is the header file (queue.h) with the functions that your ADO should provide.

    queue.h 
    // Integer Queue ADO header file
#define MAXITEMS 10

void QueueInit();        // set up empty queue
int  QueueIsEmpty();     // check whether queue is empty
void QueueEnqueue(int);  // insert int at end of queue
int  QueueDequeue();     // remove int from front of queue

    We have created a script that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this exercise. It expects to find two files named queue.c and queue.h in the current directory that provide an implementation of a queue ADO with the four queue functions shown above. You can use dryrun as follows: 

    9024 dryrun queue

    [show answer]


  8. Challenge Exercise

    A 5-digit number is divisible by a 3-digit number without remainder. Neither number contains the digit 9. If you increment by 1 each digit of both numbers, then again they can be divided without remainder. The difference between the results of the two divisions is exactly 100.

    Write a C program to find the two numbers.

    Note: Only use arithmetic operations; do not use any string operations.

    [show answer]

Assessment

This first weekly assignment is meant to give you your first practice and will not count towards your mark for the weekly homework.

However, in order to familiarise yourself with the submission and auto-marking process, you can submit your solutions to Exercises 6 and 7.

You should submit your files using the following give command: 

give cs9024 week1 brackets.c queue.c

Alternatively, you can submit through WebCMS3.

Make sure you spell the filenames correctly. You can submit multiple times. Only your last submission will be considered.

Do not submit files individually! When you make another submission, you must always submit all files you intend to submit for this problem set. Previously submitted files will be deleted when you make a new submission.

The deadline for submission is Monday, 8 January 5:00:00pm.

Auto-marking will be run by the lecturer several days after the submission deadline using different test cases than  dryrun  does. Hint: Do your own testing in addition to running  dryrun.

Please be mindful of the following assessment rules:

Do …

  • use your own best judgement to understand & solve the exercises
  • discuss assessment questions on the forum only after the deadline on Monday

Do not …

  • post specific questions about the problem sets before the Monday deadline
  • agonise too much about an exercise that you find too difficult

Plagiarism

Group submissions will not be allowed. Your programs must be entirely your own work. Plagiarism detection software will be used to compare all submissions pairwise (including submissions for similar assessments in previous years, if applicable) and serious penalties will be applied, including an entry on UNSW's plagiarism register.

You are also not allowed to submit code generated with the help automatic tools such as GitHub Copilot, ChatGPT, Google Bard.

  • Do not copy ideas or code from others
  • Do not use a publicly accessible repository or allow anyone to see your code
  • Code generated by GitHub Copilot, ChatGPT, Google Bard and similar tools will be treated as plagiarism.

Please refer to the on-line sources to help you understand what plagiarism is and how it is dealt with at UNSW:

Reproducing, publishing, posting, distributing or translating this page is an infringement of copyright and will be referred to UNSW Conduct and Integrity for action.

发表评论

电子邮件地址不会被公开。 必填项已用*标注