woshibo

CS50 Quiz 1 Practice Problems

These are some practice problems for quiz 1 of CS50 2012. If there are any similarities between these questions and those on the quiz, they are purely coincidental.
To generate these questions, I went through the notes for each class.
Try doing them on paper to simulate an actual exam environment.

Week 5

Question: What is a file format?
Answer: A standard for how to interpret the bytes in a file.

Q: How many bytes does it take to represent an RGB triple in a bitmap file?
A: 3 bytes, one for each R, G, and B.

Q: How many different colors can be represented given a pixel encoded using 24 bits?
A: 2^24 == 16,777,216 ~ 16 million. Each bit can have two values, so 24 things that can represent two values each gives 2^24 possibilities.
Note: Big powers of two can be approximated quickly. Memorize that 2^10 == 1,024 ~ 1,000. Therefore, 2^20 == (2^10) * (2^10) ~ 1,000,000. Thus, 2^24 == (2^20) * (2^4) ~ 1,000,000 * 16 == 16,000,000.

Q: Aside from this being a useless program, find the error:

#include<stdio.h>

int main(int argc, char* argv[]) {
  bool passed_no_args = argc == 1;
  if(passed_no_args) printf("You passed no arguments!\n");
  else printf("You passed an argument!\n");
  return 1;
}

A: Forgot to include stdbool.h or any other library that defines the type bool. The bool data type is not included by default.

Q: What happens when a line cannot be read by GetInt(), as defined in the CS50 Library?
A: INT_MAX is returned, indicating an error occured.

Q: How does GetString() deal with a line of input that contains more characters than it initially allocated for its buffer?
A: It calls realloc, which can modify the size of the buffer.

Week 6

Q: Give some advantages of a linked list over an array.
A: A linked list supports addition and removal of elements in constant time (i.e. the same speed no matter how long the linked list is).

Q: Give some advantages of an array over a linked list.
A: An array supports accessing and modifying any particular element in constant time.
Note: Many languages provide dynamic arrays, which automatically allocate more space for themselves as needed. Examples include vector in C++ and Java’s ArrayList. This isn’t magic; underneath, C++ and Java are using things like realloc which you would use if asked to create dynamic arrays in C. Chances are, however, that there will be fewer bugs and inefficiencies in their versions of dynamic arrays due to the extensive amount of real world testing of the code.

Q: Write the type definition of a singly linked list that stores a pointer to an integer at each node.
A:

typedef struct node {
  int* num;
  struct node *next;
} node;

Q: Write the type definition of a doubly linked list that stores a pointer to an integer at each node.
A:

typedef struct node {
  int* num;
  struct node *prev;
  struct node *next;
} node;

Q: Using the previous definitions of a linked list node, is it possible to use num to access more than one integer, or is a pointer to an integer just that, a pointer to a single integer?
A: We can use num to access multiple integers if we, for example, call in our code num = (int*)malloc(8 * sizeof(int)); . This would allocate 8 slots, each slot with enough space for an int. We can then use array notation to access and modify the slots.

Q: Assume the variable cur is of type node* using the singly linked list type definition above. What is equivalent code to cur->num[1]?
A: (*cur).num[1]

Q: Write a function that takes in a node* and frees all of the nodes in the list. Assume the singly linked list type definition above.
A:

void free_list(node* list) {
  while(list != NULL) {
    node* next = list->next;
    free(list);
    list = next;
  }
}

Q: True or false: A queue data structure can be implemented as a special linked list.
A: True.

Q: True or false: A stack data structure can be implemented as a special linked list.
A: True.

Q: Which data structure is LIFO and which is FIFO?
A: A queue is first in first out. A stack is last in first out.

Q: What might this indicate if this is the result of running Valgrind on a program:
HEAP SUMMARY:
in use at exit: 40 bytes in 2 blocks
total heap usage: 2 allocs, 0 frees, 40 bytes allocated
LEAK SUMMARY:
definitely lost: 40 bytes in 2 blocks

A: There’s a memory leak, most likely due to not freeing memory that was allocated by calling malloc or calloc.

Q: What is a desired property of a hash function?
A: A good hash function should map its inputs to outputs in an even manner, minimizing the number of collisions that occur.

Q: What’s a possible way of dealing with collisions in a hash table?
A: Make the hash table an array of linked lists so that the things that map to the same hash function output can be stored.

Q: Write the type definition for a binary search tree, where each node stores an integer.
A:

typedef struct node {
  int n;
  struct node* left;
  struct node* right;
} node;

Q: How many computer scientists does it take to screw in a lightbulb?
A: That’s a hardware issue. Another acceptable answer: The dead bulb is a feature, not a bug.

Week 7
Q: The Huffman character frequency table for a compressed file has been corrupted. Can I decompress this file using another file’s intact character frequency table?
A: If the other file was a copy of this file or extremely similar, there is a chance that the correct Huffman tree will be produced. In all likelihood, however, using a random compressed file’s character frequency table would not correctly decompress this file.

Q: 15 & 2 ==
A: 2

Q: 25 ^ 16 ==
A: 9

