Posts by AuburnMathTutor

^ Perhaps I am reading it wrong. There's a difference between checking every value (which I agree you'll have to do) and checking every subsequence (which you indeed do not have to do) in the MSS problem.

I agree that you will have to check every value in the maximum subrectangle sum problem, but I am hesitant to agree that you will have to check every subrectangle, for the same reason. It's possible you're right when you say you'll have to check every subrectangle, but you might be able to get away with less than O(n^2). I don't know. I apologize if I'm reading your post incorrectly.

I know, but it's not clear to me that the best you can do is to check every subrectangle, since it's just as easy to say that you must check every subsequence in the maximum subsequence sum problem. It's not true in that instance, and it might not be true here either.

Plus, I am no longer going to entertain the thought of helping you, since you have cross-posted and didn't even take my advice to post in the appropriate forum. For shame.

Only post in one forum. Preferably, the correct one... like CS if you need help with an algorithm. Multiple posts means no more help from me.

^ Are you sure you'll have to check *every* rectangle? That's not obvious to me, especially given the fact that you can do better than that on the maximum subsequence sum problem, to which this seems related.

Yeah, 10 digit ints are getting pretty high up there. A 32-bit signed integer can hold a maximum value of 2^31 - 1 = 2147483647. As you can see, this is indeed a 10-digit number. My hypothesis is that if you try to give your program anything bigger than that number, it probably isn't going to behave.

How do you get around that?

Well, you can try bigger integer types. Really, for what you're doing, you probably want to read the data as string data, because then the digits are manifest and the length of the number's decimal representation is no longer a real concern.

Interesting.

You could always try *every* rectangle and take the maximum sum. You would have to pick your top, left, right, and bottom coordinate independently in this approach. Since you would have sqrt(n) choices for each (well, not really, but on the order of that many) where n is the total size of the array, I suppose you're talking about O(n^2)... plus a little to actually sum the elements, and I guess this might make it as high as O(n^3). You could be tricky in how you compute the sums, though, and by saving subrectangle sums I bet you could easily make the brute-force version O(n^2). Since this would be fairly easy to do, there's no excuse for doing worse than this. You will have to look at every element of the array, so you will be at least O(n).

So whatever your answer is, it will be somewhere between O(n^2) and O(n). Not a huge range of difference.

Are there any properties we can exploit? If you have a rectangle, could a subrectangle be better? Yes, sure. If you have a rectangle, could a superrectangle be better? Again, yes. Not a lot of help there.

I don't know, man. I hope this post has been of some meager help, though. I'll think about it some more and let you know if I come up with anything.

Upon rereading, I realized I left out a few things that will be important later. This is the first of what might be several addenda to An Introduction to Alphabets, Strings, and Formal Languages.

We will call s' a substring of s if s' occurs anywhere within s. That is, if s' is a substring of s if and only if s can be written as a concatenation of the form rs't for arbitrary strings r and t. We call s' a prefix of s if and only if s can be written as a concatenation of the form s't for arbitrary string t, and a postfix of s if and only if s can be written as a concatenation of the form rs' for arbitrary string t. Note: prefixes and postfixes are substrings.

We will say that a language L is a subset of language R if and only if every string in L is also in R.

We will say that a language L is equal to a language R if and only if L is a subset of R and R is a subset of L.

We will also allow some shorthand notations. By L^n (where L is a language and n is natural number) we will denote that language T which contains all strings which can be formed by concatenating any n strings of L.

There may be further addenda, but for now this is all I can think of.

lol ninja'd.

Well, a couple of things. First off, you're never allocating any room for the string a. You're just declaring a pointer for it; when the user enters data, it has nowhere to go. You probably want to do something like

char a[32];

Or something.

Second, you are using '=' instead of '=='. '=' does assignment and returns whatever it assigned; c++ will interpret any non-null thing as "true" in an if-statement, and therefore since "yes" is not evaluating to null, '=' is returning a non-null thing and if sees that as true.

However, when comparing strings, you want to use the strcmp() function. I recommend reading up on that; it's easy to use. There may be other ways to get the same effect in c++; look into the string.h library.

I hope you found this helpful. Please don't hesitate to ask me or others any more well-worded, intelligent questions. Thanks for posting your code, by the way.

