CISC220, 06J, Final Exam (E03) —August 11 , 2006


Write your name only on this page

Name as you are called in class_____________________________________

Name as on official roster (if different) ________________________________

UD email address_________________________________________________

1. For each of the following sections of code, provide the complexity of the running time,
   e.g. O(1), O(log n), O(n), O(n log n), O(n²), etc.
   

   1. (5 pts)

      int result = 0;
      
      for (int i=n; i>0; i = i/2)
      {
         for (int j=1; j<n; j++)
            result ++;
      }
      return result;
              

   2. (5 pts)

      int result = 0;
      for (int j=0; j<n; j++)
        for (int i=0; i<5; i++)
         {
           cout << a[i];
         }
            

   3. (5 pts)

      int result = 0;
      
      for (int i=0; i<5; i++)
      {
         cout << a[i];
      }

   4. (5 pts)

      int result = 0;
      
      for (int i=0; i<(n * n); i++)
      {
         result++;
      }
      
      

   5. (5 pts)

      int result = 0;
      
      for (int i=n; i>0; i--)
      {
         for (int j=0; j<i; j++)
            result++;
      }
      
              

   6. (5 pts) Note: this one may be tricky. Even if it "looks wrong". It does compile and run. Analyze the code as it is, and determine the running time.

      int result = 0;
      
      for (int i=n; i<n; i--)
      {
         for (int j=0; j<i; j++)
            result++;
      }

2. (5 pts) This question pertains to the code for the StudentHashTable_C class that appears later on this exam.

   There is something wrong. When you try to compile, you get the following error message. What is wrong, and how would you fix it?

   > make
   CC    -c  student.cc
   CC    -c  testStudent.cc
   CC    -c  runTests.cc
   CC student.o testStudent.o runTests.o -o testStudent
   CC    -c  studentHashTable.cc
   CC    -c  testStudentHashTable.cc
   "student.h", line 7: Error: Multiple declaration for Student_C.
   1 Error(s) detected.
   *** Error code 1
   make: Fatal error: Command failed for target `testStudentHashTable.o'
   > 
     
   
   
   
   
   
   

3. This question pertains to the code for the StudentHashTable_C class that appears later in the exam.

   Originally, the following code appeared in TestStudentHashTable.cc at line 28, but it produced an error:

      test.assertEquals(h.lookup(1), NULL);
     

   The error that was produced was this one:

   > make
   CC    -c  testStudentHashTable.cc
   "testStudentHashTable.cc", line 28: Error: Could not find a match for RunTests_C::assertEquals(Student_C*, int) needed in main().
   1 Error(s) detected.
   *** Error code 1
   make: Fatal error: Command failed for target `testStudentHashTable.o'
   > 
   

   The line of code was fixed by doing the following:

      test.assertEquals(h.lookup(1), (Student_C *) NULL);
   

   The following also fixes it:

      test.assertEquals(h.lookup(1), static_cast<Student_C *>(NULL));
   

   Explain why the first line of code produced the error message that it did.
   
   
   
   
   .

