Wikipedia:Reference desk/Archives/Computing/2016 May 18

Computing desk
< May 17	<< Apr | May | Jun >>	May 19 >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 18

Hashing in an CS undergraduate degree

Hello,

How comprehensive is the teaching of hashing in a CS undergraduate degree (specially, in a data structures course)? Do they generally fully derive all the formulas regarding the expected complexity of insertion and search operations in open addressing hashing? thanks! — Preceding unsigned comment added by 212.179.21.194 (talk) 07:28, 18 May 2016 (UTC)

This is a topic for an algorithms class. Each university gives the class a slightly different name, but the point of the class is implementation of algorithms in a computer. It is, in my opinion, the implementation of the mathematics course discrete structures. I have taught this class as a 100-level and 300-level in three universities. I cover the details of searching, inserting, deleting, sorting using linked lists. Because "hash" is not an implementation, I don't say that I use hashes. How do you implement your hash? Chances are, you implement it with some sort of array or linked list. So, hash key "A3DF" could be physical offset 83 or you could step through the linked list to find it. If it is a doubly linked list, and you sorted the linked list, you could start in the middle and find it quicker. Again, it isn't about hashes. It is about lists. 209.149.114.175 (talk) 13:29, 18 May 2016 (UTC)

Presumably at your university, "100-level" loosely corresponds to a class aimed at first-year students enrolled in a four-year program; and 300-level means a course aimed at third-year students, is that correct?

Silberschatz's dinosaur book is among the gold standard references used in undergraduate and graduate computer science classes; it talks about hash functions from a utility perspective, without going into the inner workings too seriously.

My first "algorithms" book, by Goodrich and Tamassia, is available in Java and in C++. It's a great book and it covers hashing functions extensively, at an appropriate level for an undergraduate who knows how to program, but has not yet completed study of eight semesters worth of college-level math. I specifically recall those books working out the algorithmic complexity for Huffman coding, which - in the purest and truest computer-science-y sense of the term, is a hashing function - just not one you'd normally use as a checksum or a cryptographic hash. If you intend to study the theory of hashes, do yourself a service - take a field-trip out of the Computer department and visit the Math department. I highly recommend starting with A Transition to Advanced Mathematics, a book that many mathematicians know, but is remarkably absent from computer science curricula.

All of these books are probably aimed at students in their second- or third- year of formal undergraduate study of computer science (or mathematics).

If you proceed to take more advanced specialization courses in computer science at the advanced-undergraduate, or graduate level, you might get to study gory details about bit entropy and bit-comingling. In a cryptography theory class, you'll see even more math about hash functions. Here is one example of such a lecture from my undergraduate institution: CSC 574 Computer Security - Hash Functions. Such a class may ask undergraduates to implement a hash function in code or pseudocode; or they might dissect a live algorithm during a run through the SHA-2, and so on. If you study formal math in, say, a math department, instead of the engineering or computer science department, then you might do functional analysis or discrete math or group theory which are generally relevant to the topic of hashing; but you might have to do expend extra intellectual effort to see the connection to, say, the SHA-2 hash algorithm. If you implement a project as an advanced undergraduate, you may familiarize yourself with library implementations of hash functions; some of my favorite implementations of hash functions are in zlib (a compression library) and CommonCrypto (example, here's one version of SHA-2 - can an average undergraduate study and understand and use that code?); but there are thousands of options available.

Nimur (talk) 15:45, 18 May 2016 (UTC)

Correct about the class numbers. They go from 0xx to 5xx in most universities. 0xx is for non-majors. For example, I taught Computer Science 072 at a university, which was an introduction to computer programming for non-science majors. Very very low level stuff. 5xx is mainly graduate coursework. I've only taught one 5xx course. It was computer security and the students complained the entire time that I went too deep into the nuts and bolts of security algorithms (but, it is "graduate level", so I made it harder).

A point of possible confusion: When a person asks me about hashes, I have to weed out the background for the question. Are they asking about string-indexed arrays (hash maps)? Are they asking about hashing functions that turn a random-length string into a fixed-length, mostly unique, string? Are they asking about implementation of a hash map? I believe that this question is asking about the implementation of a hash map. You have a set of key values (fixed-length strings) and associated variable values. How do you insert a value? How do you delete a value? How do you update a value? Do you use a linked list (as I noted in my response)? Do you try to implement associative memory? Do you keep the keys sorted? If you have a linked list, do you make it doubly linked? Do you store it in a tree? Should it be a binary tree? What if you delete a hash from a binary tree? What about reserving memory? In my mind, very little of that has to do with "how do I turn blahblahblahblah into a hash?" It has to do with list/tree storage and manipulation. 209.149.114.175 (talk) 16:42, 18 May 2016 (UTC)

Travelling with lots of softwares and games

So, I have lots and lots of games and softwares, will I have any problems travelling around the world with them. Note: If it is considered a legal advice, than let me know what are your experiences; for analysis. -- Apostle (talk) 19:01, 18 May 2016 (UTC)

On what system? Windows? Mac? Android? Board games? Card games? Hunger games? 209.149.114.175 (talk) 19:03, 18 May 2016 (UTC)

I don't know where you're traveling from, but if you're a United States citizen, the State Department is a good resource to check.

The United States Department of State advises that Americans who travel through Ben Gurion may be subject to forcible search and seizure of their laptop computers:

"Video cameras and other electronic items must be declared upon entry to Israel. Carrying such audio-visual or data storage/processing equipment may lead to additional security-related delays, and some travelers have had their laptop computers and other electronic equipment searched at Ben Gurion Airport. While most items are returned prior to the traveler’s departure, some equipment has been retained by the authorities for lengthy periods and has reportedly been damaged, destroyed, lost, or never returned."