Is it possible?

Yes, it is possible.
Post some code and mod me up and we'll talk about how you go about doing it.

Thread necromancy killed Vaudeville!

I have noticed a few questions popping up from time to time on the subject of formal languages in general, and on regular languages in particular. As I'm pretty bored and enjoy the study of formal languages to a reasonable extent, I thought I might try to give a quick-and-dirty treatment of the subject here. Who knows, maybe somebody will find it useful some day.

If a moderator sees this and feels it is appropriate to move to the Tutorials section, that might not be a bad idea. Then again, that's not my call.

An Introduction to Alphabets, Strings, and Formal Languages

We'll start at the very beginning of the topic of formal languages. What is a formal language? To be prepared to answer this question, we must first introduce a few other concepts with which programmers are likely already familiar, if informally.

We will call an alphabet any finite, non-empty set of symbols. I won't attempt a rigorous definition of symbol here, but don't worry about it, it's usually not too hard to tell what is a symbol and what isn't. I'll be sure to make clear what I'm talking about.

We will call a string over an alphabet any finite sequence of symbols from that alphabet. For notational convenience we will omit braces and commas.

Example: Let the alphabet E be the set of symbols {a, b, c}. One string s over E is (a, b, b, a, c) (from now on, …

^ Sorry, call me a callous bastard, but if you can't scrape together $30 US, you should probably not be playing video games. If these people are genuinely financially secure in their home country, let them buy games made over there for $1 US or whatever. Russia, China, etc. have better programmers than we do in the States anyway.

Funny, I thought this was a Computer Science forum, not a forum about using Google to solve math problems, "basic math", or "differential equations".

Of course computer science problems are a kind of math problem, and programming is a kind of applied mathematics. But I don't necessarily think that is the intent of either post. In particular, Google can not solve any problem about "math" in this sense. Spam?

Oh, what the heck. Let me apply some reputation to you guys.

I stopped trusting whores a long time ago.

I'm not sure how superstitious this makes me, but I believe in demons and probably the "devil" (though not necessarily of the strict Christian interpretation) and that there are lots of things which happen which are beyond the powers of human comprehension. Generally I believe in the possibility of psychic, demonic, supernatural, and spiritual phenomena. I don't know that this makes me religious, per se... but I have a fascination for the occult and old pagan mythology.

Yeah, I'm probably nuts. At least I don't go to witch's covens and wicca sleepovers and black masses. I pretty much just read a lot, and have nightmares.

Well, unless there are human beings living on some other planet. Star wars, anyone?

For me, it has nothing to do with society. Screw society. If I want to go buy a gun tomorrow to shoot holes in a tree in my backyard, that should be my right. A few maniacs running around blowing each others' heads off doesn't invalidate that right.

There's already gun regulation for convicts and other similarly dangerous elements of society. Better they have the means to show themselves for what they really are. Some Milton perhaps to convince the Brits:

"None can love freedom heartily, but good men; the rest love not freedom, but licence."
"I made [man] just and right, Sufficient to have stood, though free to fall."

Let's not go playing God, shall we gentlemen?

Some of the arguments in this thread are just plain ridiculous.

PCSAWICK829:
How much are you selling your TV for? I guarantee I *could* come into your house and take it for free, if I feel you're overcharging me. That seems pretty black-and-white to me.

^ They probably just emailed hotmail with a friendly request to reset the password to what it was previously.

If everything you now know about programming languages, if you could go back in time and change anything about C++ that you wanted to, what would you change, if anything?

Just out of curiosity, why is calling main() recursively legal in C but "illegal" in C++? Is there a technical reason for this, or is it aesthetic?

Why is C++ so freakin awesome?

Here's the answer to the question you're really begging here.

1. Show some effort. Come on. Give me something.
2. Have you tried this? It's very easy if you think about it.
3. If you haven't thought about it and don't plan to, I suggest you drop out of your course.
4. If you have thought about it and really don't get it, I suggest you drop out of your course.
5. If you haven't thought about it but will do so now that someone has chided you for your ways, consider staying in your course with your newfound maturity.

You're welcome.

Simple. Just have a precondition that the algorithm be specified in correct C code.

"How it is that I couldn't come up with a name for my project, but the project is still good enough for it to be approved so I can get out of here (aka The Handouts and the Pauper)"

^ I would take it a step farther and say that computer programming is essentially mathematical, and anybody who is good at programming is good at mathematics - part of it, anyway. Math isn't just algebra, calculus and physics... a lot of it is "relationships and algorythms" (sic) as well as logic, set theory, and proof theory.

I will agree, though, that many programmers don't acknowledge that what they are doing is math, and that they would generally consider themselves less than great at it, and may not be good at the analytic stuff, but I digress.

Learn as many languages as you can, not because you are worried you might have to know one or the other for some job, but because it will make you a better thinker and problem-solver.

I have learned and done work (including academic work, as a disclaimer) in assembler, C, C++, C#, Java, Javascript, Basic (several flavors), Scheme, Python, Perl, PHP, Smalltalk, Ada, Pascal, Fortran90, and Prolog, and probably a few others I'm forgetting. Plus if you count SQL (MySQL) and/or HTML, those too. And CSS, which suprisingly belongs to the previous category of general-purpose programming languages.

As an aside, I think that learning as many different languages as possible is important for, more than anything, the cognitive development and intellectual maturity of a programmer. This applies mostly to programming languages, but IMHO it holds true for natural languages as well, as well as other languages which are somewhere in between (mathematics comes to mind). Programming - and computer science - is about information and computations on it, and language is the mechanism by which information is computed.

^ No I believe you, but do you know why that rule was made when it wasn't a rule at all in C? At least I don't think it was a rule in C. What changed?

Calling main results in undefined behaviour, so not really.

Huh. I wasn't aware of that... it looks like you're right though, you're not supposed to do it in C++ though it's legal in C. And it works for me when I try it on g++. Weird... whatever. I don't want to get too far off-topic, but was there any compelling reason for the change, other than the nagging feeling that having a recursive main is a funky bad idea?

It's sort of a non-issue though, because you can always have main() call a dummy main2() function immediately, and you can certainly call main2() recursively. You can even pass main2() the command-line arguments.

But of course even that is something of a non-issue, because in principle I agree that looping probably is the better solution.

You can also call main() recursively from anywhere in your program. This could be a good or a terrible idea depending on what you're doing.

im pradeesh giv me some of ideas to my project it is "online exam for blind persons"

I wouldn't worry too much about the graphical layout of the page. Audio is probably a good idea.

You know, I imagine blind people know they are blind before they get online. Something about not seeing the screen probably tips them off.

First off, I'd write the for statement as this:

for (int count = no1; count <= no2; count++)

Notice that the "no1" thing is required and the "<=" thing is my preference.

Now, you want the sum of all numbers between no1 and no2. Inside the body of the "for" loop, it is guaranteed that the variable "count" will assume each value between no1 and no2, inclusive. So you want to add all of these up.

In particular, a + b + c = (a + b) + c. Also, a + b + c = 0 + a + b + c. You'll also want a variable (perhaps named "sum"?) to hold the answer.

Let us know if you need more than that. I don't want to just write it for you, but you're very close.

^ That's a relief. There was a lingering fear, even as I mocked it, that it would become the most important language ever and people might come here and see my mockery and cast me out of the good graces of Daniweb.

Uh, I think it's normally customary for the node class and the linked-list class to be made into separate entities. Without looking too hard at your code, this could be part of the problem. In any event, it's dangerous and - frankly - weird that every node contains a reference to the front, as well as the length of the list... since all nodes do.

In other words, if you are trying to learn about linked lists for an interview, this is in the danger zone. Are you familiar with the "standard" definition of a linked list structure? I'm very serious.

Looking at your code in somewhat more detail, the problem seems to be that there are several "fronts" and there's no clear indication you're ever using the correct one, or that the correct front is ever being established. This problem is corrected by correctly separating the ideas of "node" and "list". Please let me or others know if reference material on constructing and manipulating linked lists is required.

"D is a systems programming language. Its focus is on combining the power and high performance of C and C++ with the programmer productivity of modern languages like Ruby and Python.

Danger Will Robinson! Danger! Danger!

(Then again, PL/I worked out alright.)

i am doing mca .i want develop a application software in programming language using java. and iam not getting ideas.so plse give me some title related to project.

Yeah, not a CS question. What Daniweb needs is a "Software Development" subforum entitled "Poorly-written pleas by lazy unimaginative students looking for handouts". It might clutter the menu, but I guess an acronym could be devised...

So I imagine I'll take some flak for this, but this is in no way, shape, form, or any reader's imagination a question about "Computer Science", right? Why does the CS forum get all the "I want to do a vague project, tell me what to do" threads?

Pointers are used for exactly what you say: referring to something (data) by its location rather than by the name you choose to call it. It's a subtle difference but an important one.

There are lots of ways to use this one simple principle to accomplish lots of powerful things in C/C++. So while it may not seem like a lot, it's pretty neat. If you want specific examples of cool things pointers allow you to do, say so and I'm sure many will oblige.

#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
   char Ans;

   cout << "Keep Going? ";
   cin >> Ans;
   if(Ans=='y' || Ans=='y') main(argc, argv);
}