Q: 5 | 10 ==
A: 15

Q: 2 << 5
A: 64

Q: At a minimum, how many bytes does it take to store 16 boolean values?
A: 2. A boolean can be represented by a bit. Each bit within a single byte can be individually accessed and modified with bitwise operators.

Q: What type of program is clang?
A: A compiler.

Q: What is the goal of program compilation?
A: Translation of source code that is human-readable into machine code that can be executed by the computer.

Q: Write an HTML file that has a title of “This is” and bold text in the body “CS50”.
A:

<!DOCTYPE html>

<html>
  <head>
    <title>This is</title>
  </head>
  <body>
    <b>CS50</b>
  </body>
</html>

Q: You want to fool someone into clicking a link on your webpage. Use the <a> tag to send someone to http://www.youtube.com/watch?v=dQw4w9WgXcQ while making them think they’re going to facebook.com.
A:
<a href=”http://www.youtube.com/watch?v=dQw4w9WgXcQ”>facebook.com</a>

Q: Is HTML a programming language?
A: No. HTML is a markup language used to tell a web browser how to display a web page.

Q: Why is it a good idea to provide alt text for images?
A: It makes your website more accessible to the visually impaired and those who can’t download the image.

Q: What are the ports used by HTTP, HTTPS, SMTP, SSH?
A: 80, 443, 25, 22, respectively.

Q: Why don’t you have to type a server’s address to access a web page stored on that server?
A: This service is provided by DNS, which translates names like “google.com” to IP addresses like 74.125.226.231.

Q: I try to access hello.html in the appliance, but when I navigate to localhost/hello.html, I get a Forbidden error. When I do ls -l in hello.html‘s directory, I see that it has the permissions -rw-------. What’s the issue and how could I fix it?
A: hello.html is not world-readable. Do chmod a+r to modify permissions so that anyone can see the file.

Week 8
Q: I have a div that has an id called “header”. How do I use CSS to center it?
A:

#header {
  text-align: center;
}

Q: Declare an array of the numbers 0, 1, 2, 3, 4, 5 in PHP. How is this array different from that in C?
A:

$numbers = [0, 1, 2, 3, 4, 5];

A PHP array is a hash table, not a contiguous chunk of memory as in C. There is an implicit creation of key-value mappings from the initialization of a PHP array: 0 => 0, 1 => 1, 2 => 2, 3 => 3, 4 => 4, 5 => 5.

Q: What do I add to the program hello.php below to be able to run ./hello.php instead of php hello.php.

<?php
  printf("hello, I'm a php program");
?>

A: We need to add #! followed by the path of the program php on our machine. On our machine, we could write #!/bin/php since php is located in the /bin directory. In general, you can do #!/bin/env php, because env is a program that finds and executes the program with the name you give it.

Q: What kind of a variable is $_SESSION in PHP? What is it useful for?
A: $_SESSION is a superglobal and can keep track of user data across web pages during a user’s session. It can be used as a hash table.

Q: Are there scope issues in the code below?

if($argc == 1) {
  $message = "no arguments passed";
} else {
  $message = "some arguments passed";
}
echo $message;

A: No. In PHP, if statements don’t have their own scope. This means that variables declared inside an if statement can be accessed outside of it as well.

Q: What is a necessary condition for a primary key in a SQL database?
A: A primary key must uniquely identify a row of data in a table.

Week 9

Q: What is the process of factoring out redundant information from a database called?
A: Normalization.

Q: Declare an array with five numbers in Javascript.
A:

var numbers = [0, 1, 2, 3, 4];

Q: What’s the downside of doing client-side validation versus server-side validation?
A: It is not guaranteed that Javascript will be executed on a user’s browser. Client-side validation is therefore not guaranteed to work.

Q: What’s an advantage of using jQuery instead of native Javascript?
A: jQuery solves many issues related to different browsers’ behavior with Javascript. With jQuery, you can write a single piece of code and know that it will work on all major browsers.

Q: What does the code below do?

function submitData(userData, callback) {
  $.ajax({
    url: 'submit.php',
    type: 'POST',
    dataType: 'json',
    data: userData,
    success: function(response) {
      callback(response);
    }
  });
}

A: This is a function that takes in userData and POSTs it to submit.php in the form of json. Upon a successful POST, the server sends a response, which the function passes to the callback function to handle. Note that in Javascript, functions can be passed as arguments. This means that we can pass a function we wrote to submitData and it will be executed after a successful response. This also means that we can pass in different functions if we want to handle responses differently.

Advertisements

CS50 Quiz 0 Practice Problems

These are some practice problems for quiz 0 of CS50 2012. If there are any similarities between these questions and those on the quiz, they are purely coincidental.
To generate these questions, I went through the notes for each class.
Try doing them on paper to simulate an actual exam environment.

Week 0

Question: Describe an algorithm in one sentence.
Answer: An algorithm is a step-by-step procedure for calculations.

Q: At the most fundamental level, what number system is used by computers? Why?
A: Binary. Nate’s short on binary. A naive explanation as to why is that 0’s and 1’s can be easily implemented using electricity.

