CS50 Letter of Accomplishment

Coursera

Completed Courses:

Cryptography I: Dan Boneh, Stanford University

Machine Learning: Andrew Ng, Stanford University

Computing for Data Analysis: Roger Peng, Johns Hopkins

Algorithms, Part I: Robert Sedgewick and Kevin Wayne,  Princeton University

Current Courses:

Game Theory: Matthew O. Jackson, Kevin Leyton-Brown and Yoav Shoham, Stanford University and the University of British Columbia

Introduction to Computer Networks: Arvind Krishnamurthy, David Wetherall and John Zahorjan, the University of Washington

My Experience:

Over the past few months, I have had the amazing opportunity of taking online college courses at Coursera.org. This site offers education for the sake of education alone. Actual professors post videos of lectures along with automatically graded homework assignments that anyone can access. I particularly enjoy it because it allows me to study subjects that simply are not available at my high school. Some courses are intended for college freshmen. Others are graduate level. I've tried several so far, and enjoyed every second. In some ways, even though the material is harder, I find it easier to learn when I don't have to worry about credits, prerequisites, or grades. I'm not ashamed to admit that I failed miserably in some classes that were too advanced for my experience, but I rose to the challenge in others.

Cryptography has fascinated me for years, and Coursera made it possible for me to taste the field, with a Stanford class taught by Professor Dan Boneh. For six weeks, I watched in-depth lectures and completed challenging problem sets. It was difficult to find the time on top of my typical high school coursework, but I finished successfully. I gained a new understanding of the subject matter and an incomparable sense of accomplishment. I'm incredibly grateful to Coursera and all the professors and universities involved for providing the courses I've completed so far and the ones I have yet to take. My curiosity is piqued and I'm ready to study such subjects for real as an undergraduate.

Statements of Accomplishment:

Algorithms, Part I did not issue a certificate.

CS50 Problem Set Example

Specification:

http://cdn.cs50.net/2012/fall/psets/5/hacker5.pdf

Essentially, the goal is to see if a word is in a dictionary in the fastest possible real-world time. When actually tested for speed, my program finished in 10th place out of 700 Harvard students; 20th if you count the teaching fellows' submissions.

My Solution:

/****************************************************************************
 * dictionary.c
 *

 * Victor Porras
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a dictionary's functionality.
 * This is not the fastest version of this program, but it is the most
 * extensible and elegant. I hardcoded several parts of this to make the
 * BigBoard version faster, at the expense of readability and robust design.
 *
 * Some distribution code is necessary to compile and run this. See spec.
 ***************************************************************************/
 
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
 
#include "dictionary.h"
 
#define LEVELS 4
 
// LEVEL dependent
int dict[28][28][28][28][2];
char* raw;
char** words;
char w[46];
 
unsigned int sz = 0;
 
/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    if (sz == 0)
        return false;
    
    // preprocessing
    // since I need to mess around with the characters in word, w is a non-const copy
    // char* w = (char *) malloc(sizeof(char) * (LENGTH + 1));
    
    // preparing the word size for later
    int wsz;
    
    // this makes EvRytHing lowercase
    for (wsz = 0; word[wsz] != '\0'; wsz++)
        w[wsz] = tolower(word[wsz]);
        
    // gotta null terminate!
    w[wsz] = '\0';
    
    // the first LEVELS values of w must be sequential, ie a-z then z+1 z+2, so they can be used to access arrays
    bool finished = false;
    for (int x = 0; x < LEVELS; x++) 
    {
        // check for corner cases
        if (w[x] == '\'')
            w[x] = 'z' + 1;
        if (w[x] == '\0' || finished)
        {
            w[x] = 'z' + 2;
            finished = true;
        }
        w[x] -= 'a';                
    }
    if (finished)
        w[LEVELS] = '\0';
    
    // LEVEL dependent
    // time for binary search
    int bottom  = dict[(int) w[0]][(int) w[1]][(int) w[2]][(int) w[3]][0];
    int top     = dict[(int) w[0]][(int) w[1]][(int) w[2]][(int) w[3]][1];
    int result  = 0;
    
    // top is -1 when dict[...] has no pointer        
    while (top >= bottom)
    {
        result = strcmp(&(w[LEVELS]), words[(top + bottom)/2]);
        
        if (result == 0)
            return true;
        if (result > 0)
            bottom = (top + bottom)/2 + 1;
        else
            top = (top + bottom)/2 - 1;
    }
    
    return false;
}
 
/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    FILE* f = fopen(dictionary, "r");
    if (f == NULL)
        return false;
    
    // LEVEL dependent
    // sets up all the tops with -1
    for (int i = 0; i < 28; i++)
        for (int j = 0; j < 28; j++)
            for (int k = 0; k < 28; k++)
                for (int l = 0; l < 28; l++)
                    dict[i][j][k][l][1] = -1;
    
    // gets the file size then allocates memory for it
    struct stat st;
    stat(dictionary, &st);
    unsigned long fsz = st.st_size;
    raw = (char*) malloc(fsz);
    
    // it's much faster to read the data in one huge block than in many separate pieces
    fread(raw, sizeof(char), fsz, f);
    
    // sets up the data structures to hold the words themselves
    int capacity = 262144;
    words = malloc(sizeof(char*) * capacity);
    
    // breaks the raw data into words
    char* word = strtok(raw, "\n");
    
    // LEVEL dependent
    // This will store the first LEVELS letters of the previous word so the indices can be quickly found for similar words
    char  old[LEVELS*2] = {27, 27, 27, 27};
        
    // makes sure the file is not over
    while (word != NULL)
    {
        // check if words[] is too big
        // this runs in amortized linear time
        if (sz == capacity) 
        {
            capacity *= 2;
            words = realloc(words, sizeof(char*) * capacity);
        }
       
        if (strncmp(word, old, LEVELS))
        {
            strncpy(old, word, LEVELS);
            bool finished = false;
            for (int x = 0; x < LEVELS; x++) 
            {
                // check for corner cases
                if (word[x] == '\0' || finished)
                {
                    old[LEVELS + x] = 27;
                    finished = true;
                }
                else if (word[x] == '\'')
                    old[LEVELS + x] = 26;
                else
                    // put the indices in old
                    old[LEVELS + x] = word[x] - 'a';
            }
 
            // set the bottom of the binary search range
            dict[(int) old[LEVELS]][(int) old[LEVELS+1]][(int) old[LEVELS+2]][(int) old[LEVELS+3]][0] = sz;
        }
            
        // truncate the word to the part after the indices
        int wsz = strlen(word) - LEVELS;
        if (wsz <= 0)
            *word = '\0';
        else
            word = &(word[LEVELS]);
        
        // put word into the master array    
        words[sz] = word;
        
        // set the top of the binary search range
        dict[(int) old[LEVELS]][(int) old[LEVELS+1]][(int) old[LEVELS+2]][(int) old[LEVELS+3]][1] = sz;
        
        sz++;
        
        // get the next word
        word = strtok(NULL, "\n");
    }
    
    fclose(f);
    return true;
}
 
/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    return sz;
}
 
/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    // makes sure that the memory has been malloc'd
    if (raw == NULL)
        return false;
        
    // frees the big arrays that actually hold the values
    free(words);
    free(raw);
    return true;
}