An idea, anyway. Otherwise, a do-while will work fine.

#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
   char Ans;

   do
   {
   cout << "Keep Going? ";
   cin >> Ans;
   } while (Ans=='y' || Ans=='y');
}

My question is: does the diff function above always return 0 for every floating value of x on any computer, and is there something in the implementation of the builtin round function which guarantees stability for int(round(x)) ? This does not seem to be documented in the official doc. What do you think of this ?

If it's not documented in the official documentation, use your function and forsake int+round. In fact, if you're not sure, or you think somebody reading your code later might not be sure, just go ahead and use your function. What's the harm? Performance? You're using Python.

IQ tests probably contain very good examples of questions which could be used to assess the potential of a programmer. What kinds of questions you include and which you discard will be an interesting decision, but a few come to mind...

All blargs are toogs, and some toogs are larts, therefore some larts are blargs.
True? False? Neither?

A few alien transmissions are intercepted. "Bleep quor mite sto" is translated as "Take me to your leader". "Quor sin sto ted" is translated as "You leader is good". "Quor nikste sin mite" is translated as "Your goodness pleases me." What is probably the best translation of the word "sto"?

Jim is shorter than Bob, who is taller than Anne but shorter than Tom. If Tom is the tallest, what can we say about the relative heights of Jim and Anne?