Q: How many bits are there in eight bytes?
A: Each byte is eight bits, so there are 8*8=64 bits in eight bytes.
Historical Note: There have been computers in which one byte is not composed of 8 bits but rather 9, 16, 32, or 36 bits. The vast majority of computers now use 8-bit bytes, so you can always assume 8-bit bytes for CS50.

Q: Assume hello.c is a valid C program. If I type clang hello.c, what is its executable file called?
A: a.out

Week 1

Q: Write the following block of code using a for loop:

int i = 0;
while(i < 6) {
  printf("hello world");
  i += 2;
}

A:

int i = 0;
for(; i < 6; i += 2)
  printf("hello world");

It may be confusing to have int i = 0 outside of the for loop. This is because in the original, i is still accessible after the while loop is finished executing. In order to exactly replicate the while loop code block, we need to declare i outside of the for loop. An equivalent implementation is:

int i;
for(i = 0; i < 6; i += 2)
  printf("hello world");

Q: What is printed in the terminal as a result of calling the previous block of code once?
A: hello worldhello worldhello world

Q: What does

#include <stdio.h>

do?
A: It tells the compiler to use code from stdio.h.

Q: What’s missing from the below?

#include <stdio.h>

int main(void)
{
  printf("hello, what is your name?\n");
  string name = GetString();
  printf("hello, %s!\n", name);
  return 0;
}

A: We forgot to include the CS50 Library. The string type and the function GetString() are not built into C.

Q: Name some of the primitive data types in C.
A: Commonly-used ones are int, char, float, double.

Q:

float result = 25 / 10;
result *= 10.0;

What is stored in result after the two lines above are executed?

Q: Line 1 divides 25 (an int) by 10 (an int). The result of this operation gives an int of 2, but because result‘s type is of float, result is now a floating-point 2. Line 2 multiplies the value of result by 10.0, so now, result is a floating-point 20.

Q: What is the binary number 101 in decimal?
A: 101 in binary is 2^2+2^0=5 in decimal.

Q: Find the bug.

#include<stdio.h>
#include<stdlib.h>

int main(int argc, char** argv) {
  if(argc = 2) {
    int n = atoi(argv[1]);
    int sum = 0;
    for(int i = 0; i < n; sum += i, i++);
    return 0;
  } else {
    printf("Please provide exactly one argument!");
    return 1;
  }
}

A: Line 5 should be if(argc == 2)

Week 2

Q: Find the bug.

#include<stdio.h>

int main(int argc, char** argv) {
  for(int i = 1; i < argc; i++) {
    printf("%s\n", argv[i]);
  }
  printf("There were %d command line arguments\n", i-1);
  return 0;
}

A: Line 7 should have argc-1 in place of the i-1. The i is out of scope at this point.

Q: What did the previous question’s code do?
A: It printed out the command line arguments, each on a separate line.

Q: Declare an array of 20 floats. The value at each index should be the index plus one.
A:

float arr[20];
for(int i = 0; i < 20; i++)
  arr[i] = i + 1;

Week 3

Q: What are some O(n^2) sorting algorithms?
A: bubble sort, insertion sort, selection sort

Q: Write pseudocode for mergesort.
A:

Mergesort:
On input of N elements:
  If N is less than 2
    Return.
  Mergesort the left half of elements.
  Mergesort the right half of elements.
  Merge the sorted halves.

Q: What is the running time of mergesort?
A: O(n*log(n))

Week 4

Q: Complete this function:

// reverses the string s of a given length
void reverse(char* s, int length) {
  //TODO
}

A:

// reverses the string s of a given length
void reverse(char* s, int length) {
  if(s == NULL) return;
  int mid = length / 2;
  for(int i = 0; i < mid; i++) {
    char temp = s[length - i - 1];
    s[length - i - 1] = s[i];
    s[i] = temp;
  }
}

Q: Write the above function without knowing length beforehand.
A: Add this after if(s == NULL) return;:

int length = 0;
for(; s[length] != '\0'; length++);

Q: What’s the running time of the previous function?
A: O(length)

Q: What does this mystery do? Assume length is actually the length of arr.

char mystery(int arr[], int length) {
  for(int i = 0; i < length; i++) {
    for(int j = i; j < length; j++) {
      if(arr[i] == arr[j]) return 0;
    }
  }
  return 1;
}

A: mystery checks for duplicate values in arr. If there are any, it returns 0. Otherwise, it returns 1.

Q: What is the running time of mystery?
A: O(n^2), where n represents the length of arr

Q: What bad thing happened here? What could be done to solve it?

for(int i = 0; i < 25; i++)
  malloc(sizeof(int)*i);

A: Memory leak. Always free memory you malloc. In this case, we aren’t saving the pointer returned by malloc anywhere, so we can’t free this memory later.

Q: What prints from the following?

char* a = "hello";
char* b = "hello";
printf("%d\n", a == b);

A: 0. a == b compares the value of a with the value of b. a and b store two different addresses, so they are never equal. To actually compare the values at the addresses that a and b store, use strcmp.