Level of math required for an Ada book

General
1

Hi,
I think I’ve fallen out of my depth with this book, when it comes to math. Down’s the page. First, I liked the fact that algorithmic skills were trained along with the language proper… I mean it is in the title after, “data structure”. But this is the first algo-heavy chapter, about hash table, and while I did read it with a mild interest… But the math looks like Chinese to me. I get the principles, but I can’t do the calculation or “show” anything, especially when I couldn’t verify it experimentally (q1). I suck hard at theoretical math in particular, number theory most of all.

image
image870×898 188 KB

In general this is getting really math-heavy.
What should I train first then ? What do you think of “Algorithms and Data Structures, Writh”, is it more progressive ?
Or do I need a bloody math degree to make to respond to these exercises ? Or should I just leave questions that don’t talk to me, apply the methods mechanically (like a good many students do…) and see to the “why” after the other book ?
Even though I hate disrupting a manual’s order.

2

Ada is a generic language that can be used for different things. It depends on what you want to use it for. Your book uses certain terms like traversing and folding - you need to understand those.

Computing is not about working out the math but coding the formula. Just find a formula and try to code it. You can get as simple as pythogoras computation of the hypotenuse given the two sides or perhaps Zeller’s congruence for computing the day of the week. Zeller’s is quite a good one because it teaches them about rounding, integer division and modulo arithmetic. You don’t need to know the math - just code up the formula.

Wirth’s is quite a good book but converting Pascal to Ada is something else. Pascal is the closest relative to Ada but you may find yourself fighting range and type compilation issues. That is part of the learning process that every Ada coder has to go through. I sometimes ask myself why I’m punishing myself coding something in Ada when I can easily do it in C++, Java, python or Fortran. Because it is fun.

In Wirth’s book a lot of the recursion chapter is on graphics. You will probably need to find some other exercises unless you wish to enter the world of graphics in Ada. This is a different ballgame with a lot of bad examples on the net on how not to code a graphics program.

If you want to do a bit of AI (depth/breadth first searches) then you could try towers of hanoi or the cannibals and missionaries problem.

If you want to use Ada for embedded, get the ARM distribution. Lots of examples there on interfacing with electronics.

3

what do you mean by that ? Doesn’t look like a book. I don’t mind graphics, ultimately I want to have good notions of every area. Otherwise, yeah, I figured so, that I didn’t need to understand, just know how to write or what it does language-wise. Writh’s has an oberon version, translating should be easy.

4

#1 surprises me only because first problems tend to be easier in my experience, if only to give the student some confidence. – Well, until grad school, when all bets are off, at least in mathematics.

On the other hand, the problem shouldn’t be that hard if you know some “elementary” number theory.*** You don’t even need a course in number theory since a lot of CS students would have encountered these important properties of prime numbers in a course called “discrete mathematics” (in the United States, not sure about other places).

To be honest, you might do well just to try it. Work it with a few small primes and composite numbers, and see how the behavior differs. You don’t necessarily have to do this by pen and paper; if the chapter taught you enough about hashing, you should be able to write a simple program and see what happens when the table has prime or composite size. I’ll caveat that I haven’t tried this myself in a while, but I feel fairly confident that it shouldn’t take too long to see what’s going on.**** And maybe that’s why it’s a #1.

More generally, if you want to be serious about computer science, you’ll need to reconcile yourself to learning quite a bit of mathematics. If you don’t, you’ll find yourself hampered over and over again. The upside is that what I mean by “mathematics” may not be what you think of as mathematics.

***I put “elementary” in quotes because it’s not necessarily “easy” so much as it requires on a certain kind of mathematics, unlike analytic or algebraic number theory.

****“too long” from my point of view; it may take a few hours or even days, but not more than that. And in my experience students who actually do this find it rewarding when the proverbial :bulb: glows on. But I can be wrong; other people may feel very, very differently, and some people, even people who thought they loved math, find it less than appealing. :man_shrugging: Anyway, if you go this route, I’m willing to correspond with you privately; I used to teach number theory, not necessarily well :grinning: but it was one of my favorite classes & I think most students thought it was a pleasant surprise.

3 Likes
5

I have a licence in biology but never took math courses. You could say I had a love/hate relationship with it. I think I never found the proper material + support combination. I’ll take you to your words. Let’s start with #1, shall we ?

I’ll caveat that I haven’t tried this myself in a while, but I feel fairly confident that it shouldn’t take too long to see what’s going on.

Look at this:

WITH Ada.Text_IO; use Ada.Text_IO;
WITH Ada.Integer_Text_IO;
WITH Ada.Numerics.Discrete_Random;
PROCEDURE Random_Numbers IS
  SUBTYPE KeyRange IS Positive RANGE 111111..999999;
  RandomKey: KeyRange;
  PACKAGE RandomKeys IS NEW Ada.Numerics.Discrete_Random
    (Result_Subtype => KeyRange);
  G: RandomKeys.Generator;     