Give the next number in the sequence. 1, 2, 4, 9, 23, 64, ___.

Which of the following words is least like the other?
Gold
Euros
Money
Dollars

Someone spent the following amounts of money on different drinks. Did they spend an odd number of US coins, an event number, or can it not be uniquely determined?
- 75 cents
- 89 cents
- 77 cents
...

Let a $ b = (a+b)/ab. Does (a $ b) $ c = a $ (b & c)? Does a $ b = b $ a? Is there …

Concurrency
Deadlock
functional programming
cloud computing
parallel computing
distributed computing
p vs np problem
algorithm design
communication protocols
recursion.

For my money, the following are the more promising ideas.

Concurrency
cloud computing
parallel computing
distributed computing
communication protocols

The others are too vague, beaten to death, or too hard to treat in a thoroughly technical manner and actually *do* anything.

A pretty sweet method is the Master Method (or the Master Theorem). Given a recurrence relation in a particular common form, it can often tell you immediately what the time complexity will be.

Otherwise, the general method to prove a time complexity from a recurrence is going to be to find an answer and then prove it using mathematical induction. As to how you find an answer... well, you can use techniques similar to those employed in proving the convergence of sequences.

In general, I believe solving generic recurrence relations is pretty tough. I might be mistaken, though.

You might be able to argue using a sort of tree. I know that is typically done for MergeSort, for instance.

please be serious, I'm really out of Idea!

Perhaps you can help me by going through my list and explaining what is wrong with each of the proposed system names. Most computing systems have ridiculous names, and that's part of the point I was making.

(e.g a system for enrollment in the registrar section my classmate already picked it)

Several of the names I gave are less ridiculous than actual names of similar products. My school calls its thing "AU Access" and the mail server "Tiger Mail". The names are going to be dumb. Just pick anything.

i dont know what would be my title or my project be.

Oh, you don't know your project either? Generally speaking, you need to figure out what you're doing before you name it. You can always pick a generic name and decide on the project later. Do you need help picking a project to do, or naming a project you've already formulated?

