Questions
(a) Consider the general k-ary search algorithm (generalization of binary search) which splits a sorted array...

(a) Consider the general k-ary search algorithm (generalization of binary search) which splits a sorted array of size n into k subsets each of size n/k and recursively searches only one of these k subsets. Which one of these k subsets should be searched is decided by making (k − 1) comparisons, each of which can be done in constant time. Clearly, the recurrence relation for this k-ary search algorithm can be written as,

T(n) = T(n/k) + (k − 1)

Since k is a variable in the above recurrence relation, as an algorithm designer, you have the flexibility to set the value of k. Suppose you set k = n 2/3 . Analyze running time of the resulting algorithm in Θ notation.

(b) Show that f(n) = 2n 2 + 5n+ 3 is O(n 2 ) by finding adequate constants c and n0 where f(n) ≤ cn2 for all n ≥ n0.

In: Computer Science

College Expenses Science Class Math Class C.I.S. Class English Class Tuition $200 $190 $230 $213 Books...

College Expenses

Science Class

Math Class

C.I.S. Class

English Class

Tuition

$200

$190

$230

$213

Books

$331.35

$305

$295

$280

Computer / Internet

$66.27

$80

$93

$106

Other supplies

$75.00

$30

$40

$55

Tell me about your college expenses you have by filling this table with subjects and data. Then write two paragraphs telling me about the information you provided in the table.

Give the page a proper title. Align left all your data in the table. Align left your paragraphs below the table. Indent each paragraph. Get creative and have fun!

In: Computer Science

Given a parentheses string s, compute the score of the string based on the following rule:...

Given a parentheses string s, compute the score of the string based on the following rule: • If s is not balanced, the score is 0. • () has score 1. • AB has score A + B, where A and B are balanced parentheses strings. • (A) has score 2 * A, where A is a balanced parentheses string. A balanced string satisfies the following requirements: • The number of ‘(’ equals the number of ‘)’ in the string. • Counting from the first position to any position in the string, the number of ‘(’ is greater than or equal to the number of ‘)’ in the string. (For example, ‘)(’ is not balanced.) The length of s is at most 30. Input: The input is a parentheses string s. Output: Print the score of s. Examples:

1. Input: (())

Output: 2

2. Input: (()(()))

Output: 6

