Stack Overflow
Stack Overflow

Questions tagged [discrete-mathematics]

NOTE: Only questions about software development related to discrete mathematics are on topic. Discrete mathematics is the branch of mathematics concerned with discrete phenomena – as opposed to continuous phenomena like geometry, real analysis, physics, etc. Typical discrete math topics are discrete probability, combinatorics, graph theory, algorithms and complexity, but also matrices, difference equations, recurrences.

Discrete mathematics is the branch of mathematics concerned with discrete phenomena – as opposed to continuous phenomena such as geometry, real analysis, and physics. Typical discrete math topics are discrete probability, combinatorics, graph theory, algorithms, and complexity, but also matrices, difference equations, and recurrences. Applications abound in computer science, as many computer models are built upon discrete elements.

Questions relating to discrete mathematics must still be programming-related. Questions that are not programming-related may be asked on mathematics.stackexchange.com.

1083 questions
157
votes
10 answers

How do you calculate log base 2 in Java for integers?

I use the following function to calculate log base 2 for integers: public static int log2(int n){ if(n <= 0) throw new IllegalArgumentException(); return 31 - Integer.numberOfLeadingZeros(n); } Does it have optimal performance? Does someone…
Nulldevice
  • 3,926
  • 3
  • 31
  • 37
79
votes
8 answers

Haskell or Standard ML for beginners?

I'm going to be teaching a lower-division course in discrete structures. I have selected the text book Discrete Structures, Logic, and Computability in part because it contains examples and concepts that are conducive to implementation with a…
Barry Brown
  • 20,233
  • 15
  • 69
  • 105
70
votes
7 answers

Is it possible to implement bitwise operators using integer arithmetic?

I am facing a rather peculiar problem. I am working on a compiler for an architecture that doesn't support bitwise operations. However, it handles signed 16-bit integer arithmetics and I was wondering if it would be possible to implement bitwise…
Statement
  • 3,888
  • 3
  • 36
  • 45
54
votes
1 answer

Could anyone explain Big O versus Big Omega vs Big Theta?

Possible Duplicate: Big Theta Notation - what exactly does big Theta represent? I understand it in theory, I guess, but what I'm having trouble grasping is the application of the three. In school, we always used Big O to denote the complexity of…
Doug Smith
  • 29,668
  • 57
  • 204
  • 388
47
votes
7 answers

Find non-common elements in lists

I'm trying to write a piece of code that can automatically factor an expression. For example, if I have two lists [1,2,3,4] and [2,3,5], the code should be able to find the common elements in the two lists, [2,3], and combine the rest of the…
turtlesoup
  • 3,188
  • 10
  • 36
  • 50
37
votes
23 answers

Code-golf: generate pascal's triangle

Generate a list of lists (or print, I don't mind) a Pascal's Triangle of size N with the least lines of code possible! Here goes my attempt (118 characters in python 2.6 using a trick): c,z,k=locals,[0],'_[1]' p=lambda n:[len(c()[k])and…
fortran
  • 74,053
  • 25
  • 135
  • 175
35
votes
6 answers

Height of a tree with only one node

According to Wikipedia, The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only one node (the root) has a height of zero (or one). I dont get it - is it zero or one (or both)?
Snowman
  • 31,411
  • 46
  • 180
  • 303
35
votes
15 answers

Why is squaring a number faster than multiplying two random numbers?

Multiplying two binary numbers takes n^2 time, yet squaring a number can be done more efficiently somehow. (with n being the number of bits) How could that be? Or is it not possible? This is insanity!
Jess
  • 3,111
  • 3
  • 22
  • 17
30
votes
4 answers

De Bruijn-like sequence for `2^n - 1`: how is it constructed?

I'm looking at the entry Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup from Bit Twiddling hacks. I can easily see how the second algorithm in that entry works static const int…
AnT stands with Russia
  • 312,472
  • 42
  • 525
  • 765
26
votes
10 answers

What does this definition of contiguous subsequences mean?

I don't understand the following definition of a contiguous subsequence: A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. If S is {5, 15, -30, 10, -5, 40, 10} then 15, -30, 10 is a contiguous…
user466796
  • 305
  • 1
  • 3
  • 6
24
votes
5 answers

Finding a nonzero integer x where x == -x?

In a course on algorithms and data structures at my university, I received this question: Which integer has the same bit-pattern as his negative value? Means: x == -x I know that 0 works, but I suspect that the instructor was looking for some…
codepleb
  • 10,086
  • 14
  • 69
  • 111
22
votes
9 answers

Which algorithm for assigning shifts (discrete optimization problem)

I'm developing an application that optimally assigns shifts to nurses in a hospital. I believe this is a linear programming problem with discrete variables, and therefore probably NP-hard: For each day, each nurse (ca. 15-20) is assigned a…
Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
22
votes
10 answers

How to prove max number of connection between n nodes is n*(n-1)/2

Given n nodes, if every node is connected to every other node (except itself) the number of connections will be n*(n-1)/2 How does one prove this ? This is not a homework question. I have been away from CS text books for long and have forgotten the…
Manohar
  • 3,865
  • 11
  • 41
  • 56
21
votes
5 answers

Number of n-element permutations with exactly k inversions

I am trying to efficiently solve SPOJ Problem 64: Permutations. Let A = [a1,a2,...,an] be a permutation of integers 1,2,...,n. A pair of indices (i,j), 1<=i<=j<=n, is an inversion of the permutation A if ai>aj. We are given integers n>0 and…
Shashank
  • 13,713
  • 5
  • 37
  • 63
21
votes
4 answers

Is the Sobel Filter meant to be normalized?

The x-derivative Sobel looks that way: -1 0 +1 -2 0 +2 -1 0 +1 Lets say there are two samples of my image which look like that (0=black, 1=white): 0 0 1 1 0 0 0 0 1 & 1 0 0 0 0 1 1 0 0 If I perform convolution I'll…
Tom
  • 433
  • 1
  • 4
  • 13
1
2 3
…
72 73