Jeez this is pretty weak. If you can't come up with your own completely arbitrary name for a system, how in the world can you hope to make such a system, or have any original idea ever?

I don't know. AutoSchool, RoboSchool, SchoolTool, SchoolSystemDeluxe, E-SchoolMonitor, AClockworkSchool, MS Office School 2010, Lotus OneSchool, School Chrome, SilverSchool, RedHat School, GotSchool?, Schools-R-Us, Schooltopia, Schoolocity, Schoolipedia, Schoolazon, Schoolpad, School-X, SchoolSafari, SchoolScape, Principia Schoolematica, Schoolhoo!, Alta School, School Vista, BabelSchool, SchoolFish, YouSchool, SchoolTube, FaceSchool, SchoolBook, MySchool, SchoolSpace, School Zone, OpeNSchool, SchoolOffice, CalcuSchool, DirectSchool, SchoolX, School-GL, 2001: A School Odyssey.

See how easy that was?

Perhaps a fully-automated comprehensive Computer Science tutor program? Program in all the ABET subjects and a few programming languages with practice tests, quizzes, vocabulary, etc. Make it extensible too so people can add on new features (flashcards, networked tests/quizzes, etc.) and information (maybe computer security, or real-time systems).

You could keep the features and data minimal initially, if you demonstrate a capability to make addons.

... I'll give it a shot, but I'm no expert at scripting language lambda expressions.

Lambda expressions are simply a way of defining a function without assigning a name to the function. They're sort of like function literals, in the same sense "cat" is a string literal and animalName might be associated with the value "cat".

Whenever you'd need a literal value where a value was expected (say, you call factorial(5) to get 120, rather than saying n=5;factorial(n)) you can have similar situations where a function literal might be good (you call plot(lambda x: x*x) instead of def squarefunc(x):return x*x; plot(squarefunc)).

So yeah, function literals. I think that's a fair comparison.

These are to be construed as hints; you must still show the work involved in actually solving the problem.

1) Show that the set of regular languages is closed under reversal. That is,if L is the regular, then so is { x R :x € L} where x R denotes the reversal of string r.

Hint: Every regular language is accepted by some NFA, and every language accepted by an NFA is a regular language. Assume an NFA for L, and describe how you would construct the NFA for rev(L).

2)Give the example to show each of following for the language L1 and L2:

a)If L1 belongs to L2 and L2 is regular ,then L1 can be regular or nonregular.

S* is a regular language.

b)If L1 and L2 are nonregular,then L1∏L2 can be regular or nonregular.

The empty language is regular.

c)If L1 and L2 are nonregular,then L1 U L2 can be regular or nonregular.

L union complement(L) = S*

3)Suppose language L is accepted by FA M.Let L E be the subset of L consisting of those strings in L of even length.Show how to convert M to an FA for L E.

What if you broke each state Q into two states Q_E and Q_O?

4)Prove the set of all strings of a and b with more a’s than b’s is nonregular.

Pumping lemma for regular languages.

5)For each of the following languages ,state whether it is regular or not …

Well, pseudocode is just any arbitrary description of a computational procedure not meant for interpretation by a computing machine in its initial form. I agree with a previous poster that there aren't rules of pseudocode, except what an instructor or you impose.

Always - whether doing pseudocode or real code - start by talking yourself through the problem in plain English. This probably won't work as real code, but depending on the problem, it might pass as pseudocode. If so, write that down and you're done.

How can you tell if your description is "good" pseudocode? Well, it should encode the solution to your problem in a way that you can understand it. Preferably, others should be able to understand it as well. English is a good start.

But English can be ambiguous and lack some of the precision of a more mathematical/computational notation. Go ahead and express common mathematical expressions and functions by some common symbolic representation (for instance, "add a to b and put the answer in c" becomes a c <- a + b) and identify operations which you assume have solutions and consider these as external functions (for instance, "find the number of occurrences of pattern in string and put the answer in repcount" could be repcout <- countall(pattern, string)). Anything else that has an obvious shorthand or symbolic representation should be transformed, simply because it reduces ambiguity to use the symbolism.

Now, to make sure you have really tight, coherent pseudocode …

^ Ninja'd me.