(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 |
$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: • 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 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
In: Computer Science
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 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:
Note: you can alias columns as you sit fit
b. select data from VENDORS table as follows:
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 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 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
In: Computer Science
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 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 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
In: Computer Science