19
голосов
3ответов
17471 просмотров

In Natural language processing, what is the purpose of chunking?

In Natural language processing, what is the purpose of chunking?

2
голосов
2ответов
988 просмотров

Is there a simple way I can tokenize a string without a full-blown lexer?

I'm looking to implement the Shunting-yard Algorithm, but I need some help figuring out what the best way to split up a string into its tokens is. If you notice, the first step of the algorithm is "read a token." This isn't exactly a non-trivial thing to do. Tokens can consist of numbers, oper...

21
голосов
6ответов
4471 просмотров

Hilbert System - Automate Proof

I'm trying to prove the statement ~(a->~b) => a in a Hilbert style system. Unfortunately it seems like it is impossible to come up with a general algorithm to find a proof, but I'm looking for a brute force type strategy. Any ideas on how to attack this are welcome.

2
голосов
8ответов
2903 просмотров

Context Free Grammar for Unary Addition

Given an alphabet of 1s I want to parse addition of the form 1^k + 1^j = 1^k+j This is pretty easy to represent with a pushdown automaton simply by pushing a 1 on to the stack on each of the first two 1s, and then popping on the last set of 1s. However, I can't seem to figure out how to repre...

19
голосов
3ответов
16605 просмотров

What is the difference between monotonicity and the admissibility of a heuristic?