begin 
  for M in 1..100 loop
    declare
      SUBTYPE HashRange IS Natural RANGE 0..50+M;
      type NarrayT is array (HashRange) of Integer;
      Narray: NarrayT := [others => 0];
      HashValue: HashRange;
    begin
      RandomKeys.Reset (Gen => G);
      for A in HashRange'Range LOOP
          RandomKey := RandomKeys.Random(Gen => G); -- integer
          HashValue := Randomkey mod (HashRange'Last + 1);      
          Narray (Hashvalue)  := @ + 1;
      end LOOP;
      Put_line(Narray'Reduce(Natural'Max,0)'Image);
    end;
  end loop;
end Random_Numbers;

if I’m not mistaken, what I wrote gives the highest number of collision over the whole table, of a size ranging from 51 elements to 101 elements. Some fancy statistics tools would be more appropriate but this should do in practice. I don’t see any change. You can DM me, cantanima.

6

You’re on the right track, but the use of completely random numbers masks the problem. For each M, use a table of size M, pick a random number x, then hash x, 2x, 3x, 4x, … M * x. That worked for me.

(Random numbers can be useful that way: they sometimes get you out of jams imposed by hidden symmetries, etc. But in this case that utility is the opposite of useful… :grin: )

7

I see that using a single random number then hashed x times creates 0 collision, against up to 5 like before if generated for each hash value calculated. I don’t know why though. I still see no correlation between table size and the number of collision :-/

8

Either I misunderstand you, or you misunderstand me. I’ll elaborate, so there will be spoilers.

My code looks something more like this:

         RandomKeys.Reset (Gen => G);
         RandomKey := RandomKeys.Random (Gen => G); -- integer
         for A in HashRange'Range loop
            Hashvalue := RandomKey * A mod Size;
            Narray (Hashvalue) := @ + 1;
         end loop;
         IO.Put ("[");
         for Each of Narray loop
            IO.Put (Each'Image & ",");
         end loop;
         IO.Put_Line ("]");

A clip of one run:

Trying 7
[ 1, 1, 1, 1, 1, 1, 1,]
Trying 8
[ 2, 0, 2, 0, 2, 0, 2, 0,]
Trying 9
[ 1, 1, 1, 1, 1, 1, 1, 1, 1,]
Trying 10
[ 2, 0, 2, 0, 2, 0, 2, 0, 2, 0,]
Trying 11
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,]
Trying 12
[ 4, 0, 0, 0, 4, 0, 0, 0, 4, 0, 0, 0,]
Trying 13
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,]

Already you should see something suspicious about 8, 10, 12. Run again:

Trying 7
[ 7, 0, 0, 0, 0, 0, 0,]
Trying 8
[ 1, 1, 1, 1, 1, 1, 1, 1,]
Trying 9
[ 3, 0, 0, 3, 0, 0, 3, 0, 0,]
Trying 10
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,]
Trying 11
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,]
Trying 12
[ 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0,]
Trying 13
[ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,]

In this case, 9 also misbehaves, as does 7. But 7 misbehaves in a very peculiar way; that is, the random number was a multiple of 7. That’s not true about the pattern I pointed out for 8, 9, 10, or 12.

The patterns you see for those composite numbers – multiple 0, multiple nonzero – will never appear for a prime number: with a prime number, it’s all 1’s or all at 0. Can you figure out why?

That last question is not trivial unless you’ve had elementary number theory, but you should still see it if you try it by hand with some x and 7 (x not a multiple of 7, as noted!) and with some x and, say, 8. With 8, be sure to pick an x that shares a common factor with 8.

10

Oberon doesn’t have ranges by default, they’re an extension, non-standard and I’ve no idea if any compiler has implemented them outside ActiveOberon and OberonX.

11

I can not see any variation here, run this and see:

WITH Ada.Text_IO; use Ada.Text_IO;
WITH Ada.Numerics.Discrete_Random;
PROCEDURE Random_Numbers IS
  SUBTYPE KeyRange IS Positive RANGE 111111..999999;
  RandomKey: KeyRange;
  PACKAGE RandomKeys IS NEW Ada.Numerics.Discrete_Random
    (Result_Subtype => KeyRange);
  G: RandomKeys.Generator;
begin
  for Size in 1..10 loop
    declare
      SUBTYPE HashRange IS Natural RANGE 0..Size;
      HashValue: HashRange;
    begin    
      RandomKeys.Reset (Gen => G);
      RandomKey := RandomKeys.Random (Gen => G);
      for A in HashRange'Range loop
        Hashvalue := RandomKey * A mod Size;
        Narray (Hashvalue) := @ + 1;
      end loop;
      Put ("Size "& Size'Image & ": ");
      for Each of Narray loop
        Put (Each'Image & ",");
      end loop;
      Put_Line ("]");
    end;
  end loop;
end Random_Numbers;

Size 1: 2, 0,]
Size 2: 3, 0, 0,]
Size 3: 4, 0, 0, 0,]
Size 4: 2, 1, 1, 1, 0,]
Size 5: 2, 1, 1, 1, 1, 0,]
Size 6: 2, 1, 1, 1, 1, 1, 0,]
Size 7: 2, 1, 1, 1, 1, 1, 1, 0,]
Size 8: 2, 1, 1, 1, 1, 1, 1, 1, 0,]
Size 9: 4, 0, 0, 3, 0, 0, 3, 0, 0, 0,]
Size 10: 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,]

Sometimes the 7 / 0 or 3 / 0 patterns concerns 3, or 4, or 5, or 7, or 10. No pattern on my screen. In each series, of course the Size-th element equals Size * Random mod Size, so always give 0. But beside writing the equation on paper does nothing to illuminate me… I have zero math intuition.

12

  1. That code won’t compile. For example, Narray isn’t defined.

  2. That said, comparing your output to the code you do provide shows what the problem probably is: use

    subtype `HashRange` is Natural range 0 .. Size - 1;