CS50: Weeks 6-11

Question 1

What is hashing?

Answer 1

Hashing is taking an input and using that input to compute a value (e.g., where to place in a sorted list), using a hash function.

Question 2

What is separate chaining?

Answer 2

Separate Chaining is an array of linked lists, one method to handle collisions in a hash table.

Question 3

What is linear probing?

Answer 3

Linear Probing is traversing along an array to find an open spot to put a new element; another method to handle collisions in a hash table.

Question 4

What is a trie?

Answer 4

A Trie is a search tree that is optimized for retrieval.

Question 5

What is a stack?

Answer 5

A Stack is a data structure with the actions Push, Pop that is LIFO (last in, first out).

Question 6

What is a queue?

Answer 6

A Queue is a data structure with the actions Enqueue, Dequeue that is FIFO (first in, first out).

Question 7

What is a binary search tree?

Answer 7

A Binary Search Tree is a data structure where each element has two children: a left and right path (to divide/conquer related values) – n log n sorting.

Question 8

What is a hash table collision?

Answer 8

Collisions occur when attempting to put two values (whose placements were produced by the hash function) into the same index. This can be resolved with either linear probing or separate chaining.

Question 9

What is an IP address?

Answer 9

An IP (Internet Protocol) address is a unique ID that every device on the internet has in order to communicate.

Question 10

What is the path of communication on the internet for a typical computer?

Answer 10

laptop -> AP (access point) -> Switch (device with data jacks) -> Router (route packets from sender to destination) -> Internet.

Question 11

What is DHCP and what does it do?

Answer 11

DHCP (Dynamic Host Configuration Protocol) provides dynamic IP address to consumers.

Question 12

What is DNS and what does it do?

Answer 12

DNS (Domain Name System) transalates URLs (host names, domain names) to IP address and vice versa.

Question 13

What is TCP?

Answer 13

TCP (Transmission Control Protocol) is the communications backbone of the internet.

Question 14

What is HTTP?

Answer 14

HTTP (Hypertext Transfer Protocol) is the layer by which websites are delivered on the internet.

Question 15

What is HTML?

Answer 15

HTML (Hypertext Markup Language) is the markup language used to create websites.