subject programming algorithm

2401ICT Data Structures and Algorithms – Assignment 1 –  This assignment contributes 15% towards your final grade and will be marked out of 100: • Maximum of 65 marks for question 1. • Maximum of 35 marks for question 2. Marking criteria for this assignment will include: • Overall correctness of program function • How well the requirements have been met. • Use of appropriate C++ features. • Understandability and reliability of C++ code. • Documentation supplied with the assignment. All assignments must include, in a separate folder for each problem: • A pdf document formatted as shown in “Sample Documentation” on the Assignment page of the course web-site. • C++ source code in appropriately labelled files & following style guide. • MSVisualStudio2010 C++ project files (or makefiles). • Any test data files. • Statically compiled executable (runs standalone without needing any dlls) Students are also advised to read Section 7 of the course profile, particularly with regard to plagiarism. The Griffith University policy will be strictly enforced in this course. Questions 1. Write a dynamic memory manager class to manage memory from an array. The class constructor should take an integer specifying the size in bytes of the memory to managed by the class. The constructor should then allocate a dynamic array of the given size. Your class will need to implement the following functions: • MemManage(int maxsize=0); //- creates initial memory array • ~MemManage(); //- frees all memory resources • void* Alloc(int size); //- returns a pointer to allocated memory • void Free(void*); //- deallocates memory • void* Realloc(void*, int); //- enlarges the allocated size • void Compact(); //- eliminates memory fragmentation • int Avail(); //- returns the amount of free memory • void Dump(); //- prints raw memory contents out • ostream& operator<<(ostream&, const MemManage &); • MemManage & operator=( const MemManage &); The following requirements must be met: • The memory array allocated by the constructor must be private • Use a linked list to keep track of the location and size of free memory fragments. You must write your own, you can not use std::list • Avail() returns the total amount of free memory in all free fragments • Alloc() returns NULL if insufficient memory exists to fulfil request • Alloc tries to reuse the smallest memory fragments it can rather than grabbing memory from larger free blocks. • Realloc() first attempts to enlarge the size allocated at the location given by the pointer and if that is not possible makes a new allocation and frees the existing. It returns a pointer to the allocation or NULL if reallocation was not possible • Dump() and operator << prints the contents of the memory out byte by byte as consecutive rows of 16 hexadecimal values with a single space between each value. • Compact() essentially defragments your memory resulting in having a single free fragment. • Operator= makes a deep copy of a MemManage object • You will need to write a test program (given below) and provide a printout of its output void Main() { char* ptrs[20] = {0}; char* strgs[] = {“zero”, “one”, “two”, “three”, “four”, “five”, “six”, “seven” “eight”, “nine”, “ten”, “sixteen”, “eighteen”, “nil”, “twenty”, “seventy three”}; MemManager cpy, mem(100); for (int i = 0; i<=10; i++) strcpy(ptrs[i] = (char*)mem.Alloc(1+strlen(strgs[i])), strgs[i]); printf(“\nFree Space = %d\n”, mem.Avail()); cout << mem << endl; strcpy(ptrs[6] = (char*)mem.Realloc(ptrs[6], 1+strlen(strgs[11])), strgs[11]); strcpy(ptrs[8] = (char*)mem.Realloc(ptrs[8], 1+strlen(strgs[12])), strgs[12]); printf(“\nFree Space = %d\n”, mem. Avail ()); mem.Dump(); mem.Free( memset(ptrs[1], 0, strlen(ptrs[1])) ); mem.Free( memset(ptrs[3], 0, strlen(ptrs[3])) ); mem.Free( memset(ptrs[5], 0, strlen(ptrs[5])) ); mem.Free( memset(ptrs[7], 0, strlen(ptrs[9])) ); mem.Free( memset(ptrs[9], 0, strlen(ptrs[9])) ); printf(“\nFree Space = %d\n”, mem. Avail ()); mem.Dump(); for (int i = 13; i<=15; i++) strcpy(ptrs[i] = (char*)mem.Alloc(1+strlen(strgs[i])), strgs[i]); printf(“\nFree Space = %d\n”, mem.Avail()); mem.Dump(); strcpy(ptrs[2] = (char*)mem.Realloc(ptrs[2], 1+strlen(strgs[3])), strgs[3]); strcpy(ptrs[5] = (char*)mem.Realloc(ptrs[5], 1+strlen(strgs[7])), strgs[7]); printf(“\nFree Space = %d\n”, mem.Avail()); mem.Dump(); cpy = mem; printf(“\nAlloc(50) returned %p\n”, cpy.Alloc(50)); cpy.Compact(); printf(“\nFree Space = %d\n”, cpy.Avail()); cout << “Mem: \n” << mem << endl; cout << “Copy: \n” << cpy << endl; } 2. Implement a scientific calculator using recursion (see Textbook, Chapter 7, Programming Exercise 10 but without using a stack). You will need to implement a simple recursive descent parser. Your Calculator class should have the following public member: • double Calculate(char* expression); • You need to handle floating point numbers and the following operators: +, -, *, /, ^, (, ). • You will need to observe precedence rules, ie 5 * 2 + 3 = 13 not 25 (note ^ has the highest precedence) • The program should prompt the user to enter an expression, after enter is pressed is shall evaluate it, print out the result and prompt for the user to enter a new expression in a loop until the user enters the command ‘q’, which will cause the program to end. • The result should be printed out using no more than 3 decimal places. • You can limit the input to single digit numbers • You should test your calculator on the following expressions: o 2^2 + 3 – 4 o (2 + 3) * 5 o (2 + 3) * (5 - 1)^2 o 2 + ((3 + 1) * (6 - 2) – 1) / (4 - 2) o 2 + 3 * (1 + 4) – 9 / 2 * 3 + 1 Marking Scheme Question 1: Memory Manager Marks (Total 65) • Constructor & Destructor 5 • Alloc() & Free() 5 • Dump() & operator<< 5 • Realloc() 5 • Compact() 10 • Avail() 5 • Operator= 5 • Linked list implementation 5 • Correctness of test program execution 5 • Compileable source code and runnable executable provided 5 • Requirement Acceptance testing 5 • Documentation and code style 5 Question 2: Calculator Marks (Total 35) • Support for +, -,*, /, ^ operators 5 • Support for () in expressions 5 • Correct handling of precedence 5 • Correct handling of compound expressions 5 • Correct implementation of recursion 5 • Compileable source code and runnable executable provided 5 • Documentation, Requirement acceptance tests etc 5