I'm reading over my AI textbook and I'm curious about what the difference is between monotonicity and admissibility of heuristics (I know they aren't mutually exclusive). As far as I can tell, an admissible heuristic simply means you are ensured to get the shortest path to a solution if one exi...

29
голосов
5ответов
15721 просмотров

How to keep up to date on latest computer science?

I was re-reading some of my Steve McConnell books and this quote got me thinking 'scientists build in order to learn, engineers learn in order to build'. On the vein of 'learning in order to build' I was wondering: How are the software engineers keeping up to date on the latest technologies and ...

14
голосов
8ответов
909 просмотров

How to compute the absolute minimum amount of changes to convert one sortorder into another?

Goal How to encode the data that describes how to re-order a static list from a one order to another order using the minimum amount of data possible? I have a feeling there is an algorithm or computer science term that will help me but right now I'm too stuck on the problem to figure out other ...

3
голосов
6ответов
5079 просмотров

comparisons of data structures, algorithms, basic computer science, online resources

I am searching for an online resource referring to data structures and algorithms. Basicaly what I am interested in, is a kind of comprehensive list of things such as: when a data structure or algorithm is used, pros and cons compared to each other, real life-problem usage, etc. I have a couple ...

2
голосов
2ответов
1463 просмотров

How can I modify the breadth-first search algorithm to also include the solution path?

I have the following pseudo-code in my book for a breadth-first search: function breadth_first_search: begin open := [Start] closed := []; while open != [] do begin remove leftmost state from open, call it X; if X is a g...

1
голосов
2ответов
1177 просмотров

How to argue that if we could solve the halting problem, then we could solve busy beaver?

This is one of the tasks of my assignment. I have a Turing machine simulation which can simulate a busy beaver function. I have done some research about proving this problem, but still don't get it so I guess maybe you can help me here. A good source for me to go to or example of how to argue th...

0
голосов
2ответов
911 просмотров

Question About VC Dimension

If I have the input space of (1,2,....999). And I have a concept class C, with 10 concepts: C0,C1,C2...C9. Given an input, that input is an element of ci if the it contains the digit i. For example, the number 123 is an element of c1 and c2 and c3. What is the VC Dimension of this concept clas...

1
голосов
1ответов
1067 просмотров

Binary Tree Isomorphism

I have an assignment to write among other things, a set of prolog predicates that determine if any two binary tree's are isomorphic to each other. The predicate must also be able to provide all of the isomorphic graphs to any given binary tree. Here is what I have so far, it works except for re...

1
голосов
4ответов
178 просмотров

Looking for a good reference on calculating permutations

As a programmer, I frequently need to be able to know the how to calculate the number of permutations of a set, usually for estimation purposes. There are a lot of different ways specify the allowable combinations, depending on the problem at hand. For example, given the set of letters A,B,C...

13
голосов
12ответов
2589 просмотров

How can I learn higher-level programming-related math without much formal training?

I haven't taken any math classes above basic college calculus. However, in the course of my programming work, I've picked up a lot of math and comp sci from blogs and reading, and I genuinely believe I have a decent mathematical mind. I enjoy and have success doing Project Euler, for example. I ...

5
голосов
6ответов
258 просмотров

Are there useful static analysis tools for databases?

Is there a tool for examining the configuration and schema of a database for dubious fields, relationships and configuration, similar to how static analysis tools like lint will flag dubious lines of code? I'm not necessarily asking for normalization, but surely there's stupid stuff that can be ...

0
голосов
1ответов
1404 просмотров

How can I modify the backtracking algorithm so it can run on "and/or" graphs?

In Artificial Intelligence we studied the backtracking algorithm. Here is the pseudocode our book offers: function backtrack; begin SL:= [Start]; NSL := [Start]; DE := [] CS := Start; while NSL != [] do begin if CS = goal (or meets goal description) t...

5
голосов
4ответов
2388 просмотров

Permutations of letters and numbers in a phone number

For my computer science class, we need to write a program (in C++) that takes an input of characters and outputs the possible permutations of it according to the dial pad on a phone, leaving non-digit characters in place. For example, inputing 2 outputs 2, A, B, C. Inputing 23 outputs 23, A3, B3...

9
голосов
3ответов
1548 просмотров

Coinduction - clear, concise description

I am studying coinduction(not induction) as part of a class on static analysis. Rummaging around the internet, I am simply not finding clear, concise description of: What coinduction is How coinduction actually proves something(it seems that coinduction is like waving a magic hand in the treatm...

13
голосов
6ответов
1637 просмотров

Create a program that inputs a regular expression and outputs strings that satisfy that regular expression

I think that the title accurately summarizes my question, but just to elaborate a bit. Instead of using a regular expression to verify properties of existing strings, I'd like to use the regular expression as a way to generate strings that have certain properties. Note: The function doesn't ne...

973
голосов
16ответов
433781 просмотров

What is the difference between statically typed and dynamically typed languages?

I hear a lot that new programming languages are dynamically typed but what does it actually mean when we say a language is dynamically typed vs. statically typed?

7
голосов
4ответов
537 просмотров

Secret computing: does such an animal exist?

A question in theory of Computer Science Today I can secretly store files in the cloud (say, amazon s3), by having them encrypted before I store them and decrypt them after I download. The storage provider cannot obtain any information from the stored files - everything is encrypted safely, and ...

7
голосов
1ответов
243 просмотров

What class of language can Perl regular expressions be used against?

I know that some of the capabilities of the Perl regular expression engine are not regular. However, what class is it? It might be context-free, but CS theory was never my strongest subject.

47
голосов
23ответов
15445 просмотров

O(log N) == O(1) - Why not?

Whenever I consider algorithms/data structures I tend to replace the log(N) parts by constants. Oh, I know log(N) diverges - but does it matter in real world applications? log(infinity) <100 for all practical purposes. I am really curious for real world examples where this doesn't hold....

7
голосов
4ответов
4338 просмотров

Memory-efficient way of computing the median of a large data set?

If one computer can only hold 1 million numbers, how to find out the median number from 100 million numbers?

0
голосов
2ответов
978 просмотров

Logic question (universal and existential quantifications)

I have a logical statement that says "If everyone plays the game, we will have fun". In formal logic we can write this as: Let D mean the people playing. Let G be the predicate for play the game. Let F be the predicate for having fun. Thus [VxeD, G(x)] -> [VyeD, F(y)] V is the computer sci...

2
голосов
4ответов
1805 просмотров

Closest grid square to a point in spherical coordinates

I am programming an algorithm where I have broken up the surface of a sphere into grid points (for simplicity I have the grid lines parallel and perpendicular to the meridians). Given a point A, I would like to be able to efficiently take any grid "square" and determine the point B in the square ...

2
голосов
7ответов
1042 просмотров

What are the most valuable parts of Computer Science studies for Cocoa developers?

What are the most valuable parts of Computer Science studies for Cocoa developers? Another way I might word this question is: If I’m not going to go to school for Computer Science but want to be a developer working primarily with Cocoa, what are the things I should make sure I learn that I oth...

4
голосов
3ответов
2716 просмотров

How can I write a program to generate a sorting decision tree?

In class we were given a simple decision tree for sorting 3 elements (a,b,c). (source: brpreiss.com) While looking at this, it makes sense to me. I was able to follow it. However, I now have to make a decision tree for 4 elements (a,b,c,d) and the number of leafs just shot up to 24. I'm ...

2
голосов
5ответов
150 просмотров

Most efficient way to encode 2 positions between 0 and 64?

I have 64 bit values that I want to compress by exploiting the fact that only a portion somewhere in the middle contains data and before and after that are zeroes. Say the actual data is l bits long and padded with n 0s in front and m 0s at the end such that n + l + m = 64. Instead of transmitti...

1
голосов
4ответов
284 просмотров

Resources for Beginning CS

I have been writing PHP, Ruby, ColdFusion, and javascript (not a language, I know), for several years. But I am really wanting to get more into the world of Computer Science and writing in lower-level languages. What are some good resources for starting out? It seems like every book I have g...