Question 1
In Module 2 (Assignment 3) you wrote a program where the computer searches an array. For this question you will need to write a program that uses this algorithm to determine how many guesses are needed to find each element in the array. For example - if we used an array of size 10 - here is the output (if I used the floor function to round)
Number Guesses Needed
1 3
2 2
3 3
4 4
5 1
6 3
7 2
8 3
9 4
10 3
You will create a JSFiddle program to allow the user to input a number - and that will give this output. You will copy and paste the output for an array of size 15 - and give a link to the fiddle in the response. I will be testing your Fiddle - it should allow me to enter an array of size n and give me this table.
Answer 1
This can be implemented easily by taking the Module 2 code and running it in a for loop – keeping track of the number of search tries to for each number. The output would be
Number: Guesses Needed:
1 4
2 3
3 4
4 2
5 4
6 3
7 4
8 1
9 4
10 3
11 4
12 2
13 4
14 3
15 4
Question 2
A simple design for a Linked List uses this design;
Class: Node; Properties: Next
Class: List; Properties: Head
Where aNode.Next is of class Node
Where aList.Head is of class Node
Is there any sort algorithm which simply cannot be used with this design? Why?
A full list of sorting algorithms is at https://en.wikipedia.org/wiki/Sorting_algorithm - you only need to list and defend one algorithm.
Answer 2
A singly linked list allows for iteration in only one direction. This provides some limitations to the types of sorting and searching algorithms that can be used without significant modifications to the implementation of the list. In fact most Sort algorithms (outside of insertion sorting) will have some level of difficulty working with a singly linked list. Some sort algorithms that would be particularly challenging would be;
Binary Sort – no simple way to determine the midpoint of the List, any algorithm that requires breaking up the List into smaller defined chunks is pretty much out – such as Merge Sort.
Quick Sort – this sort algorithm requires bi-directional iteration through the List. Any algorithm that requires bi-directional iteration can be pretty much ruled out.
This list is not exhaustive – but the point of this question is to identify that uni-directional nature of a singly linked list and understand the limitations of this implementation.
Any answer that demonstrates the challenges of the single direction traversal of Singly Linked Lists and how they would present a challenge to specific sort algorithms is acceptable.
Question 3
Is it possible to implement a Queue (enqueue/dequeue) using one or more Stacks (push/pop) - if so how? and how many Stacks would you need? You can show this with actual code or pseudocode. I can read all forms of pseudocode - so you are free to use any of the forms you are comfortable with to demonstrate how you would implement Enqueue and Dequeue of a Queue using stacks.
Answer 3
The enqueue and dequeue algorithms can be implemented using 2 stacks.
Enqueue – Stack 1: A-B-C-D
Push N to Stack 1 Stack 1: N-A-B-C-D (same as Enqueue)
Dequeue – Stack 1: A-B-C-D
Pop from Stack 1, Push to Stack 2; Stack 2: D-C-B-A
Pop from Stack 2; Stack 2: C-B-A
Pop from Stack 2, Push to Stack 1; Stack 1: A-B-C
Question 4
In an complete graph all nodes have an edge that connects with all other nodes (you should know this). If your graph has 3 nodes (triangle) - there are 6 possible paths that traverse all nodes (all of which use external edges - since all edges are external). ABC, ACB, CAB, CBA, BAC, BCA If you create a 4 node graph - how many possible paths are there that can traverse all nodes that do not use ONLYexternal edges. Hint: Draw a square and connect the cross vertices. Paths can use an external edge, it just cannot use all external edges. Paths starting from different nodes are different paths. If the nodes of the graph are labeled ABCD (and an external edge traversal is ABCD) - give all the non-external edge traversals.
Answer 4
Starting at Node A there are 4 paths that do not use external edges
B - C
| |
A – D
A-B-D-C
A-C-B-D
A-D-B-C
A-C-D-B
Since there are 4 starting points that can implement the same pattern then there are 16 possible traversals.
Question 5
You wish to implement the Math.Pow(x, y) function available in Javascript yourself. Do it - paste your function into the code box - call your function Power - it should accept 2 arguments.
What is the time complexity O of your algorithm?
function Power(base, power) {
}
Answer 5
function Power(base, power) {
var result = base;
for (var i=1; i < power; i++)
{
result *= base; }
return result;
}
Complexity O(n) – where n is the power. This is the simple case which was sufficient for the problem. I would also accept the more complex cases and the recursive cases which are outlined at http://www.programcreek.com/2012/12/leetcode-powx-n/ . You must also have the correct complexity associated with the case – as the complex cases are not O(n)
Question 6
Using the following definition for a Binary Tree Node - complete the functions isFull and isLeaf - returning either true or false.
var TNode = function(_content) {
this.left = null;
this.right = null;
}
Answer 6
TNode.prototype.isLeaf = function() {
return (this.left == null && this.right == null);
}
TNode.prototype.isFull = function() {
return (this.left != null && this.right != null);
}
Question 7
Describe (you can use pseudo-code or write the function in Javascript) of an algorithm that can check an algebraic expression to determine if the parentheses are balanced.
For example;
passing the text string "3 * (x + (y + 9) - 4)" should answer true
the string "3 * (x + (y + 9 - 4)" should answer false
Use the CORRECT data structure to create an efficient algorithm.
Answer 7
function parenCheck(cString) {
var cStringArray = cString.split("");
var stack = new Stack(); // A javascript array will also work here
for (var i=0; i < cStringArray.length; i++)
{
if (cStringArray == “(“) stack.Push(“+”); // anything pushed will do
if (cStringArray == “)“) stack.Pop();
} return (stack.length == 0); }
Question 8
Describe in less than 20 words why the study of data structures in important for computer science and IT. There are some key words I will be looking for in grading this - make sure you include them.
Answer 8
Data structure are fundamental to the efficient storage and retrieval of data in computer systems.
You must convey these three concepts in your solution (efficiency, data storage, data retrieval) for full credit.