3. Input: ((()())

Output: 0

sketch code:

#include <iostream>

#include <string>

using namespace std;

void SolveC(){

string s;

cin >> s;

/* your code starts here */

}

int main() {

SolveC();

return 0;

}

In: Computer Science

In C++ with lots of comments please Complete a binary search tree of 20 numbers Show...

In C++ with lots of comments please

Complete a binary search tree of 20 numbers

Show in the output the steps while it's performing the search with 20 numbers in a text file called list.txt

The numbers will be imported to the program

Simple program that should let you have the option to search for numbers, remove numbers, print numbers, and insert numbers in the binary tree

If the number isn't there then give an error

In: Computer Science

You will write classes from the last in-class assignment, R&DLibrary. R&DLibrary is the main file in...

  1. You will write classes from the last in-class assignment, R&DLibrary. R&DLibrary is the main file in which a user can choose to enroll themselves, check out an item, return an item, pay a fine and display their account (what is currently checked out, accumulated fines).
  2. Write a material class that calculates the fine based off of the type of item, the length it’s been checked out and whether or not it’s even been checked out.
  3. Lastly, write a employee Class that contains the username of a user, the items that person has checked out, a copy of the accumulated fines and the number of items checked out.

In: Computer Science

produce the pseudo code for the Barber routine Clipaway() and the Customer routine Cutmyhair() such that...

produce the pseudo code for the Barber routine Clipaway() and the Customer routine Cutmyhair() such that each customer is given a customized haircut and each customer pays for the Barber’s service.

The Sleeping Barber Problem This works for a shop that holds a total of N customers with one barber. If a customer cannot enter the shop, the customer will be forced into the street. Start the Barber before the customers.

Shared variables:

const int num_chairs = N; // number of patrons allowed in shop at a single instant

semaphore customer = 0, // customer semaphore

barber = 0, // barber’s semaphore

mutex = 1; // for mutual exclusion to a shared area

int num_waiting = 0; // # of customers that are waiting

Customer( )

{

// Customer begins by trying to get into the shop. acquire(mutex); // I am trying for a chair in the waiting area but must get into the

// critical section . .

if (num_waiting < num_chairs)

{ // If a chair is available.

num_waiting++; // I am a (one more) waiting customer.

release(customer); // Hey Barber! I want my hair cut! Wake up!

release(mutex); // Release my hold on mutual exclusion.

acquire(barber); // I will wait until the barber is ready for me.

Cutmyhair( ); // Showtime . . . its makeover magic!

}

else

{

release(mutex); // Release my hold on mutual exclusion – no chairs – I’m

// going home!

}

}

Barber( )

{

While (TRUE)

{

acquire(customer); // Catch up on my sleep if no customers are waiting.

// Who dare wake me? Oh, this is my job!

acquire(mutex); // Mutual exclusion to grab the next customer . . .

num_waiting--; // . . . who won't be waiting anymore

release(barber); // . . . as soon as I wake the poor soul up.

release(mutex); // I am feeling very creative – hmmm, what is in style today?

Clipaway( ); // This is where I do my best work, ooops – ah nothing a hat won’t

// fix.

}

}

--------------------------------------------------------------------------------

Please write in c++

In: Computer Science

using java language "Data Structures" I have to write program which stores string entered by user...

using java language "Data Structures"

I have to write program which stores string entered by user into cursor array implementation

here is the code

public static void main(String[] args) {

CursorArray sorted =new CursorArray();//the strings must added here how can i store them
         
       String []inputs = new String[50];
          
       for (int i=0; i< 50; i++) {
           System.out.println("Enter the words you want to sort and use exit to stop");
           if(input.next().equals("exit"))
               break;
       inputs[i] = input.nextLine();
       }
}   
      

you can put the code of reading in a method

and this is part of cursor class

public class CursorArray {

   Node[] cursorArray = new Node[10];

   public int initialization() {

       for (int i = 0; i < cursorArray.length - 1; i++) {

           cursorArray[i] = new Node(null, i + 1);
       }
       cursorArray[cursorArray.length - 1] = new Node(null, 0);
       return 0;
   }

   public int malloc() {
       int p = cursorArray[0].next;
       cursorArray[0].next = cursorArray[p].next;
       return p;
   }

   public void free(int p) {
       cursorArray[p] = new Node(null, cursorArray[0].next);
       cursorArray[0].next = p;
   }

}

public class Node {
  
  
   String data;
   int next; //index

   public Node(String data, int next) {
       this.data = data;
       this.next = next;
}

}

In: Computer Science

1. Write a query to: a. select data from INVOICES table as follows: Invoice date in...

1. Write a query to:

a. select data from INVOICES table as follows:

  • Invoice date in MM/DD/YYYY format
  • Invoice Date in DD-Mon-YYYY format
  • Invoice Total rounded to the nearest dollar

Note: you can alias columns as you sit fit

b. select data from VENDORS table as follows:

  • Vendor Name
  • Concatenate Vendor Name with the string ‘s Address
  • Concatenate Vendor City, Vendor State and Vendor Zip Code (alias this)

Your output should look like this (this is just an example of it). Note how after each vendor name there is ‘s

vendor_name Vendor Address
Register of Copyrights Register of Copyright's Address: Washington, DC 20076
Newbrige Book Clubs Newbrige Book's Address: Los Angeles, CA 90045

In: Computer Science

modify code to write the output as an HTML table to a file in the output...

modify code to write the output as an HTML table to a file in the output directory.

The file that is saying to work at :

SOURCE CODE IN PERL:

print "Enter principal amount: ";
$P=;
while($P<=0)
{
print "Principal must be positive. Try again: ";
$P=;
}
print "Enter number of times interest is applied in a year: ";
$n=;
while($n!=12 && $n!=4 && $n!=2 && $n!=1)
{
print "It must be 12, 4, 2 or 1. Try again: ";
$n=;
}
print "Enter the annual rate of interest: ";
$r=;
while($r<=0 || $r>=25)
{
print "Rate of interest should be between 1 and 24. Try again: ";
$r=;
}
print "Enter the number of years: ";
$t=;
while($t<=0 || $t>=100)
{
print "Rate of interest should be between 1 and 99. Try again: ";
$t=;
}
print "\nYear Period Starting Balance Interest Ending Balance\n";
for($i=1; $i<=$t; $i=$i+1)
{
for($j=1; $j<=$n; $j=$j+1)
{
$interest=$P*($r/($n*100));
print sprintf("%-4d %-6d \$%-15.2f \$%-7.2f \$%-13.2f\n",$i, $j, $P, $interest, $P+$interest);
$P=$P+$interest;
}
}
print sprintf("Final Balance is \$%.2f\n", $P);

In: Computer Science

Write a C++ program that uses array to store the salaries of 10 employees working in...

Write a C++ program that uses array to store the salaries of 10 employees working in a small firm. The program should take average of the salaries and the max and min salaries being paid to the employees

In: Computer Science

convert the following grammar to Chomsky Normal Form S -> D0S1 | 1 D -> F0D1...

convert the following grammar to Chomsky Normal Form

S -> D0S1 | 1
D -> F0D1 | 0 | e | FG
F -> SF | DD | S
G -> GK | DG

In: Computer Science

Websites and online applications need to be secured as they are exposed to the world. What...

Websites and online applications need to be secured as they are exposed to the world. What role
does the TLS and SSL handshake process play when initiated by a web client accessing a
secure website? Explain how public key encryption works. Explain how encryption methods are
evaluated using a CIA triad. (20 Mark

In: Computer Science

Allison is a system analyst; she needs to ensure to create a system design which is...

Allison is a system analyst; she needs to ensure to create a system design which is flexible and adaptable. The better the system design the more cost can be saved in the future. X is performed most often to improve the existing software rather than respond to a crisis or a system failure. Identify X. State and explain in details the practice of X.

In: Computer Science

Design a program in JAVA that allows you to experiment with different sort algorithms. The algorithms...

Design a program in JAVA that allows you to experiment with different sort algorithms. The algorithms are shell sort and quick sort. Assume that input data is stored in a text file.

Experimenting with a prototype data (integers from 1 to 10) to ensure that your implementation works correctly and the results match expectations. The program will sort what is in the text file and print the amount of comparisons and exchanges for both algorithms.

In: Computer Science

Google relies on__ to relay information related to its mapped software?

Google relies on__ to relay information related to its mapped software?

In: Computer Science