Have a look at Country Specific Information for Israel, the West Bank and Gaza, or for any other destinations. The Israeli border police are not very friendly if they decide you don't belong on which-ever-side of their border they think is the wrong place for you. WP:OR, If you have an encrypted laptop or if you have a non-zero number of cameras, you might end up locked in a dark room for a few hours while the police search and seize your computer - even if you are an American citizen, even if you politely comply with all applicable rules, laws, and instructions.

If you are traveling to People's Republic of China, you might want to avoid carrying an encrypted computer, as this can cause you more trouble than the "value" of any important data you are trying to protect. From the travel advisory, " Security personnel carefully watch foreign visitors and may place you under surveillance. Hotel rooms (including meeting rooms), offices, cars, taxis, telephones, Internet usage, and fax machines may be monitored onsite or remotely, and personal possessions in hotel rooms, including computers, may be searched without your consent or knowledge."

American travelers to Russia have recently been subject to unwarranted search and seizure of personal computer equipment at the Russian border.

These are probably the highest profile places where your laptop or the software on your laptop may be scrutinized, searched, or destroyed. If you're going to somewhere like Syria, Libya, or North Korea, you might find it interesting that the State Department does not worry about seizure of your computer or its software; but those places have extensive additional "Special Circumstances."

Nimur (talk) 19:29, 18 May 2016 (UTC)

A note on my experience in China: I had my laptop in my carry-on. Airport security just glanced at it, decided it did not look like a bowling ball with a burning fuse sticking out of it, and waved me on. Granted, it was like 4 AM local time and they were somehow still super busy. Most people here keep their jobs whether or not they catch anyone, so search and seizure is more likely to be the result of the passenger being a troublemaker or the security worker being xenophobic or greedy than actual regulations. Don't be a spy, missionary, terrorist; don't look rich, stay out of the way and be nice to people, and get in the longest but fastest moving line possible.

As for the actual games: before I came to China, I made ISO images of any games I had physical copies of that I wanted to keep during the move. That can be trickier with some newer titles, but those usually have versions you can download through a service like Steam. Ian.thomson (talk) 04:21, 19 May 2016 (UTC)

I'll be going back to UK, probably USA and Canada sometimes, not sure about travelling the world; might do - its good to know. What do you guys suggest? Shall I install all of my softwares and games before departing? The only worries I have is PC running slow... -- Apostle (talk) 18:48, 19 May 2016 (UTC)

This question is difficult to answer, but I'll try anyway. This is my personal experience, YMMV. When I travelled to Georgia, not long after the Russo-Georgian War, I brought my old laptop and my old usb-stick-style mp3 player with me. I cleaned the harddrive of the laptop a couple of weeks before I travelled and then used it for a while because if your history is empty that is a bit suspect. I ensured that everything on the laptop was unencrypted, I enabled guest access (no password required) and set the password for my administrator account to my first name. I doublechecked that the laptop contained no policitally sensitive information. For example, I own a collection of old Soviet propaganda and Soyuzmultfilms, but I did not bring it to Georgia. I also didn't bring my ebooks (many of which are political or religious) and I didn't bring my folder of religion-related pictures (I am an atheist, I am talking about pictures like this one). I have a lot of software that is related to security and encryption that I left at home. I also left my collection of malware (mainly source code for old botnets and old virii) and anti-malware at home. I put a lot of holiday photos from my then-recent holidays in neighbouring Turkey in the My Documents folder, and some pictures of the ex-GF I was travelling with. I told my friends and family to use my alternative email account (which does not require two-factor authentication) to contact me. I put all electronic equipment in my carry-on luggage. My old MP3-player is a USB-stick, and that thing contained not just music but also 1 encrypted file with some phonenumbers and passwords, the plane tickets, information about my bank accounts and a scan of my passport et cetera. I stored the software used to decrypt it in the same folder, together with a plain text document named "password.txt" that contained the password for the encrypted file. At the border they were very curious about my laptop, and it took them a long time to check it, but no one asked me about the MP3 player (which I was listening to while waiting for them to check the laptop) and they didn't even touch it. Maybe they were unaware that that MP3player is basically a USB stick with some added functionality that enables it to play music. I am not sure but I think they wanted to find out if I was a journalist or not (I am not). I brought an inexpensive low-quality camera and a cheap old flipphone. Once inside the country I was repeatedly warned not to take photos of military installations and soldiers (even by taxi drivers and a random person on the street). Because my government warned that there were snipers active in the region I visited I wore brightly-colored T-shirts; wearing black clothes (like I usually do) is a bad idea. Bringing camouflage clothing is a very bad idea, even if you are not a soldier but a hunter or someone who lacks fashion sense. My ex-GF speaks a bit of Russian, and we are Dutch, so every time we met someone we explained that we are not German and that we are not Russian. Luckily everyone knew Dutch footballplayers.

I always try to keep at least roughly 15-20% of my harddisk free, to ensure it has enough space. Installing many games shouldn't make the computer much slower, most of the games I have use only a handful of registry keys. And if your bring the installers with you (or a copy of your Steam folder if you use Steam) then they don't have to be installed. The Quixotic Potato (talk) 11:21, 20 May 2016 (UTC)

I have 2TB of games and of softwares (some with registry keys and some with, you know what!?!). I have three HDD partions, I'm planning to install everything on the D & E Drive by keeping the C drive for OS only of course. Any suggestions? -- Apostle (talk) 20:40, 20 May 2016 (UTC)

Defragmenter won't run if you have less than 15% free on your hard disk, so as you say, it pays to keep at least that much free. Akld guy (talk) 00:07, 21 May 2016 (UTC)