CCCS $315$: Data Structures and Algorithms

Assignment $1$

Type of Assignment

Individual Work

Estimated Time: $120$ minute

Description

In this Assignment, you will study, Analyze $($Big$-$O$),$ and implement a singly Linked List Arrays. You also compare an implementation of a method using recursive programming vs iterative programming.

Learning Outcomes

Recognize the use of the linked$-$list and recursive programming

Apply Big$-$O notation to analysis of an algorithm

$$Evaluation

$\backslash$table$[[$Points$,],[10,$Code formatting$],[40,$Part $1$ Java implementation of a Linked List$],[15,$Part $2$ Big$-$O Analysis Questions$],[4,$Part $3$ Comparison of recursive vs iterative solution$],[69,$Total$]]$Part $1$: Java implementation of a Linked List

For this part, you will be provided a set of skeleton classes for you to implement a singly linked list of

type int. You will also be provided a minimal set of test cases. You are encouraged to augment the test

suite.

Import the eclipse project Assignment$1.$zip into your workspace. The package includes a complete Node

class as well as a test suite MyLinkedListTest. A skeleton MyLinkedList class is provided with the

following methods that need to be implemented:Note that each of the above method are thoroughly commented in the included assignment$1$ package

and that additional methods may be required. Additionally, you may assume that methods are provided

valid input.

To submit this part of the assignment, you are required to export your project as an Archive ZIP file and

compress it using the ZIP format for upload in MyCourses. See instructions posted on MyCourses for

importing and exporting Eclipse Projects.

Part $2$: Big$-$O Analysis

Please indicate the Big$-$O time$-$complexity of each method in your Linked List implementation in the

comments of each method. One point for each method.

Part $3$: Comparison of recursive vs iterative solution

In the comment header of the LinkedList class, answer the following questions:

$[2$ points$]$ Which findMin implementation is faster and why?

$[2$ points$]$ Which findMin implemtation has less lines of code and why?