Your solution to the posed problem is due at the start of class on the day shown. Homework can be done in groups of up to three, but all individuals in the group need to be part of the discussion and familiar with the proposed solution. Each homework should take about 2 to 3 hours of thought (and group discussion if in a group) and 30 minutes to write down. The emphasis will be on the thoughtfulness of your response rather than its correctness. Homework is to be completed without the use of outside resources. Answers should be in the form of typed explanations, typed algorithms, and/or hand drawn figures with some typed explanation. Little or no credit will be given for late homework.
Binary Search Tree: Word or text file
Priority Queues: Word or text file
Dictionaries: Word or text file
Problem #0a due on 25 Jan.
Describe how to use an array to implement an unordered list of nodes (as described in class). Assume the max number of nodes (elements) is 100. Determine how to do the
following functions: access, length, concat, createEmptyList, isEmptyList,
searchFor, remove, inserti, and insert. How would any of these functions
change if the list was to be ordered?
Problem #0b due on 25 Jan.
Write the recursive function:
fac(x) returns x factorial.
Tutorial #1 due on 6 Feb.
Complete the following units of the Java tutorial:
Hello World
Variables
Object-Oriented Java
Conditionals and Control Flow
Arrays and ArrayLists (just the Arrays part)
Loops
Email Jay at jnash1@conncoll.edu when you have completed
all of the assigned units.
Problem #1a due on 30 Jan.
Describe how to use a set of nodes with pointers (as described in class) to
implement an unordered list with no size limit. Determine how to do the
following functions: access, length, concat, createEmptyList, isEmptyList,
searchFor, remove, inserti, and insert. How would any of these functions
change if the list was to be ordered?
Problem #2a due on 1 Feb.
Describe how to implement a stack using an array (assume it will never
have more than 100 elements).
Do the five stack functions.
Describe how to implement a stack using an set of nodes with pointers (this stack will have no number of element limit).
Do the five stack functions.
Do not use the List abstract data type as part of your solutions.
Problem #3a due on 6 Feb.
Describe how to implement a queue using an array (assume it will never
have more than 100 elements).
Do the five queue functions.
Describe how to implement a queue using an set of nodes (this queue will
have no number of element limit).
Do the five queue functions.
Problem #3b due on 6 Feb.
Write the recursive function:
towers(x,y,n) moves n disks from peg x to peg y. You can use the predefined functions move(x,y), which moves one disk from peg x to peg y, and otherPeg(x,y), which returns the other peg besides x and y. So a call to otherPeg(A,B) would return C.
Show how it would run if called with towers(A, C, 3). In other words, show all the recursive calls to towers and calls to move in order. Then consider just the calls to move. Did it properly move all the disks from A to C?
Problem #4 due on 8 Feb.
Describe how to implement a binary search tree using a set of nodes (this tree will have no number of element limit).
Do the six BST functions.
Can you determine how to implement a binary search tree using an array (assume it will never have a depth of more than 7)?
Consider the six BST functions.
Problem #5 due on 15 Feb.
Describe how to implement a search tree that has a worst time search,
insert, and delete time of no more than O(lg n). This tree should have no number of element limit.
Do the six functions defined for binary search trees.
Discuss how you would implement this if there was a maximum to the number of elements.
Problem #6 due on 20 Feb.
Describe how to implement a priority queue that has a worst case findMin of O(1)
and an insert and delete time of no more than O(lg n). Do not use an AVL tree.
You can assume that n is always less than 128. In other words, there
is a max of 127 elements that can be stored in the queue.
Do the five Priority Queue functions.
Problem #7 due on 22 Feb.
Describe how to implement a dictionary that has an average lookUp,
insert, and delete time of O(1), but uses an array of
no more than 2 times the maximum number of elements that will be stored in the dictionary.
Do the five Dictionary functions.
What is the worst case time for lookUp?
Tutorial #2 due on 27 Feb.
The Evening TA Sessions are in progress. See
here for the schedule.
Go to one of the TA Sessions in NLH214 before class on 27 Feb to gain familiarity with the lab and ensure you can log into the Ubuntu machines. If you are unable to attend one of these evening sessions, you may go to the lab at any time when it's unoccupied to complete the assignment, although you will need to contact one of the class TAs or the CS Tech (see the Course Description for contact information). Also contact them if you have any issues with logging in or completing the assignment.
Complete lessons 1 through 5 of this introduction to the Ubuntu operating system. You can use the computers in NLH214 for this assignment, but in addition, you should consider setting up Unix/Linux/Ubuntu on your home computer. Once you have completed the tutorial, use the NLH214 computers to make sure your login works and run through this short sequence of commands to practice on the machines in the lab.
Email Jay at jnash1@conncoll.edu when you have completed the assignment.
This assignment is due before class.
Problem #8 due on 27 Feb.
Give a one sentence explanation of how you would perform each of these procedures on a graph using both methods of representing a graph as described in class. In addition, what is the runtime (big O) for each procedure for each method of representing? Note: as with the other HWs, your answers need to be very readable, preferably typed. Also, unlike other HWs, this one will be graded on correctness.
incidentEdges(v) -- returns the set of edges touching vertex v
adjavency list:
adjavency matrix:
areAdjacent(v u) -- tests if vertices v and u are adjacent -- returns T or F
adjavency list:
adjavency matrix:
neighbors(v) -- returns the set of nodes adjacent to v
adjavency list:
adjavency matrix:
insertEdge(v u) -- inserts an edge between vertices v and u
adjavency list:
adjavency matrix:
removeEdge(v u) -- removes the edge between v and u
adjavency list:
adjavency matrix: