Data Structure and Algorithms

Assignment Scenario

This coursework is aimed at testing the students understanding of data structures and algorithms. Several problems with practical examples are given for each task which the learner must answer fully to demonstrate their grasp of the subject.

Where applicable, each student is expected to implement the solution in C# and include the source code in a printed report. The student will demonstrate a working program in class for oral examination. Microsoft Visual C# 2010 Express or later will be used to develop the program.

LO1: Understand Data Structures and Algorithms

1. Discuss abstract data types such as int, double, float, bool and show your understanding of the relationship between these data types and a computer memory.

2. Discuss the different types of data structures below and show appropriate practical application by giving an example, produce design specification for data structures explaining the valid operations that can be carried out on the structures.

a. Array
b. Array list
c. Linked list
d. Stack
e. Queue
f. Tree
g. Strings

3. Design pseudo-code and flow charts and then write a program in C# that generates an array of 1,000 random integers. Add three methods for bubble sort, insertion sort and quick sort to use on this array. Time each algorithm and compare the times. Draw a graph of time versus size of the array by varying the elements of the array from 10 to a 1000 in steps of 50 for the algorithms and comment of the  shape of the graph in relation to efficiency of each of the algorithms.

4. Design pseudo-code and flow charts to demonstrate different numerical algorithms over the integers, including EUCLID, FIBONACCI and SIEVE OF ERATOSTHENES. You should include recursion where appropriate.

LO 2: Implement Data Structures

1. Implement Stack and Queue data structures in C# using both arrays and arrayList. In both cases implement methods to add and subtract elements as well as counting and clearing the data structure.

2. By selecting an appropriate data structure for the problem, design and implement a C# class that allows a teacher to track the grades in a single course. Include methods that calculate the average grade, the highest grade, and the lowest grade. Write a program to test your class implementation. Your design should include Pseudo-code.

3. Write an class with methods of GenerateRadomArray() to generate an array of random 100 elements in the range of 100 to 1000 and search methods: SequentialSearch() and BinarySearch() . Add a new private Integer data member named compCount that is initialized to 0.

In each of the search algorithms, add a line of code right after the critical comparison is made that increments compCount by 1. Run both methods, searching for the same number, say 230, with each method. Compare the values of compCount after running both methods. What is the value of compCount for each method? Which method makes the fewest comparisons?

LO 3: Understand how Strings are Structured and Processed

1. Given the string “Understand how strings are structured and processed” as an input, write a C# class with the following methods to:

a. Determine the position of any character in a string.

b. Extract any word from the given string.

c. Remove all spaces from the string.

d. Order the letters in the given string alphabetically.

2. Write a function that converts a phrase into pig Latin. A word is converted to pig Latin by removing the first character of the word, placing it at the back of the word, and adding the characters “ay” to the word. For example, “hello world” in pig Latin is “ellohay orldway.” Your function can assume that each word consists of at least two letters and that each word is separated by one space, with no punctuation marks.

1.1 produce design specification for data structures explaining the valid operations that can be carried out on the structures

1.2 explain the operation and performance of sorting and search algorithms

1.3 explain the operation of recursive algorithms and identify situations when recursion is used

2.1 implement data structures in an executable programming language in the context of well-defined problems

2.2 implement opportunities for error handling and reporting

2.3 test results to enable comparison with expected results

3.1 explain common string operations and their practical applications

3.2 demonstrate the outcome of string operations in specified algorithms.