4. Below you will find complete listings of several files, except that at a few places in the files code has been removed.

   Fill in the missing code.

   These files include source code for:

   • a C++ class to represent a student with: student id and name
   • a C++ class to represent a hash table of such students, with the student id as the key
   • a C++ class to support test-driven development (the same RunTests_C class we've been using all semester
   • a Makefile to compile, link, and run the tests

   hashTable/Makefile

   1	# Makefile for StudentHashTable
   2
   3	CCC = CC
   4
   5	BINARIES = testStudent testStudentHashTable
   6
   7	all: ${BINARIES} test
   8
   9	test: ${BINARIES}
   10	./testStudent
   11	./testStudentHashTable
   12
   13	testStudent: student.o testStudent.o runTests.o
   14	${CCC} student.o testStudent.o runTests.o -o $@
   15
   16	# //** (a) (5 pts) Include the rule needed to link the executable for
   17	# //** testStudentHashTable. Be sure to include ALL files that
   18	# //** are needed.
   19
   20
   21
   22
   23
   24	testStudent.o: student.h testStudent.cc
   25
   26	testStudentHashTable.o: student.h studentHashTable.h testStudentHashTable.cc
   27
   28	runTests.o: runTests.h runTests.cc
   29
   30	clean:
   31	/bin/rm -f ${BINARIES} a.out core *.o

   hashTable/student.h

   1	// student.h P. Conrad for CISC220 Final Exam 06J
   2
   3
   4
   5
   6	#include <string>
   7	using std::string;
   8
   9	class Student_C
   10	{
   11	public:
   12	Student_C(int theStudentId, string theName);
   13
   14	int getStudentId() const;
   15	string getName() const;
   16
   17	bool operator==(const Student_C & right);
   18
   19	private:
   20	int studentId;
   21	string name;
   22
   23	};
   24
   25
   26

   hashTable/student.cc

   1	// student.cc P. Conrad for CISC220 Final Exam 06J
   2
   3	#include "student.h"
   4
   5	Student_C::Student_C(int theStudentId, string theName)
   6	{
   7	studentId = theStudentId;
   8	name=theName;
   9	}
   10
   11	int Student_C::getStudentId() const
   12	{
   13	return studentId;
   14	}
   15
   16	string Student_C::getName() const
   17	{
   18	return name;
   19	}
   20
   21	bool Student_C::operator==(const Student_C & right)
   22	{
   23	//** (b) (5 pts) Complete the definition of this function.
   24	//** Keep in mind the differences in how C-string and C++ strings
   25	//** are compared.
   26
   27
   28
   29	}

   hashTable/studentHashTable.h

   1	// studentHashTable.h P. Conrad, CISC220 06J for CISC220 final exam
   2
   3	#ifndef STUDENTHASHTABLE_H
   4	#define STUDENTHASHTABLE_H
   5
   6	#include "student.h"
   7
   8	class StudentHashTable_C
   9	{
   10	public:
   11
   12	// construct a hash table with "theSize" entries.
   13	// table never gets full, since linked collision resolution is used
   14
   15	StudentHashTable_C(int theSize);
   16
   17	// lookup looks for an student with the key "theStudentId".
   18	// if it is found, a new Student_C object is allocated on the heap, and
   19	// a pointer to that object is returned.
   20	// Otherwise, a NULL pointer is returned.
   21
   22	Student_C *lookup(int theStudentId) const;
   23
   24	// add returns false if a student with a key matching
   25	// thisStudent's key is already in the table.
   26	// Otherwise, it adds this student to the hash table, and returns true.
   27
   28	bool add(const Student_C &s);
   29
   30	StudentHashTable_C(const StudentHashTable_C &orig)
   31	{ deepCopy(orig);}
   32	StudentHashTable_C & operator=(const StudentHashTable_C &right);
   33	~StudentHashTable_C() {cleanup();}
   34
   35	private:
   36
   37	// private data members
   38
   39	struct Node_S // linked list nodes, used for collision resolution
   40	{
   41	Student_C *student; // separately allocated on heap
   42	Node_S *next;
   43	};
   44
   45	int size; // size of hash table
   46	Node_S **hashTable; // array of Node_S * values, size s, allocated on heap
   47
   48	// private member functions
   49
   50	int hash(int key) const;
   51	void cleanup() ;
   52	void deepCopy(const StudentHashTable_C &orig);
   53
   54	};
   55
   56	#endif // STUDENTHASHTABLE_H

   hashTable/studentHashTable.cc

   1	// studentHashTable.cc P. Conrad, CISC220 06J for CISC220 final exam
   2
   3	#include "studentHashTable.h"
   4
   5	// construct a hash table with "theSize" entries.
   6	// table never gets full, since linked collision resolution is used
   7
   8	StudentHashTable_C::StudentHashTable_C(int theSize)
   9	{
   10	size = theSize;
   11
   12	//** (c) (5 pts) Fill in a line of code to allocate an array
   13	//** with the correct number of (Node_S *) elements
   14
   15
   16
   17	}
   18
   19	// lookup looks for an student with the key "theStudentId".
   20	// if it is found, a new Student_C object is allocated on the heap, and
   21	// a pointer to that object is returned.
   22	// Otherwise, a NULL pointer is returned.
   23
   24	Student_C * StudentHashTable_C::lookup(int theStudentId) const
   25	{
   26	Node_S *p = hashTable[hash(theStudentId)];
   27
   28	if (p==NULL)
   29	return NULL;
   30
   31	while (p!=NULL)
   32	{
   33	if (p->student->getStudentId() == theStudentId)
   34	return new Student_C(*(p->student));
   35	else
   36	p = p->next;
   37	}
   38
   39	return NULL;
   40	}
   41
   42	// add returns false if a student with a key matching
   43	// thisStudent's key is already in the table.
   44	// Otherwise, it adds this student to the hash table, and returns true.
   45
   46	bool StudentHashTable_C::add(const Student_C &s)
   47	{
   48	//** (d) (5 pts) Somewhere in this code there is a memory leak. Find it,
   49	//** and insert a line of code that will fix it. I've left space
   50	//** between each line of code so that you will have room.
   51
   52
   53	Student_C *p = lookup(s.getStudentId());
   54
   55	if (p!=NULL)
   56	{
   57
   58	return false;
   59
   60	}
   61
   62	int pos = hash(s.getStudentId());
   63
   64	Node_S *q = new Node_S;
   65
   66	q->student = new Student_C(s);
   67
   68	q->next = hashTable[pos];
   69
   70	//** (e) (5 pts) One line of code is missing here that is needed for the
   71	//** code to be correct. What is it?
   72
   73
   74
   75	return true;
   76	}
   77
   78
   79	StudentHashTable_C &
   80	StudentHashTable_C::operator=(const StudentHashTable_C &right)
   81	{
   82	//** (f) (5 pts) Fill in the code for the overloaded = operator
   83
   84
   85
   86
   87
   88
   89
   90
   91
   92	}
   93
   94
   95	int StudentHashTable_C::hash(int key) const
   96	{
   97	//** (g) (5 pts) insert the code for the hash function
   98	//** only one line of code is needed.
   99
   100
   101
   102	}
   103
   104	void StudentHashTable_C::cleanup()
   105	{
   106	// Cleanup the hash table and recycle all the memory
   107
   108	for (int i=0; i< size; i++)
   109	{
   110	while (hashTable[i] != NULL)
   111	{
   112	Node_S *trailp = hashTable[i];
   113	hashTable[i] = hashTable[i] -> next;
   114	delete trailp;
   115	}
   116	}
   117
   118	//** (h) (5 pts) A line of code is missing below. What is it?
   119
   120
   121
   122	}
   123
   124	void StudentHashTable_C::deepCopy(const StudentHashTable_C &orig)
   125	{
   126	size = orig.size;
   127
   128	for (int i=0; i<size; i++)
   129	{
   130	hashTable[i] = NULL; // start with an empty list
   131
   132	// traverse the original list
   133	for (Node_S *p=orig.hashTable[i]; p!=NULL; p=p->next)
   134	{
   135	// for each node found, allocate a new node
   136	// and add it to front of the linked list
   137
   138	Node_S *q=new Node_S;
   139
   140	//** (i) (5 pts) The next three lines of code are missing.
   141	//** Fill them in
   142
   143
   144
   145
   146	}
   147	}
   148
   149	} // deepCopy

   hashTable/runTests.h

   1	// runTests.h Class for Test-Driven Development
   2	// P. Conrad for CISC220, 06J
   3
   4	// A barebones class for doing test-driven development (TDD)
   5	// in the stule of "Agile" or "eXtreme Programming".
   6	// Inspired by suites such as JUnit for Java TDD
   7
   8	#ifndef RUNTESTS_H
   9	#define RUNTESTS_H
   10
   11	#include <iostream>
   12	#include <cstdlib>
   13
   14
   15	#include <string>
   16	using std::string;
   17
   18	class RunTests_C
   19	{
   20	public:
   21	RunTests_C () {run = passed = failed = 0;}
   22	int getPassed() const {return passed;}
   23	int getFailed() const {return failed;}
   24	int getRun() const {return run;}
   25
   26	void print(std::ostream & out = std::cout) const;
   27
   28	void assertEquals(const char * const s1,
   29	string s2);
   30
   31	void assertEquals(string s1,
   32	const char * const s2);
   33
   34	void assertEquals(const char * const s1,
   35	const char * const s2);
   36
   37	template<typename T> void assertEquals(T x, T y);
   38
   39	// exit ends the program with the status code of the number
   40	// of failed tests.. if that is zero, then test is a success
   41	void finish() const { exit (failed); }
   42
   43	private:
   44
   45	int run; // number of tests run
   46	int passed; // number of tests passed
   47	int failed; // number of tests failed
   48
   49	void generateInstances(); // a hack to generate functions
   50
   51	};
   52
   53	#endif // RUNTESTS_H

   hashTable/runTests.cc

   1	// runTests.cc Class for Test-Driven Development
   2	// P. Conrad for CISC220, 06J
   3
   4	#include "runTests.h"
   5
   6	#include <iostream>
   7	#include <cstring>
   8	#include <string>
   9	using std::string;
   10
   11	void RunTests_C::print(std::ostream & out) const
   12	{
   13	out << "tests run: " << run
   14	<< " passed: " << passed
   15	<< " failed: " << failed << std::endl;
   16	}
   17
   18	void RunTests_C::assertEquals(const char * const s1,
   19	const char * const s2)
   20	{
   21	run++;
   22	if (strcmp(s1, s2) == 0)
   23	{
   24	passed++;
   25	std::cerr << "Passed: assertEquals(\"" <<
   26	s1 << "\",\"" << s2 << "\")" << std::endl;
   27	}
   28	else
   29	{
   30	failed++;
   31	std::cerr << " *Failed: assertEquals(\"" <<
   32	s1 << "\",\"" << s2 << "\")" << std::endl;
   33	}
   34	}
   35
   36	void RunTests_C::assertEquals(string s1,
   37	const char * const s2)
   38	{
   39	string s2s(s2);
   40	assertEquals(s1,s2s);
   41	}
   42
   43	void RunTests_C::assertEquals(const char * const s1,
   44	string s2)
   45	{
   46	assertEquals(s1,s2.c_str());
   47	}
   48
   49	template<typename T>
   50	void RunTests_C::assertEquals(T x, T y)
   51	{
   52	run++;
   53	if (x == y)
   54	{
   55	passed++;
   56	std::cerr << "Passed: assertEquals(" << x << "," << y << ")"
   57	<< std::endl;
   58	}
   59	else
   60	{
   61	failed++;
   62	std::cerr << " *Failed: assertEquals(" << x << "," << y << ")"
   63	<< std::endl;
   64	}
   65	}
   66
   67	void RunTests_C::generateInstances()
   68	{
   69	// this might not be necessary, but I was having trouble
   70	// getting the linker to find a version of assertEquals(int, int);
   71
   72	int x=1; int y=2;
   73	assertEquals(x,y); // generates a version for ints
   74
   75	// update: this seems to NOT be necessary with CC, but it DOES
   76	// seem to be necessary with g++
   77
   78	char a='x'; char b='x';
   79	assertEquals(a,b);
   80
   81	bool c=true; bool d=true;
   82	assertEquals(c,d);
   83
   84	string s1,s2;
   85	assertEquals(s1,s2);
   86
   87	}

   hashTable/testStudent.cc

   1	// testStuden.cc TDD for Student class
   2	// P. Conrad for CISC220 final exam, 06J
   3
   4
   5	#include <iostream>
   6	using std::cout;
   7	using std::cerr;
   8	using std::endl;
   9
   10	#include <string>
   11	using std::string;
   12
   13
   14	#include "student.h"
   15	#include "runTests.h"
   16
   17	int main(void)
   18	{
   19	RunTests_C test;
   20
   21	Student_C s(34,"Phill Conrad");
   22
   23	test.assertEquals(s.getStudentId(),34);
   24	test.assertEquals(s.getName(),"Phill Conrad");
   25
   26	test.print();
   27	test.finish();
   28	}

   hashTable/testStudentHashTable.cc

   1	// testStudentHashTable.cc TDD for StudentHashTable class
   2	// P. Conrad for CISC220 final exam, 06J
   3
   4	#include <iostream>
   5	using std::cout;
   6	using std::cerr;
   7	using std::endl;
   8
   9	#include <string>
   10	using std::string;
   11
   12	#include "student.h"
   13	#include "studentHashTable.h"
   14	#include "runTests.h"
   15
   16	int main(void)
   17	{
   18	RunTests_C test;
   19
   20	StudentHashTable_C h(5);
   21
   22	{ // enter inner scope
   23
   24	Student_C s1(13,"Phill Conrad");
   25
   26	test.assertEquals(h.lookup(1), static_cast<Student_C *>(NULL));
   27
   28	bool a1 = h.add(s1);
   29
   30	test.assertEquals(a1,true);
   31
   32	Student_C *r1 = h.lookup(13);
   33
   34	test.assertEquals(r1->getStudentId(),13);
   35	test.assertEquals(r1->getName(),"Phill Conrad");
   36
   37	//** (j) (5 pts) Explain (in a C++ comment)
   38	//** why the following line of code is needed,
   39	//** and what the result is if we don't include it.
   40
   41	delete r1;
   42
   43
   44
   45
   46
   47
   48	//** (k) (5 pts) Also, explain (in a C++ comment)
   49	//** why it is NOT necessary or correct
   50	//** to write the following line of code:
   51	//** delete s1;
   52
   53
   54
   55
   56
   57
   58	}
   59
   60	{ // enter inner scope
   61
   62	Student_C s2(23,"George Bush");
   63	Student_C s3(27,"George Washington");
   64	Student_C s4(27,"George Foreman");
   65
   66	bool a2 = h.add(s2);
   67	test.assertEquals(a2,true);
   68
   69	bool a3 = h.add(s3);
   70	test.assertEquals(a3,true);
   71
   72	bool a4 = h.add(s4);
   73	test.assertEquals(a4,false);
   74
   75	Student_C *r3 = h.lookup(27);
   76
   77	//** (l) (5 pts) Insert a line of code that will use the "deep compare"
   78	//** (that is, the overloaded == operator) to determine whether
   79	//** the value returned by h.lookup(27) is a copy of
   80	//** the student s3 (27,George Washington).
   81
   82
   83
   84	//** (m) (5 pts) Insert code to do whatever is necessary here to
   85	//** do proper memory management. There may be more blanks than
   86	//** the necessary number of lines of code.
   87
   88
   89
   90
   91
   92
   93
   94
   95
   96
   97	}
   98
   99	test.print();
   100	test.finish();
   101	}

End of Exam: total 100 pts